Sunday morning puzzle
Sunday morning puzzle
I was led to this problem by my great friend Karthik’s son – Aadi – who is a whizkid in logic and numbers problems. I need to spend more time with him just to learn about more puzzles.
This problem was published in New York Times as the Tax Man Problem. I have changed the description a little – but the problem is the same.
You and I sit across a table with twelve cards marked 1 thru 12 between us. Following are the rules of the card:
1. You pick a card.
2. I get to pick all the factors of that card that are remaining on the table.
(To explain, if you picked card marked “10” first, I pick up “1”, “2” and “5”. )
3. We continue with this.
(To explain, now if you pick “8”, I pick “4”. Remember “1” and “2” are already gone in the previous move)
4. You CANNOT pick a card if there are no factors of that card left for me to pick.
(To continue with the above example, you cannot pick “11” now, because its only factor “1” is already gone and I am left with nothing to pick)
5. Finally, when you have run out moves (there is no card left for you to pick without violating Rule 4 OR there are no cards left on the table), the game is over.
6. Now we add up our cards.
Whoever has higher total, wins.
To finish off that example:
You: 10
I: 1,2,5
You: 8
I: 4
You: 12
I: 3,6
You: run out of moves (you cannot pick any of the remaining cards – 7,9,11 – since they have no factors left)
I: 7,9,11
Your total: 10 + 8 + 12 = 30
My total: 48 . I WIN!!
Question: What is the highest total you can get and win?
Now for the answer
As many of you have figured out, 50-28 is the answer. Let’s work thru that.
Let’s follow a “hungry” algorithm ( we will do local optimization at every step. Following are the possible moves as your first move: (the numbers after “|” are the factors that I will get)
12 | 1,2,3,4,6 (tot for me 16, diff between you and me -4)
11 | 1 (tot 1 for me, diff between you and me 10)
10 | 1,2,5 (tot 8 for me, diff between you and me 2)
9 | 1,3 (tot 4 for me, diff between you and me 5)
8 | 1,2,4 (tot 7 for me, diff between you and me 1)
7 | 1 (tot 1 for me, diff between you and me 6)
6 | 1,2,3 (tot 6 for me, diff between you and me 0)
5 | 1 (tot 1 for me, diff between you and me 4)
4 | 1,2 (tot 3 for me, diff between you and me 1)
3 | 1 (tot 1 for me, diff between you and me 2)
2 | 1 (tot 1 for me, diff between you and me 1)
The best bet for you to have maximum advantage is to you pick 11. Note that after that you cannot take 7,5,3 or 2 since there are no factors left. Now the board is:
12 | 2,3,4,6 (tot for me 15, diff between you and me -3)
10 | 2,5 (tot for me 7, diff between you and me 3)
9 | 3 (tot for me 3, diff between you and me 6)
8 | 2,4 (tot for me 6, diff between you and me 2)
6 | 2,3 (tot for me 5, diff between you and me 1)
4 | 2 (tot for me 2, diff between you and me 2)
7 | invalid
5 | invalid
3 | invalid
2 | invalid
To maximize your advantage, you pick 9. I get 3. You are up to 20 now and I am at 4. Next..
12 | 2,4,6
10 | 2,5
8 | 2,4
6 | 2
4 | 2
7 | invalid
5 | invalid
2 | invalid
Using the above algorithm, your maximum advantage is to pick 10 and give me 2 and 5. So you are 30 and I am 11. Next
12 | 4,6
8 | 4
6 | invalid
4 | invalid
7 | invalid
Biggest advantage is if you pick 8 and give me 4. So you are 38 and I am 15. Next
12 | 6
6 | invalid
7 | invalid
You take 12 and I get 6. So you are 50 and I am 21.
Only 7 is left on the table which I get. That makes it 50-28. You have 12,11,10,9,8 and I have the rest.
NOW THE QUESTION IS HOW DO YOU PROVE THAT YOU CANNOT GO BEYOND THIS?
Essentially, how do you prove that the local optima add up to global optimum?
For this, we just need to prove that you CANNOT be more than 50.
Step 1:
Note that all prime numbers above the midpoint excepting the highest one are really immaterial. They all belong to me.
Any number you take as the first step, I get 1. Moment I get 1, you CANNOT take any prime numbers (since I have no factors to pick then). Those prime numbers are either going to be picked by me or left at the end on the table. The prime numbers below the half point (in this case 2,3,5) have a chance pf being picked by me – if you pick their multiples (like 4,6,9,10 etc etc) but the ones beyond the mid point (7 and 11 here) – you can pick one and then the rest are all going to be left on the table till the end.
So, as a first move, you do not want to pick anything but the highest prime number (this optimizes your giving away 1).
Step 2:
The deck of cards now left for play between us is the full deck minus all the prime numbers past midpoint and 1. Which means, we are left with 9 cards now.
Note that for every card you pick, I will pick at least one card (else your move is illegal). So under no circumstances can you have more cards than me. (it has to be equal to or less).
We have 9 cards left. Your maximum possible number of cards is 4 (and I get 5 by the above logic).
So, in all, you can have no more than 5 cards (inclusive of the highest prime you picked first) out of 12 cards.
Step 3:
The maximum total of any 5 cards from a deck of 1-12 is 8,9,10,11 and 12 (the five highest numbers). And that is exactly what the hungry algorithm got us.
Therefore, we can say conclusively that 50 is the maximum you will get.
P.S. This logic can be extended to 24 and 48 cards too.
Baah! Khoob moja! Very well explained too! 🙂