4

Part of 2008 Bundeswettbewerb Mathematik

Problems(2)

Finite number of moves to yield a configuration

Source: Germany Bundeswettbewerb Mathematik 2008, Round 1, Problem 4

In a planar coordinate system we got four pieces on positions with coordinates. You can make a move according to the following rule: You can move a piece to a new position if there is one of the other pieces in the middle of the old and new position. Initially the four pieces have positions

\{(0,0),(0,1),(1,0),(1,1)\}

. Given a finite number of moves can you yield the configuration \{(0,0), (1,1), (3,0), (2, \minus{} 1)\} ?

analytic geometryalgebra unsolvedalgebra

Bubblesort algorithm with 3 iterations for a bookcase

Source: Germany Bundeswettbewerb Mathematik 2008, Round 2, Problem 4

On a bookcase there are

n \geq 3

books side by side by different authors. A librarian considers the first and second book from left and exchanges them iff they are not alphabetically sorted. Then he is doing the same operation with the second and third book from left etc. Using this procedure he iterates through the bookcase three times from left to right. Considering all possible initial book configurations how many of them will then be alphabetically sorted?

algorithmcombinatorics unsolvedcombinatorics