Puzzles involving binary numbers

[Greg_Charles]

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

[septimus]

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

[psychonaut]

@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”.

[Greg_Charles]

@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:

 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:

 X         1
 X         1
XXX       11

[Left_Hand_of_Dorkness]

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

[septimus]

@Greg_Charles

 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!

[Greg_Charles]

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!

[Left_Hand_of_Dorkness]

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.

[Left_Hand_of_Dorkness]

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.