Game Theory Puzzle: The Race To 15
Vložit
- čas přidán 23. 06. 2024
- I have seen this puzzle in a few places. Most recently I came across it in Peter Winkler's "Mathematical Puzzles: A Connoisseur's Collection" amzn.to/1DcPE4V
The Race to 15 Game Theory Puzzle. Alice and Bob take turns selecting cards numbered 1, 2, .., 9 without replacement. (Alice goes first, then Bob picks a remaining card, and so on).
The first player to make a set of 3 cards that adds up to 15 wins the game. Does Alice have a winning strategy?
The video relies on the fact there is only 1 unique arrangement. See this proof: • Why is there only one ...
If you like my videos, you can support me at Patreon: / mindyourdecisions
Connect on social media. I update each site when I have a new video or blog post, so you can follow me on whichever method is most convenient for you.
My Blog: mindyourdecisions.com/blog/
Twitter: / preshtalwalkar
Facebook: / 168446714965
Google+: plus.google.com/1083366085665...
Pinterest: / preshtalwalkar
Tumblr: / preshtalwalkar
Instagram: / preshtalwalkar
Patreon: / mindyourdecisions
Newsletter (sent about 2 times a year): eepurl.com/KvS0r
My Books
"The Joy of Game Theory" shows how you can use math to out-think your competition. (rated 4/5 stars on 23 reviews) www.amazon.com/gp/product/150...
"The Irrationality Illusion: How To Make Smart Decisions And Overcome Bias" is a handbook that explains the many ways we are biased about decision-making and offers techniques to make smart decisions. (rated 5/5 stars on 1 review) www.amazon.com/gp/product/152...
"Math Puzzles Volume 1" features classic brain teasers and riddles with complete solutions for problems in counting, geometry, probability, and game theory. Volume 1 is rated 4.5/5 stars on 11 reviews. www.amazon.com/gp/product/151...
"Math Puzzles Volume 2" is a sequel book with more great problems. www.amazon.com/gp/product/151...
"Math Puzzles Volume 3" is the third in the series. www.amazon.com/gp/product/151...
"40 Paradoxes in Logic, Probability, and Game Theory" contains thought-provoking and counter-intuitive results. (rated 4.9/5 stars on 7 reviews) www.amazon.com/gp/product/151...
"The Best Mental Math Tricks" teaches how you can look like a math genius by solving problems in your head (rated 4.7/5 stars on 3 reviews) www.amazon.com/gp/product/150...
"Multiply Numbers By Drawing Lines" This book is a reference guide for my video that has over 1 million views on a geometric method to multiply numbers. (rated 5/5 stars on 1 review) www.amazon.com/gp/product/150... - Věda a technologie
Great puzzle, but I misunderstood it! I assumed they were picking the cards out randomly!
There's a really easy solution to this. Whenever Alice has picked two numbers, there's only one number remaining which fits the first two numbers. That means that Bob can pick the first number at random, and then pick number [15-A1-A2] as the second one, to always secure a draw.
+Simen Bjelland When Alice picks a third number A3, there are two more pairs (A1,A3) and (A2,A3) that Bob might worry about. Here's an example : Alice picks 6, Bob picks 3 (completely at random). Alice picks 8. Bob picks 15-6-8=1. Alice picks 2 and wins the game! Because A1+A3=6+2=8, so she wins by picking 7 next turn, but A2+A3=8+2=10, so she also wins by picking 5 next turn, and Bob cannot win right now, because he only has two numbers adding up to 4 and cannot pick 11.
You can take a magic square and put X's on every number played by Alice and O's for every number played by Bob to get the visual counterpart :)
But what if Bob picked 5?
The names Alice and Bob show up in a course that isn't cryptography?
What is this witchcraft?!
Actually, juste like the model of Stackelberg in game theory, the first player to make a move in a game can garantee a lock on his win. For instance here, picking first the number 5 can garantee a lot of potentiel number combinaisons that can garantee his win and therefor, not be constantly blocked to end up with a draw in the game.
To come back to the model of Stackelberg in game theory, the first firm to produce a quantity of product X can know how much he exactly needs to produce more than the other firm and therefor make more profit than the other firm on the market.
Then again, the model of Stackelberg is just an illlustration of a lot more other models in game theory where the first player to make a move can actually know wich moves he needs to do to lock his win.
Nice! It'd be nice to see a mathematical derivation of the up-right or down rule! :D
I think it's just a pattern they noticed historically: en.wikipedia.org/wiki/Siamese_method
Also. If alice picks up say 5 and then bob picks up a random number 2, alice gets two in a row by 6 and a few more numbers one of which she picks, bob shall always destroy her pair by picking the last number
I think it'd be worth saying that they're allowed to see the cards they choose from. Also, I came up with combinations such as 771, which was not an option (no repeats). Lastly, it'd be great to see an explanation of that magic square algorithm. Sorry if I'm nagging too much - just some suggestions/requests.
Didn't put a ton of work into this, just a couple minutes. I've listed the only eight possible winning unordered triples. I've listed how many times each number appears in the list, just for a general idea of the best number(s) to choose -- 5 appearing 4 times, all even numbers appearing 3 times, and all other odd numbers appearing just 2 times. So 5 would APPEAR to be the best choice for first pick. However, I played it out a couple of times and it just doesn't "feel" winnable for either player if they are both perfect players. So that is my hypothesis; now I will watch.
Ahhh, right! It's logically equivalent to a game of tic-tac-toe. Didn't notice that. My hypothesis was correct, though.
You, unlike the video maker, have found out the exact reason why 5 should be in the middle of a tic-tac-toe board, the evens on the corners, and the odds in the remaining spots.
Excellent!
"Up+Right or Down" works wherever you start, actually, any combination of "diagonal or (opposite of one part of the diagonal)" does, to give us sum of 15 in each row and in each column.
Only when 5 is in the middle does it give us sum of 15 in the diagonals as well.
Looks like he had the solution and tailored an explanation to fit it...
"Did you solve this puzzle" Ha! That's funny!
I have a mathematical way to obtain the magic square. First like someone pointed out that there are 8 ways to get a sum of 15. The list is (159)(168)(249)(258)(267)(348)(357)(456). There are 4 main steps.
1) Since 5 appear 4 times it has to occupy the center square because there are 2 diagonals, one row and one column that pass through the center square.
2) 7, 8 and 9 cannot be in the same row and column because 7 + 8, 7 + 9 or 8 + 9 are already greater than 15.
3) 8 must occupy a corner square because it appears 3 times in the list above. 7 and 9 must not occupy corner squares because they appear twice in the list.
4) Once this is done the numbers for remaining squares can be determined by checking for a sum of 15.
Imagine this; either 2,3 or 4 cards may add up to 15, you keep playing even if a player is above 15. From the 4th turn you discard your earliest picked card each turn (To keep games above 15 without draws) before discarding your card you may count all 4 cards up to 15 if not still discard. There is a strategy to force winning within 10 turns (Or less, i forgot) If you have found the strategy please tell me in a reply. Tip; second turn you do not force any card unto your opponent. This means you need to have a strategy for 6 different responses to your second turn
I got as far as determining that there was no forced win for Alice, and was about to explore the situation assuming best play by both sides (I started out assuming that Bob would only try to prevent Alice from winning)... but I got impatient :'(
It's a tic-tac-toe game across a magic square. The magic square is:
294
753
618
And as it's a tic-tac-toe game, she cannot guarantee a win.
For tictactoe if you choose a corner and they don’t choose the middle - in this instance 5 - then you win!
Wow nice magic square which relates to tic tak toe aka ZERO-KATA XD
I consider myself a young math wizard yet the solution was magic to my lol ;)
Why can't you win with 2 cards, or 4?
I dont think alice can guarantee a win
5 is clearly the strongest number (4 ways to make 15 compared to 4,2,8,6 having 3 and 9,7,3,1 having 2), so Alice should take 5.
From there Bob takes one of 4 2 8 or 6 it doesn't matter, for now let's assume 8.
Now for alice, 2 is a terrible option so we won't pick it, the only reasonable options are 9,7,4 and 6. 9/7 are functionally identical while 4 and 6 are also functionally indentical.
Either way Bob blocks alice and can continue to do so indefinitely.
in your senario of Alice taking #5 and Bob taking #8 for Alice's second move taking #2 is actually her best option. the reason for this is because Bob has already blocked the 3 in a row for that option which means he has to now choose another random number. Bob would then be left with #'s 1,3,4,6,7,9. With these options unless Bob picks #'s 4,6 Alice has a win. This is basic tic-tac-toe.
do they get to see what card they are picking before they pick it
Alice picks 5
Bob picks 9 for example
Alice picks 4
Bob can not pick 6 because he will have reached 15 too soon, he picks another number.
Alice picks 6 - DONE
Another example
Alice picks 5
Bob picks 3
Alice picks 9
Bob can not pick 1 as he won't make it to 15 in 3 cards. He picks another number.
Alice picks 1 DONE
She can guarantee a win.
She can only guarantee a draw IF Bob breaks the rules of the game set out at the beginning of the video - to be the first to take 3 cards that add up to 15.
You didn't explain why "Up+Right or Down" - any "diagonal or (opposite of one part of the diagonal)" will produce a square with sum 15 in each row and column.
You didn't explain why to start with 1 at the center of the top row.
The only way that the sums of the diagonals will be 15 as well, is to have the 5 in the middle.
This "conveniently/magically" happens when you start with 1 where you did.
I think there are 8 magic squares: 4 rotations and their mirrors.
@Ace Diamond figured out:
"5 appearing 4 times, all even numbers appearing 3 times, and all other odd numbers appearing just 2 times.".
There are 4 lines through the center, so 5 should go there,
There are 3 lines through each corner, so the even numbers should go there, and
There are 2 lines through the remaining spots, so the odd numbers should go there.
After putting the 5 in the center,
put any even at any corner and you find the opposite even,
put one of the remaining 2 evens in one of the remaining corners and the last has only one place to go,
after that, the odds "fall into place on their own"...
there are strategies to winning tic tac toe, there are plans to get two ways of winning, created in one move.
+WhovianMinecrafter if both players play perfectly it will end up in a draw. You can only create such a scenario if thet other player plays suboptimally, but this game was about guaranteeing a win.
How the fuck can you play this without knowing WHETHER YOU CAN SEE THE OPPONENTS CARDS??
where you read card faces/number was hidden?
It can be inferred from the full video that you can, but I agree it was slightly sloppy of Prush not to have said so.
Wait. How do you know that your magic square contains all possible 15 sums?
***** It can be proven the 3x3 magic square is unique (up to rotation and reflection), so this is the only way to arrange the numbers so every row, column, and the two diagonals sum to 15.
I'd think about it this way. If you play the game with numbers, it will correspond to some arrangement of X's and O's on the magic square that was drawn. So if you play by a tic tac toe strategy, you can block a sum of 15.
That doesn't answer the question. How do I know that there isn't a sum, a+b+c=15, such that a,b and c do not appear all in one column, row, or diagonal?
***** Have you tried working it out? There are not too many possibilities. It is easy to see the middle number has to be 4, 5, or 6. (If the middle number is 3, the maximum sum is 2+3+9 = 14. For similar reasons, the middle number cannot be 2, 7 or 8.) From there you can work out the combinations and see they are in the magic square.
+MindYourDecisions If there are not too many possibilities, why didn't you show them in the video? I did the math, and it's really simple. There are only 8 sums of three different one-digit numbers that add up to 15 (you can show them by creating all triplets starting with 1, then all triplets starting with 2 and not containing 1, and so on). Then, you can just state that you are going to create some figure in which every triplet adding up to 15 will be in a row, and the fact that 5 appears in 4 of these sums naturally creates a star-like arrangement, with the 5 at the center and the 4 lines - \ | / drawn from it. The argument of "even numbers appears more frequently, so let's put them in the corners" works perfectly, and tadaaa, you create the magic square, but showing that it contains all possible 15 sums. That's actually what I did on the paper, and I was like "oh, great, a magic square" at the end :)
Lets assume there is a sum a+b+c=15 that doesn't appear in any column, row, or diagonal.
a, b and c must be all 3 in different rows, columns and diagonals: If a and b are in the same row, for instance, then the c we need to sum up to 15 would be the other digit in the row.
So we just need to look into all the possibilities of sets of 3 numbers that don't share and columns, rows or diagonals.
They are: 8+7+9, 1+3+2, 1+7+4 and 6+3+9.
None of these sums up to 15. Thus, every possibility of a+b+c=15 is covered in the tic tac toe.
I missunderstood it. Actually I thought that Alice begins with 1, then Bob takes 2, Alice takes 3, etc. So in this case only Alice can win.
Yeah.. You're right. Alice can win the game.
This is really cool. Just showed this to my roomates.
Isnt this the same as the product to 32768 problem?
I figured out this was isomorphic to Tic-Tac-Toe without watching the video, yaaaay :D So yeah, she can't guarantee a win, but can always guarantee not to lose.
How can Alice not win? If she picked up 1,5, and 9, wouldn't she have 3 cards that add up to 15? 1+5+9=15. Did I misunderstand the rules of the game? I mean yea she'd also have 3 and 7, but the game said the first with a set of 3 that add up to 15, so 3 and 7 don't matter.
Nvm, I'm assuming the cards are in random order. That would make much more sense.
why does the magic squre is equle to 15? and why are you doing it the way?
So the goal of the game is to grab any 3 of the total 9 cards, and if those three add up to 15, you win. Since there are 9 cards and each one is labeled 1-9, then there are no repeats. The magic square is only there just to help us see all the possibilities at once שחר לאופר
I got it right! This was a fun puzzle.
i got it!! i think im good with game theroy
I did some math and got that she has a 1/7,560 chance to get a win on her first three cards, and then I noticed that's not what I needed to do.
***** Well, I didn't listen to the directions, and I did the completely wrong calculation
The cc says this is pressure locker
alice is not guaranteed a win, because with 36 playing cards, 4 each of aces-9's in a perfect random order I have simulated 5 of these games, alice won thrice to bob's two times, thus disproving a guaranteed win.
Garrison Pendergrass there aren't 36 cards in this puzzle dumb ass
I know other method to generate a magic square first write up the numbers 1 througth 9 then swap the opposite corners (3 with 7 and 1 with 9 then rotate every outer piece clockwisely
4 9 2
3 5 7
8 1 6
Wow, imagine fusing this with notakto.
I was so close!! I thought of the tic tac toe but had no experience with magic squares so I gave up.... dammmmmit.. :S
You didn't offer any proof that that's the one and only way to arrange those numbers to sum to 15. You just asserted it. As such that's not a proof.
There are more ways to arrange those nunbers to sum to 15, except they are just rotations/reflections of the one shown in the video
Observation: If Alice picks 5 in her first round and Bob picks any of the odd numbers in his first round, then Alice will always win. If Bob picks any of the even numbers in his first round, it is always a tie.
Nope. Bob can pick any random number for the first round, just that he needs to be aware from second round onwards
This is tictactoe, If alice picks 5 which is the centre square in the 3x3 magic square. Bob loses if he doesnt pick a corner (which is an even number)
Alice has a guaranteed win if she chooses 6, 7, 8, or 9 first...the rest is just following basic tic tac toe strategy to seal the game... (the reason 6, 7, 8, or 9 is guaranteed is because it forces the opponent to pick a number that would have equaled 15 [6+9, 7+8])...and the number they are forced to pick is bad with regards tic tac toe strategy, always susceptible to defeat
+ownageLSU
No, you misunderstood the rules.
Your examples, 6+9 and 7+8, each utilise just _two_ cards, whereas the object of the game is to accumulate exactly _three_ cards totaling 15.
touchè, I def saw that as a set of up to 3 cards seeing as the game is called "Race to 15"...so I made the fatal assumption that 2 cards would suffice...good call
I think Alice can win in this:
Alice picking 8
Bob have to take 7
Alice picking 4
Bob have to pick 3 (or Alice will get 8 4 3 )
Alice picking 5
then Bob have to take 2 ( or Alice will get 8 5 2 )
then Alice will pick 6 and she will get ( 4 5 6 )
You have to have a set of 3 cards to equal 15, so Bob does not have to take 7 in your scenario.
I actually had created a board and went through different iterations and came to this conclusion (before I saw it was a tic-tac-toe game):
If Alice picks 8, then Bob MUST choose either 4, 5, or 6. If you consider 8 + 7 = 15, then consider the pairings for 1 + 6, 2 + 5, & 3 + 4, you'll notice Bob cannot allow Alice to have any of these combinations, or she wins. If Bob chooses 1, 2, 3, 7, or 9, Alice can simply choose each of 4, 5, or 6 in an appropriate order to force Bob to "block." So, let's say Bob chooses 2, for example. Alice chooses 6, this forced Bob to block on 1. Alice then chooses 4, forcing Bob to block on 3. This leaves 5, but because Alice now has 4 & 6, she doesn't need 2 + 5 + 8 anymore, she can just use 4 + 5 + 6 = 15.
So that means if Alice chooses 8, Bob is down to 3 choices. However, if Bob chooses 4, Alice simply needs to pick 5, which forces Bob to block at 2. Then Alice picks 1, which forced Bob to block at both 9 & 6, which he cannot do. If Bob chooses 6, the same thing will happen except with the iteration of 8-6-5-2-3 and then Bob has to block both 4 & 7.
However, I couldn't figure out any way to force Bob to lose if he chose 5 with his first option, so I gave up. Turns out I was solving Tic-Tac-Toe, lol, oh well.
[EleG] Northern King in the scenario where Alice picks eight then Bob picks four after Alice pics eight Bob could block at nine which would give them a win
Good call, you are definitely right. ethan wintill
Bob picks 5 here and secures a draw
1/5/15 is win.
Yay I did it.
816
357
492
so tic tac toe! wow....
Easy one
Hi this is crushed a locker