Number Games
Source: Puzzle Toad, CMU
Problem: Its raining outside and Alfonso and Bernadette are bored.
Alfonso suggests the following games:
(a) Two players alternatively erase some 9 numbers from the sequence 1,2,...,101 until only two remain. The player that starts wins x−54 dollars from the player that plays second. Here x is the difference between the remaining two numbers. Would you rather be the first or the second player?
(b) Two players alternatively erase one number from the sequence 1,2,...,27 until only two numbers remain. The first player wins if the sum of these numbers is divisible by 5; otherwise the second player wins. Who has a winning strategy?
Update (Oct 10, 2010):
Solution posted by Siddhant Agarwal (Senior Undegraduate, EE, IITB) in comments!! Also at Puzzle Toad page (http://www.cs.cmu.edu/puzzle/solution31.pdf)
Problem: Its raining outside and Alfonso and Bernadette are bored.
Alfonso suggests the following games:
(a) Two players alternatively erase some 9 numbers from the sequence 1,2,...,101 until only two remain. The player that starts wins x−54 dollars from the player that plays second. Here x is the difference between the remaining two numbers. Would you rather be the first or the second player?
(b) Two players alternatively erase one number from the sequence 1,2,...,27 until only two numbers remain. The first player wins if the sum of these numbers is divisible by 5; otherwise the second player wins. Who has a winning strategy?
Update (Oct 10, 2010):
Solution posted by Siddhant Agarwal (Senior Undegraduate, EE, IITB) in comments!! Also at Puzzle Toad page (http://www.cs.cmu.edu/puzzle/solution31.pdf)
You need to remove the middle 9 numbers so you are left with 1,2,...46,56,57,58,...101. Now you have 46 pairs (1,56),(2,57),(3,58)..So A can easily ensure that only one of these pairs will be left in the end. So his earning would be 55-54 = 1.
ReplyDeletea) Winning strategy for 1st player:
ReplyDeleteerase 47,48..,54,55 in first move.
let A={1,2,..,46}
and B={56,57,..,101}
Now every time the second player plays, suppose he removes x no of elements from A and (9-x) no of elements from B, the first player then removes the biggest (9-x) no of elements from A and x smallest no of elements from B.
Hence at the end 45 elements are removed from A and 45 elements are removed from B. Also we see that by this strategy the min value in A is increased only by actions of the second player and the max value of B is decreased by the actions of the second player alone.
=> at every action of 2nd player maxB - minA can decrease by a max of 9 (and also for cumulative actions).
as (101-1)-45=55>54 => 1st player always wins some money
b) 1st player has winning strat:
1st player: removes 27
let
A1= {1,2,3,4}
A2= {6,7,8,9}
..
A5= {21,22,23,24}
A={5,10,15,20,25,26}
suppose 2nd player removes x from Ai.. then remove from Ai the element y s.t 5|(x+y)
If x removes from A then remove 26 and then later on any element of A.
As in the end, only two elements are left => at some time 2nd player has to remove some element from A and then we can get rid of 26. After this point, sum of all nos is divisible by 5 at each combined step.
Hence last two no will have sum divisible by 5.
if only serial number can be remove then first player can win 91-54=37 always...
ReplyDeletehere take a look.
spse 1st player remove 2 to 10 or 92 to 100 any one of above seq. now 2nd player will remove 93 to 101 or 1 to 9 in respective to 1st. and again 1st will remove 83 to 91 or 11 to 19 in respective cases.in both way remaining number will be 1 and 92 or 10 and 101 and so difference x will be 92-1=101-10=91.
//////////////////////////////////////
if player can remove any nine number then ....
first will remove middle numbers and 2nd will remove biggest and lowest numbers...in all ways 2nd player can make minimum value of x = 1 so 2nd will win...that is obvious...
@yash.. I am sure you meant at least 55-54=1.. nice solution for part a)
ReplyDelete@sid.. As always.. good solution.. thanks.. :)
@brijendra.. did not understand your solution.. if you are asking a question, could you please use more words? Thanks
Solution at http://www.cs.cmu.edu/puzzle/solution31.pdf
27 no can be divided in 5 classes
ReplyDeleteclasses : 5k 5k+1 5k+2 5k+3 5k+4
no of elements: 5 6 6 5 5
now there are 2 elements which are causing trouble one in 5k+1 and other in 5k+2.
Player A strategy:
1. Player A will remove the first no from 5k+1 group to equilize it with 5k+4 group
2. Player A will not remove from class 5k before player B
3. In the process Player B has to remove atleast one element of 5k. In the next turn A will remove from class 5k+2 to equilize it with class 5k+3.
4.In any other case if player B chooses Class 5k+a, then player A will choose a no from Class 5k+(5-a)
After step 3 is execute once in game the total sum of all elements is M(5) with next turn being B's. Every move after that belongs to step 4. So after every move of A from here, the sum will remain M(5). Hence ensuring the sum of last two no to be M(5).