Pi-ed to the galaxy

You may have heard that yesterday, March 14th, was 'Pi Day', or possibly 'American Pi Day', since it's in the usual American format that the date: 3/14/15 9.26:53 reads as the first ten digits of the number represented by the Greek letter pi. Usually the representation would be something like 3/14 1.59:26, but this year was of special interest to enthusiasts - and the precise time of the celebration was altered - because it is the only year of the century in which the two-digit year number can be incorporated, increasing the precision of the approximation.

But anyway. All this talk of pi reminds me of something that happened to a couple of friends one lazy Saturday afternoon...

Adam and Doug were sitting in the living room drinking tea when a package arrived at the door. Of course, it didn't arrive directly, but Adam watched through the window as the delivery man approached the door and posted a 'sorry we missed you' card, which is essentially the same thing. After a short sprint down the driveway and a forcibly-polite conversation in which Adam found himself conceding that the notion of 'being in' is fraught at the first hurdle with ill-defined notions of 'being', he returned with a small white box that Doug eyed gleefully as Adam slammed the door shut. It was funny, because he felt pretty 'in' right now.

"It's here! Open it up!" said Doug. Adam did so, producing a small card with a disc in the jacket.

"What is it?" he asked.

"It's the Answer to the Great Question, of Life, the Universe and Everything!" exclaimed Doug. "Quick, let me see!"

"I thought we already settled that?" said Adam, handing over the card. "Isn't it-"

"Yes, yes, that's just how they market it. But this is so much more than that - look!"

Doug showed Adam the card. On the cover was the single Greek letter, pi. On the inside it read:

"CONGRATULATIONS on your purchase of the Answer to the Great Question, of Life, the Universe and Everything - and so much more! Contained in this innocuous little number is the answer to every question you could possibly imagine - and even some you can't! Simply load up the software, which contains an algorithm for calculating pi to whatever degree of accuracy you need. Enter your question and watch in amazement as the answer appears before your very eyes!*

*(Some computation time required).

HOW DOES IT WORK? Pi is perhaps the most famous of many numbers conjectured to be 'NORMAL', which means that its INFINITE decimal expansion contains every imaginable sequence of digits, however long, infinitely many times! THAT MEANS THE ANSWER TO YOUR BURNING QUESTION LIES HIDDEN DEEP WITHIN THE VERY FABRIC OF MATHEMATICS ITSELF! Simply assign a code, such as 'A' = '01', 'B' = '02', 'C' = '03' to all the letters and symbols in your language, then wonder as the SECRETS OF PI REVEAL THEMSELVES TO YOU. Try it now!"

Adam was bemused. "So it's saying we can read pi like some sort of message from the universe?" he asked.

"Exactly!" replied Doug. "And every conceivable answer is contained it in, because SOMEWHERE in there, the correct sequence of digits appears. We just need to pick a code. I suppose we may as well try the one they suggest. So my name, DOUG, would be coded using 04 for D, 15 for O, 21 for U and 07 for G. That's... 04152107. Let's just load up a few digits of pi here..."

Doug had inserted the disc into their supercomputer and pressed some buttons. The initial digits of pi flashed up on the screen:

"3.141592653589793238462643383279502884197169399"

Doug looked excited. "Let's have a read! So the first digits are 3 and 1, 31. Under our code that means... uhh. Hang on. Hm."

"I guess they haven't explained the full picture here," observed Adam. "There are too many two-digit numbers for the letters of the alphabet."

"No no, I'm sure it's fine" stammered Doug, trying to pick apart the card for a missing page. "Let's just-"

"It's ok - how about we just start again once we get to 27? So when we see 26 we get Z, then 27 will be A again, 28 is B and so on. We can keep wrapping round until we run out of numbers. A will be 01, 27, 53 and 79. Once we get to 99 it'll be U, so 00 can be V. I'll draw out a quick table...

A	B	C	D	E	F	G	H	I	J	K	L	M	N	O	P	Q	R	S	T	U	V	W	X	Y	Z
01	02	03	04	05	06	07	08	09	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26
27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49	50	51	52
53	54	55	56	57	58	59	60	61	62	63	64	65	66	67	68	69	70	71	72	73	74	75	76	77	78
79	80	81	82	83	84	85	86	87	88	89	90	91	92	93	94	95	96	97	98	99	00

"Okay great," said Doug, nodding. "So we get 31, 41, 59, 26, 53, 58, 97, 93, 23, 84, 62... what's that? E, U, G, Z, A, F, S, O, W, F, J..."

"Eugzafsowfj?" interjected Adam, eyebrows raised. "Sounds like the 'very fabric of mathematics' has had one too many spins."

"Well, there's going to be some junk, obviously," replied Doug, a little defensively. "After all, EVERY combination of numbers is in pi somewhere!"

"Conjecturally, right?"

"Yes yes, conjecturally. You're right, we'll get all manner of complaints if we don't say that."

"From who?" said Adam, confused, but Doug didn't seem to hear. He continued:

"But you see, it found the word 'SOW' - that's a good start. We just need to search deeper. So what we do now is input our question, and the algorithm will calculate the digits of pi, one by one, until it locates the question in our code. What comes after that will be the answer!"

Doug thought for a second, then said:

"You know what, let's use a completely different code from that one from now on, and don't say it out loud, just in case anyone decides to check what we do for themselves."

He glanced over his shoulder, then back again. Adam was about to say something, but thought better of it.

"We'll start with something simple," continued Doug, beginning to type, "WHEREISMYTOWEL... and it says you have to select an answer length... ok". The supercomputer whirred into action. After a minute, it came back with the words:

"INYOURTRAVELBAG"

"Wait, what?" said a shocked Adam. "How can-"

"I knew it!" exclaimed Doug, rushing to the corner of the room and producing a very sandy towel from an equally sandy suitcase. "I remember now, I was sleeping under it during my last desert stargazing visit. Hm, it's a bit dirty. But you see, it works! The power of pi! Don't you see how big this is? All the knowledge of the universe is at our fingertips - cures for all the diseases of the world, the secret to world peace... lottery numbers!"

"I suppose for that we'd need to encode for some numbers as well as letters," said Adam, still hesitant.

"Try something else!" cried Doug. He was bouncing.

"Ok, let's try... WHATISTHECUREFORTHECOMMONCOLD" said Adam, pressing 'enter'. The computer sprang into action again, noticeably more pained this time. It began to make thumping noises from within, but Doug didn't notice because he was shaking out his towel, muttering something about a mini-raft. Eventually, the answer came back:

"RAISINSBOILEDUNDERAFULLMOONKDQZ"

"Raisins boiled under a full moon, really?" said Doug. "Well, that's useful to know."

"What's that KDQZ at the end there?" asked Adam.

"Oh, just unused answer space, I guess. The computer doesn't understand when to stop reading - that's why you have to tell it. What are you asking it now?"

"I'm typing HOWMANYLEGSDOESASPIDERHAVE."

"Why are you asking it that? We know the answer is-"

"FORTYTWO."

"What?"

"That's the answer it gave - forty two. How about WHATISTHECAPITALOFSPAIN?"

"Wait a minute..."

"Oh - HJKSDMAFT, of course!"

"What's going on?"

Adam sighed and turned to his friend.

"Don't you see, Doug? The digits of pi have all the answers, yes-"

"Conjecturally," Doug reminded him.

"Yes - conjecturally, all the answers are there, but there's also a LOT of complete rubbish! If every string of numbers exists, infinitely often, within the digits of pi, then not only is every answer there, but so is every conceivable WRONG answer, as well as a load of pure gobbledegook. It's the the ultimate internet troll. Frankly it's amazing the code and questions we picked returned answers that made any sense whatsoever the first few times. Someone must have left an infinite improbability drive running somewhere nearby."

Doug typed another query into the computer.

"Yikes," he gasped as the response popped up. "Well, that's just obscene." He turned back to Adam. "So it's completely useless?" he asked, starting to look somewhat dejected.

"Perhaps not. I mean, it's an algorithm for calculating the digits of pi, at the very least. I guess if you wanted to generate a string of random numbers, you might argue that as far as anyone can predict them, pi's digits are random. Of course, they're really completely fixed, but if you don't know what's coming next it's much the same thing in practice."

Doug stood in thought. "I suppose it goes to show," he said, "that having the universe's information at your fingertips is no good if you have no way of making head or tail of it. It's one thing to claim that pi contains all the great works of art under some sophisticated encoding, but that doesn't help us to produce that art ourselves, nor does it detract from the achievements of those who do create it. But you know, now I can't decide whether it's fascinating that pi contains all that information, both true and false..."

"Conjecturally"

"Yes - conjecturally... or whether it's a complete banality! I mean, it's just an abstract notion, at the end of the day, isn't it? We could have constructed a number with the same properties just by taking some source of randomness and converting it into a string of digits. Or are there deterministic methods that don't require randomness? How many numbers even are 'normal' the way pi might be?"

"Who knows," said Adam, and added jokingly: "Let's ask pi."

As he entered the question, the computer shuddered visibly and smoke began to billow from the casing. With what sounded like a sigh of relief, it completed the calculation and spat out the response:

"SEEYOUNEXTWEEK"

Adam and Doug glanced at one another nervously. Adam went to the window and quietly shut the curtains.

Folic-ing with infinity

In the previous post we left Cleo searching for her lost ant, Tony, who is moving at some unknown, but constant, velocity, up or down an infinite pavement. Since we are imagining the pavement extends infinitely in both directions, imagine the pavement slabs are labelled using the positive and negative numbers ... -3, -2, -1, 0, 1, 2, 3 ... . Tony started at some integer position x, and is moving at some integer velocity v slabs per minute (both may be positive, negative or 0). How can Cleo, with the power (via maternal chauffeuring) to examine one point anywhere on the pavement every minute, ever hope to find him?

Two examples of schemes that may not work were given last time. Although Cleo might be lucky, there's no way to be sure she isn't heading in the wrong direction, or just too slowly to catch Tony up. But what if he weren't moving? In other words, what if he has velocity v = 0? Then the second method will eventually catch him, although the first still might not. In this case, Tony is fixed, unmoving, at a point x. Suppose Cleo checks slab 0 first, then 1, then -1, then 2, then -2, and so on. Here is that diagram from last time, with step-numbers labelled:

Whatever x may be, she will eventually reach it in a finite number of steps. She checks 0 on the initial try (call this time t = 0), then 1 at time t = 1, then a positive slab every 2 attempts. So if x is positive, she checks slab x at time t = 2x - 1. Similarly if x is negative, the time is t = -2x + 1. Although Cleo can't be sure at what time she'll find Tony, she knows that it is finite.

What all of the above comes down to is the notion of 'counting' an infinitely-large set. Colloquially, 'infinity' is often used to refer to an unimaginably large quantity, such as the size of the universe, and has a connotation of 'going on forever'. This is similar in spirit to the mathematical meaning, but here infinity has a very precise definition - in fact, several very precise definitions, since there is more than one kind of infinity!

First, think of the set of whole numbers {1, 2, 3, ..., n} with no numbers missed out. Call this set [n]. Unsurprisingly, the size of [n] is n. This is a set with finite size. But this is only a smaller part of the full collection of positive whole numbers {1, 2, 3, ...} going on forever. This collection is referred to as the set of 'natural numbers', denoted N. How big is this set? Since [n] is contained in N, we know N has at least n elements, since that is the size of [n]. But there is no limit to how large we could take n. If we tried to claim the size of N to be some number m, we could immediately disprove that claim by taking n = m + 1. This is what it means to say that N is infinite: for any number we choose, we can find a quantity of elements of N that exceeds that number.

You could say the same of other sets of numbers, such as the negative and positive whole numbers (including 0) - referred to as the integers Z - or just the even integers, 2Z. What is the size of the set of positive square numbers, {1, 4, 9, 16, ...}? It's infinite again, since however big you choose m, the set {1, 4, 9, ..., (m+1)²} contains only square numbers and has m + 1 elements. But what all these sets have in common is that they are 'countably' infinite. This means that they can be written down in a list without missing a single element of the set. For the natural numbers, this list could simply be 1, 2, 3, ... . For the integers, it could be Cleo's 'motionless Tony' algorithm 0, 1, -1, 2, -2, ... . We could explicitly label the step at which each number appears:

1. 0
2. 1
3. -1
4. 2
5. -2
...

This is precisely the meaning of countably infinite: there is what's known as a bijection between Z and the natural numbers: each element of N is coupled with precisely one of Z. In this sense, the two sets are 'the same size'. This seems counter-intuitive! It seems that Z should be 'twice as big' (at least) as N, because it contains every element of N as well as its negative counterpart. Another strange phenomenon is that the order in which you count the same set can determine whether or not you 'hit' all of it: compare the above method of counting Z with simply counting in the ascending order 1, 2, 3, ... . The second version misses all the negative numbers, no matter how far you go.

This is something first-year undergraduates at university have to get used to, which they often do kicking and screaming. The thing is, there's just no sensible meaning to the term 'twice as infinite', because infinity isn't a number, but the concept of a magnitude a number can't possibly exceed. It can be dangerous trying to apply an intuitive notion of what 'size' means in a situation where that idea breaks down, and our definition of infinity doesn't attempt to do that. The vital thing is that our results are consistent under this paradigm, however weird they occasionally seem, and mathematicians define infinite sizes as described above because it's the convenient way to think about maps from one set to another*. If they want to know whether it's possible for a function to take a value in N and spit out a value in Z, the answer is 'yes', because the sets are both countably infinite. And this is useful, because it's precisely the property of Z that Cleo uses to guarantee than she can scan through it without missing a value. Notice that even though Z is infinite, because it is countably infinite, there is no value that cannot eventually be reached, given enough time. Conversely, it's impossible to 'search' the entire set of decimal numbers in such a way, so this set (known as the 'real numbers', R) is called uncountably infinite.

So Cleo has used her understanding of infinite cardinalities to determine that if Tony is motionless, she can find him so long as she persists long enough (and they say the education system is being dumbed down!). Unfortunately, Tony probably is moving. It's no good being able to check every integer exactly once if Tony appears at that slab of pavement before or after Cleo checks it. Is there a way to get around this?

The answer, amazingly, is yes! Remember that Tony has two unknown parameters: his velocity, v, and his initial position x. If she knew what both of these were, Cleo would know exactly where along the pavement Tony is at time t: it's his initial position, plus his velocity times the number of minutes that have passed. So if we call his initial position x(0) = x, and denote by x(t) his position at time t, then

x(t) = x + t*v.

Knowing this, Cleo can 'try out' a pair (x,v) of parameters to see whether they are correct, by keeping track of the passage of time and checking slab x(t) for the current t. So long as she has a way of checking every possible combination of parameters, she will find Tony. One way to do this is to imagine a grid of numbers, with the x parameter along the horizontal axis and the v parameter along the vertical axis. Now starting with t = 0 at coordinate (0,0), Cleo checks the parameters x = 0, v = 0, then moves in a spiral pattern to (0,1), (-1,1), (-1,0), (-1,-1), (0,-1), (1,-1), (1,0), (1,1), (1,2), (0,2), (-1,2), and so on. What she is actually doing is 'counting' the infinite number of points as shown in this two-dimensional grid (numbers indicate the time this coordinate is visited).

The first time you see it, I think it's kind of intriguing that adding a whole new dimension doesn't prevent the new set of points from being counted just like the one-dimensional number line (of course, this would be considered a banality for seasoned mathematicians!). The diagram, however, makes it apparent that every single coordinate will eventually be enveloped by the spiral**. To be clear, the diagram doesn't explicitly indicate spatially where Cleo should search: she is navigating an imaginary parameter space which she then converts into a point on the pavement using the formula for x(t). The result of this method is that Cleo would check the following squares:

(0,0), t = 0: x(0) = 0 + 0*0 = 0
(0,1), t = 1: x(1) = 0 + 1*1 = 1
(-1,1), t = 2: x(2) = -1 + 2*1 = 1
(-1,0), t = 3: x(3) = -1 + 3*0 = -1
(-1,-1), t = 4: x(4) = -1 + 4*(-1) = -5
(0,-1), t = 5: x(5) = 0 + 5*(-1) = -5
(1,-1), t = 6: x(6) = 1 + 6*(-1) = -5
(1,0), t = 7: x(7) = 1 + 7*0 =1
(1,1), t = 8: x(8) = 1 + 8*1 = 9
(1,2), t = 9: x(9) = 1 + 9*2 = 19
(0,2), t = 10: x(10) = 0 + 10*2 = 20
(-1,2), t = 11: x(11) = -1 + 11*2 = 21
...

Notice that Cleo may check the same square many times, even staying put for several consecutive minutes. By following this strategy, she can be sure of finding Tony the moment she picks the correct pair of parameter values. So we're done!

I like this problem for a couple of reasons. Firstly, it is fairly simple to describe, but the answer gets to the heart of some fairly chewy thoughts about the nature of infinity and the unusual way in which it's traversed. Secondly, to solve the problem it's enough to describe the method of checking pairs of parameters and prove that this two-dimensional parameter space can be explored with a diagram like the one above, but this graphically simple answer hides a level of complexity that is revealed only if you work out the exact values of x(t) at each time point. The sequence 0, 1, 1, -1, -5, -5, -5, 1, 9, 19, 20, 21, ... doesn't, at first glance, appear all that predictable, in spite of the simple mechanism behind it. Part of what mathematicians come to love about their field is the hidden complexity behind ideas that can be expressed very simply. Because the answers can behave in ways that cannot be anticipated, the process is a lot like exploring a new and unknown land, created the moment a new concept is imagined (or perhaps it 'existed' all along - ask a mathematical philosopher!). Even the natural numbers, so simply defined, burst almost immediately into a cornucopia of properties, the unpredictable nature of the prime numbers being one example.

So, will Cleo actually find Tony? If she persists indefinitely, the answer is yes, but although the success time is finite, she doesn't know how large it is and would have to live indefinitely to be certain of success! The weird thing about a countable infinity is that every given element can be reached in finite time, but no matter how far you count, there will always be infinitely-many that remain untraversed. If you tried to express the progress you'd made as a percentage, the only sensible answer would be 0%, because to have any other value, such as 0.0001%, would be to suggest that you only had to carry on (for this example) 999,999 times as long as you already had done to reach the end. You won't! Infinity defies any attempt to visualise its magnitude.

Actually, Cleo's patience lasted even less time than her mother's, and after half an hour's trundling up and down the road she gave up and went inside to paint fractals on the walls. Tony had a near miss with a chef from the Insectivoracious restaurant, but escaped with the help of a vegetarian spider and went on to become one of the great forefathers of the insect-arachnid peace movement. If you see him giving a speech on a little podium, try not to step on him.

---

* Sometimes when asked 'why does maths work this way?', the boring answer is that it's a matter of definition, rather than some mysterious, universal truth. A definition might be chosen because it seems to extend our intuition in the most logical way without causing contradictions, or because it is the most useful choice when it comes to answering related questions. You might come up with a different notion of 'infinity' that didn't behave this way, but it would be best to call it something else, since the results you prove using it won't be the same. As I note later in the article, the mystery is what follows once you've laid down your definitions and start to see what you can do with the ideas that spring from them.

** It would also be possible, however, to choose a path that went on forever but didn't cover the entire grid. Imagine going up one from (0,0) to (0,1), then diagonally down to (1,0), then across to (2,0), then diagonally up through (1,1) and (0,2), up to (0,3), and so on, following all the diagonals with positive coordinates. This only covers a quarter of the whole grid. The path (0,0), (1,0), (2,0), always moving horizontally to the right, is a truly pathetic effort!

A Bug Strife

Young Cleo has lost her ant. The ant, whose name is Tony, didn’t have any particular complaints about life under Cleo’s care; he just decided he wanted to explore the sights and scents of the world for himself, rather than reading about them on Crickipedia*. He had written Cleo a fond pheromonal farewell on the side of his tank, so he assumed she was ok with this.

The escape was a particularly manic and haphazard affair. Cleo had been taking Tony for his daily walk down the long, straight path outside their house. She had let Tony off his leash because he was so good at walking to heel. Suddenly a huge gust of wind came blasting down the length of the path and Tony, seeing his chance for High Adventure, chose not to cling to the pavement and went careening into the distance. Bizarrely, the wind abruptly changed and came rushing back in the exact opposite direction. Cleo has no idea where on the path Tony landed, ahead of her or behind.

Cleo is naturally concerned, especially since the local insect-delicatessen (‘Insectivoracious’) is just down the road. She’s determined to find Tony, but he’s pretty small. Due to her young age, Cleo has never ventured all that far from her house, and she has no idea how far the road spans in either direction since every house is labelled with an un-orderable symbol rather than a number (a particularly valiant attempt at egalitarianism on the part of the local council) - Cleo lives at ‘Purple Blob’**. As an aspiring cosmologist, she conjectures that the road has infinite length and that Tony might be anywhere along it, moving in one direction or the other at a fixed speed (which could include zero – just staying put).

Cleo can’t see Tony without getting to the ground and examining closely, so she has to check for him one spot at a time. Conveniently, the pavement is split into fairly long, thin slabs, spanning its entire width, and she thinks she can check one of them thoroughly in about a minute. Tony is very safety-conscious and will almost certainly stick to the path. Moreover, Cleo has noticed that left to his own devices, Tony moves an exact number of slabs per minute, but she can’t for the life of her remember how many. She considers her own speed not to be an issue, since she can get her mum, who will no doubt be horrified at Tony’s impromptu departure, to drive her up and down the road at a speed that makes Tony’s negligible.

Cleo starts off where she is, first checking the slab she's standing on, then moving one step forward and checking that slab.

After a few minutes, she realises this might never work. What if Tony is behind her and moving away? Then she’s fruitlessly checking a set of slabs that he’ll never appear in. She tries a different approach, jumping back to the first unchecked slab behind her, then forward to the first unchecked slab in front of her, then back again, and so on.

This still won’t work, she realises. If he’s moving away from her (and there’s a roughly 50% chance he is) in either direction, he’ll be moving away faster than she can check, since on average she checks only half a slab in each direction every minute. But if she skips some, she could end up missing him! This is going to take some thought.

Can Cleo develop a search strategy that will certainly result in her finding Tony eventually after a finite time, so long as she never gives up until she’s successful?

Answer here! Skip the next block if you don’t want a…

HINT:
If we did know Tony’s initial position and velocity, how could we express his position after time t (measured in minutes)? This is where Cleo has to check at that time, except that she doesn’t know the initial conditions. How can she cycle through the possibilities in a way that eventually checks each one?

I first encountered this problem in a mathematically identical, but narratively distinct, form: a train starts at an unknown integer along a track described by a number line of infinite length in both positive and negative directions. There are sensors at the integer values along this line that can tell you whether or not the train is there, but only at the time you check them. The velocity of the train is known only to be an integer, positive or negative, and at every time-step you can check exactly one sensor. Arguably some extra suspension of disbelief is required for my version, since Cleo’s equivalent to ‘checking the sensor’ is actually driving to the spot that needs examining: Cleo moves at unlimited speed! On the other hand, our assumptions of an ‘infinite road’ and ‘unlimited speed’ aren’t really any crazier than an infinitely long train track with an infinite number of sensors along it, and the signal from each sensor must take some time to reach us, too. Perhaps the biggest assumption here is that Tony, being a male ant, is still alive after any appreciable length of time! It sucks to be a boy in the insect world.

---

*The insectese translation of Wikipedia is in the cricket dialect, a decision made by its grasshopper founders and the source of no small amount of contention in the insect world.

** You might complain that hues and shapes do still admit an ordering, and you'd be right! If this troubles you, feel free to substitute your favourite unorderable set.

Much Ado About Muffin - THE RESULTS

My previous post told the exciting tale of how Ruby, an intrepid bakerista, saved the day (having first sabotaged it, but shh!) at Tetris HQ. While her coworker Howard may have been content simply to ferry cakes back and forth between taskmasters all day, I'm sure you were wondering (or maybe you've already deduced) what the results of her glutenous ingenuity were. To explain, here's the same illustration as previously, with the squares labelled. Since it takes eight pieces to make two tetrominoes, every puzzle involved removing a single square in such a way that the remaining eight made up the shapes required.

We may as well nerd-it-up a notch and use the proper Tetris terminology, which of course I researched using Wikipedia. Have a click if you're curious - the main point is that the pieces are denoted by the letters that roughly approximate their shape: I, L, T, S, Z, J, O. J is 'backwards L' and O is the square-shaped one. Swotted up? Good! Here we go.

Answer 1
Which square should be removed to leave a shape containing a Z and a T together? Luckily for methodical types, the answer was A. Here's how it works, and do excuse Howard's paint-job, won't you. He hasn't had to do this since 1998!

  

Answer 2

Unfortunately the dream world was much kinder to our heroes than the real thing, and Ruby found herself having to take her best stab with the information 'two of the same - possibly Ls, Js or Ts'. There was no question of which slice to remove: as Ruby noted, there is only one configuration that allows any pairs of twin pieces. If we trust her on that, it means that if we find just one pair of twins in a configuration, then it must be the one that contains all the others, too. She also said it contained only twins, so if we're checking a configuration and find a pair of different pieces, we know instantly that we're in the wrong one. These pieces of information actually made this an easier question than the first, and the answer was... B! Maybe Howard's painting will be better in the real world?

Oh dear, I guess not.

Answer 3

This is where we part company with Ruby, since the tastiest-looking piece is obviously D. However, the piece she had to remove in order to leave the highest number of combinations is I. Perhaps she was trying to make herself feel better about giving most of the cake away, but I think it's more likely that as she began discovering her inner mathematician, her idea of what is tasteful became more questionable*. There are four possible combinations: LS, LO, JZ and JO:

I'm not sure even the Mario mushrooms can explain these ones, Howard!

Unlike question 2, question 3 was much harder than the first, since it required you to find all pairs of shapes that can be made from all combinations. How to do this? I think the most efficient way is to pick a square in the configuration that looks like it can't be used to form many different shapes, form what you can using that square, then see what you have left. As an example, try 'eating' G and examine the square labelled I. With G gone, I can only be part of the L shape made with squares IHED. The only configuration possible if you eat G is the pair LJ.

Even if there are several ways to use your chosen square (e.g. eating I as above), it's not hard to make this procedure fairly methodical and be sure you haven't missed any. Notice once you've exhausted all ways of using that single square, you're done, since every configuration must use that square somehow in a way you've already tried.

Answer 4ish

What about Ruby's other comments? The worst square to eat is H, since it leaves I hanging off the end and unusable. The next-worst are C and D. If you eat C, you can make just the pair JZ, but we already saw that that's contained in the 'eat I' set. Similarly eating D leaves the pair JT, which you'll find is included in the two pairs possible when you eat A.

You might also wonder whether other pairs are unique to a particular configuration, like ZT was if you ate A. The answer is 'yes', and in some cases it's the only pair that can be made, so allowing only a small number of pairs doesn't necessarily make the configuration useless. This property of some configurations to be 'contained' in others on the basis of which pairs they allow, while others neither contain nor are contained, hints at the mathematical notion of a 'partial ordering', where you say a set X is 'larger' than Y for some choices of X and Y, but not all choices admit a comparison. (Compare the 'total ordering' on the number line, where you can always say which of two different numbers is larger.)

Epilogue

What about the fate of Ruby and Howard? Since Tetris HQ is currently enveloped by a thick smog of flour, sugar and edible glitter, it's hard to say, but we can certainly work out the probability that they gave Paul what he requested. With seven shapes - I, L, T, S, Z, J, O - available, there are 28 different ways to make a pair from two of them**, and Ruby only gave Howard four, leaving just a 1/7 (about 14%) chance of success. If she had given him all nine pieces and trusted him not to eat the extra one, they would have had access to eight more possible combinations, increasing their chances to 12/28 = 3/7 (about 43%). Not hopeful, but better. Expensive cake, Ruby!***

So I'm afraid it looks like Paul was probably not very happy with Ruby once again, and this should be a lesson to all of us: while an apple a day keeps the doctor away, a cake protégée won't get Tetris to play.

---

* If you doubt this phenomenon, pay a visit to Warwick Maths Department, where a decent number of professors have decided that shoes and socks are not necessary equipment for lecturing. And actually they have a point, I guess?

** There are 7*7 = 49 ways to pick two pieces in a set order, but some of these are double-counted since the order doesn't matter. There are 7 pairs of twins, and of the remaining 42, 21 are unique. So 7 + 21 = 28 combinations. This happens to be the 7th triangle number 28 = 7*8/2. To see why, draw a table with the first piece along the top and the second piece down the side and ignore the entries that get counted twice:

	I	L	T	S	Z	J	O
I	*	*	*	*	*	*	*
L		*	*	*	*	*	*
T			*	*	*	*	*
S				*	*	*	*
Z					*	*	*
J						*	*
O							*

*** With a few reasonable (?) assumptions, economists could use this information to estimate how much Ruby values cake relative to her job (or hers and Howard's together!). Ruby has sacrificed a 8/28 = 2/7 increased chance of success... for a piece of cake. If the probability of her getting fired for this blunder is p, the value of cake is c and the value of her job is j, then Ruby has implicitly declared:

c > 2/7*p*j

(the value of the cake is greater than the value of her job times the increased probability of losing it), or rearranging:

j < (7/2)/p*c.

We don't really know p, but we can see what happens at various points, for instance if p = 1% then Ruby considers her job worth at most 350 pieces of cake. If p = 100% then she would happily trade her job for the certainty of four slices of cake. If that's the case, she should have just kept the whole thing and not worried!

Much Ado About Muffin - or - A Tale of Two Tetrominoes

Ruby awoke with a pounding in her head and chocolate on her breath. What had she been doing last night? As she peeled her forehead from the hard wooden surface it had been resting on, it dawned on her that she wasn’t at home at all, but seated awkwardly at her desk in the Tetris Block Management offices.

Ah yes. The office party.

She conducted a quick forensic analysis. Strewn across the floor were the scattered fragments of broken tetrominoes, empty power-up bars and experimental cheat codes. The theme music was spinning relentlessly between her ears with laboured speed and questionable tuning, and for some reason the air was thick with cake crumbs, floating like pollen grains in the morning sun. Ruby racked her brains to remember. That was it: a friend of hers had been promoted on the day of the party, and to celebrate Ruby had gone on a bit of a baking spree. Well, a baking frenzy. Cake after cake flying out of the office kitchen, all sliced into small squares to fuel the geometric obsession for which Tetris employees are renowned. She noticed she had narrowly avoided sleeping face-down in the half-finished remains of one of her creations. Smiling, she reached for one of the pieces. The chocolate coating had gone rock-solid overnight, fusing the cake into one delicious lumpy mess, but she managed to snap a piece away and chewed recuperatively as the clock struck 9am.

Suddenly her coworker, Howard, burst through the door. He seemed agitated, and not purely by the overpowering fumes of chocolate that to Ruby had become a second oxygen. Relieved to see someone in the office, he rushed over to her desk and stammered:

“There’s an emergency in the warehouse! Someone forgot to bulk-order the tetrominoes” (here Ruby almost choked on her cake) “and there’s nothing left to send the clients! Paul is clamouring for supplies – says someone was up playing all night and reached level 143. What are we going to give him?”

The guilt in Ruby’s head quickly gave way to panic. Paul was already less than pleased with her after Frances had beaten her to the highest turnover last month, and the only thing quicker than his temper was his tetromino drop rate.

“Oh god, what are we supposed to do?” she cried.

She reached down for another consolatory chunk of cake, but stopped herself with a gasp.

“Wait! Howard – what does Paul say he needs?”

“He said he needed that one that’s kind of Z-shaped to send down, and a T-thingy to stick in the ‘coming next’ box.” Howard’s grasp of Tetris terminology was never particularly good, owing to a previous career in the Ministry of Mario Mushrooms. “But why…”

“Shh!” interrupted Ruby, “I’m thinking. Do we still have the paints from that Gameboy Color merger back in the 90s?”

“I think so – why?”

“Because – look! We can pass off pieces of cake as tetrominoes so long as we paint them the right colour, and there’s nine little squares here – more than enough for two tetrominoes! The only question is which one we can do without…” Now that the crisis was partially resolved, Ruby’s mind was eager to return to her improvised breakfast.

“We need to be careful,” she realised. “Only one of the nine configurations produced by removing a chunk will leave us able to cut out a Z and a T, and there’s no hope of sticking any blocks back together once they’re cut.”

Which square can Ruby safely remove?

As Howard scampered away through the cocoa mist, Ruby breathed a sigh of relief and returned to her solitary square of cake. She hoped the client appreciated the sacrifice she had just made. As she went in for another bite, she heard a voice in her ear:

“Ruby! Ruby, wake up! RUBY!”

“Whuhhh…” groaned Ruby. “Where am I?”

It was Howard, shaking her awake with a vigour that, in her opinion, ought to be reserved for baking and baking alone.

“In the office – it’s morning! Paul is livid – he says someone forgot to bulk-order the tetrominoes and there’s nothing left to send the clients! What are we going to do?”

Ruby sat up and noticed that her dream office had almost perfectly represented her present surroundings, except that – disappointingly – the first piece she’d removed from the cake was already gone. Perhaps she had eaten it in her sleep (it wouldn't be the first time). Grumpy, disorientated and feeling like the victim of a lazy plot device, Ruby snapped:

“Well all right, what does he want?”

“Umm… I think he said something about those backwards Ls, or was it the backwards-backwards Ls? Wait – maybe it was tutus, I mean two Ts… or something. All I remember is he wanted two of the same thing!”

Ruby grimaced. Dream-Howard had been far more competent than the real thing, and that was saying something. She dragged her eyes towards the cake, which was exactly as before, except that she was a piece hungrier this time.

“Ok, well it looks like we can manage this so long as he wanted two identical pieces, and the shape was one of those three... are you at least certain about that?”

Howard looked terrified.

“Look – we’re just going to have to hope for the best. There's only one configuration that allows two duplicates to be cut from it anyway. Come to think of it, it allows nothing but pairs of duplicates! I’ll cut out this piece, you take the rest, confirm what he wants then slice it appropriately and slap on the paint, ok?”

Which square does Ruby have to remove this time?

Ruby sat back to begin her breakfast for a second time, but the cake had barely reached her mouth before Howard had returned, wheezing more than ever in the saccharine atmosphere.

“It wasn’t enough – the guy’s still going strong!” he moaned. “This time Paul needs… uh, well he needs… oh no…”

Miraculously, Ruby had opened her desk drawer to find a perfect replica of the previous cake sitting inside. She was only mildly surprised – quantum entanglement was an occasional by-product of serious baking. It was no use scraping Howard’s mushroom-addled brain for more information, and there was no way she was letting a piece of cake go to waste by sending all nine down with Howard. No job was worth that. So she examined the cake closely.

“Ok, well there’s no way to give him any straight lines – the sides aren’t long enough for that – but a line never turns up when you need it anyway. If I remove this chunk you can only get one tetromino out of the resulting shape – that’s no good. There’s no point taking this one out because you’d get the same options and more if you took out this one instead – I guess you could say one set of options is contained in the other. That's true for this other pair of configurations too. Still, six to choose from – I’ll just have to give you the shape that leaves the highest number of combinations. That chunk looks tastiest anyway. Now take it away and write down what he wants next time. You’re a tetromino delivery man, not a waiter at Burger Kong.”

Which was the tastiest-looking square? Which three options did Ruby dismiss? Which combinations of two tetrominoes is it possible to produce?

Ruby stumbled into the kitchen and turned on the oven. As she did so, she felt renewed life rushing through her fingertips and into every fibre of her body. She took a deep, sugary breath and grinned. Today, Tetris needed a baker... and a baker it had.

[Early post this week – I hope you enjoy reading it half as much as I enjoyed writing it! Answers are now available in the follow-up post. Many thanks to Imogen, whose half-eaten cake as pictured above was the inspiration for this post! It was as delicious as the story recollects.]

Mirrors, memories and memoirs - nostalgic numbers rack their brains

Last week I introduced nostalgic numbers as two-digit numbers with the property that, when written in a certain base, each one can (loosely speaking!) look at itself in the mirror and see half of its own value reflected back at it: swapping the digits has the same effect as dividing by 2. I gave some expressions for constructing all possible nostalgic pairs, and it turned out that they are fairly prescriptive: although you can choose any number n to be the first digit of the pair's lowest member, it's then determined that the other digit will be 2n+1, the base will be 3n+2 and the value of the resulting number will be (n+1)(3n+1). Towards the end we asked the question: 'what about numbers that are effectively multiplied/divided by some other number besides 2 when you swap their digits?'

I think we're going to need some more terminology here. We already defined a 'nostalgic pair', and if we want to be clear we can say 'of base k' as well. How about saying that if the lower number doubles when you read it backwards, then it's a 'nostalgic pair of memory 2', and similarly if switching the digits causes it to become a times itself, then it has memory a. We've dealt fully with the memory 2 case - now we can start to examine numbers with better memories! What about a = 3? If I hadn't given the game away last week, you might be asking whether memory 3 pairs exist at all, and the quickest way to prove they do is just to find one:

15₇ = 1*7 + 5 = 12₁₀ and
51₇ = 5*7 + 1 = 36₁₀.

Done! Expressed in base 10, {12,36} is the lowest nostalgic pair of memory 3. There's nothing special about the way I found any of these initial pairs, memory 2 or 3. For memory 2, I simply took the formula we deduced last week for the digits (x,y),

y = (2k - 1)/(k - 2) x,

and dived in to see what happened. You'll see exactly what I mean if you give it a try - some cases work and others don't. You spot a pattern in the ones that work and do a little more investigating to prove that intuition correct. We can't always be so lucky as to have the pattern roll out like that, but it's great when it does.

If you're not the sort to find yourself scribbling maths on any bit of paper you can grasp, hours after you were supposed to be sleeping, I may not be able to convince you of how much fun this process of exploring and discovering mathematical ideas is to us lost-cause types: the best way to experience it is to have a go yourself. If you're enjoying this story of nostalgic pairs (and I hope you are at least a little!) then I urge you to have a go at playing with these ideas on your own before reading on, since it's that process of 'maybe this will work... well ok, not quite, but what if I... ooh!' that really gives this rec-math stuff its flavour. If you do plan to experiment, avert your eyes now, because here's the corresponding table for pairs of memory 3:

k	x	y	Base 10 representation
7	1	5	12
11	2	8	30
15	3	11	56
19	4	14	90
...	...	...	...
4n+3	n	3n+2	(4n+2)(n+1) [any base]

Great - a whole new list of numbers, and another rule for constructing them. So we have {12,36}, {30,90}, {56,168}, {90,270} for our first few memory 3 pairs. Can you conjecture what the memory 4 pairs will look like? Hurry up - here they come!

k	x	y	Base 10 representation
9	1	7	16
14	2	11	39
19	3	15	72
24	4	19	115
...	...	...	...
5n+4	n	4n+3	(5n+3)(n+1) [any base]

So we get memory 4 pairs {16,64}, {39,156}, {72, 288}, {115,460} - easy. It goes on, and the general formula for pairs of memory a is:

k	x	y	Value
(a+1)n+a	n	an+(a-1)	((a+1)n+(a-1))(n+1)

I think that's pretty nice. So we're done, right? Well... not quite. Last week I explained why it wasn't possible to take one of the memory 2 pairs we'd found and divide or multiply both numbers by a constant to create a new pair. The issue was that the digits in memory 2 pairs have the form (x,y) = (n,2n+1), so if any number b>1 divides n exactly then it divides 2n+1 with remainder one, and that means (2n+1)/b isn't a whole number. But if we consider memory 3 pairs, their digits are (x,y) = (n,3n+2). There's a 2 on the end for that second digit now, so if n is divisible by 2, so is 3n+2. We can take any memory 3 pair whose n was even and divide the digits (in the specified base) by 2 to get a new pair. {30,90} with digits (2,8) (base 11) gives us {15,45} with digits (1,4). {90,270} with digits (4,14) (base 19) gives us {45,135} with digits (2,7).

We could do the same for pairs of memory 4, with digits (n,4n+3). Now whenever 3 divides n, we can not only divide all digits by 3 to get a new pair, but we can also multiply that result by 2 to get yet another one - the resulting digits won't be too big since we already divided by 3. So our pair {72,288} with base 19 digits (3,15) also gives us {24,96} with digits (1,5) and {48,192} with digits (2,10).

Since for any pair of memory a>2 the digits are (n,an+(a-1)), they all will admit some extra pairs for values of n that share common divisors with a-1. As it's only the case for certain generating values of n, and hence the bases (a+1)n+a, these bases and the pairs within them are something special - we'll call them 'memoir bases' and the pairs within them 'memoir sets'... because numbers in these bases have so many memories, they can write a book about them! Which are the most memoir-rich bases? They're the ones where the value of n used is equal to, or a multiple of, a-1, so they will only get larger and larger as the memory label increases. As for how many relatively memoir-rich bases we expect to see, that depends on how many factors a-1 has. Look at a detailed table for a = 7, for example:

k	x	y	Base 10 representation
15	1	13	28
23	2	20	66
	1	10	33
31	3	27	120
	2	18	80
	1	9	40
39	4	34	190
	2	17	95
47	5	41	276
55	6	48	378
	5	40	315
	4	32	252
	3	24	189
	2	16	126
	1	8	63
63	7	55	576
...	...	...	...
8n+7	n [highest for this base]	7n+6 [highest for this base]	(8n+6)(n+1) [for highest (x,y)]

That's a big memoir set for base 55, generated by n = 6, but because a-1 = 6 has two factors, not just one, there are also smaller sets for the bases 23, 31 and 39 generated by n = 2, 3, 4 (and more, if we carried on past n = 7). Maybe it's interesting to consider which bases have the most memoirs if you add them all up over many different memories. For example, base 55 gets 6 memoirs for memory 7, but also 2 for memory 3 (since for memory 3, base 55 is generated by n = 18, which is divisible by 2). We'll see! We've started to re-frame part of the study of nostalgic pairs in terms of factors. I wonder whether primes/biprimes will turn up? (ha)

I have to say I'm immensely enjoying experimenting with this growing concept of nostalgic pairs. There's much more I want to say, and I will in the future, although to prevent this becoming the Nostalgic Pairs blog I may break it up a bit! Food for thought, though: is every number a member of some nostalgic pair? Or a slightly different question: is every number a base for a nostalgic pair of a certain memory? How well can we predict and summarise properties such as memoir size?

By the way, if you weren't sure whether or not to believe me about grabbing any piece of paper for maths extemporising, here's the result [click to enlarge] of my finding only blank white envelopes around the home to use as scrap:

I figure the more I find myself doing this kind of thing, the less people will want to write to me anyway!

Nostalgic numbers - fun with numerical anagrams

As I battled to dry the tears running down my wrinkled face with facts about my latest age, there was a fleeting moment when I thought 'hey, when you double 26 you reverse its digits, don't you?'. Answer: uhh.... no (exercise: prove this). But I started to wonder whether any two-digit numbers did have this property, that switching the digits results in a number that's twice the original. Have a go if you like and see what you find.

The answer this time? Well, it's also 'uhh... no', but a slightly more impressive one. To prove it, notice that if our number is written with two digits, xy, then it has value 10x + y. We'll write (x,y) rather than xy to avoid confusion with multiplication. We want (y,x) to be twice (x,y), which means the following property must hold:

10y + x = 2(10x + y) , so
10y + x = 20x + 2y,
8y = 19x,
y = 19/8 x.

We can see that x needs to be divisible by 8, or y won't be a whole number. So x must be at least 8, but then y needs to be at least 19. What does it mean for a digit to be greater than 9? Not much! There can't be any pairs of digits (x,y) that satisfy this equation. Bam.

[I initially wrote a different proof of the above, which I'll post as a comment below.]

On first glance, that's a shame, but on second - not really. There's something much more interesting going on behind the scenes, namely that if we choose to work in a different base, it is possible to find solutions. Quick base primer: usually when we write a number, it's code for adding powers of ten together to represent a quantity, for example

217 = 2*100 + 1*10 + 7*1.

But we don't have to use ten as the base: for instance, since

217 = 4*49 + 3*7 + 0*1,

we could write the same quantity as 430₇, which we call the 'base 7' representation of the number. 'Binary' refers to the base 2 representation; 217₁₀ in binary would be 11011001₂. Mathematicians don't like numerical statements that are dependent on an arbitrary label such as the number's base representation, unless that notion can be generalised to all bases. If we had found solutions, but only in base 10, we would still be missing infinitely many others!

Let's get ourselves into a more general mood here. In base k, the number with digits (x,y) has value kx + y, and we're looking for numbers with the property that

ky + x = 2(kx + y).

Expand this out, rearrange (as before) and we're left needing

y = (2k - 1)/(k - 2) x.

The problem is now just a matter of finding the values of k, x and y that solve this equation. To get the ball rolling, one solution is (k,x,y) = (5,1,3), i.e. in base 5, the number written '31' is twice the number written '13'. Indeed, we find that

13₅ = 1*5 + 3 = 8₁₀ and
31₅ = 3*5 + 1 = 16₁₀ = 2*8₁₀.

Since I initially had decrepitude in mind when thinking about these, I've decided they should be called 'nostalgic pairs', which to me evokes images of the larger number gazing into the mirror (calibrated to a certain base!) and seeing its old self, half its current age, reflected back. The table shows the lower halves of a few more nostalgic pairs and a general rule for constructing the rest. The rule is fairly easy to deduce once you notice a pattern, and you can check it's correct by plugging it into the above formula.

k	x	y	Base 10 representation
5	1	3	8
8	2	5	21
11	3	7	40
14	4	9	65
...	...	...	...
3n+2	n	2n+1	(3n+1)(n+1) [any base]

So the first few nostalgic pairs, expressed in base 10, are {8,16}, {21,42}, {40,80} and {65,130}. Although 130 is three digits in base 10, in base 14 it's only two: 94₁₄. You can see that the list goes on: there are infinitely-many two-digit nostalgic numbers and the second digit and base are entirely determined by the first digit. Note that we can't construct, say, the digits (2x,2y) from (x,y) in this table and have a solution for the same base, since 2y would be (4n + 2), larger than the base it's supposed to be written in. Similarly we can never divide (x,y) by some constant to find a smaller pair of digits, because if a number were to divide x = n, it would always leave a remainder of 1 when dividing y = 2n + 1. There's a little more work involved in proving the above ratios between x and y are the only solutions and it's more fiddly than interesting, so I'll omit it and leave it for you to do if you're really keen.

It gets better! Why stop at doubling numbers to reverse their digits? What about numbers that flip when you triple them, quadruple them, and so on? They also exist, also in infinite quantities, and although the situation is similar there's a few extra things to say about them (as well as more cute names to give them, of course), which I'll leave for another week. I'm also pleased to report the first three-digit nostalgic pair, which took me a little while, but starts with the base 5 quantity:

143₅ = 48₁₀, which is double 341₅ = 96₁₀.

Awesome.