# Did anyone ever participate in the Putnam math competition? What'd you think? **URL:** \ **Category:** Miscellaneous and Personal Stuff I Must Share\ **Created:** [October 13, 2017, 10:14am UTC](https://boards.straightdope.com/t/did-anyone-ever-participate-in-the-putnam-math-competition-whatd-you-think/798717 "2017-10-13T10:14:35Z")\ **Posts on this page:** 2\ **Page:** 2
**Author:** ![Bullitt](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/bullitt/32/5725_2.png) [@Bullitt](https://boards.straightdope.com/u/Bullitt)\ **Post date:** [October 17, 2017, 4:22pm UTC](https://boards.straightdope.com/t/did-anyone-ever-participate-in-the-putnam-math-competition-whatd-you-think/798717/21 "2017-10-17T16:22:59Z")
> [@Left\_Hand\_of\_Dorkness](#): > > How is it scored? > > Also, I found [some sample questions here](http://www.math.nyu.edu/~bellova/putnam/putnam08_1.pdf). My high school/college-level math concepts and vocabulary are frankly pitiful, so I don’t even understand how to start most of them. But I think I have one of them (okay, in typing it out I realize I don’t understand it as well as I thought and would love some help): > > > [@](#): > > > > Consider the following game played with a deck of 2n cards numbered from 1to 2n. The deck is randomly shuffled and n cards are dealt to each of two players. > > > > Beginning with A, the players take turns discarding one of their remaining cards and announcing its number. The game ends as soon as the sum of the numbers on the discarded cards is divisible by 2n + 1. The last person to discard wins the game. Assuming optimal strategy by both A and B, who wins? > > My answer: > > [spoiler]B wins, and here’s why. 2n+1 is 1 higher than the highest card in the deck. A sequence from 1 to 2n contains an even number of cards, and the cards can be rearranged into pairs with the value 2n+1. For example, if n=5, the cards are from 1-10, 2n+1=11, and you can arrange the cards into (1, 10); (2,9); (3,8); (4,7); and (5,6). > > Player A may have some of these pairs, and optimal play will involve playing members of a complete pair. Continuing the example, if Player A has a hand of (1, 3, 4, 6, 8), the only complete pair is (3, 8); she should play one of these cards, knowing that player B won’t have the other card to win the game. > > The problem is that for every pair Player A has, Player B **necessarily** has a pair. In this example, Player B must have a hand of (2, 5, 7, 9, 10), with the matching pair (2, 9). Optimal play will look something like this: > A: 3 > B: 2 > > A knows not to complete her match with (8), because then B completes his with (9) and wins. But if A plays anything that’s not from a match, B can then win. > > Huh. I’m losing my train here. Basically, I think B’s ability to choose to play from matches or not matches, in response to A’s plays, creates an unbeatable advantage. Can anyone smooth out my thinking on this, using very small words?[/spoiler] > [@DPRK](#): > > I think the simplest way to put it is: whenever it is A’s turn, no matter what card A plays B can respond so as to prevent A from winning on the next turn. > > Whatever A chooses to play, it will be B’s turn; A has k-1 cards in hand and B has k. That means B can leave k different totals while at most k-1 of these allow A to win. For **DPRK** , k = (n/2), and I’ll tweak it just a little:I think the simplest way to put it is: whenever it is A’s turn, no matter what card A plays B can respond so as to _ **either win immediately, or** _ prevent A from winning on the next turn. But I’m not sure if **DPRK** ’s is a definitive proof. Is it? For all n? The following shows that B always wins for n = 1 and for n = 2. Furthermore, for n = 1 and n = 2, it is impossible for A to win. B must be the winner, even if B can misplay its hand. For n = 1, regardless of what A plays, either a 1 or a 2 (the only cards in the deck), B’s play results in Σ = 3 and B wins. Trivial, but important to show. If it is true that the same player must win regardless of n, then this proves B always wins for any n, because B wins for n = 1, and the proof is complete. Continuing, for n = 2, A can have one of six possible hands: (1,2), (1,3), (1,4), (2,3), (2,4), and (3,4). [ul] [li]If A(1,2) plays either 1 or 2, respectively, then B(3,4) plays either 4 or 3, respectively. Σ = 5 and B wins.[/li][li]If A(1,3) plays either 1 or 3, respectively, then B(2,4) plays either 4 or 2, respectively. Σ = 5 and B wins.[/li][/ul] A(1,4) is just a little more complicated… [ul] [li]If A(1,4) plays 1, then regardless of what B(2,3) plays, either the Σ = 3 or Σ = 4. A then plays 4. Still no winner. With B’s remaining play, Σ = 10 and B wins.[/li][li]If A(1,4) plays 4, then regardless of what B(2,3) plays, either the Σ = 6 or Σ = 7. A then plays 1. Still no winner. With B’s remaining play, Σ = 10 and B wins.[/li][/ul] Similarly for A(2,3), A(2,4), and A(3,4), B always wins: [ul] [li]Note that for {A(2,3), B(1,4)} each of their hands sum to the winning total, as for {A(1,4), B(2,3)} above – B can only win after all four cards are played, **and as above it is impossible for A to win. B must win**.[/li][li]Also note that for {A(2,4), B(1,3)} and for {A(3,4), B(1,2)}, as for A(1,2) and A(1,3) above, regardless of what A plays, B wins on the very next play. **Even if B misplays, it is impossible for A to win. Again, B must win** [/li][/ul] Therefore, for n = 2, B always wins. Not only that, but A can never win – B must win, even if B misplays the game. This is a brute force approach. There’s probably a more elegant proof! ---
**Author:** ![Left\_Hand\_of\_Dorkness](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/left_hand_of_dorkness/32/7156_2.png) [@Left\_Hand\_of\_Dorkness](https://boards.straightdope.com/u/Left_Hand_of_Dorkness)\ **Post date:** [October 17, 2017, 9:11pm UTC](https://boards.straightdope.com/t/did-anyone-ever-participate-in-the-putnam-math-competition-whatd-you-think/798717/22 "2017-10-17T21:11:45Z")
My current understanding: The way the game is written, for any particular nonwinning sum at the end of my turn, my opponent has one theoretical card that can be played to win. If there are ten cards, if I end my turn at 11, I win; but if I end it at 12, my opponent must play a 10 to win, and if I end at 13, they must play a 9, and so on. Call the sum at the end of my turn the “end-sum”; the card I play is the “sum determiner”; the card they must play to win is the “winning card.” Each card is unique. I can choose among my cards which sum determiner to play, giving a unique end-sum for each choice, and requiring a unique winning card. I have one more sum determiner than they have potential winning cards. If I have five cards left in my hand, that’s five different possible end sums. And they only have four cards. I can choose the end sum for which they lack the winning card. [Previous page](https://boards.straightdope.com/t/did-anyone-ever-participate-in-the-putnam-math-competition-whatd-you-think/798717.md?page=1)