Logic Puzzles

Today we worked on a puzzle Renata found in The Man Who Counted. Then I introduced some logic puzzles written by Charles Lutwidge Dodgson, better known as Lewis Carroll. Some of the puzzles may be found here.

Fibonacci Nim

Last week we started playing a game that starts out with two players and a pile of stones. The players take turns taking away handfuls of stones, and whoever takes the last stone wins. The first player may take as many stones as they like, but not the whole pile. After that first move, each player may take up to twice as many stones as the last person took. Passing is not allowed.

A sample game might go like this: we start out with 10 stones. Player A takes 2 stones, leaving 8. Player B may take up to 4 stones, but decides to take only 3, leaving 5. Player A may now take up to 6 stones, so Player A takes the remaining 5 and wins the game.

Depending on the number of stones in the initial pile, either Player A can always win if they play brilliantly enough, or Player B can always win if they play brilliantly enough. After the kids figured out who should win depending on the number of stones, I revealed that the name of the game is Fibonacci Nim.

I won't say more than that, in case someone wants to play you in this game!

Partitions

Today I visited Elaine's class and introduced the kids to partitions. A partition is a way of breaking up a number into a sum of numbers. For example, we can partition 3 in three different ways:

3=3+0

3=2+1

3=1+1+1.

In order to make things fun, we partitioned groups of kids. To partition the number 3, we had a group of 3 kids stand holding hands, and the other kids rearranged those 3 into a pair and a single, or three singles. We got all the way up to partitions of 6!

See Elaine's post for pictures!

Modular Origami and Fibonacci Numbers

On Monday, Renata was out sick and I got to do math all by myself. First we worked in Singapore books, then we did modular origami. I taught those who hadn't learned yet how to make a Sonobe unit (less technically known as a "box side"). Six units can be assembled to make a cube. More units can be assembled to make other things.

We also made sure everyone was familiar with the Fibonacci sequence, which is the sequence of numbers

1,1,2,3,5,8,13,21,34,55,89,...

The first two numbers are predetermined. To get each number from the third number on, we add the previous two numbers. The next number if we continue the sequence above would be

55+89 = 144.

Today, Tuesday, we reviewed how to write numbers in base 3. It can be helpful to break the numbers up first - for example, to write 17 in base 3, first we notice that

17=9+6+2

and then we can write 17 in base 3 as

122.

We also broke numbers up into sums of Fibonacci numbers. The rules:

• Use the biggest Fibonacci numbers you can
• No Fibonacci number may be used more than once.

Some examples:

11=8+3

12=8+3+1

40=34+5+1

We wouldn't write 40=34+3+2+1, because we can write 5 instead of 3+2, and the first rule says we should use the biggest Fibonacci numbers we can. We also wouldn't write 12=8+2+2, because we're not allowed to use any Fibonacci number more than once.

The kids also came up with their own Fibonacci-type sequences, by deciding what they wanted the first two numbers to be, adding those to get the third number, and so on.

Here they are writing their sequences up on the board:

And here are the completed sequences:

Finally, here's Maria's origami "other thing," using 12 units:

Beyond Base 10

This week we looked at numbers written in different bases.

We usually write numbers in base 10. In base 10, the string of digits

321

represents the sum of 3 hundreds, 2 tens, and 1 one. In base 10 the places are

..., ten thousands, thousands, hundreds, tens, ones.

Another way to say this is that the places are powers of ten:

..., 10^4, 10^3, 10^2, 10^1, 10^0.

We could also write numbers in base 2, in which case we're only allowed to use the digits 0 and 1. The places in base 2 are powers of two instead of powers of ten:

..., 2^4, 2^3, 2^2, 2^1, 2^0

or in other words,

..., sixteens, eights, fours, twos, ones

In base 2, the string of digits

1101

represents the sum of 1 eight, 1 four, 0 twos, and 1 one for a total of thirteen.

We could also write numbers in base 3, or base 4, or any base we like. Computers use base 2 a lot. They also use base 16, better known as hexadecimal. In base 16 we use the digits from 0 to 9, but we also use letters:

10 A

11 B

12 C

13 D

14 E

15 F

The place values in hexadecimal are powers of 16:

..., 4096, 256, 16, 1

Thus the string

10AF

represents the sum of 1 four-thousand ninety-six, 0 two-hundred fifty-sixes, 10 sixteens, and 15 ones for a total of 4271.

The class solved the following puzzle:

If only you, I, and DEAD people know hexadecimal, how many people know hexadecimal?

Cryptology

In December we studied codes and properties of the English language. The kids worked in two "competing" groups.

Group 1 came up with this message:

HI STANLEY I LIKE PIZZA THIS CODE IS EASY.

They encoded their message with the classic Caesar Cipher (where each letter is shifted 3, so instead of A we write D, instead of B we write E, and so on). The coded message was:

KL VWDQOHB L OLNH SLCCD WKLV FRGH LV HDVB.

Group 2 broke the code by recognizing that "HI" is a very good word for starting a message, and then seeing that the whole alphabet had been shifted by three characters.

Then Group 2 came up with a message:

HELLO PEOPLE OF EARTH,

THE SKELETAL DEVIL HAS COME OUT OF THE EARTH, FOR I PROSPERO THE MAGICIAN HAVE LET HIM OUT! FOR LUNCH.

P.S. HE WANTS TO EAT YOU ALL.

They encoded this by a random letter substitution, so the coded message was

WEUUI NEINUE IX EGHVW,

VWE YLEUEVGU TERBU WGY QIDE IFV IX VWE EGHVW XIH B NHIYNEHI VWE DGPBQBGZ WGRE UEV WBD IFV XIH UFZQW NY WE KGZVY VI EGV OIF GUU!

Group 1 broke the code using some useful properties of the English language. They knew B should mean either A or I, since those are the only valid one-letter words in English. They also figured out that VWE was THE, since THE is one of the most commonly occurring three-letter words in English. Since the alphabet was all mixed up instead of shifted, this code was pretty tricky to break.

Along the way, I had the kids pick storybooks they were reading and count how many times different letters occurred. This gave everyone a feeling for how common different letters are. For example, T and E show up all the time, but J and Z and Q hardly show up at all. This can be useful in cracking a code - the most frequently occurring symbol probably doesn't mean Z, unless the message is about pizza!