Ponder This Challenge - March 2007 - Shooter / target game

Ponder This Challenge:

Puzzle for March 2007.

This month's puzzle is about a two player game involving a shooter, S, and a target, T. The target can move among three locations 0,1,2. The game is played in rounds. Each round begins with T located where he was at the conclusion of the previous round. In each round T can choose to stay at the same location or move to a location 1 different. So T can move freely among the locations except moves from 0 to 2 or 2 to 0 are impossible. In each round S also picks a location (without knowing the T's choice). If T and S pick the same location S scores a point. At the end of each round S is told T's new location. The game is played over many rounds.

Part 1: The objective of S is to score points at the greatest possible rate. The objective of T is to allow S to score points at the least possible rate. If S and T play optimally at what rate (points/round) will S score points?

Part 2: Suppose the objectives are reversed, T is trying to get S to score points and S is trying to avoid scoring points. Again if both play optimally at what rate will S score?

**Note: a correct solution is required for both parts.

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

  Answer:

  It turns out T basically need only consider the current round.

  Part 1: Answer is a rate of 3/7.
  T minimizes S's score for the current round by picking each of the choices with equal probability. If T does this it is easy to verify T will start the round at 0, 1 or 2 with probability 2/7, 3/7 or 2/7 respectively. When T starts at 0 or 2, S will score at most 1/2 the time. When T starts at 1, S will score 1/3 the time. So overall S will score at a rate of 3/7 or less. Conversely S can guarantee scoring at a rate of 3/7 or more with the following strategy. When T starts at 0, S picks 0,1 with probability 3/7,4/7 respectively. When T starts at 1, S picks 0,1 or 2 with probability 2/7,3/7,2/7 respectively. When T starts at 2, S picks 1,2 with probability 4/7,3/7 respectively. It is easy to see this guarantees S will score at rate 3/7. When T stays put S will score 3/7 of the time. When T moves from 1 to 0 or 2, S will only score 2/7 of the time but when T returns to 1 from 0 or 2, S will score 4/7 of the time. So overall S will score at rate 3/7.

  Part 2: Answer is a rate of 1/5.
  Clearly T can only force scores when he starts at 1. If T starts at 1 and picks 0,1,2 with probability 1/3, S will score 1/3 of the time. When T starts at 0 or 2 he should immediately move to 1 to be in a position to force a score. If T follows this strategy it is easy to see he will start 1/5,3/5,1/5 of the rounds at 0,1,2 respectively and force S to score at a rate of 1/5. Conversely S can hold the rate he scores to 1/5 by following the following strategy. When T starts at 0 or 2 pick the other guaranteeing a miss. When T starts at 1 pick 0,1,2 with probability 2/5,1/5,2/5. So if T stays at 1, S will score at rate 1/5. If T moves from 1 to 0 or 2, S will score at rate 2/5 but will score 0 the next round. So overall S will score at a rate of at most 1/5.

  ---

  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

• Michael Brand (03.02.2007 @07:07:24 PM EST)
• Tom Gutman (03.02.2007 @07:22:29 PM EST)
• Alan Murray (03.03.2007 @12:54:32 PM EST)
• Ed Shepard (03.03.2007 @11:06:16 PM EST)
• James Dow Allen (03.03.2007 @11:22:26 PM EST)
• Bart De Vylder (03.04.2007 @ 07:11:15 AM EST)
• Yoav Raz (03.04.2007 @10:08:32 PM EST)
• Antonio Manuel Gutierrez Fernandez (03.05.2007 @12:15:57 PM EST)
• Luke Pebody (03.05.2007 @06:29:25 PM EST)
• Frank Yang (03.05.2007 @10:14:49 PM EST)
• Joseph DiVincentis (03.05.2007 @10:51:58 PM EST)
• Serge Gautier (03.06.2007 @08:06:37 AM EST)
• Gale Greenlee (03.06.2007 @10:50:33 AM EST)
• John T. Robinson (03.06.2007 @04:57:24 PM EST)
• Joshua Green (03.06.2007 @05:31:38 PM EST)
• Dan Dima (03.06.2007 @06:39:39 PM EST)
• Dharmadeep Muppalla (03.06.2007 @11:22:58 PM EST)
• Gary M Gerken (03.07.2007 @12:03:03 AM EST)
• Wolf Mosle (03.07.2007 @01:53:37 PM EST)
• V Balakrishnan (03.07.2007 @02:30:28 PM EST)
• Celia Anteneodo (03.07.2007 @07:54:27 PM EST)
• Patrick J. LoPresti (03.08.2007 @02:02:23 AM EST)
• Ashish Srivastav (03.09.2007 @03:14:39 AM EST)
• Greg Janee (03.09.2007 @12:52:03 PM EST)
• Andrew Buchanan (03.10.2007 @04:54:16 AM EST)
• Arjun Acharya (03.10.2007 @08:55:59 PM EST)
• Adriano Batista (03.11.2007 @10:54:22 PM EDT)
• Zhou Guang (03.12.2007 @03:56:47 AM EDT)
• arnab.x.bose (03.12.2007 @10:20:37 AM EDT)
• Kerry M. Soileau (03.12.2007 @ 03:45:00 PM EDT)
• Forrest McClellan (03.13.2007 @05:03:07 PM EDT)
• Andrea Andenna (03.14.2007 @01:09:52 PM EDT)
• Clive Tong (03.14.2007 @05:28:51 PM EDT)
• Se Kwon Kim (03.16.2007 @10:11:23 PM EDT)
• Dion Harmon (03.20.2007 @03:50:20 PM EDT)
• David McQuillan (03.21.2007 @07:08:41 PM EDT)
• Jiri Navratil (03.22.2007 @06:30:26 PM EDT)
• Teodora Baeva (03.24.2007 @o5:25:25 PM EDT)
• Mark Pilloff (03.27.2007 @08:32:27 PM EDT)
• Alan Curry (03.28.2007 @07:35:22 PM EDT)
• Phil Muhm (03.30.2007 @12:08:24 PM EDT)
• Du Yang (03.31.2007 @09:43:24 PM EDT)
• Rogerio Ponce da Silva (04.01.2007 @07:47:31 PM EDT)
• Koen Vossen (04.03.2007 @06:18:02 PM EDT)