# Puzzles involving binary numbers **URL:** \ **Category:** In My Humble Opinion\ **Created:** [April 27, 2012, 7:30pm UTC](https://boards.straightdope.com/t/puzzles-involving-binary-numbers/620168 "2012-04-27T19:30:29Z")\ **Posts on this page:** 9\ **Page:** 2
**Author:** ![Greg\_Charles](https://avatars.discourse-cdn.com/v4/letter/g/839c29/32.png) [@Greg\_Charles](https://boards.straightdope.com/u/Greg_Charles)\ **Post date:** [April 30, 2012, 11:19pm UTC](https://boards.straightdope.com/t/puzzles-involving-binary-numbers/620168/21 "2012-04-30T23:19:20Z")
> [@Left\_Hand\_of\_Dorkness](#): > > Greg Charles, that’s very similar to Nim, which septimus already mentioned. I like your explanation of how to solve the game–but can anyone explain why that solution works, in a simple narrative that I might be able to follow? (I can maybe try to convert that narrative into a third-grade friendly one, but I’ve been trying to understand why the solution works since I figured out how to implement it earlier this afternoon). Is it? Sorry, I didn’t know it by the name Nim. I can’t explain why it works exactly, but sort of inductively: First define the state where there are an even number of Xs in each row as GOOD, and all other states as BAD. You want the state of the grid to be GOOD after your turn. If you leave the grid with two rows, each with one X, that’s a GOOD state. It’s clear that your opponent will have to cross out one X, leaving you with the last X and the win. Call that the base state. Now, I could show by example that you can always go from a BAD state to a GOOD state via a legal move, and that you can never go from a GOOD state to another GOOD state via a legal move. (I’m pretty sure that this could be proven mathematically, but I’m also pretty sure I couldn’t do it myself.) If you keep putting the grid into a GOOD state, and your opponent perforce puts it into a BAD state, then eventually you will hand him or her the GOOD base state I defined above, and he/she will lose. There doesn’t seem to be an equivalent trick for the Last-One-Loses variation of the X Game. I believe that’s because, while there’s only one way to put a BAD grid into a GOOD state, there are usually multiple ways to put a GOOD grid into a BAD state. ---
**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\ **Post date:** [May 1, 2012, 6:30am UTC](https://boards.straightdope.com/t/puzzles-involving-binary-numbers/620168/22 "2012-05-01T06:30:04Z")
> [@Left\_Hand\_of\_Dorkness](#): > > can anyone explain why that solution works, in a simple narrative that I might be able to follow? Define Winning Position as one where you win if it is opponent’s turn to move. The game is symmetric so we need only show two facts: (1) Any Losing Position can be converted to a Winning Position. (2) No Winning Position can be converted to a Winning Position. Proofs: (1) We need only invert each imbalance in the binary-place sums. This can always be done by playing in the largest row. (2) There are no imbalances. Removing pegs from any single row will create imbalance(s). > [@Greg\_Charles](#): > > There doesn’t seem to be an equivalent trick for the Last-One-Loses variation of the X Game. To the contrary. The exact same strategy works except that when playing in the final row with two or more pegs, you flip the 1’s bit, i.e. reduce to a single peg when you’d reduce to zero in Last-One-Wins, or vice versa. ---
**Author:** ![psychonaut](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/psychonaut/32/4655_2.png) [@psychonaut](https://boards.straightdope.com/u/psychonaut)\ **Post date:** [May 1, 2012, 11:16am UTC](https://boards.straightdope.com/t/puzzles-involving-binary-numbers/620168/23 "2012-05-01T11:16:47Z")
> [@Left\_Hand\_of\_Dorkness](#): > > I showed them a few tricks with binary: how you can use it to guess a number between 1 and 1000 (really 1,024) in 10 guesses or fewer if the audience will tell you “higher” or “lower,” just by guessing each place value in turn (e.g., if your first guess is 512, you’re really asking whether, in base 2, there’s a 1 in the 9th place). I don’t see what base-2 has to do with this; you’re essentially describing a binary search, which can be done in any base. At each step you simply guess the midpoint of the interval, and then use that midpoint as the lower or upper bound of the new interval, depending on whether the audience said “higher” or “lower”. ---
**Author:** ![Greg\_Charles](https://avatars.discourse-cdn.com/v4/letter/g/839c29/32.png) [@Greg\_Charles](https://boards.straightdope.com/u/Greg_Charles)\ **Post date:** [May 1, 2012, 8:24pm UTC](https://boards.straightdope.com/t/puzzles-involving-binary-numbers/620168/24 "2012-05-01T20:24:44Z")
> [@septimus](#): > > To the contrary. The exact same strategy works except that when playing in the final row with two or more pegs, you flip the 1’s bit, i.e. reduce to a single peg when you’d reduce to zero in Last-One-Wins, or vice versa. Hmm, interesting, though I don’t understand your explanation. Let’s say it’s my turn and the remaining grid is: ```auto X 1 XXX 11 ``` In LOW, I would erase two lower Xs. In LOL, I would erase all of them. What 1s bit am I flipping to tell me that? What if the grid were: ```auto X 1 X 1 XXX 11 ``` ---
**Author:** ![Left\_Hand\_of\_Dorkness](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/left_hand_of_dorkness/32/7156_2.png) [@Left\_Hand\_of\_Dorkness](https://boards.straightdope.com/u/Left_Hand_of_Dorkness)\ **Post date:** [May 1, 2012, 8:55pm UTC](https://boards.straightdope.com/t/puzzles-involving-binary-numbers/620168/25 "2012-05-01T20:55:44Z")
> [@psychonaut](#): > > I don’t see what base-2 has to do with this; you’re essentially describing a binary search, which can be done in any base. At each step you simply guess the midpoint of the interval, and then use that midpoint as the lower or upper bound of the new interval, depending on whether the audience said “higher” or “lower”. Yeah, you don’t have to do it in base-2, but since I’d just shown them the place values for base 2, I showed them that the questions could look something like this: -Is there a 1 in the 512 place? -Is there a 1 in the 256 place? -Is there a 1 in the 128 place? and so on. We were therefore building a base-2 number through a series of yes-no questions, and by asking 10 questions, we were able to determine exactly which number had been chosen. Update, anyway: today was a thrilling race to figure out the solution to the game of 100. Yesterday a couple of people figured out that if you got to 89, you controlled the game, and then today a couple of people figured out that if you got to 78 you’d win, and pretty quickly after that it cascaded into a realization of what your first number would have to be. It was awesome watching them figure it out, exactly the kind of thing that [rant] I ought to be doing more of instead of asking students to do end-of-grade test practice [/rant]. So I taught them Nim, and we played for a bit, and they’ve figured out some basic stuff, but we’ll continue tomorrow working with it to see what they can figure out. ---
**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\ **Post date:** [May 1, 2012, 11:38pm UTC](https://boards.straightdope.com/t/puzzles-involving-binary-numbers/620168/26 "2012-05-01T23:38:56Z")
> [@Greg\_Charles](#): > > ```auto > > X 1 > XXX 11 > > ``` > > In LOW, I would erase two lower Xs. In LOL, I would erase all of them. What 1s bit am I flipping to tell me that? In LOW, you reduce to 1,1. In LOL, you reduce to 1,0. The difference between 1,1 and 1,0 (or more simply, between 1 and 0) is a “flipped 1’s bit.” Earlier I wrote “reduce to a single peg when you’d reduce to zero in Last-One-Wins, or vice versa.” I hope at least one of these explanations works for you! 😃 ---
**Author:** ![Greg\_Charles](https://avatars.discourse-cdn.com/v4/letter/g/839c29/32.png) [@Greg\_Charles](https://boards.straightdope.com/u/Greg_Charles)\ **Post date:** [May 2, 2012, 9:11pm UTC](https://boards.straightdope.com/t/puzzles-involving-binary-numbers/620168/27 "2012-05-02T21:11:48Z")
I think I’ve got it. I play a LOW strategy as long as there are multiple rows with multiple Xs, but when there’s just one row with multiple Xs, the LOW strategy is going to either tell me to erase that entire row, or leave one X remaining, depending on whether an odd or even of other rows are left in the grid. In that case, I do the opposite of what LOW tells me to do, and I win LOL. Cool. I never thought of that! ---
**Author:** ![Left\_Hand\_of\_Dorkness](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/left_hand_of_dorkness/32/7156_2.png) [@Left\_Hand\_of\_Dorkness](https://boards.straightdope.com/u/Left_Hand_of_Dorkness)\ **Post date:** [May 2, 2012, 10:43pm UTC](https://boards.straightdope.com/t/puzzles-involving-binary-numbers/620168/28 "2012-05-02T22:43:44Z")
Okay, I think I’m starting to understand Nim, and am nearly ready to prove why the binary-states work for a very simple game (3 piles of 3, 4, and 5 items). A “winning position” is one where you end your turn with it, and if you play right, nothing your opponent does can keep you from winning. The most basic such position is 1/1/0 cubes: at this point, your opponent must remove one entire stack, and then you remove the other and win. It’s pretty easy to see that 2/2/0 is also a winning position, because an opponent has only two choices: take 1 from one pile, or take 2 from one pile. If the opponent does the first thing, then you take 1 from the other pile and have the 1/1/0 winning position; if the opponent does the second thing, then you remove the other pile and win. 3/3/0 is similarly a winning position: if the opponent removes a whole stack, then you remove the other stack and win, and otherwise you remove the same amount from the one stack as the opponent removed from the other, reducing it to a different winning position (2/2/0 or 3/3/0). Similar logic works for 4/4/0, and in other games, for any similar situation with two equal stacks. If two equal stacks are a winning position, then two unequal stacks are clearly a losing position, because your opponent can equalize the stacks, gaining a winning position. Present your opponent with 5/2/0, for example, and the opponent removes three from the first stack, gaining 2/2/0, costing you the game. That leaves the question of 3 stacks. If two of the three stacks are equal, then it doesn’t matter what the third stack is: your opponent can remove the whole shebang, presenting you with two equal stacks and costing you the game. 3/5/3 can be reduced to 3/0/3, for example. So only stacks with three unequal quantities can be winning (assuming none of the stacks are empty). Here’s where my analysis fails. I think it has something to do with the doubles, and how each double is essentially an equal pair of a lower number, but I’m not quite sure I understand. There are two winning positions I can find: 1/3/2 (whatever you opponent does, you’ll be able to reduce play to two equal piles next turn), and 1/4/5 (whatever your opponent does, you’ll either be able to reduce it to 1/2/3 or to two equal piles next turn). The explanation needs to be narrative, I think, not involving symbols. ---
**Author:** ![Left\_Hand\_of\_Dorkness](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/left_hand_of_dorkness/32/7156_2.png) [@Left\_Hand\_of\_Dorkness](https://boards.straightdope.com/u/Left_Hand_of_Dorkness)\ **Post date:** [May 2, 2012, 10:53pm UTC](https://boards.straightdope.com/t/puzzles-involving-binary-numbers/620168/29 "2012-05-02T22:53:02Z")
And to be clear, the explanation I’m looking for is one where you hear it and can say, “Oh, right, that makes sense,” not one that you can understand logically but not really intuit. I can explain intuitively why any two equal stacks is winning, or why any two equal stacks plus one unequal stack is losing, but I want to explain intuitively why 1/2/3 or 1/4/5 is winning, and especially relate that intuitively to binary numbers or to doubling. [Previous page](https://boards.straightdope.com/t/puzzles-involving-binary-numbers/620168.md?page=1)