EB: Cryptology

The first class we learned about the Caesar Cipher and other shift ciphers, as well as learning some useful cryptology words.

• Plaintext - the meaningful English message
• Ciphertext - what you actually send; the secret coded message
• Encrypt - turn the plaintext into ciphertext
• Decrypt - turn the ciphertext back into plaintext

The students paired off and sent their partners encrypted messages to decrypt.

Today I gave the class several encrypted messages to break, of increasing degrees of difficulty. We worked them all out on the board. It was helpful that I forgot what the plaintext messages were!

Here's the first one:

MJQQT, HQFXX.

HTSLWFYZQFYNTSX TS GWJFPNSL YMNX HNUMJW!

- OJXXJ

This one is pretty easy. It looks like a letter, and I wrote it, so "OJXXJ" stands for "JESSE." The first word, "MJQQT," is "HELLO." Since I used a shift cipher, the rest follows from there.

For the next message, I didn't give them any helpful formatting.

KXNDRSCYXOKVCYFOBIXSMO

The most common English letter is "E," and the most common characters in this ciphertext are "X" and "O." I was still using a shift cipher, so there were really only two things to try. That didn't take long either.

Then, since they kept breaking my shift ciphers, I changed to a cipher that randomly mixed up the letters. I did give them back the formatting, though - I didn't want it to be impossible (or take more than the hour-long class)!

VCPT PT E DPYYRHRNV VMSR FY ZFDR

The letter "E" in the ciphertext is a one-letter word, so it must be either "I" or "A" (assuming I'm using grammatical English!). The class went with "A".

Then the two-letter words in the ciphertext, "PT" and "FY," must translate to two-letter English words that don't contain the letter "A." Also, the two-letter word "PT" is the second half of the four-letter word "VCPT." It was agreed that "THIS IS" was a reasonable guess at those first two words.

From there, they got the answer!

The picture shows, from left to right:

• The ciphertext-to-plaintext translation (we used this more for the first two puzzles)
• The ciphertext, with plaintext underneath
• A list of common 2-letter English words

More Killer Sudoku

Yesterday and today we worked on this puzzle. Renata and I were impressed with how well everyone worked on it - almost every moment was full of raised hands and kids saying "I know something!" We finished before the end of class!

Origami and Pascal's Triangle

The first quarter of April was spring break, and we haven't had time to do a whole lot since then. We've made some neat origami vases and boxes. The vase required folding the paper exactly in thirds, so we had to figure out how to do that (Google "origami thirds" and you'll find several different ways).

We also did a little more stuff with Pascal's Triangle. If we left-justify all the numbers, we get a staircase instead of a pyramid:

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

If we sum the numbers in each row, we get doubles:

Sum

1 1

1 1 2

1 2 1 4

1 3 3 1 8

1 4 6 4 1 16

1 5 10 10 5 1 32

If we sum the numbers on each finite diagonal, we get the Fibonacci numbers. I think this is really cool.

Sum

1 1

1 1 1

2 1 2 1

3 1 3 3 1

5 1 4 6 4 1

8 1 5 10 10 5 1

Pascal's Triangle and Tetrahedrons

Here's Pascal's Triangle as we left it yesterday. Comparing to the one I posted yesterday, it looks like we made a few mistakes in the bottom two rows. Oops! I think the infinity signs on the right are there to show that the triangle can keep going on and on forever.

Today we started with square numbers, so called because they're the numbers of dots you can arrange into squares of increasing sizes (see upper right corner of chalkboard). There are also "triangular numbers," which are the numbers of dots you can arrange into equilateral triangles of increasing sizes (see middle right chalkboard).

The diagonal of Pascal's triangle that contains the numbers 1, 3, 6, 10, 15, etc. consists of the triangular numbers.

Pascal's triangle also contains "tetrahedral numbers." To make sense of this we had to know what a tetrahedron is. First we tried to make one out of ourselves:

Since our building pieces (the kids) were different heights, this didn't exactly work. I started to build a tetrahedron using pencils, and then the kids brought out the zometools. I had never played with these before. Now I want buckets of zometools. So much fun!

We all built tetrahedra, myself included.

Lydia built a tetrahedron tree.

Saul made a very large tetrahedron and filled it with the little white zomespheres. This is where the "tetrahedral numbers" come in - by counting up the number of spheres it takes to make tetrahedra of increasing sizes.

He very kindly let Noah put on the last one:

The tetrahedral numbers are 1, 4, 10, ... which just happen to be the next diagonal in Pascal's Triangle. We have the natural numbers, the triangular numbers, and the tetrahedral numbers:

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

1 7 21 35 35 21 7 1

1 8 28 56 70 56 28 8 1

1 9 36 84 126 126 84 36 9 1

1 10 45 120 210 252 210 120 45 10 1

1 11 55 165 330 462 462 300 165 55 11

When Saul counted up all the zomespheres he stacked inside his tetrahedron, he got 165, which is indeed one of the tetrahedral numbers. No zomespheres were lost in the counting of this tetrahedral number.

Patterns in Pascal's Triangle

Today we got all the way to row 14. The very first row, the point of the triangle that only has one number, is row zero.

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

1 7 21 35 35 21 7 1

1 8 28 56 70 56 28 8 1

1 9 36 84 126 126 84 36 9 1

1 10 45 120 210 252 210 120 45 10 1

1 11 55 165 330 462 462 300 165 55 11 1

1 12 66 220 495 792 924 792 495 220 66 12 1

1 13 78 186 715 1287 1716 1716 1287 715 186 78 13 1

1 14 91 264 901 2002 3003 3432 3003 2002 901 264 91 14 1

We expanded on some of the patterns from yesterday and found new patterns. I was very impressed with the pattern-finding. Here are some of the patterns.

The numbers in the second diagonal go up by 1 each time:

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

1 7 21 35 35 21 7 1

1 8 28 56 70 56 28 8 1

1 9 36 84 126 126 84 36 9 1

The numbers in the next diagonal go up by 2, then 3, then 4, then 5, etc.

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

1 7 21 35 35 21 7 1

1 8 28 56 70 56 28 8 1

1 9 36 84 126 126 84 36 9 1

The numbers in the next diagonal go up by 3, then 6, then 10, then 15, etc.:

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

1 7 21 35 35 21 7 1

1 8 28 56 70 56 28 8 1

1 9 36 84 126 126 84 36 9 1

The numbers in row 7, except for the outer 1's, are all multiples of 7. I added that this is true for any prime number row: all the numbers in that row, except the outer 1's, will be multiples of the prime.

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

1 7 21 35 35 21 7 1

1 8 28 56 70 56 28 8 1

1 9 36 84 126 126 84 36 9 1

1 10 45 120 210 252 210 120 45 10 1

1 11 55 165 330 462 462 300 165 55 11 1

1 12 66 220 495 792 924 792 495 220 66 12 1

1 13 78 186 715 1287 1716 1716 1287 715 186 78 13 1

1 14 91 264 901 2002 3003 3432 3003 2002 901 264 91 14 1

Row 0 has 1 number, the next row has 2 numbers, the next row has 3 numbers, etc.:

1 - 1 number

1 1 - 2 numbers

1 2 1 - 3 numbers

1 3 3 1 - 4 numbers

Only even-number rows have a middle number (this is because we can split an even number in half, but we can't split an odd number in half).

In even-number rows the "choose 2" number is a multiple of half the row number. In row 4 the number 4C2=6 is a multiple of 2, in row 6 the number 6C2=15 is a multiple of 3, in row 8 the number 8C2=28 is a multiple of 4, etc:

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

1 7 21 35 35 21 7 1

1 8 28 56 70 56 28 8 1

1 9 36 84 126 126 84 36 9 1

1 10 45 120 210 252 210 120 45 10 1

1 11 55 165 330 462 462 300 165 55 11 1

1 12 66 220 495 792 924 792 495 220 66 12 1

1 13 78 186 715 1287 1716 1716 1287 715 186 78 13 1

1 14 91 264 901 2002 3003 3432 3003 2002 901 264 91 14 1

The other numbers in that diagonal, on the odd-number rows, are special for a different reason:

3*1=3

5*2=10

7*3=21

9*4=36

etc.

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

1 7 21 35 35 21 7 1

1 8 28 56 70 56 28 8 1

1 9 36 84 126 126 84 36 9 1

1 10 45 120 210 252 210 120 45 10 1

1 11 55 165 330 462 462 300 165 55 11 1

1 12 66 220 495 792 924 792 495 220 66 12 1

1 13 78 186 715 1287 1716 1716 1287 715 186 78 13 1

1 14 91 264 901 2002 3003 3432 3003 2002 901 264 91 14 1

Counting Part 3: Buttons

Buttons (The Big Group)

Take 5 buttons: red, white, green, yellow, and purple. How many ways are there to choose 1 button from those 5? 5, of course.

How many ways are there to choose 2 buttons of different colors? The class agreed that order didn't matter - choosing red and white was the same thing as choosing white and red. The students found 10 ways to choose 2 buttons from 5.

We started in with the mathematical notation. The mathematical notation for "the number of ways to choose 2 things from 5" is 5C2. So we found

5C1=5

5C2=10

The most prevalent guess was that 5C3 would be 15, but it turned out that 5C3=10.

We found that 5C4=5, because choosing 4 buttons is the same as choosing 1 button to exclude. Here's what the board looked like after we figured all this out and started discussing what would happen if we started with 6 buttons:

The next day we continued finding 6C0, 6C2, ... , 6C6. Then we went back and started with 0C0. There's only one way to not take any buttons, which is to not take any. So

0C0=1

If we start with 1 button, we get

1C0=1, 1C1=1

With 2 buttons,

2C0=1, 2C1=2, 2C2=1

With 3 buttons,

3C0=1, 3C1=3, 3C2=3, 3C3=1

We continued down to row 6, and got the following pretty picture:

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

This is a very famous creature called "Pascal's Triangle." To get each number for the next row, you add up the two numbers above it. For example, 5+10=15:

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

On their own, each kid completed the triangle up to row 10 and looked for patterns. Some student observations:

• All the numbers in row 7 (except 1) are multiples of 7:

1 7 21 35 35 21 7 1

• All the numbers along the outside of the triangle are 1.
• The numbers that aren't quite along the outside go up by 1 each time:

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

• To fill in the triangle, you only have to find half of a row because the second half mirrors the first:

1 6 15 20 15 6 1

• In rows that have a "middle number," the middle number is always even:

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

Counting Part 2: Poker

Poker (The Small Group)

The first question: How many possible poker hands are there?

After playing around with 2- and 3- card hands, which are easier to think about, they arrived at their first answer:

52*51*50*49*48.

This is a good start, but it's assuming order matters, and thus is counting each hand more than once. Order doesn't matter in poker, because whether you have 2-3-4-5-5 or 2-5-5-4-3, it's the same poker hand. Each 5-card hand gets counted 5*4*3*2*1 times, so the real answer is

(52*51*50*49*48)/(5*4*3*2*1)=2,598,960

possible poker hands.

Then we figured out how many ways there were to get various hands. There are only 4 ways to get a a royal flush, which means the probability of getting a royal flush is

(4)/(2598960) ~=~ .0000015

A straight flush that isn't also a royal flush can start on A, 2, 3, 4, 5, 6, 7, 8, or 9, so there are 9 ways per suit for a total of 36 ways to get a royal flush. The probability of getting a straight flush is

(36)/(2598960) ~=~ .000014

These hands are not very likely!

It's harder to figure out how many ways there are to get one pair. There are 13 choices of what the pair will be (A through K). Suppose we have a pair of aces. There are 6 different ways to choose a pair of aces from the 4 aces in the deck. Then we have to fill in the other 3 cards in the hand.

A-A-_-_-_

Since the third card can't be an ace (or we wouldn't have one pair), there are 48 choices for the third card. The fourth card can't be an ace, and also can't be whatever we picked for the third card, so there are 44 choices. The fifth card can't be an ace, the same as the third card, or the same as the fourth card, so there are 40 choices for the fifth card.

To make sure we aren't over-counting those last three cards, we need to divide by 6 (the number of ways to order those cards). This gives us

(13*6*48*44*40)/6 = 1,098,240

ways to get a single pair. The probability of getting a single pair in a five-card poker hand is

1,098,240 / 2,598,960 ~=~ .42

After figuring all this out, we spent a couple of days playing poker and tallying up the hands we got to see if they looked like we expected they would. There were lots of single pairs, as expected, with a scattering of two pair and three of a kind. I got lots of junk hands, which the kids found very amusing.

We played with buttons, starting with 20 buttons each. I pointed out to the loser of the first game that if we had been using real money, he would have just lost $20 in half an hour. He replied that he wasn't going to gamble with real money. :)

Here's a site that explains how to calculate odds for various poker hands.