Sunday, November 16, 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?

23 comments:

  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

    ReplyDelete
  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.

    ReplyDelete
  3. Was there?

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

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

    :)

    it's way before your first srm hehe..

    ReplyDelete
  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

    ReplyDelete
  6. Maybe http://books.google.com/books?q=tic-tac-toe+magic+square&btnG=Search+Books can help?

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

    ReplyDelete
  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...

    Pages 15-16 is where I read about this "change in representation". Don't know if it's a good book because I've only read a few pages.

    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...)

    ReplyDelete
  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!!

    ReplyDelete
  10. I first found this property in book

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

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

    ReplyDelete
  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.

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

    ReplyDelete
  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.

    ReplyDelete
  15. The first player to have exactly 3 cards with numbers that sum to 15 wins.
    IMHO 'exactly' is mesleading here.

    ReplyDelete
  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?

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

    ReplyDelete
  18. It's very good when you ask and receive answers... =/

    ReplyDelete
  19. 2Paulinho: sorry for not answering your question. Those competitions are designed to be onsite competitions, not online ones. There're many locations throughout Russia and CIS where each of those takes place simultaneously. The idea is to have a local organizer that will oversee that the participants follow the rules. Each of those locations is usually some university. I believe you can try to apply for your university to be one of the locations for the contest, and they'll tell you how to proceed. You can try contacting regions(ASCII 64)opencup(ASCII 46)ru for more information from the organizers (I'm not one of them).

    ReplyDelete
  20. Ok, I felt "displaced" here.
    But I think this is practically impossible since in my university it's not common to play this kind of competition. There are at most 2 or 3 people who likes to play. It is very difficult to find guys to practice for ACM (for example). I start to practice last year (in October) for the ACM but I'm training alone for a while.
    If there were many guys who liked that, I'd think in the case but.....
    Thanks for the answer.

    ReplyDelete
  21. Dead peepz dizz dayzzz

    ReplyDelete
  22. Think Twice - Michael j. Mauboussin

    ReplyDelete