Monday, May 1, 2017

logical deduction - Perambulating ants


An ant is a methodical creature, and the ants in this puzzle are particularly so. When they start walking they always walk in a straight line, and when they reach a boundary they always turn exactly $90^\circ$ anticlockwise. If they still cannot move, they turn through $180^\circ$ and try to move. After this they have tried all directions and so stop. (Put otherwise, the ant tries turning left; if that fails, it tries turning right from its original heading.)


When an ant is set on the lower left corner on a $5\times 5$ board, as shown below as cell $A1$, and it treats any cell it has already visited, as well as the edges of the board, as boundaries, it traverses the entire board (as shown in blue). enter image description here


However, if the ant starts in a different cell, say $B3$ then it omits some cells on its journey, as shown: enter image description here (in this case cells $B4, C4$ and $D4$).


Given the $11\times 11$ grid below, there are two starting cells for such an ant that omit exactly one cell when the ant cannot move any more. The ant always starts moving the $A \rightarrow K$ direction, unless it starts in column $K$ in which case, applying the $90^\circ$ rule, it moves up. Which two cells are they?


EDIT: As pointed out by Stiv there is actually only one starting cell for which the ant will omit a single cell, not two.


enter image description here



Answer



Initial notes:






  • If the ant ever starts at one corner of a blank region which is a perfect rectangle, then it will fill that whole rectangle and stop.






  • Starting in row 1 will not solve the problem.






Detailed deduction


Say the starting point is row number $n>1$, column letter $l$, and exactly one cell is omitted. The ant's journey can be described as follows:





  1. First, it will fill in the rest of row $n$ to the right. (If it starts in column K, skip this step.) All of row $n$, columns $\geq l$, filled.







  2. Then it will go up in column K to the top. (Assume $n$ is not 11 at this stage.) All of column K, rows $\geq n$, filled.






  3. Then along row 11 to the cell A11. All of row 11 filled.







  4. Then down. If the starting column $l$ was A, then either the rest of the grid now gets filled in one big spiral (if it was A1) or there's at least one whole row of omitted squares. So we know $l$ is not A, and we end up at A1 now. All of column A filled.






  5. Then across to K1. All of row 1 filled.







  6. Then up column K to the row $n-1$. All of column K filled. If $n$ is 2, contradiction. Then across row $n-1$ to column B. All of row $n-1$ filled. If $n-1$ is not 2, we then turn left and stay in the lower chunk of the board, omitting at least two squares unless the starting point was C10. If $n$ was 3, we either fill the rest of the board above or we just get stuck in whatever's left of row 3 omitting the above part.





Final answer


The only possible starting point is



C10:

C10 grid solved




No comments:

Post a Comment

classical mechanics - Moment of a force about a given axis (Torque) - Scalar or vectorial?

I am studying Statics and saw that: The moment of a force about a given axis (or Torque) is defined by the equation: $M_X = (\vec r \times \...