Difference between revisions of "KGS math club/solutio prince"
(Created page with "Only for the 1x1 board. Consider a board with at least two rows and columns and assume a Hamiltonian circuit as described in the problem. Let B be the square in the upper rig...") |
|||
| Line 1: | Line 1: | ||
Only for the 1x1 board. | Only for the 1x1 board. | ||
| − | Consider a board with at least two rows and columns and | + | Consider a board with at least two rows and columns and label the squares in the upper right resp. lower left as follows. |
| − | Now, on the circuit, there has to be some path P from | + | [[File:Prince_01.gif]] |
| + | |||
| + | Now, assume a Hamiltonian circuit, as in the problem description. Given the available moves, the prince may enter the square B only with a move to the east and may leave it only with a move to the south. That is, the short path A -> B -> C is a forced part of the circuit. | ||
| + | |||
| + | [[File:Prince_02.gif]] | ||
| + | |||
| + | Similarly, there is a forced path X -> Y -> Z on the circuit. | ||
| + | |||
| + | [[File:Prince_03.gif]] | ||
| + | |||
| + | Now, on the circuit, there has to be some path P from C to X. Similarly, there has to be a path Q from Z to A. For topological reasons, P and Q have to intersect somewhere on the board. | ||
| + | |||
| + | [[File:Prince_04.gif]] | ||
| + | |||
| + | But, given the available moves, the prince can never cross its own path. | ||
| + | This is easily seen as follows. Draw the circuit as a piecewise linear curve from square center to square center. | ||
| + | It is clear, that two such line segments may only intersect when they are diagonal and perpendicular to each other. | ||
| + | But the prince has only one diagonal move at his disposal. | ||
| + | |||
| + | '''Note:''' This argument applies not only to rectangular boards but to any board having an upper right resp. lower left corner in the sense of this argument. | ||
Latest revision as of 14:46, 9 January 2017
Only for the 1x1 board.
Consider a board with at least two rows and columns and label the squares in the upper right resp. lower left as follows.
Now, assume a Hamiltonian circuit, as in the problem description. Given the available moves, the prince may enter the square B only with a move to the east and may leave it only with a move to the south. That is, the short path A -> B -> C is a forced part of the circuit.
Similarly, there is a forced path X -> Y -> Z on the circuit.
Now, on the circuit, there has to be some path P from C to X. Similarly, there has to be a path Q from Z to A. For topological reasons, P and Q have to intersect somewhere on the board.
But, given the available moves, the prince can never cross its own path. This is easily seen as follows. Draw the circuit as a piecewise linear curve from square center to square center. It is clear, that two such line segments may only intersect when they are diagonal and perpendicular to each other. But the prince has only one diagonal move at his disposal.
Note: This argument applies not only to rectangular boards but to any board having an upper right resp. lower left corner in the sense of this argument.
