Time for MATH MINUTE! (provide your favorite theme music
here).
Get out
your paper & pencil, because I have a new puzzle for you!!
Responses/Hints: PUZZLE #84 If you are left standing, you win!
From
the puzzle we know we have the following results:
Size Winning
position
8 1
9 3
10 5
11 7
If
you happened to check the smaller numbers 4, 5, 6, 7 (this is quick and easy)
you found:
Size Winning
position
4 1
5 3
6 5
7 7
Also,
for 12, 13, 14, 15, 16 we get:
Size Winning
position
12 9
13 11
14 13
15 15
16 1
A
pattern is definitely starting to form here!
Putting
this all together we have:
Size Winning
position
4 1
5 3
6 5
7 7
8 1
9 3
10 5
11 7
12 9
13 11
14 13
15 15
16 1
So,
you can now guess that the result for 20 is 9 (check this), and the result for
32 is 1?
Also,
you can see that each time we have a group of size equal to a power of 2, like
4 = 22, 8 = 23, 16 = 24, and 32 = 25,
we get the result 1.
The
size number immediately before a power of 2 has winning position equal to
itself. The winning position for size 7 is 7, for size 15 it is 15, and so on.
Note
that each time we get a winning position of 1 we start over with the (odd)
numbers 3, 5, 7, 9, 11, etc. as winning positions?
There
is actually a formula for computing the winning position using the form 2k + 1
for odd numbers, and the highest power of 2 less than the group size (actually
the difference between the group size and the highest power of 2 less than this
number).
Can
you figure it out?
If
so, then it is easy to compute that the winning position for 100 is 73, and for
1000 (???).
This
is a version of the Josephus Problem, see Wikipedia: http://en.wikipedia.org/wiki/Josephus_problem
Have
fun!
Send
your comments, ideas and solutions before Monday to the email below, and
in the subject line be sure to put
MM in the subject line
Visit
us here online at:
http://www2.potsdam.edu/parksjm/MM1.1.htm
to see the results every Friday.
See you next time on MATH MINUTE! (theme music fades out here).