An ant is placed on a large sheet of graph paper on which numerous concentric squares have been marked in ink, indicating each successive odd prime starting with 3. The ant starts moving North, from the centre square of the 3x3 block, and will alternately;
1. Turn right when it reaches an ink line (which seems like a ‘wall’ to the ant); and
2. Resignedly clamber over the ‘wall’ and continue to scurry forwards in its current direction until confronted by another wall.
Hence the first few moves of the ant will be: North 1 step, turn right, East 2 steps, turn right, South 4 steps, turn right, West 7 steps, turn right, and so on.
Question: How many steps will the ant have had to take by the time it climbs over the 10,000th ‘wall’?
At any given stage of travel, past the first two such straight runs, the ant travels the distance based on the given prime number plus that based on the second previous prime. That is, for example, the first three primes that are used are 3, 5, 7 and 11. A "distance based on" is (p-1)/2, so the based distances away from the axes are 1, 2, 3 and 5 respectively (despite appearances, these are not always prime or 1).
So for example, the "south 4 steps" mentioned in the puzzle is the 3+1, and the "west 7 steps" is the 5+2.
10 for Stp=1 to 10
20 P=prm(Stp+1)
30 Pprev=Prev:Prev=Dist:Dist=(P-1)//2
40 Steps=Dist+Pprev
50 Tot=Tot+Steps
60 print stp,Steps,Tot
70 next
calculates the first few runs as:
run# length total so far
1 1 1
2 2 3
3 4 7
4 7 14
5 9 23
6 13 36
7 15 51
8 19 70
9 23 93
10 26 119
During run 1, the ant has not yet climbed a wall; only after run 2 has the ant climbed one wall. This lag by one must be kept in mind at the end.
Changing the program to
10 for Stp=1 to 10001
20 P=prm(Stp+1)
30 Pprev=Prev:Prev=Dist:Dist=(P-1)//2
40 Steps=Dist+Pprev
50 Tot=Tot+Steps
60 print Stp,Steps,Tot
70 next
results in the last few lines being:
run# length total so far
9990 104663 495108407
9991 104669 495213076
9992 104679 495317755
9993 104686 495422441
9994 104691 495527132
9995 104699 495631831
9996 104705 495736536
9997 104711 495841247
9998 104716 495945963
9999 104722 496050685
10000 104732 496155417
10001 104743 496260160
So that after its 10001th run, it has climbed 10000 walls and taken 496,260,160 steps. But some of those steps were taken after having climbed over that 10,000th wall, upon reaching the 10,001st wall, but not yet ready to climb it--only diverting to the right. To backtrack to where the 10,000th wall was climbed we have to subtract the difference between the distance based on the 10,002nd prime and the distance based on the 10,001st prime. Those primes are 104759 and 104743, with respective axial distances of 52379 and 52371, which differ by 8, so at the 10,000th wall crossing the ant has traveled 496,260,160 - 8 = 496,260,152 steps.
We can codify what we did so as to verify that this is the correct procedure, by looking at the beginning of the tour:
10 for Stp=1 to 10
20 P=prm(Stp+1)
30 Pprev=Prev:Prev=Dist:Dist=(P-1)//2
40 Steps=Dist+Pprev
50 Tot=Tot+Steps:Adjusted=Tot-(Dist-Prev)
60 print Stp,Steps,Tot,Adjusted
70 next
yielding adjusted totals in the rightmost column:
1 1 1 0
2 2 3 2
3 4 7 6
4 7 14 12
5 9 23 22
6 13 36 34
7 15 51 50
8 19 70 68
9 23 93 90
10 26 119 118
which can be verified by inspection of the diagram of the original few steps. Restoring the full number of steps, the resulting last few lines are:
9996 104705 495736536 495736534
9997 104711 495841247 495841244
9998 104716 495945963 495945960
9999 104722 496050685 496050682
10000 104732 496155417 496155410
10001 104743 496260160 496260152
verifying the figure found previously.
But actually, we need to add .5 to these steps as the and needs to go 1/2 step to get to the actual wall.
So the final answer becomes 496,260,152.5 steps, counting the wall-crossing square as being two half-steps.
Edited on October 6, 2010, 2:52 am
|
|
Posted by Charlie
on 2010-10-06 02:50:37 |
computer-aided solution
