2015 pieces of stones are placed to form a circle. They are numbered with 1,2,3,4,...,2015 clockwise. Starting from somewhere, you remove a stone. Then going clockwise, you remove every other stone, one at a time. Finally, there is only stone left, and that stone is 2014. What was the first stone you removed?
Let's say you start with 1 and proceed to remove all the odd-numbered stones. When you've removed number 2015 the next one around is #2, but you skip that and remove all the multiples of 4, ending with 2012. You then leave 2014 in place and remove #2, then leave 6 in place and remove #10.
I thought this would lead to a consistency with binary number positions, but now we're down to removing those that are congruent to 2 mod 8. Perhaps I chose a poor starting place.
Rather than try to find a place with a consistent set of rules for deleting binary values, I wrote a program arbitrarily starting at position 1 and performing the removal procedure from there, to find out how many positions from the starting position the last remaining stone is.
DefDbl A-Z
Dim crlf$, stone(2014)
Private Sub Form_Load()
Form1.Visible = True
Text1.Text = ""
crlf = Chr$(13) + Chr$(10)
remain = 2015: psn = 0
Do
stone(psn) = 1
remain = remain - 1
distant = distant + 1
If distant < 11 Then Text1.Text = Text1.Text & Str(psn + 1)
If remain = 1 Then Exit Do
ct = 0
Do
psn = psn + 1
If psn > 2014 Then
psn = 0: Text1.Text = Text1.Text & crlf: distant = 0
End If
If stone(psn) = 0 Then ct = ct + 1
DoEvents
Loop Until ct = 2
Loop
Text1.Text = Text1.Text & crlf & crlf
For i = 0 To 2014
If stone(i) = 0 Then
Text1.Text = Text1.Text & i & crlf
End If
Next
Text1.Text = Text1.Text & crlf & " done"
End Sub
finds that the last remaining stone is 1981 positions beyond the one where you started, so you started at 2014-1981=33.
Going back to the original methodology, If we had started with removing 1 and all odd numbers first, the sequence would have been the following, showing the first few removals of each circuit of the circle:
1 3 5 7 9 11 13 15 17 19 ...
4 8 12 16 20 24 28 32 36 40 ...
2 10 18 26 34 42 50 58 66 74 ...
6 22 38 54 70 86 102 118 134 150 ...
14 46 78 110 142 174 206 238 270 302 ...
30 94 158 222 286 350 414 478 542 606 ...
126 254 382 510 638 766 894 1022 1150 1278 ...
62 318 574 830 1086 1342 1598 1854
190 702 1214 1726
446 1470
958
ending with one left at 1982, which is 1981 beyond the first removal.
|
|
Posted by Charlie
on 2017-11-16 15:19:18 |
tried analytic but had to resort to program (spoiler)
