Consider cards labeled 1, ..., 2n. The cards are shuffled and dealt to two playe
ID: 1889055 • Letter: C
Question
Consider cards labeled 1, ..., 2n. The cards are shuffled and dealt to two players A and B so that each gets n of the cards. Let x be the sum of the labels on the cards that have been played; initially, x = 0. Starting with A, play alternates between the two players. At each play, a player adds one of his or her remaining cards to x. The first player who makes x divisible by 2n + 1 wins. Prove that for every deal, player B has a strategy to win. (Hint: Prove that B can always make it impossible for A to win on the next move).Explanation / Answer
Lets prove that B cannot lose, so the sum of all cards is n(2n+1) which is divisible by 2n+1 hence then B will win. Say that 2k-1 (k=1, ..n) cards have been played and B has not yet lost. So the current sum is x Now B will play B has n-k+1 cards and A has n-k cards because B knows his cards and we know there were initially 1,2..2n cards and the play of the cards in known by B then we can say that B knows the cards in A's hand. if B plays y then sum is x+y then A must play the card z st 2n+1 | x+y+z so we need to play a y st for all z which A has x+z not congruent to y (mod 2n+1) we have such a y as B has one more card than A hence B can always ensure that he plays a card which A cannot win in the next turn. A cannot win in his first play. So B wins. message me if you have any doubts