CombinatoricsDifficulty 9.1IMO levelProve itBaltic Way
Anne, Ellie and Milo play a game on a hexagonal board tiled with hexagons, n>2 hexagons on each side. The game begins with a token on a tile in one of corner of the board. Ellie and Milo are on the same team, playing against Anne, and they win if the token lands on center of the board. Anne, Ellie and Milo take turns moving the token, Anne begins, then Ellie and then Milo. The turns proceed as follows: * Anne has to move the token to an adjacent hexagon, in any direction. * Ellie has to move the token by two hexagons in any of the 6 possible directions. * Milo has a choice of passing the turn, or moving the token by three hexagons in any of the 6 possible directions. Find all n>2 for which Ellie and Milo have a winning strategy.
Figure 1: A board with 5 hexagons on each side.
Solution
We colour the board in three colours in such a way that no neighbouring tiles are of the same colour. We can give each hexagon a coordinate using e1=(1,0) and e2=(cos(120∘),sin(120∘))=(2−1,23) as basis. Let the center square be the origin. Then each hexagon has center at a⋅e1+b⋅e2, (a,b)∈Z2. The tuple (a,b) is the coordinate for a given hexagon; its neighbours are (a+1,b), (a+1,b+1), (a,b+1), (a−1,b), (a−1,b−1) and (a,b−1).
We colour the hexagon with coordinates (a,b) with colour number (a+b)(mod3). It is clear that neighbouring hexagons do not share a colour. (In fact this is the only three colouring of a hexagonal tiling). See figure 8.
We see that if n≡1(mod3), the token begins in a space in the same colour as the center hexagon, let that colour be grey. By regarding a few cases, we see that whatever Anne does, Ellie and Milo can end their turns by getting the token to a prescribed grey hexagon of the closest grey hexagons. Therefore they can get the token to the center.
If n≡1(mod3), the token does not begin on the same grey colour as the center. Say the stone begins on a white tile, and say the third colour is black. Anne can always move the stone to a grey hexagon that is not on the same horizontal/diagonal line as the center hexagon. Then Anne moves the stone to a white or black hexagon. After Milo moves the token is still again on a white/black hexagon. Anne can continue this indefinitely, with the token never reaching the center.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.
Source: MathNet,
licensed CC-BY-4.0.
Statement reproduced verbatim; metadata (topic, difficulty) added by this project.