I wanna love you, but I better not touch

Here’s a classic puzzle: you are a rather evil King. You have 1000 bottles of wine. Exactly one is poisoned. You need to find out which one. You have 10 prisoners. You can use them to test the wine.
Now, to make the problem more difficult: poison takes effect only after 10 hours, and you need to find the poisoned bottle within a day. (If the poison worked instantly, you could easily find the poisoned bottle by making just one prisoners test them all one by one. If you had unlimited time, you could cut the number of bottles in half while using just one prisoner by making him test half of the bottles, and it would be enough with 10 to find the right one. But you do not have time for this.)

You may stop here and try finding the solution on your own, if you want to, but the puzzle is considered hard, and it will most likely will take time. My intent is to simplify the solution a bit, and make it more transparent.

I was very excited to learn that there is a song titled Smooth Operator. Unfortunately, its actual content turned out to be very disappointing. Pity. We need more songs about smooth operators. And dense sets, and Banach spaces.

As you know, there exists a bijection . Cantor demonstrated that. You even know how to construct this bijection: if and their decimal expansions are and then . It may be slightly more complicated than that, because in order to get a honest-to-god bijection you’ll need to somehow get around the fact that two decimal expansions may correspond to the same decimal number (for example: 0.999…=1), and it may get tricky, but it’s very doable.

You already knew all of this, or nearly all, but have you ever wondered what does the plot of look like? Well, wonder no more:

What do we see here? First, the surface, or whatever you want to call it, is a fractal. It’s asymmetric, because is asymmetric with respect to its arguments. each of its level-sets consists of a single point, and it’s easy to see why. You may also notice that I cheated a bit, and this is not really the plot of the function I described in the beginning – instead this is a slightly modified version that uses binary expansions instead of decimal ones. It makes no difference in theory, but the plot looks better this way.

Outside In

Yes, yes, you have already seen this highly awesome video and you are aware of Smale’s paradox. But for as long as there is a possibility, no matter how remote, that some poor soul out there doesn’t know about these things, I am not taking any chances.

Fun with restrictions

If is a function, let us call a restriction of to . Let’s analyze one nice and pretty surprising fact concerning restrictions.

Fact: Suppose we have a function of two variables and it’s restriction to every straight line going through the origin has a strict local minimum at . This does not necessarily imply that has a local minimum at the origin.

Funny, isn’t it – all the (straight) roads lead down, and yet you are not on top.

Counterexample: . Verifying that a) this function does not have a local minimum at and b) has a local minimum at is trivial, boring, and will be left as an exercise for the reader.

What’s going on here? Let’s plot this function:

Well, maybe this time it doesn’t help much. But if we look at this surface above, it will make things more clear:

What we have here is a kind of a distorted saddle at the origin (big black point). The function is equal to zero there. There are points where the function is positive (red region) in every neighborhood of the origin, no matter how small, so it’s definitely not a local maximum. But at the same time, every straight line going through the origin will have to cross the blue region (where the function if negative) before it crosses  the red region, and therefore the restriction of a function to that line will have to decrease for a little while and will have a local minimum. No matter which straight line you chose, you can’t get to the red region before you get to the blue one. Now, if you were allowed to choose a parabola…

But even then I could modify the example so that even parabolic roads wouldn’t help. I think you can now guess how – by replacing squares with 4-th powers: . Now, we could take not one, but two families of lines, each completely covering the plane – all the straight lines and all the parabolas , and still all the restrictions would have strict local maxima, while the function itself wouldn’t. (We could take this even further, by using such functions as , but then  we would have to dance the singularity-patching dance, and that’s boring.)

This could be the scariest prank ever, if I had someone to play it on:

Step 1. Trick the victim into graphing this slightly modified version of Tupper’s Self-Referential Formula:

in the region, say , , where n=

381025769433284440392319964900539302335
336506037124716737876327885349255244053
654529126222910795091774837392244419620
805572082941110711057252345724567742835
679828220923525384477934725633019757953
249733463908820850208792361145516746285
337177182564212162731442.

Step 2. Existential terror.

This is Tupper’s Self-Referential Formula:

what makes it interesting is that the set of points , for which the inequality holds, in the rectangle , , you will get this:

Turns out that the graph of the formula resembles the formula itself, which at first sounds pretty incredible. Oh, wait: I didn’t specify the value of n. It should be equal to:

960939379918958884971672962127852754715004339660129306
651505519271702802395266424689642842174350718121267153
782770623355993237280874144307891325963941337723487857
735749823926629715517173716995165232890538221612403238
855866184013235585136048828693337902491454229288667081
096184496091705183454067827731551705405381627380967602
565625016981482083418783163849115590225610003652351370
343874461848378737238198224849863465033159410054974700
593138339226497249461751545728366702369745461014655997
933798537483143786841806593422227898388722980000748404719.

Read more about it in Wikipedia.

I spent a couple of evenings trying to figure out how does it work, and intended to write a long post about it, but I see that it has already been done here much better than I could, so I’ll only give you the main idea: the graph of the formula contains all possible combinations of pixels of size and what you need to do is to locate the right fragment of the graph by choosing the value of n. Fortunately, the formula is constructed in such a way that it can be done rather easily. For instance, if you set n to be equal to:

770137614616740349659457383109219250729889213023196245
754997397474539522884572693040838328048207848222847384
255800207585680609541957604841348860558024608884092791
814186507612666983299083984568308963916568266347954249
445046515417964282372279838338100838479512127675315663
107944860681436794491747199511098181076928

you will get a fragment of the graph saying “hello world!”. (Oh, and it will be upside down, as pointed out in the blog post I already mentioned)