Ponder This Challenge - February 2008 - What are the rules of the game?

Ponder This Challenge:

The following integer sequences are the winning positions for a parametric two players game.

1. Find the rules of the game which are consistent with the partial data.
2. Fill in the missing values in the table according to those rules.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  Ponder This Solution:

  The game is played on a set of n pebbles using a parameter p.

  Each player in turn takes some of the pebbles. Players must take at least one, but no more than p times the amount of pebbles the previous player took.
  In the first move, where no pebbles were previously taken, the first player can take any number of pebbles up to n-1. If a player cannot take a turn, he or she loses.

  The first player usually wins. The table lists, for a parameter p, the numbers for which the second player wins.

  For example, when p=1, meaning that each player can take no more than the amount taken in the previous step, the winning strategy for the first player, if n is not a power of 2, is to take the highest possible power of 2 which divides n. One can see that if n is a power of 2, then the second player can win by taking the highest power of 2 which divides the first player’s move.

  Similarly, p=2 gives the Fibonacci sequence as winning numbers for the second player (why?); and p=3 even appears in the On-Line Encyclopedia of Integer Sequences (https://www.research.att.com/~njas/sequences/A003411).

  The missing values are

  Parameter	Sequence
  3	1	2	3	4	6	8	11	15	21	29	40	55	76	105	145	...
  4	1	2	3	4	5	7	9	12	15	19	24	31	40	52	67	...

  ---

  If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solvers

• Balakrishnan V (02.01.2008 @11:44:00 PM EDT)
• Minjen Mao (02.02.2008 @01:39:32 AM EDT)
• Michael Brand (02.02.2008 @08:45:00 AM EDT)
• Mithil Ramteke (02.02.2008 @12:52:17 PM EDT)
• Rickard Björklund (02.03.2008 @05:07:53 AM EDT)
• Phil Muhm (02.04.2008 @03:26:54 PM EDT)
• Kapil Arya (02.05.2008 @04:36:17 AM EDT)
• Marian Moldenhauer (02.05.2008 @07:49:46 AM EDT)
• Andreas Kabel (02.05.2008 @05:59:23 PM EDT)
• Rani Hod (02.06.2008 @07:28:49 AM EDT)
• Gary M Gerken (02.07.2008 @07:07:08 AM EDT)
• Dharmadeep Muppalla (02.07.2008 @09:41:20 AM EDT)
• Arjun R. Acharya (02.07.2008 @11:56:46 AM EDT)
• Álvaro Martínez Echevarría (02.07.2008 @12:46:24 PM EDT)
• Jimmy Hu (02.08.2008 @06:50:43 PM EDT)
• Frank Yang (02.08.2008 @06:50:43 PM EDT)
• Maurizio Monge (02.11.2008 @01:40:50 PM EDT)
• Dan Dima (02.12.2008 @05:24:08 PM EDT)
• Mathias Krohn (02.13.2008 @07:38:54 AM EDT)
• Jiri Navratil (02.13.2008 11:22:00 PM EDT)
• Gale Greenlee (02.19.2008 @09:07:00 AM EDT)
• Hongcheng Zhu (02.24.2008 @12:40:05 AM EDT)
• Rajkumar Pal (02.26.2008 @01:24:03 AM EDT)
• Albert Stadler (02.27.2008 @01:26 PM EDT)
• Michael Talbot (02.27.2008 @09:25 PM EDT)
• Dion Harmon (03.03.2008 @10:57 PM EDT)