## Monday, November 17, 2008

### Sum of 15

Two players are playing a game and take alternating turns. Initially, there are 9 cards with numbers from 1 to 9 on the table. On each turn, a player takes one of the cards. The first player to have exactly 3 cards with numbers that sum to 15 wins. If no one can after all cards are distributed, then it's a draw.

Can you tell who wins and how to play this game without using a computer to analyze all possible positions?

1. First Player has choice of 5 cards , So using Pigeon hole principle , We can always have a subset of 5 Number from 9 Number that can sum upto 15 with three numbers.

First player will always win

2. hehe, there's been an old srm problem with the exact problem :)

this problem is equivalent to tic-tac-toe, so if both players play optimally, the result is draw.

3. Was there?

You're right, the magic square does the trick.

4. http://www.topcoder.com/stat?c=problem_statement&pm=1850&rd=4665

:)

it's way before your first srm hehe..

5. There's a book explaining this problem, where you can think about the 3x3 magic square and use the tic-tac-toe strategy. I saw it once in the library but I could never find it until today!

I'd really appreciate if someone could tell me the name of this book. It was in the artificial intelligence section I think, it was explaining about different ways to "see a problem". :)

It also talks about the "limits of our mind", better ways to remember and strategies to solve problems... It was written by an engineer, but it's all I can remember... I was looking for problem solving strategies books...

Can someone help me to find it again? :P

7. Excellent posts! Keep going! Eagerlay waiting for your next post.

8. Found it! Thanks, Petr! ^^

It was in the 11th page of google books search. "Patterns of problem solving" by Moshe F. Rubinstein (1975). It's quite an old book; I was only curious to look at some books, when I suddenly had to go home that day...

By the way, Petr, is there a book you would recommend about math or problem solving?

Could be something for a "beginner"... I don't have good skills in math or programming yet.

I will try to participate in ACM-ICPC competition next year, so any advice is welcome, specially from you!

Thanks for sharing your time with us! Have a nice day! :)

(Sorry for the kinda long post; or if you already answered this somewhere...)

9. to Jamaj,
in his topcoder chat session petr said that "Introduction to Algorithm" & "Concrete Mathematics" are enough for Algorithm & math skills.

to Petr,
please Post more "Tips & Ticks" style articles Petr!!

10. I first found this property in book

"Winning Ways for Your Mathematical Plays" by Elwyn R. Berlekamp, John H. Conway, Richard K. Guy

11. nice blog. keep posting. we're always reading. by the the way, you inspire me a lot. :)

12. Generating a matrix as below:
2 7 6
9 5 1
4 3 8

The first one always chooses the center number - 5, and will always win.

13. Don't you think it can be more valuable to post in russian?

14. Why? Most (if not all) of Russian-speaking people I know that might be interested in programming competitions speak English as well; the reverse doesn't hold.

15. The first player to have exactly 3 cards with numbers that sum to 15 wins.

16. Petr, you said in your interview for TopCoder that you participate in ~8 ACM style Russian Open contest a year. Are these contest open to everyone on the internet or only open to participate locally?

17. Petr write again, we are waiting for your posts