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!