wu :: forums « wu :: forums - NIM game » Welcome, Guest. Please Login or Register. Apr 24th, 2024, 9:01pm

RIDDLES SITE WRITE MATH! Home Help Search Members Login Register

wu :: forums    riddles    hard (Moderators: Grimbal, Icarus, william wu, ThudnBlunder, towr, SMQ, Eigenray)    NIM game « Previous topic | Next topic » Pages: 1  Reply Notify of replies Send Topic Print    Author  Topic: NIM game  (Read 3219 times) Altamira_64 Junior Member     Posts: 116 NIM game   « on: Apr 29th, 2012, 1:32pm » Quote Modify Force the other player to take the last matchstick. In this game there will be 9 rows of matchsticks: First row has 1 matchstick, second has 2 etc and last one has 9 and the two players alternate to take matchsticks from the rows. Each time a player can take any number of matchsticks from any one row, but he cannot take matchsticks from multiple rows. The one who is forced to take the last matchstick loses. What is the strategy to always win the game? IP Logged towr wu::riddles Moderator Uberpuzzler Some people are average, some are just mean.     Gender: Posts: 13730 Re: NIM game   « Reply #1 on: May 8th, 2012, 2:59am » Quote Modify If you take the bitwise exclusive or (xor) of the binary representation of the counts of the number of matchsticks in each row, it should be 0 after your move, except when it would leave all the remaining rows with just one matchstick, in which case you should leave an odd number of rows. Since we start with an xor of 1 (and some rows have more than 1 matchstick), this means we can win.   This the regular nim strategy. « Last Edit: May 8th, 2012, 2:59am by towr » IP Logged Wikipedia, Google, Mathworld, Integer sequence DB Altamira_64 Junior Member     Posts: 116 Re: NIM game   « Reply #2 on: May 8th, 2012, 10:09am » Quote Modify Wow!   So I assume we write all the numbers from 1 to 9 in binary, that is:   0001 0010 0011 0100 0101 0110 0111 1000 1001   So the xor sum is 0001. My first move is, for example, to take one matchstick from the last row and leave 8 (xor=0) and so on? IP Logged towr wu::riddles Moderator Uberpuzzler Some people are average, some are just mean.     Gender: Posts: 13730 Re: NIM game   « Reply #3 on: May 8th, 2012, 12:12pm » Quote Modify Yes. (Just be sure to remember that the rule changes for the last moves: when there are only rows with a single matchstick left it must be an odd number) IP Logged Wikipedia, Google, Mathworld, Integer sequence DB Pages: 1  Reply Notify of replies Send Topic Print Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board