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.

Continue reading

Posted in Elementary | Tagged | 2 Comments

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.

Posted in sillyness | 3 Comments

As you know, there exists a bijection \varkappa: [0, 1]^2 \mapsto [0, 1]. Cantor demonstrated that. You even know how to construct this bijection: if x, y \in [0, 1] and their decimal expansions are x=0.x_1 x_2 x_3... and y=0.y_1 y_2 y_3... then \varkappa (x, y)=0.x_1y_1x_2y_2x_3y_3.... 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 \varkappa(x, y) 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 \varkappa 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.

Posted in Math, pretty pictures | Tagged | 1 Comment

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.

Posted in Math | Tagged | Leave a comment

Fun with restrictions

If f: A \mapsto B is a function, let us call f: a\subset A \mapsto B a restriction of f to a. Let’s analyze one nice and pretty surprising fact concerning restrictions.

Fact: Suppose we have a function of two variables f(x, y) and it’s restriction to every straight line going through the origin f(l_1t, l_2t) has a strict local minimum at t=0. This does not necessarily imply that f 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: z=(x^2-y)(y-x^2). Verifying that a) this function does not have a local minimum at [0, 0] and b) (l_1^2t^2-l_2t)(l_2t-2l_1^2t) has a local minimum at t=0 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: z=(x^4-y)(y-x^4). Now, we could take not one, but two families of lines, each completely covering the plane – all the straight lines x=l_1 t, y=l_2 t and all the parabolas x=t, y=ct^2, 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 exp(1/x^2), but then  we would have to dance the singularity-patching dance, and that’s boring.)

Posted in Math | Tagged , | Leave a comment

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:

\displaystyle z= \left\lfloor \mathrm{mod} \left( \left\lfloor{\frac{y}{7}}\right\rfloor 2^{-7\lfloor x \rfloor - \mathrm{mod}(\lfloor y \rfloor, 7)}, 2 \right) \right\rfloor

in the region, say -10 \leq x \leq 150, n \leq y \leq n+8, where n=


Step 2. Existential terror.

Continue reading

Posted in Math, sillyness | 1 Comment

This is Tupper’s Self-Referential Formula:

\displaystyle \frac12 < \left\lfloor \mathrm{mod} \left( \left\lfloor{\frac{y}{17}}\right\rfloor 2^{-17\lfloor x \rfloor - \mathrm{mod}(\lfloor y \rfloor, 17)}, 2 \right) \right\rfloor

what makes it interesting is that the set of points [x, y], for which the inequality holds, in the rectangle 0 \leq x \leq 106, n \leq y \leq n+16, 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:


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 106 \times 17 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:


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)

Posted in Math | 3 Comments