# 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:** 20\ **Page:** 1
**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:** [April 27, 2012, 7:30pm UTC](https://boards.straightdope.com/t/puzzles-involving-binary-numbers/620168/1 "2012-04-27T19:30:29Z")
I teach third grade, and three times a week I take the high-performing math kids from the whole grade level and do an activity with them. Last week I introduced them to the idea of binary numbers. We did a Socratic dialog in which they puzzled out how a base-2 number system would work, including what the place values would be, and then I showed them how it related to powers of 2, and we talked about the use of binary in computer codes. 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 showed them [how to guess a number between 1 and 100](http://www.dr-mikes-math-games-for-kids.com/magic-number-cards.html) just by asking whether the number was on 7 different cards, again by taking advantage of binary numbers/powers of 2. And I showed them the old trick about choosing between winning $1,000 a day every day for 10 years, or getting a penny the first day and doubling it every day for thirty days. They were amazed and delighted with all these tricks: it’s a group of kids ranging from competent to scary-bright, and I tried to keep the pace just a couple steps lower than what the scary-bright kids could do, which is much faster than what they usually get. And now I’m almost out of tricks/puzzles for them, and I need enough for next week. I’d love to hear from y’all to see if you have some. Here’s my last example, a puzzle from Car Talk some years ago that I finally solved when I thought of using binary: > [@my memory of the puzzle](#): > > You’ve got seven rolls of coins, with 100 coins in each roll. Each coin should weigh 1 gram. But you think there might be one or more rolls of counterfeit coins; the counterfeit coins would weigh 1.1 grams instead of 1 gram. You also have a digital scale that’s accurate to within .1 grams. What is the fewest number of weighings you could do in order to determine which, if any, rolls have counterfeit coins? And given that the answer to that question is “one,” how do you accomplish that weighing? If anyone has other puzzles or tricks that take advantage of binary or the powers of two, I’d love to hear them! ---
**Author:** ![cormac262](https://avatars.discourse-cdn.com/v4/letter/c/f14d63/32.png) [@cormac262](https://boards.straightdope.com/u/cormac262)\ **Post date:** [April 27, 2012, 7:50pm UTC](https://boards.straightdope.com/t/puzzles-involving-binary-numbers/620168/2 "2012-04-27T19:50:44Z")
Not really a trick or puzzle (I’ll keep thinking of some, though), but now that you’ve introduced them, you could have them try to “see” where things are limited because a device is using a binary system (bytes) to manage the items. For example, certain powers of 2 (indicating binary storage) pop all over the place in ads: - 512 channels - 64 different power settings - “over 8192 different combinations” So you could have them report when they see/hear of a binary stored value, and then tell you how many bits the device uses to store the value (512 = 9 bits, etc.) ---
**Author:** ![TriPolar](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/tripolar/32/3008_2.png) [@TriPolar](https://boards.straightdope.com/u/TriPolar)\ **Post date:** [April 27, 2012, 8:17pm UTC](https://boards.straightdope.com/t/puzzles-involving-binary-numbers/620168/3 "2012-04-27T20:17:11Z")
Make a type of punched cards out of index cards. Use a reasonable number like 32 cards labeled 0 to 31. Put a set of holes close to the edge of one side of each card with a hole punch. Then use scissors to cut a notch out to the edge where the 0 bits would be. Now take a bicycle spoke (that’s what I used in the 5th grade) to pull a number out. For the binary number 10101 (21 decimal) put the spoke in the first hole (least significant bit) and shake out all the 0 cards and keep the ones on the spoke. Put the spoke in the second hole, shake out the 0 cards and keep those. I’m sure you can figure out the rest of the process to select a specific card. Next, shuffle the cars and sort them. Put the spoke in the first hole, shake out the 0 cards, and put them in front of all the 1 cards left on the stick (keeping the same order for the 0 cards you shake out). Repeat this for the other bits and the cards will be in order when you’re done. This is how data processing was done for decades before computers, and for a couple of decades afterwards as well. ---
**Author:** ![jharvey963](https://avatars.discourse-cdn.com/v4/letter/j/54ee81/32.png) [@jharvey963](https://boards.straightdope.com/u/jharvey963)\ **Post date:** [April 27, 2012, 8:19pm UTC](https://boards.straightdope.com/t/puzzles-involving-binary-numbers/620168/4 "2012-04-27T20:19:16Z")
These aren’t puzzles but are a few binary facts that you may be able to weave in to your teaching. - Every power of 2 number has only ONE ‘1’ bit in its binary representation. E.g., 2 = b’10, 4 = b’100, 8 = b’1000, etc. - Conversely, any number with more than one ‘1’ bit is NOT a power of 2. - Mathematically, you can determine if any number ‘N’ is a power of 2 by using this expression: if ((N & (N - 1)) == 0) then N is a power of 2 (where ‘&’ is the bitwise operator AND). - A 10-bit binary number can represent 0 - 1023. A 20-bit binary number can represent 0 - 1048576. Or loosely, a 10-bit number is about 1000, a 20-bit number is about a million. - Multiplication by 2 is simply adding a ‘0’ to the right side of the number. Or, saying it another way, multiplication by 2 is equal to left-shifting the number by 1. Examples: 5 \* 2 = 10 101 \* 10 = 1010 13 \* 2 = 26 1101 \* 10 = 11010 - Conversely, integer division by 2 just removes one bit from the right hand side. Examples: 12 / 2 = 6 1100 / 10 = 110 19 / 2 = 9 10011 / 10 = 1001 - For multiplying or dividing by powers of 2, just use the “power” as the number of bits to add or remove from the number. Example: 10 \* 8 = 80 1010 \* 1000 = 1010000 j. ---
**Author:** ![PacifistPorcupine](https://avatars.discourse-cdn.com/v4/letter/p/7ea924/32.png) [@PacifistPorcupine](https://boards.straightdope.com/u/PacifistPorcupine)\ **Post date:** [April 27, 2012, 8:37pm UTC](https://boards.straightdope.com/t/puzzles-involving-binary-numbers/620168/5 "2012-04-27T20:37:04Z")
Not so much a puzzle but neat nevertheless. You start with a little triangle formed by 3 1’s. Like so: ```auto 1 1 1 ``` The next row is constructed by binary addition of the two elements above each number. So through 5 rows: ```auto 1 1 1 1 0 1 1 1 1 1 1 0 0 0 1 ``` This is equivalent to evaluating the parity of Pascal’s Triangle. If you do enough rows, you’ll notice a pattern appear, which is the [Sierpinski triangle.](http://en.wikipedia.org/wiki/Sierpinski_triangle) ---
**Author:** ![Thudlow\_Boink](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/thudlow_boink/32/320_2.png) [@Thudlow\_Boink](https://boards.straightdope.com/u/Thudlow_Boink)\ **Post date:** [April 27, 2012, 9:33pm UTC](https://boards.straightdope.com/t/puzzles-involving-binary-numbers/620168/6 "2012-04-27T21:33:17Z")
> [@TriPolar](#): > > Make a type of punched cards out of index cards. Use a reasonable number like 32 cards labeled 0 to 31. Put a set of holes close to the edge of one side of each card with a hole punch. Then use scissors to cut a notch out to the edge where the 0 bits would be. Now take a bicycle spoke (that’s what I used in the 5th grade) to pull a number out. For the binary number 10101 (21 decimal) put the spoke in the first hole (least significant bit) and shake out all the 0 cards and keep the ones on the spoke. Put the spoke in the second hole, shake out the 0 cards and keep those. I’m sure you can figure out the rest of the process to select a specific card. Next, shuffle the cars and sort them. Put the spoke in the first hole, shake out the 0 cards, and put them in front of all the 1 cards left on the stick (keeping the same order for the 0 cards you shake out). Repeat this for the other bits and the cards will be in order when you’re done. This is how data processing was done for decades before computers, and for a couple of decades afterwards as well. I remember reading about this in an article by Martin Gardner. …ah, [here it is!](http://assets.cambridge.org/97805217/56075/excerpt/9780521756075_excerpt.pdf)—complete with illustration. He also describes the old chestnut with “mind-reading cards” (or [“magic age trick” or “magic number trick”](http://www.1728.org/cards.htm)). ---
**Author:** ![TriPolar](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/tripolar/32/3008_2.png) [@TriPolar](https://boards.straightdope.com/u/TriPolar)\ **Post date:** [April 27, 2012, 10:00pm UTC](https://boards.straightdope.com/t/puzzles-involving-binary-numbers/620168/7 "2012-04-27T22:00:29Z")
> [@Thudlow\_Boink](#): > > I remember reading about this in an article by Martin Gardner. > > …ah, [here it is!](http://assets.cambridge.org/97805217/56075/excerpt/9780521756075_excerpt.pdf)—complete with illustration. > > He also describes the old chestnut with “mind-reading cards” (or [“magic age trick” or “magic number trick”](http://www.1728.org/cards.htm)). Hey that’s something, I had Martin Gardner beat by 20 years! But actually I think I read about this in Boy’s Life as a magic trick. I didn’t really understand the principles in the 5th grade. Later when I has to use punched sorters I realized what it was. I used to give an introduction to computers to high school students, back when understanding binary was important. This was a simple way to demonstrate some of the rudimentary things computers do, and how binary numbers fit into that scheme. Anyway,\*\* Left Hand\*\*, I hope you use this. It’s got the hands on quality and the entertainment value that might get them interested. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [April 27, 2012, 11:39pm UTC](https://boards.straightdope.com/t/puzzles-involving-binary-numbers/620168/8 "2012-04-27T23:39:00Z")
Teach them to count to 1023 on their fingers. ---
**Author:** ![newme](https://avatars.discourse-cdn.com/v4/letter/n/e0b2c6/32.png) [@newme](https://boards.straightdope.com/u/newme)\ **Post date:** [April 28, 2012, 12:38am UTC](https://boards.straightdope.com/t/puzzles-involving-binary-numbers/620168/9 "2012-04-28T00:38:02Z")
> [@ultrafilter](#): > > Teach them to count to 1023 on their fingers. You’re going to get in trouble when they get to 4, 128, and 132. ---
**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:** [April 28, 2012, 2:53am UTC](https://boards.straightdope.com/t/puzzles-involving-binary-numbers/620168/10 "2012-04-28T02:53:42Z")
Waste a day letting the kids play [Nim](http://en.wikipedia.org/wiki/Nim). Then show them how to find winning moves by writing the numbers in binary. ---
**Author:** ![Shalmanese](https://avatars.discourse-cdn.com/v4/letter/s/45deac/32.png) [@Shalmanese](https://boards.straightdope.com/u/Shalmanese)\ **Post date:** [April 28, 2012, 3:48am UTC](https://boards.straightdope.com/t/puzzles-involving-binary-numbers/620168/11 "2012-04-28T03:48:06Z")
Towers of Hanoi require 2^n-1 moves for n rings. Have them solve a 3 or 4 ring puzzle then ask them to guess how long it would take to solve a 10 ring or 20 ring puzzle. ---
**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:** [April 30, 2012, 12:47am UTC](https://boards.straightdope.com/t/puzzles-involving-binary-numbers/620168/12 "2012-04-30T00:47:37Z")
Dangit, my post was eaten. I think I’m actually going to take this in a slightly different, Nim-influenced direction, as all these very cool ideas are something I’m having trouble understanding, much less feeling confident about teaching to third-graders. I’m going to teach them about solvable games, starting with tic-tac-toe, and then moving into “100” (each player adds a number between 1 and 10 to a running total; the player that can say “100” wins), and have them work toward a solution for the game. ---
**Author:** ![from\_a\_to\_z](https://avatars.discourse-cdn.com/v4/letter/f/5fc32e/32.png) [@from\_a\_to\_z](https://boards.straightdope.com/u/from_a_to_z)\ **Post date:** [April 30, 2012, 2:03pm UTC](https://boards.straightdope.com/t/puzzles-involving-binary-numbers/620168/13 "2012-04-30T14:03:48Z")
> [@Left\_Hand\_of\_Dorkness](#): > > …Here’s my last example, a puzzle from Car Talk some years ago that I finally solved when I thought of using binary… The Car Talk puzzle could be this one from May 2004: [In Search of the Bogus Coins](http://cars.cartalk.com/content/puzzler/transcripts/200419/index.html), a key part being “If one coin in the stack is counterfeit, they’re all counterfeit”. ([2004 list of puzzles](http://www.cartalk.com/content/puzzlers/2004).) ---
**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:** [April 30, 2012, 3:57pm UTC](https://boards.straightdope.com/t/puzzles-involving-binary-numbers/620168/14 "2012-04-30T15:57:23Z")
> [@from\_a\_to\_z](#): > > The Car Talk puzzle could be this one from May 2004: [In Search of the Bogus Coins](http://cars.cartalk.com/content/puzzler/transcripts/200419/index.html), a key part being “If one coin in the stack is counterfeit, they’re all counterfeit”. ([2004 list of puzzles](http://www.cartalk.com/content/puzzlers/2004).) That’s the one, and yes, when I say “one or more rolls of counterfeit coins,” I definitely mean that each roll contains either real coins or counterfeit coins but not both. I played “Race to 100” today with them, and several of them almost instantly realized that you’d win the game if you said “89” (I said it during the example game I played with them–what can I say, I’m competitive), but nobody was able to backtrack from there to a perfect starting strategy. We’ll do that tomorrow, and then I might introduce Nim. ---
**Author:** ![Ximenean](https://avatars.discourse-cdn.com/v4/letter/x/aca169/32.png) [@Ximenean](https://boards.straightdope.com/u/Ximenean)\ **Post date:** [April 30, 2012, 5:31pm UTC](https://boards.straightdope.com/t/puzzles-involving-binary-numbers/620168/15 "2012-04-30T17:31:40Z")
Couldn’t you take this many coins, say, from each pile: 1, 3, 5, 13, 25, 49, 97 ? ---
**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:** [April 30, 2012, 7:06pm UTC](https://boards.straightdope.com/t/puzzles-involving-binary-numbers/620168/16 "2012-04-30T19:06:07Z")
> [@Ximenean](#): > > Couldn’t you take this many coins, say, from each pile: 1, 3, 5, 13, 25, 49, 97 ? Looks good to me, but you took more than you have to. The binary solution is elegant for a couple of reasons: it’s the fewest possible coins to weigh, and it gives you the answer in a number that, converted to binary, tells you the number of the coin roll at fault. But yeah, as long as you’re sure that each number is at least double the previous number, you’ll have a workable solution. ---
**Author:** ![amarinth](https://avatars.discourse-cdn.com/v4/letter/a/3be4f8/32.png) [@amarinth](https://boards.straightdope.com/u/amarinth)\ **Post date:** [April 30, 2012, 7:15pm UTC](https://boards.straightdope.com/t/puzzles-involving-binary-numbers/620168/17 "2012-04-30T19:15:18Z")
I remember doing the thing **PacifistPorcupine** mentioned on diamond shaped graph paper with various bases (not just binary) and then coloring in the numbers (all the 0s would be red, all the 1s blue) so that you could see the pattern. And Towers of Hanoi & Nim, too. ---
**Author:** ![si\_blakely](https://avatars.discourse-cdn.com/v4/letter/s/d9b06d/32.png) [@si\_blakely](https://boards.straightdope.com/u/si_blakely)\ **Post date:** [April 30, 2012, 7:44pm UTC](https://boards.straightdope.com/t/puzzles-involving-binary-numbers/620168/18 "2012-04-30T19:44:38Z")
> [@newme](#): > > You’re going to get in trouble when they get to 4, 128, and 132. Don’t forget 6, 384 and 390 for British students. 😉 ---
**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, 10:04pm UTC](https://boards.straightdope.com/t/puzzles-involving-binary-numbers/620168/19 "2012-04-30T22:04:13Z")
There’s a simple paper-and-pencil game called the “X Game”. It starts with various number of Xs written in rows. Two players take turns erasing Xs, and can erase as many as they want, but only from a single row and they must erase at least one X. The player who erases the last X wins. The trick is to convert the number of Xs in each row to binary numbers. You then want to erase Xs to make the number of 1s in each place even. For example, a typical starting grid is: ```auto X XXX XXXXX XXXXXXX ``` With the binary: ```auto X 1 XXX 11 XXXXX 101 XXXXXXX 111 ``` That’s already perfect: 2 1s in the fours place, 2 in the twos place, and 4 in the ones place. So, there’s no proper starting move … and you try not to go first. Your opponent does and it becomes, say: ```auto X 1 XXX 11 XXXXX 101 XXX 11 ``` The (unique) proper counter move is: ```auto X 1 XXX 11 X 1 XXX 11 ``` As long as you always end with an even number of 1s at each place, you will guarantee your win. ---
**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:** [April 30, 2012, 10:36pm UTC](https://boards.straightdope.com/t/puzzles-involving-binary-numbers/620168/20 "2012-04-30T22:36:48Z")
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). [Next page](https://boards.straightdope.com/t/puzzles-involving-binary-numbers/620168.md?page=2)