The Surprise Test Paradox

As promised, today’s blog post is about the Surprise Test Paradox. A quick recap:

On Friday, a teacher says to their class that on some day during the next week, there will be a surprise test. However, the students make the following deductions:

The teacher can’t wait until next Friday, otherwise the test won’t be unexpected, so a Friday test is impossible.
Having eliminated Friday, Thursday is now the last possible day for the test to occur.
Rinse and repeat. We eliminate all possible days of the week, so a surprise test is impossible!

However, the teacher sets a test on Wednesday, to the surprise of all the students.

Why did I put off this blog post, promising to talk about it some time before the New Year? To illustrate the paradox for real. Despite any readers of this blog being able to follow the same logic as the students, you had no idea when I was going to make this post. So is there a problem with the above logic?

What follows is heavily inspired by an excellent article written by Timothy Chow.

Essence of the Paradox

Here are a few observations which try capture some subtleties in the premise of the paradox.

In the story, the teacher sets the test on Wednesday. The choice of Wednesday isn’t important at all. Indeed, as soon as the students had convinced themselves that there would be no test, the teacher would have been able to surprise them on any day of the week. This doesn’t resolve the situation, in that it doesn’t find a flaw in the reasoning process. In fact, it’s wholly unsatisfactory. The correct reasoning of the students convinces them that no surprise is possible, which makes a surprise possible, somehow rendering their correct conclusion incorrect…

What the last paragraph does usefully illustrate is that ‘surprise’ might depend on all kinds of things, like the students’ current states of reasoning, as well as their knowledge of the teacher’s announcement. Surprise and knowledge are very vague and tricky concepts to try and pin down logically.

For example, we can blame the teacher for announcing the test to begin with. The implicit Step 0 in the student’s reasoning is their knowledge that a test will occur (even more than this, their trust in the teacher’s announcement).

The students’ argument also uses the fact that there is a ‘final day’ on which the surprise test can happen. If the teacher had merely promised them a surprise test in the future, there would be no paradox. Their reasoning would not make it past Step 1.

Resolution?

Two essential features of the paradox are the announcement of the test, and the fact that there is a “final day”. So let’s consider the simplest possible case (in fact, this is the case that the students arrive at):

On Friday, the teacher announces “There will be a surprise test on Monday!”

Of course, this statement is badly written. Most humans would probably now interpret the “surprise” as pertaining to the content or length of the test, rather than the day on which it was to be held, since the teacher has stated this. Slightly better:

On Friday, the teacher announces “There will be test on Monday. On Monday, the timing of the test will come as a surprise to you!”

Taken in the context of the original paradox, this statement is clearly absurd. It seems as though the teacher is at fault for giving the students a contradictory statement. We could say the same for the original. A precise way of reformulating the teacher’s announcement is:

On Friday, the teacher announces “There will be a test next week. It is not possible to deduce the day of the test from this announcement”

Self-reference. The teacher might as well have said “This is not an announcement”. Actually, you can go through the formal steps as Chow does, and phrase even this self-referential statement mathematically using Godel numbering and such things. The conclusion is still that the announcement is contradictary.

Conclusion

The self-reference argument is just about good enough for me. Reformulating the announcement seemed to clear things up quite a lot. But unfortunately, the teacher’s statement is justified undeniably after the fact, logically ridiculous until it comes true. Isn’t this as bad as our observation before, with the correct reasoning of the students becoming incorrect only later?

There is no universally accepted resolution to the surprise test paradox. But that’s the one that I like the best.

26

Posted by maycontainmaths

Here’s a fun fact. 26 is the only integer that is sandwiched directly above a square number, and below a cube number. How do we know that this is the only one? Let’s find out…

We’ll try to find integers $n$ that satisfy the same conditions:

$n$ is one bigger than a square, i.e. $n = x^2 + 1$ for an integer $x$
$n$ is one less than a cube, i.e. $n = y^3 - 1$ for an integer $y$

Actually, now that we have these, we might as well eliminate $n$ completely to get a single equation. What we want are integers $x$ and $y$ that satisfy $y^3 = x^2 + 2$ .

The next step is to factorise the right hand side:

$y^3 = (x+\sqrt{-2})(x-\sqrt{-2})$

But what next? Write $\mathbb{Z}[\sqrt{-2}]$ for the collection of numbers of the form $a+b\sqrt{-2}$ where $a$ and $b$ are integers. Now, $\mathbb{Z}[\sqrt{-2}]$ has the special property that, just like normal integers, there are ‘prime’ numbers, and every number in the collection has a unique factorisation into primes. These ‘primes’ don’t necessarily coincide with the usual prime numbers. For example, $7= (3+\sqrt{-2})(3-\sqrt{-2})$ , so it isn’t a ‘prime’. Click here for more details.

We can show that $\sqrt{-2}$ is a ‘prime’. Suppose $a+b\sqrt{-2}$ divides it, for some integers $a$ and $b$ . Let’s take a look at the absolute values of these as complex numbers. It’s a fact that $|z||w| = |zw|$ for any complex numbers $z$ and $w$ . So we get that $|a+b\sqrt{-2}|^2 = a^2+2b^2$ divides $2=|\sqrt{-2}|^2$ . Now clearly neither $a$ nor $b$ can be very big, otherwise $a^2+2b^2$ is bigger than 2. The only options are $b = 1,-1$ with $a=0$ , and $b=0$ with $a=1,-1$ , meaning $\sqrt{-2}$ only factorises as $\sqrt{-2} \times 1$ or $-\sqrt{-2} \times -1$ . Compare this with the usual prime numbers! Similarly, $-\sqrt{-2}$ is also ‘prime’.

Now, say some ‘prime’ $p+q\sqrt{-2}$ divides both of $x-\sqrt{-2}$ and $x+\sqrt{-2}$ . Then it divides the difference of the two, $-2\sqrt{-2} = (\sqrt{-2})^3$ . Since we have unique factorisation into ‘primes’, $p+q\sqrt{-2}$ must be equal to $\sqrt{-2}$ or $-\sqrt{-2}$ .

Apart from these, any other ‘primes’ $p+q\sqrt{-2}$ that divide $x+\sqrt{-2}$ don’t divide $x-\sqrt{-2}$ . Note that if this is the case, then $p+q\sqrt{-2}$ divides $y^3$ , and hence $y$, in our original equation. Then, this means that since we have $y^3$ on the left hand side, $p+q\sqrt{-2}$ divides the right hand side 3 times. It doesn’t divide $x-\sqrt{-2}$ , so it divides $x+\sqrt{-2}$ three times.

The result is that $x+\sqrt{-2}=(\sqrt{-2})^k (a+b\sqrt{-2})^3$ , with $k = 0,1$ or 2 (if $k$ is 3 or more, we just absorb some of the $\sqrt{-2}$ into the second bit of the expression).

We’re almost there! If we expand the brackets, $(a+b\sqrt{-2})^3 = a^3 - 6ab^2 + (3a^2 b - 2b^3)\sqrt{-2}$ .

If $k=2$ , then we find that $-6a^2 b +4b^3 = 1$ by looking at the coefficient of $\sqrt{-2}$ . But this is absurd since it would mean that 2 divides 1.

If $k=1$ , then this time, we find that $a^3 - 6ab^2=1$ . Then $a$ divides 1, so $a$ is 1 or $-1$ . This means that $1-6b^2$ is 1 or $-1$ , so the only integer solution is when $b=0$ . But this leads to $x=0$ , which does not give a solution to our original equation.

If $k=0$ , then we find that $3a^2 b -2b^3 = 1$ . Then $b$ divides 1, so $b$ is 1 or $-1$ . Therefore, $3a^2 - 2$ is equal to 1 or $-1$ . The only way this can be satisfied for an integer is if $a$ is also 1 or $-1$ . Now, the value of $x$ is given by the other coefficient, $a^3 - 6ab^2$ , which is 5 or $-5$ . This means that $y^3 = 27$ so $y=3$ .

And of course, this gives $n=26$ .

Egyptian Fractions

Posted by maycontainmaths

These days, most people use fractions and decimals to describe numbers. The Ancient Egyptians liked to use fractions too, but they had some interesting rules about which fractions they could use. When representing a rational number, they wrote it as a sum of fractions, with all of the numerators equal to 1, and all of the denominators different. We now call these Egyptian Fractions.

Take a look at three ways of writing $\frac{3}{4}$ .

$\frac{3}{4} = \frac{2}{3} + \frac{1}{12} \\ = \frac{1}{4} + \frac{1}{4} + \frac{1}{4} \\ = \frac{1}{2} + \frac{1}{4}$

The first way isn’t allowed because one of the numerators is 2. The second way is also wrong because we’ve used 4 as a denominator three times. But the third way is a valid way to write $\frac{3}{4}$ in Egyptian Fractions.

There are often lots of ways to write a number in Egyptian Fractions.

$\frac{3}{4} = \frac{1}{2} + \frac{1}{6} + \frac{1}{12} \\ = \frac{1}{2} + \frac{1}{4} \\ = \frac{1}{2} + \frac{1}{7} + \frac{1}{14} + \frac{1}{28}$

This is in contrast to using normal fractions in lowest terms, and writing numbers using decimals (well, almost).

How to Write in Egyptian Fractions

It can be very easy to spot the correct representation of a number, and there are some tricks which can often help.

For example, suppose that we have some odd integer $n$ and we want to write $\frac{2}{n}$ in Egyptian Fractions. The following equation is true for any number except 0 and 1, so not just for odd $n$ .

$\frac{2}{n} = \frac{2}{n+1} + \frac{2}{n(n+1)}$

How does this help? Well, since $n$ is odd, $n+1$ is even, and so $N = \frac{n+1}{2}$ is also an integer. So what we actually have is

$\frac{2}{n} = \frac{1}{N} + \frac{1}{nN}$

Another way is to look at the largest fraction with numerator one that is less than your number. Then subtract this, and try to express the new number in Egyptian Fractions.

$\frac{71}{72} = \frac{1}{2} + \frac{35}{72} = \frac{1}{2} + \frac{1}{3} + \frac{11}{72}$

$= \frac{1}{2} + \frac{1}{3} + \frac{1}{9} + \frac{1}{24}$

Actually, this method always leads to an Egyptian Fraction representation of any positive rational number. To see why, we need to write things a little more abstractly. The function $\lceil \cdot \rceil$ rounds up to the next whole number, and mod is described here.

If we’re working with $\frac{x}{y}$ , then the largest fraction with numerator one that is less than this is given by 1 over $\lceil \frac{y}{x} \rceil$ . When we subtract this from $\frac{x}{y}$ , the answer is $\frac{ (-y \mod x)}{y \lceil y/x \rceil}$ . Therefore, this method of writing in Egyptian Fractions will always finish in a finite number of steps, because the numerator of our new fraction is $(-y \mod x)$ , which is strictly less than $x$ , meaning that if we keep going with this method, we will eventually be left with something that has numerator 1.

This doesn’t always give the nicest or shortest representation.

$\frac{587}{1081} = \frac{1}{2} + \frac{1}{46} + \frac{1}{47}$

But using the method above, we get $\frac{587}{1081} = \frac{1}{2} + \frac{1}{24} + \frac{1}{742} + \frac{1}{740402} + \ldots$ . The numbers were getting too small for my calculator to handle, so I didn’t finish it off.

Unfortunately, nobody knows an efficient way of finding the shortest representation of a number in Egyptian Fractions.

Egyptian Fractions and Sharing

Egyptian fractions can sometimes be useful in sharing situations. Imagine that you’re throwing a huge party, and invited 20 tables full of people, with one chocolate cake for each table. However, unable to help yourself, you eat one of the cakes the night before, and are now left with the problem of dividing 19 cakes between 20 tables. The obvious thing to do is to cut $\frac{1}{20}$ out of each cake, but this is very difficult to do.

Fortunately, $\frac{19}{20}$ has a particularly nice Egyptian Fraction representation as $\frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6}$ . Cutting cakes into these small fractions is much easier. All you have to do is give each table a third, quarter, fifth and a sixth of a cake.

The Waiter Paradox

Posted by maycontainmaths

Today, I’ll discuss one of my favourite paradoxes, and unravel it. It’s called the Waiter Paradox.

What is a Paradox?

The dictionary definition says that a paradox is “A seemingly absurd or contradictory statement or proposition which when investigated may prove to be well founded or true”.

The Waiter Paradox

The following is taken from the Paradox section of www.curiouser.co.uk (it’s called the Missing Pound Paradox here, but I always thought that the Waiter Paradox sounded more catchy).

“Three ladies go to a restaurant for a meal. They receive a bill for £30. They each put £10 on the table, which the waiter collects and takes to the till. The cashier informs the waiter that the bill should only have been for £25 and returns £5 to the waiter in £1 coins. On the way back to the table the waiter realises that he cannot divide the coins equally between the ladies.

As they didn’t know the total of the revised bill, he decides to put £2 in his own pocket and give each of the ladies £1.

Now, each of the ladies paid £9. Three times 9 is 27. The waiter has £2 in his pocket. Two plus 27 is £29. The ladies originally handed over £30.

Where is the missing pound?”

Where indeed?

Resolution

The “Paradox” here stems from a misrepresentation of the facts, leading to some bad counting. Let’s do some simple book-keeping.

We’ll call the ladies $L$ , $M$ and $N$ . The waiter will be $W$ and the cashier will be $C$ . The amounts of money held by all parties at any time will be stored like this: $(L,M,N,W,C)$

Ignore all the rest of the money involved, like other money that the ladies and waiter are carrying, and the rest of the money in the cashier’s till. It’s not important because we only want to keep track of £30. At the start, each lady has £10.

$(10,10,10,0,0)$

The waiter collects the money.

$(0,0,0,30,0)$

The cashier takes £25 for the meal and returns £5 to the waiter.

$(0,0,0,5,25)$

The waiter returns £1 to each lady.

$(1,1,1,2,25)$

We started with £30 in circulation and we end this way too. Clearly there’s no missing pound here. So where does the paradox come from? It’s true that each lady paid £9. It’s true that 3 times £9 is £27, and it’s true that the waiter has £2 at the end.

It’s also true that £2 plus £27 is £29, but why are we adding these numbers together? The ladies have paid £27 in total, of which £25 is with the cashier and £2 is with the waiter. So the £2 held by the waiter is already included in the £27. Why would we add it on again? What we should be adding is the money that the ladies have not paid; the £3 that they got back in change. This makes £30. There’s no paradox, just bad book-keeping.

More Paradoxes: The Suprise Test Paradox

On Friday, a teacher says to their class that at some point during the next week, there will be a surprise test. However, the students start thinking about this:

The teacher can’t wait until next Friday for the exam, because then the test won’t be unexpected. So it can’t be Friday.
Since we’ve removed Friday from the possible test days, the same logic applies to Thursday.
By repeating this logic, we removed all the possible test days.
So, it turns out that the teacher can’t give a surprise test at all.

However, the teacher sets a test on Wednesday and all the students are surprised! Teachers can certainly give surprise tests, as anybody who has experienced one will tell you. So where did the students go wrong? The Surprise Test Paradox is subtle and much harder to pin down than it first appears. Have a think about it.

I’d like to take this opportunity to announce that I’ll be writing a surprise blog article on this paradox, at some point before the end of 2014. See you next week!

More paradoxes may be found at http://www.curiouser.co.uk/ and http://www.paradoxes.co.uk/.

Divisibility Tests

Posted by maycontainmaths

Many schoolchildren know a trick for quickly finding out whether a number divides by 3, just by looking at the digits. But not many of them know why, and most adults that I’ve met don’t either! This week, we’ll check out some tests which tell you whether a number divides by another one, and explain why they work.

We’ll start simple and work up to some more complicated ones. We’ll use a number $N$ which has digits $a_n,a_{n-1},\ldots,a_0$ (so the digits are all numbers from 0 to 9, and $N=a_n \times 10^n + a_{n-1} \times 10^{n-1} + \ldots + a_0$ ). The expression $3 \mid N$ means “N divides by 3”.

2 and 5

“But these are easy!”, I hear you cry. Well, yes, it is very easy to tell whether a number is divisible by 2 or 5, but we might as well start at the beginning.

The reason that it’s so easy to tell whether a number is divisible by 2 or 5 is that we usually write numbers in base 10, that is, in units, tens, hundreds, thousands, and so on, using digits 0 to 9. The number 10 factorises into prime numbers 2 and 5. Apart from the units digit, all the other digits of a number represent parts of the number that are divisible by powers of 10, and so these parts are automatically divisible by 2 or 5. Therefore, we only have to check the last digit. A number is divisible by 2 or 5 if, and only if, the last digit is divisible by 2 or 5. For example:

$4376 = 4\times 1000 + 3\times 100 + 7\times 10 + 6$

The first three numbers in the expression above are all divisible by 2 (and 5), so 4376 is divisible by 2 (or 5) if and only if 6 is. So 4376 is divisible by 2 but not 5.

$2 \mid N \leftrightarrow 2\mid a_0$

$5 \mid N \leftrightarrow 5\mid a_0$

This seems obvious, but we can take the idea further.

Powers of 2 and 5

Because 10 is divisible by 2 and 5, this means that 100 ( $=10^2$ ) is divisible by $2^2$ and $5^2$ , and also, 1000 ( $=10^3$ ) is divisible by $2^3$ and $5^3$ , and so on. Using the same idea as above, apart from the last $k$ digits, all the other digits of a number represent parts that are divisible by powers of $=10^k$ , hence automatically by $2^k$ or $5^k$ . Therefore, we only have to check the number formed by the last $k$ digits to see if a number is divisible by $2^k$ or $5^k$ .

$2^k \mid N \leftrightarrow 2^k \mid a_{k-1} \ldots a_0$

$5^k \mid N \leftrightarrow 5^k \mid a_{k-1} \ldots a_0$

3 (and 9)

How about divisibility by 3? The trick here is to take the sum $S$ of the digits. For example:

$4376 = 4\times 1000 + 3\times 100 + 7\times 10 + 6$

$S = 4 + 3 + 7 + 6 = 20$

However:

$4376 = 4\times 1000 + 3\times 100 + 7\times 10 + 6 = 4\times 999 + 3\times 99 + 7\times 9 + S$

From this, it’s easy to see that you can write any number as a sum of many parts that divide by 3 (and 9), plus $S$ . Because 20 doesn’t divide by 3 (or 9), 4376 doesn’t either.

So we discover that $3 \mid N \leftrightarrow 3 \mid S$ and $9 \mid N \leftrightarrow 9 \mid S$ .

Sometimes, for a really big number, the sum of digits might itself by extremely large and it may be difficult to tell immediately if it divides by 3 or 9. But, we can just apply the same idea again: the sum of digits of the sum of digits is divisible by 3 or 9 if and only if the sum of digits is, if and only if the original number was. This can be repeated as many times as necessary until we obtain something manageable.

Divisibility by 11 is a bit similar to 3 and 9, except that this time we take the alternating sum of digits:

$A = a_0 - a_1 + a_2 - \ldots$

Here’s why it works:

$4376 = 4\times 1000 + 3\times 100 + 7\times 10 + 6 = 4\times 1001 + 3\times 99 + 7\times 11 + A$ .

It turns out that the sequences of numbers $11, 1001, 100001,\ldots$ and $99, 9999, 999999,\ldots$ are all divisible by 11 (one easy way to see why is to use modular arithmetic and note that $(10)^n = (-1)^n \mod 10$ ).

This means $11 \mid N \leftrightarrow 11 \mid A$ . As before, we can keep taking the alternating sum again and again until we get a number that is small enough to manage.

Last one:

This looks like a bit of a strange one. We’ll test to see if 23984744 is divisible by 7.

First we split the number into blocks of 3, starting from the right.

$23,984,744$

We then take the alternating sum of these blocks. The W here stands for weird…

$W = 744-984+23 = -217$

Now, since 217 divides by 7, so does 23984744. Looks like magic!

Let’s have a closer look.

$23984744 = 2\times 10^7 + 3\times 10^6 + 9\times 10^5 + 8\times 10^4 + 4\times 10^3 + 7\times 10^2 + 4\times 10 + 4$

$= 2\times 9999990 + 3\times 999999+ 9\times 100100 + 8\times 10010+ 4\times 1001 + A$

So what is going on? It looks like we have two sequences of interesting numbers to look at. We want to look at 1001 from the fourth digit, (we ignore 10010 and 100100 from the fifth and six digits since these are just 10 and 100 times this, not that interesting), 999999 from the seventh digit (again, the eighth and would-be ninth are not that interesting), 1000000001 (from the would-be tenth digit), 999999999999 (from the would be thirteenth digit)…

It turns out that all of these are divisible by 7 (modular arithmetic helps again, $(10)^3 = -1 \mod 7$ and $(10)^6 = 1 \mod 7$ ).

Therefore, $7 \mid N \leftrightarrow 7 \mid W$ .

More Divisibility Rules

With these divisibility rules, alone or in some combination, you should now be able to check, without a calculator and without a very long division, whether a number is divisible by any number from 2 to 12.

We’ve barely scratched the surface of all the weird and wonderful divisibility tests that exist. To have a look at some more, click on this link.

The Infinite Monkey Theorem: Part 2

Posted by maycontainmaths

Last week, we discussed the Infinite Monkey Theorem: given long enough, we can expect monkeys bashing randomly at the keys of typewriters to produce the works of Shakespeare.

But we merely established that we should expect this to happen at some point. How long should we be willing to wait for our monkey slaves to produce results? First, a reminder of our assumptions.

Assumptions

Monkeys press one key (and only one key) on the keyboard every second. They never stop, slow down, or speed up, and they don’t die either.
The typewriters don’t change. They don’t break down or run out of ink.
All of the typewriters have 50 keys. When pressing a key, the monkey is equally likely to select any of the keys on the typewriter, completely independently of what has happened previously.

A Good Guess

All we need to do now is think carefully about how close a monkey is to succeeding at any time, and to carefully find the expected value of the time a monkey will take to succeed. Just like last time, we’ll keep things simple by first considering a single monkey who is trying to type “HAMLET”, which is 6 letters long, and then think about the works of Shakespeare, which might be $N$ letters long (for some pretty huge $N$ !).

The probability that a collection of 6 consecutive letters from the typewrite is “HAMLET” is $(\frac{1}{50})^6$ , so we might expect that after $50^6$ tries goes at typing 6 letters, the monkey succeeds in typing “HAMLET” once. This takes $6\times 50^6$ seconds to type ( $N\times 50^N$ for all of Shakespeare).

In fact, if you think about it, after the monkey has typed $50^6 + 5$ letters, there are $50^6$ lots of 6 consecutive letters (the first 6 letters, the 6 starting from letter 2, the 6 starting from letter 3 and so on). So maybe $50^6 + 5$ seconds is enough ( $50^N + N-1$ for all of Shakespeare).

In any case, it seems like the answer should have something to do with $50^6$ .

Some More Explicit Maths

A diagram will make things much easier to understand. Here it is (click to enlarge):

This diagram represents the monkey’s current progress in typing “HAMLET”. Each stage is represented by a circle, or state, in the diagram. The circle with a dash inside represents no progress at all, while each successive letter shows the monkey getting closer and closer to the goal. For example, having typed “HAMLEX” would put the monkey in the dash state, as it has typed an “X” and lost all progress. If the monkey typed “HAMHAMHAMHAMHAM” then it would be in state M. You get the idea.

The arrows show the possibilities for the monkey as it types the next letter.

Green arrows show the best possible outcome, where the monkey types the next letter correctly. A monkey having typed “ATXKHAML” then “E” would move from the “L” state to the “E” state.
Orange arrows are a bad outcome. The monkey is doing well, but types an “H” incorrectly. This is bad, but not the worst, because at least “H” is the first letter of “HAMLET”, so one letter is done. The monkey moves into state “H”.
Red arrows are the worst outcome. The monkey types an incorrect letter that is not “H” and loses all progress.

The fractions show the probabilities of moving between states along the coloured arrows.

We will write $T_-,T_H,T_A,T_M,T_L,T_E,T_T$ to be the amount of time, in seconds, that we expect it to take for the monkey to succeed from a particular state. Immediately, we can see that $T_T = 0$ since if the monkey reaches this state, it has already succeeded. The answer that we are looking for is $T_-$ .

We can write down another equation for $T_-$ : $T_- = 1 + \frac{49}{50}T_- + \frac{1}{50}T_H$ . We have this equation because from the dash state, the monkey presses another key after one second (giving the 1), then moves into the dash state again with probability $\frac{49}{50}$ and then takes time $T_-$ , or moves into the H state with probability $\frac{1}{50}$ and then takes time $T_H$ .

Intuitively, this equation just says that the time it will take the monkey to finish from the dash state is one second, plus the time it will take the monkey to finish from it’s next state.

There are other equations coming from the other Ts. Here’s the full set:

$T_- = 1 + \frac{49}{50}T_- + \frac{1}{50}T_H$
$T_H = 1 + \frac{48}{50}T_- + \frac{1}{50}T_H + \frac{1}{50}T_A$
$T_A = 1 + \frac{48}{50}T_- + \frac{1}{50}T_H + \frac{1}{50}T_M$
$T_M = 1 + \frac{48}{50}T_- + \frac{1}{50}T_H + \frac{1}{50}T_L$
$T_L = 1 + \frac{48}{50}T_- + \frac{1}{50}T_H + \frac{1}{50}T_E$
$T_E = 1 + \frac{48}{50}T_- + \frac{1}{50}T_H + \frac{1}{50}T_T$
$T_T = 0$

These can be solved without too much difficulty. If you just want to see the answer, skip to the end of the ==== signs.

====Solving Method====

Equation 1 simplifies to $T_- = 50 + T_H$ , or $T_H = T_- - 50$ . Now, we can substitute this value for $T_H$ into equation 2, to get an equation containing only $T_-$ and $T_A$ . You should find that $T_A = T_- - 50^2$ .

Now, we can substitute to get rid of $T_H$ and $T_A$ from equation 3, to get an equation containing only $T_-$ and $T_M$ .

We can do a similar thing with equation 4, getting rid of $T_H$ and $T_M$ to get an equation containing only $T_-$ and $T_L$ . Then we can do a similar thing with equation 5 to get an equation containing only $T_-$ and $T_E$ . You might see a pattern here which lets you guess what the next equation is going to be.

Finally, we deal with equation 6, and get something containing only $T_-$ and $T_T$ . But we know that $T_T$ , so we can now find the value of $T_-$ .

=====================

It turns out that we get $T_- = 50^6$ seconds (roughly 495 years!) which is in line with our guesses. If you think about a longer text, the structure of the equations we get doesn’t really change (although we have more of them) and the answer has exactly the same form. If the works of Shakespeare are $N$ characters long, then we would expect a monkey to take $50^N$ seconds to bash them out randomly on a typewriter. I’d find an actual number for N, but even if we just take a single play, the numbers are a bit big for my calculator or computer to handle. In any case, trying to get a monkey to produce a novel for you in this way is a no-go.

Many Monkeys and Final Thoughts

We worked out a length of time for a single monkey. What happens if more than one monkey is used? Well, thinking about monkeys as random typing machines as we have before, the monkeys should have no effect on each other, so we still expect each individual monkey to take $50^N$ seconds as before. However, if we had $50^N$ monkeys, and came to see what they had produced after $N$ seconds, we would expect one of them to have succeeded, since there are $50^N$ sequences of $N$ keys on our typewriters. I’ll leave you to think about this apparent paradox. And if you want to find out what happens when real monkeys are used, click here and enjoy.

The Infinite Monkey Theorem: Part 1

Posted by maycontainmaths

One of the most popular ways I know of describing an unlikely event is to compare the chance of it occurring to the chance that a bunch of monkeys sitting at typewriters will type the works of Shakespeare. I first encountered this in a debate on evolution; the unlikely event in question being the formation of the ridiculously complex molecule DNA from random interactions between simple chemical substances. One opposing argument was that although the formation of DNA seems unlikely, the universe is so vast, and so old, that perhaps we might expect such an unlikely event to occur after all. So how likely is it that monkeys with typewriters could reproduce Shakespeare? How long would we expect it to take?

DNA

By the end of this blog post, we’ll see how likely the monkeys are to succeed. The calculation isn’t actually that difficult, but before we begin, we’ll need to make some assumptions.

Assumptions

Monkeys press one key (and only one key) on the keyboard every second. They never stop, slow down, or speed up, and they don’t die either.
The typewriters don’t change. They don’t break down or run out of ink.
All of the typewriters have 50 keys. When pressing a key, the monkey is equally likely to select any of the keys on the typewriter, completely independently of what has happened previously.

Implausible, not Impossible

Let’s work out the probability that a lone monkey succeeds in typing the works of Shakespeare. Actually, let’s start by looking at the probability that a monkey manages to type the word “HAMLET”.

Could this happen in the first 6 letters? For this to happen, the first letter needs to be an H, occurring with probability 1/50, the second letter needs to be an A, occurring with the same probability, and so on. Multiplying the probabilities together, the probability that the monkey types “HAMLET” is 1/50 to the power 6. The probability that the monkey doesn’t type “HAMLET” is 1 minus this, which is less than one. We’ll call this probability p.

Now, if the monkey types N blocks of 6 letters, the probability that none of these blocks is “HAMLET” is p to the power N. Since p is less than one, if we make N larger and larger, p to the power N gets closer and closer to 0.

In fact, the probability that the monkey doesn’t type “HAMLET” anywhere in these 6N letters (not just contained in a single block of 6) is less than p to the power N. This is because rather than just ruling out possibilities like “HAMLET asdfgh” we also rule out possibilities like “asdHAM LETfgh” (lower case letters used here for clarity). So, as the monkey types more and more, the chance that “HAMLET” is typed gets increasingly close to 1.

The complete works of Shakespeare are much longer than just 6 letters, but exactly the same reasoning applies. Thus, given long enough, a monkey sitting at a typewriter is likely to succeed in this seemingly impossible task. This is humourously referred to as the Infinite Monkey Theorem.

Next Time…

We know that given long enough, it’s not completely impossible that monkeys chained to typewriters might be able to type out Shakespeare. But how long might we expect them to take? Once again, some simple maths provides the answer, so check out next week’s post to find out.

Zero Knowledge

Posted by maycontainmaths

Sometimes, it would be nice if you could convince somebody without having to give too much away. For example, a fast-food chain (or stockbroker) might like to secure money from investors. But how can they convince investors that their money was legitimately spent on ingredients (or stocks and shares) without giving away their secret sauce recipe (trading algorithms)? If every party trusts each other, then there is no problem. Unfortunately, trust can be hard to come by.

Luckily, cryptography provides us with a way forward. For a large class of different problems, there are methods of convincing people without giving away all of the details. These are called Zero Knowledge protocols, because they do not leak any additional information beyond convincing somebody of a particular fact. They are described in terms of two parties called the Prover and the Verifier, often replaced with characters Peggy and Victor to make things more understandable (see this link for the extended cast of characters). Peggy is the one with some kind of extra knowledge, and always tries to convince Victor.

What does it take to make a process or argument zero knowledge? Here are three basic requirements:

It’s convincing. If Peggy knows what she claims to know, then she practically always succeeds in convincing Victor.

It’s fair. If Peggy doesn’t know what she claims to know, then she practically never succeeds in convincing Victor.

It doesn’t leak information. When Peggy manages to convince Victor to believe a fact, he is convinced. Nothing more, and nothing less.

Without further ado, let’s see some examples of zero-knowledge ideas.

1. Where’s Wally?

Victor has a new “Where’s Wally?” book and has been searching for Wally for 3 hours straight with no success. He is starting to lose faith that Wally even appears inside the book, and is thinking of giving up. Peggy already knows where on the page Wally is located, and she wants to convince Victor of this without giving away the location, so that Victor will keep searching (because Peggy finds Victor much more agreeable when he is occupied. Or perhaps she just enjoys the feeling of power).

In order to convince Victor, Peggy takes a huge piece of newspaper, and makes a small hole in the shape of Wally. She holds the book behind the newspaper, with Wally showing through the hole, and shows Victor.

If Peggy really knows where Wally is located, the whole process is very easy and convincing.
If Peggy doesn’t know where to find Wally and Victor sees something else through the hole, he immediately knows that Peggy was lying. So the process is fair.
The piece of newspaper is huge, so Victor can’t tell the position of the book behind the newspaper. Therefore, no information about Wally’s position is leaked.

2. Colour-blindness

Victor is colour-blind, and can’t tell the difference between red and green. As a result, his red and green shirts seem identical to him. Peggy would like to convince Victor that the shirts are different, without giving away which is red and which is green (because watching Victor wear clashing outfits is rather amusing).

This time, Victor has a more active role. He hides both shirts behind his back, with one in each hand, and then swaps them between his left and right hands at random. However, though he still does not know which is which, he is careful to keep track of which shirt was originally in his right hand, and which was originally in his left. When he is ready, he brings the shirts out from behind his back. Now Peggy simply points left or right to identify which shirt was originally in Victor’s right hand.

If Peggy is not colour-blind, she can easily tell between the two shirts and will identify the correct one.
If Peggy can’t tell between the shirts, she can only convince Victor with probability 1/2, since he swaps the shirts about randomly.
Poor Victor doesn’t learn which shirt is which. He only learns the Peggy knows which is which.

Of course, if Peggy is cheating and just guesses, she will still convince Victor with probability 1/2. In order to fix this, they can repeat the process many times. If Peggy is cheating, the probability that she guesses correctly every time is one half, to the power n. If she is honest, she will still be able to choose correctly every time.

Concluding Remarks

In both examples above, there’s a very simple reason why Victor doesn’t learn any new information: he already knows exactly what he is going to see. In the first example, he knows that he will see a Wally through the hole in the newspaper. In the second, he knows that Peggy will, every time, correctly identify which shirt was originally in his right hand. This is the key to putting zero knowledge on a firm logical and mathematical footing. A protocol is zero knowledge if Victor can produce, by himself, the correct distribution of conversations between himself and Peggy, before they even talk. If he already knew exactly what she was going to say, then there’s no way that Victor could learn anything new from their conversation.

There are plenty of real-world applications of zero knowledge. It’s possible to prove that you are a member of a particular group of people, without giving away your identity. Zero knowledge also opens up possibilities for things like voting securely over the internet, where the voters can give zero knowledge proofs that they voted correctly (i.e. voted for one candidate only) and the vote counters can count the votes without learning any individual vote.

Zero knowledge is a powerful tool in modern cryptography. It’s counter-intuitive, but sometimes you really can prove that you know a secret without giving it away.

Magic Squares

Posted by maycontainmaths

Today’s post is all about how to construct magic squares of different sizes. A magic square is a square grid where each cell contains a different positive whole number. They have the special property that the total of the numbers in each row, column, and the two long diagonals, is the same. They are often made up of consecutive numbers, starting from 1, but they don’t have to be.

A 1 x 1 magic square is extremely boring if you think about it, and it’s pretty easy to see that there are no 2 x 2 magic squares (try to find one!). So the smallest interesting magic squares are 3 x 3. We’ll see a categorisation of all 3 x 3 magic squares. It’s also possible to create magic squares of any size greater than 3. We can create most of these by combining smaller magic squares together to create larger ones.

3 x 3 Magic Squares

With a little work, we can actually find all of the 3 x 3 magic squares. Let’s say that the total of our rows, columns and long diagonals is equal to S. We begin by placing our first number c in the centre of the square.


	c

Now, we can place two more numbers m and n in the top corners. We’ll write these as c + a and c + b, where a is the difference between c and m, and similarly with b and n.

c+a		c+b
	c

This forces us to write particular values in the bottom two corners to make the total of each diagonal equal to S.

c+a		c+b
	c
S-2c-b		S-2c-a

To make the left and right columns add up to S, we are forced to write in particular values again. In the middle of the left column, we must write in S – (c + a) – (S – 2c – b) = c – a + b. Similarly, in the middle of the right hand column, we write c + a – b.

c+a		c+b
c-a+b	c	c+a-b
S-2c-b		S-2c-a

Now, adding up the middle row, we find that (c – a + b) + c + (c + a – b) = 3c = S. So the total of each row, column and diagonal is actually equal to 3c. We can easily fill in the missing squares, and substitute in 3c instead of S, to get the following magic square.

c+a	c-a-b	c+b
c-a+b	c	c-b+a
c-b	c+a+b	c-a

We wanted all of the numbers to be different positive integers. Some further investigation tells us that we need to have 0 < a < b < c – a and b not equal to 2a. This gives all of the 3 x 3 magic squares! Just choose values for a, b and c to generate your own. Here’s an example with a = 1, b = 3 and c = 5.

6	1	8
7	5	3
2	9	4

Combining Magic Squares

You can actually combine an n x n magic square with an m x m magic square to make an nm x nm magic square. Let’s see how to do this with a 3 x 3 and a 4 x 4 :

3 x 3

8	1	6
3	5	7
4	9	2

4 x 4

1	15	14	4
12	6	7	9
8	10	11	5
13	3	2	16

We’re going to create a 12 x 12 square. Here’s the method:

Divide a 12 x 12 square into 4 x 4 blocks of 3 x 3 squares. Each block is going to be a small 3 x 3 magic square.
Look at the square labelled 1 in our 4 x 4 square. Put the 3 x 3 square in the corresponding block on our 12 x 12 square. This adds the numbers 1 to 9 into our large square.

8	1	6	.	.	.	.	.	.	.	.	.
3	5	7	.	.	.	.	.	.	.	.	.
4	9	2	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.

Look at the square labelled 2 in our 4 x 4 square. Find the corresponding block on our 12 x 12 square. Now, add 9 to every number in the 3 x 3 square, and put this in the block. This adds the numbers 10 to 18 into our large square.

8	1	6	.	.	.	.	.	.	.	.	.
3	5	7	.	.	.	.	.	.	.	.	.
4	9	2	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	17	10	15	.	.	.
.	.	.	.	.	.	12	14	16	.	.	.
.	.	.	.	.	.	13	18	11	.	.	.

Do the same again for the square labelled 3 in our 4 x 4. Add 18 to every number in the 3 x 3 square. This adds 19 to 27 into our large square. Carry on, and this is what you get in the end!

8	1	6	134	127	132	125	118	123	35	28	33
7	5	3	129	131	133	120	122	124	30	32	34
2	9	4	130	135	128	121	126	119	31	36	29
107	100	105	53	46	51	62	55	60	80	73	78
102	104	106	48	50	52	57	59	61	75	77	79
103	108	101	49	54	47	58	63	56	76	81	74
71	64	69	89	82	87	98	91	96	44	37	42
66	68	70	84	86	88	93	95	97	39	41	43
67	72	65	85	90	83	94	99	92	40	45	38
116	109	114	26	19	24	17	10	15	143	136	141
111	113	115	21	23	25	12	14	16	138	140	142
112	117	110	22	27	20	13	18	11	139	144	137

We can use the same method to multiply any two magic squares together.

Magic Squares of Any Size

If we can multiply magic squares together like this, then we can find magic squares of all kinds of sizes. This link shows how to create magic squares of any odd size. Here’s a 5 x 5 example created using this method:

17	24	1	8	15
23	5	7	14	16
4	6	13	20	22
10	12	19	21	3
11	18	25	2	9

Say we want to create a magic square that is n x n. If n is odd, we’re already covered by the previous link, and we can make an n x n square. But what if n is an even number?

Divide n by 2 as many times as possible, stopping when we finally get an odd number m. Suppose we managed to divide by 2 a total of P times. Then we can write n = m x 2^P (2^P is 2 to the power P).

If P is even, set Q = P/2. Then we can rewrite n = m x 4^Q = m x 4 x 4 x … x 4 (there are Q 4s). In this case, since m is odd, we can construct an m x m magic square. We also know a 4 x 4 magic square from earlier in the blog post. So it’s possible to combine all of these one by one and finally get an n x n magic square.

If P is odd, set Q = (P – 1)/2. This time we can rewrite n = 2 x m x 4^Q. Since we know a 4 x 4 magic square, if we also had a 2m x 2m one, we could combine them all to find an n x n one (we can’t just combine with a 2 x 2 square since these don’t exist!). Luckily, there are methods known to construct squares of this type. Squares of the form 2m x 2m, where m is odd, are called singly-even squares, and one construction is given here.

Since we can construct an odd square of any size, and a singly-even square of any size, and we have a 4 x 4 magic square in our possession, this means that we can construct magic squares of any size (except 2) by the rule for combining that we saw earlier.

How to Win a Gunfight

Posted by maycontainmaths

So, you’re wandering through the Old West, accidentally stumble into an unfriendly saloon, and find yourself at the wrong end of the barrel of a gun. As your life flashes before your eyes, you find yourself wishing that you’d paid more attention in your maths classes…

But fear not! In this post, we’ll go over the best strategy for winning a simple gunfight. Who knows? This might even save your life someday…

The Rules

You and your adversary stand 10 paces apart.
You take it in turns to act. On your turn, you can either shoot, or walk one pace forwards. We’ll assume here that neither of you ever run out of bullets.
At 10 paces, the chance that you hit your opponent is 1/10. At 9 paces, this improves to 2/10, at 8 paces 3/10, and so on, until at 1 pace away, you are certain to hit your opponent.
It should go without saying, but if you get shot, you lose.

The Strategy

So, should you use your turn to try and shoot your opponent, or take a step forward in order to improve your chances next time round?

If you’re only 1 pace away, and it’s your turn, then you’re certain to win if you shoot, so obviously, that’s what you should do. If you’re two paces away, however, then stepping forward means that your opponent is certain to win, so clearly you should shoot. What about 3 paces away, or further?

Let’s start by working out how likely you are to win if it’s your turn, and you decide to shoot every turn, no matter what your opponent does.

Two Paces

At two paces, we’ll assume that your opponent is intelligent, and never takes a step forward (so that you don’t shoot them with certainty). This means that the best strategy for either player is to shoot on their turn. But what is the chance that you actually win the gunfight? We can think about the shots fired as a sequence of hits and misses. Since the first player to hit wins the gunfight, this sequence will always be a long string of misses, followed by a hit.

If you take the first turn, then you win with the following sequences:

You hit
You miss, they miss, you hit
You miss, they miss, you miss, they miss, you hit

…and so on. There are infinitely many winning sequences like this and it’s easy to tell what they are, so we won’t write out the whole infinite list here. At two paces, the probability that you hit is 9/10, and the probability that either player misses is 1/10. Therefore, the probability that you miss, then they miss, is 1/10 x 1/10 = 1/100.

Then the probability of the first sequence is 9/10, the second is 9/10 x 1/100, the third is 9/10 x 1/100 x 1/100, and so on. These numbers form a geometric series so we can add them up using a simple to formula, to discover that our chance of winning the gunfight is equal to 10/11, or slightly over 90.9%.

More Than Two Paces

At three paces, assuming that nobody takes a pace forward, the chance of winning involves adding a geometric series like before, but with slightly different numbers. The probability of a hit is now 8/10, and the probability of a miss is 2/10. So the probability that you miss, and then they miss, is 2/10 x 2/10 = 4/100 = 1/25. We then find that in this case, your chance of winning the gunfight has dropped to just over 83%.

The same method gives your chance of winning for any number of paces. The results are shown in the table below (to one decimal place).

# Paces	First Player Win %	Second Player Win %
1	100.0	0.0
2	90.9	9.1
3	83.3	16.7
4	76.9	23.1
5	71.4	28.6
6	66.7	33.3
7	62.5	37.5
8	58.8	41.2
9	55.6	44.4
10	52.6	47.4

One important thing to note is that while the gunfight is in progress, any shots fired in the past don’t matter. Assuming that you’re still alive, and both players just keep shooting, the second column gives your chances of winning on your turn, and the third column gives your chances of winning on your opponent’s turn.

Now, we can see that taking a step forward is always a bad idea. This is because taking a step forward resets the situation at a slightly closer distance. Further, whoever takes a step forward gives the other player the opportunity to shoot first. For example, if you are 10 paces away, assuming that both players just shoot, your chance of winning is 52.6%. If the other player decides to take a step forward, they only increase your chance of winning to 55.6%. If you take a step forward, this gives your opponent a 55.6% chance of winning, which means that you have dropped to a 44.4% chance.

If it’s your turn and you just keep shooting, your chance of winning is at least the value in the second column (it increases if your opponent steps forward). If your opponent takes a pace forward, move one cell up. Your chance of winning if you just keep shooting is now at least the value in this cell. If you take a pace forward, move one cell up and one cell to the right in the table. Your chance of winning is now at most the value in this cell, assuming that both of you just keep shooting from now on.

So in this case, you should shoot first and ask questions later.

8	1	6	.	.	.	.	.	.	.	.	.
3	5	7	.	.	.	.	.	.	.	.	.
4	9	2	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.

8	1	6	.	.	.	.	.	.	.	.	.
3	5	7	.	.	.	.	.	.	.	.	.
4	9	2	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	17	10	15	.	.	.
.	.	.	.	.	.	12	14	16	.	.	.
.	.	.	.	.	.	13	18	11	.	.	.

8	1	6	134	127	132	125	118	123	35	28	33
7	5	3	129	131	133	120	122	124	30	32	34
2	9	4	130	135	128	121	126	119	31	36	29
107	100	105	53	46	51	62	55	60	80	73	78
102	104	106	48	50	52	57	59	61	75	77	79
103	108	101	49	54	47	58	63	56	76	81	74
71	64	69	89	82	87	98	91	96	44	37	42
66	68	70	84	86	88	93	95	97	39	41	43
67	72	65	85	90	83	94	99	92	40	45	38
116	109	114	26	19	24	17	10	15	143	136	141
111	113	115	21	23	25	12	14	16	138	140	142
112	117	110	22	27	20	13	18	11	139	144	137

8	1	6	.	.	.	.	.	.	.	.	.
3	5	7	.	.	.	.	.	.	.	.	.
4	9	2	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.

8	1	6	.	.	.	.	.	.	.	.	.
3	5	7	.	.	.	.	.	.	.	.	.
4	9	2	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	17	10	15	.	.	.
.	.	.	.	.	.	12	14	16	.	.	.
.	.	.	.	.	.	13	18	11	.	.	.

8	1	6	134	127	132	125	118	123	35	28	33
7	5	3	129	131	133	120	122	124	30	32	34
2	9	4	130	135	128	121	126	119	31	36	29
107	100	105	53	46	51	62	55	60	80	73	78
102	104	106	48	50	52	57	59	61	75	77	79
103	108	101	49	54	47	58	63	56	76	81	74
71	64	69	89	82	87	98	91	96	44	37	42
66	68	70	84	86	88	93	95	97	39	41	43
67	72	65	85	90	83	94	99	92	40	45	38
116	109	114	26	19	24	17	10	15	143	136	141
111	113	115	21	23	25	12	14	16	138	140	142
112	117	110	22	27	20	13	18	11	139	144	137

8	1	6	.	.	.	.	.	.	.	.	.
3	5	7	.	.	.	.	.	.	.	.	.
4	9	2	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.

8	1	6	.	.	.	.	.	.	.	.	.
3	5	7	.	.	.	.	.	.	.	.	.
4	9	2	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.	.	.	.	.
.	.	.	.	.	.	17	10	15	.	.	.
.	.	.	.	.	.	12	14	16	.	.	.
.	.	.	.	.	.	13	18	11	.	.	.

8	1	6	134	127	132	125	118	123	35	28	33
7	5	3	129	131	133	120	122	124	30	32	34
2	9	4	130	135	128	121	126	119	31	36	29
107	100	105	53	46	51	62	55	60	80	73	78
102	104	106	48	50	52	57	59	61	75	77	79
103	108	101	49	54	47	58	63	56	76	81	74
71	64	69	89	82	87	98	91	96	44	37	42
66	68	70	84	86	88	93	95	97	39	41	43
67	72	65	85	90	83	94	99	92	40	45	38
116	109	114	26	19	24	17	10	15	143	136	141
111	113	115	21	23	25	12	14	16	138	140	142
112	117	110	22	27	20	13	18	11	139	144	137