New Wikipedia sized proof explained with a puzzle

Articles, Blog

New Wikipedia sized proof explained with a puzzle

New Wikipedia sized proof explained with a puzzle


Hello, everyone. There’s been some maths in the news this week with these headlines: “Wikipedia-size proof too big for humans to check.” So, a Wikipedia-size proof– hopefully more accurate than Wikipedia. But what did they do? Now, I’m going to explain to you what they proved this week, and I’m going to do this through a puzzle, and it’s going to be a puzzle that we can all play, we can all solve at home, and you won’t need a Wikipedia-sized proof to do it. So, let’s start. So here’s my puzzle. All right. So, there you are. Behind you, two steps behind you, is a cliff. Two steps in front of you is a nest of angry snakes. And not just any old angry snakes, but, like, snakes with really bad breath and stuff. So, your torturer tells you that you can go free if you can write a set of twelve instructions that you have to follow without falling off the cliff or being poisoned by the snakes. A move is either one step forwards, or one step back. But your torturer warns you that he might decide to make you follow every second instruction– instruction 2, 4, 6, 8, 10, 12. He might make you follow every third instruction, or every fourth instruction, or every fifth instruction, or every sixth instruction–bop, bop! Can you write a set of instructions that will keep you safe? Now, if you want to try this puzzle, do it now–pause the video or something, because I am going to talk about the solution after this flash. Flash. [snaps fingers] So hopefully you’re ready for the solution now, because this problem is actually one of those impossible problems. So give it to someone you don’t like. Now, how can we prove that this is impossible? Let’s try that out. So we’ve got twelve instructions to fill in. OK–so one to twelve. So let’s start off with– let’s say we start off with one step forwards, because why not? So we’re going to start with one step forwards. Now, our next step is going to have to be a step back. We can’t have two steps forwards, because we’ll end up in the nest of snakes. So our next step has to be a step back, which I’ve put in there with a minus one. Now don’t forget, our torturer can make us follow every second instruction. If he does that, then you’ll start with instruction two, then it’s instruction four next. So instruction four cannot be a step back, because you will have two step backs, falling off the cliff. Instruction four, you’re forced to find out, that it’s a one– you’re stepping forwards one place. So I can write that in like that. But we can do the same again with the eighth instruction. If the torturer makes you follow every fourth instruction, then you don’t want to go forwards twice. So number eight is actually a step backwards this time. So we can fill in all those instructions. Those all come for free. Now let’s fill in some of these gaps. Let’s fill in the gap there in the third place. Well, let’s see what we’ve got here. Step forwards– step back– it can’t be two steps forwards next, so this one, number three, has to be a step back. So I’ll fill that in. So we’ve got minus one there. Now again, you could follow every third instruction, which forces you to deduce that the sixth step must be a step forwards. It must be a plus one. I’ll write it in. So we’ve got plus one there for the sixth step. And then, by the same logic, if you follow every sixth instruction, you can’t make two steps forward, so number twelve is a step back–it’s a minus one. I’m going to write that in, as well. There we go–minus one. Now, what else can I fill in? I can fill in this gap here with the five. Step forwards–step back–that’s OK. Step back–step forwards– we can’t have two step forwards here, not in a row, so number five has to be a step back. Number five is a step back, and then automatically you get number ten. Number ten will be a step forwards. So that will be with a plus one. Let’s see if we can fill in these remaining gaps. Uh–I think, let’s see– step forwards–step back– step back–step forwards– step back–step forwards–looks fine to me. We can’t have two step backs here. This must be a plus one. Let’s fill this in. And in the same way, number nine here is a minus one. And number eleven is a plus one. So you fill in these instructions. Now, all of this was forced on me–there was no free choice here. But, if you look at every third instruction– so at three, six, nine and twelve– you go step back–step forwards–good. Step back– step back again– whoops-a-daisy, fall off a cliff. So you are forced to fall off a cliff. These were the only instructions that you can really come up with, and still you will die. So you’ll find out that it’s an impossible problem. But, this is quite nice– if I remove the last step there, number twelve, so we just have the first eleven steps, then those instructions do work. Those eleven instructions will keep you safe. So if you want to give this puzzle to someone you like, ask them to give eleven moves, instead of twelve. So that’s what happens when the cliff and the snakes are two steps away from you. So what would happen if the cliff and the snakes were three steps away from you? How many instructions would your torturer force you to write so that he can guarantee that you’ll die? So this was an open problem, but it was solved this week by these two guys from the University of Liverpool, and they worked out that the solution is 1,161. So if your torturer makes you write 1, 161 instructions, then he’s guaranteed to have at least one subsequence that will topple you over the cliff with three steps. Now, that does also mean that there is a sequence of 1,160 that will keep you safe. And here’s one of them. [music plays] So to prove this result took them six hours using computers. They didn’t say how many computers they used, but they generated a 13 gigabyte file, which they compared to Wikipedia, because apparently the text for Wikipedia is a 10 gigabyte file, and they claimed it was the longest proof ever. It’s an example of a computer-assisted proof. It looks like a clever kind of brute force. I tried to read the paper, but I’m not a computer scientist myself, so I didn’t quite get it. So if you want to read the paper, I’ll put the link in the description. Now, what we’ve shown is if we have the cliff two steps away, we can kill the guy. If we put the cliff three steps away, we can kill the guy, if we have a long enough sequence. So is this always true? Is this true for any number? This is called Erdős Discrepancy Problem. It was proposed by the Hungarian mathematician Paul Erdős in the 1930’s. These guys from the University of Liverpool are already working on the next step. So imagine the cliff now four steps away. They’re trying to work out how many instructions you need to guarantee that you can kill this guy. But we’re going to need a smarter way to solve it in general. We can’t just check every number in turn. So why do this? Well, I could talk about discrepancy theory, and wireless communication, and cryptography, and applications like that. But the real reason we do it is because it’s a hard problem, and the methods we develop to solve this problem could then be used in other problems. Perhaps more important problems. It adds to our knowledge of the world. Now, they are working on the next step. Imagine the cliff four steps away from you. They haven’t yet found what length sequence you need to guarantee to kill your victim, but they have found a sequence of 13,700 that will keep you safe. So any subsequence will never be longer than four, so you can avoid the cliff, and you can avoid the snakes. I’m going to show you what that sequence looks like. It’s going to scroll past. It’s going to take about a minute. So, for now, if you have been, thanks for watching. [music plays to end of video]

100 thoughts on New Wikipedia sized proof explained with a puzzle

  1. okey, but will our captor see the instructions before he tells us, whether to follow every 2nd, 3rd, 4th. ???
    If not, we could go psychological. Either we assume he does not know that in this "best possible result" only "every 3rd" does not work, and we go for it, hoping that he will say different number (1,2,4,5,6, saying any higher number would be really stupid of him, since it would execute only one instruction :))
    Or we assume that he knows that, so we make less-good set of instruction, that does not work for more numbers, but works for 3.

  2. As someone who owns the entire text of wikipedia in .txt files, I can confirm that wikipedia was 11,777,750,982 bytes (about 10.9GB) as of the time it was downloaded.

  3. he said nothing about doing away with the torturer. I'd overpower the torturer, feed him to the snake. while the snake is busy with the torturer, i'd grab the snake by the tail and toss the snake off the cliff leaving one poisoned (and subdued) torturer to also toss off the cliff.

    * dont we have enough exercises in futility in the world without this blokes example?!*

  4. It seems to me, at first glance, that this problem is unseparable from other problems involving the prime number theorem.

  5. Mathematician Terrance Tao has proven that there is always a certain number of instructions to guarantee death no matter how far apart the 2 deathpoints are.

  6. Damn it. I spent 20 minutes trying to solve it in excel before realizing it probably couldn't be done.
    Here's the spreadsheet I used if anyone wants to play with it:
    https://docs.google.com/spreadsheets/d/1yyjL0drxIuEn0Cl8hC6w-G_HYaGSgQ_mAXjvBVG35ck/edit?usp=sharing

  7. It's like in the old Czech movie 'Baron Prášil', where the protagonist, descendant of Baron Munchhausen, dramatically narrates how he was surrounded by bears on a narrow bridge over a chasm.

    Baron: So consider this: a bear in front of me, a bear behind me, me in the middle, and below me a chasm.
    Butler: So what did you do?
    Baron: What was I supposed to do? I got myself eaten!

    (But the ghost of the old baron, which caused a plate to fall down from the wall whenever somebody told a lie, was polite enough to wait until the end of the story.)

  8. Will there always be a number of steps in which you can't avoid being killed, even with arbitrarily large numbers of safe steps between snakes and cliff? I guess I will have to check OEIS daily now 😄

  9. there are only 2^12 possible sets of instructions
    couldn't we easily prove that its impossible by testing all 12
    edit: i just watched the rest of the video

  10. The minus signs at the last sequence, when appearing at least 3 in a row, bend downwards, like an smile. But not if you look specifically at them. Nothing to do with the proof but funny

  11. You put your left foot in one step, you put your left foot out one step, you put your left foot in one step and you shake it all about . . .

  12. The 12 step puzzle that you gave us is actually possible, just start at -1 and go from there. You never said that you have to start at 0

  13. Honestly I think the torturer giving you 1160 instructions (as opposed to the 'necessary' 1161) would be even more sadistic.

  14. Apparently the general problem is settled now, just one year later. https://www.quantamagazine.org/terence-taos-answer-to-the-erdos-discrepancy-problem-20151001/

  15. This problem is related to the "run length limit" problem, where you in a binary sequence you want to limit the maximum (and also minimum) number of 1's and 0's in a row, while also controlling the "DC component" of the waveform. (Could Fourier analysis do this better?) I did this for a 16-bit block code, and had to resort to a brute-force approach. It took a 1MHz controller 1 month to go through all the possible sequences (with all possible bit-orderings) to get an acceptable code set. What you are saying is what I suspected: there is no "short cut" algorithm (like the traveling salesman problem). How were the run-length limited codes developed for the CD standard?

  16. Choose step one 1 step forward
    then step 2 must be -1 as you say
    then by the jailer step 4 must be 1 step forward
    this already leads to a contradiction and you may stop as the jailer from 1 might skip to 4 and 2 steps forward into the snakes,
    therefor insoluble

  17. "We're just a few steps away from proving the general Erdős discrepancy problem. Oh no, watch out, a cliff! Aaaaaaah…"

  18. "Alright, here, let me give you this problem, pause the video and try it out!"
    "Alright, so there's no solution, this is one of those problems I only give to people I don't like."

    🙁

  19. Who says that Wikipedia isn't accurate? All you have to do is check all of the 200 cited sources along with all 100 authors that edited the page for reliability! Simple!

  20. I paused this video for 5 years trying to figure this out… I unpause it AND HE SAYS ITS IMPOSSIBLE!?!?! WTH

  21. Stop translating video titles in diffrent languages, please! "Neuer Wikipedia grosser Beweis erklärt mit einem Rätsel" is neither good German nor is the video content in German!

  22. The two step solution to survive is an odd number, the three steps solution to survive is even, how much do you want to bet the survival solution to a four step problem will be odd?

  23. When the 4-steps partial solution scrolls past, the sequences of minuses look like they are curved, optical illusion!

  24. Move right, move right, move right, move right, move right, move right, move right, move right, move right, move right, move right and finally move right.

    Just saved your life, you're welcome

  25. Mathematicians make propositions and are remembered forever. I make propositions and get slapped in the face.

  26. 7:30 if we have the cliff two steps away we can kill the guy, if we put the cliff three steps away we can kill the mathematician

  27. 1. Jump.
    2. Jump.
    3. Jump.
    4. Jump.
    5. Jump.
    6. Jump.
    7. Jump.
    8. Jump.
    9. Jump.
    10. Jump.
    11. Jump.
    12. Jump.

  28. Guy: make a sequence of 30'000 an you will live.
    Me: I would rather jump of a cliff as write a so long sequence.

  29. So the problem is as i understand it in (m) moves what is the longest sequence you can have without surpassing (+/-n) where no subset of the sequence also surpasses (+/-n)?
    And (m=+1or-1)

  30. why there should be a number of steps except infinity, where you can not "kill the guy" with big enough set of instructions? assuming he can live forever of course 9_9

  31. 7:50 Everyone keeps calling him Paul "Urdish", and yet, we are expected to have perfect English diction. 🙁

  32. What if the guy just wants to die? 2 steps forward seems like a sensible idea. No more worrying about jigsaw amusing himself on your behalf!

  33. So every sixth step is the maximum (every step)? So there won't be a condition to follow every 7th step, is that correct? Thank you.

  34. The most impressive thing here is the fact that all of wikipedia is only 10GB. I would've guessed WAYYY more…

  35. Actually, it all depends on what a person would call an instruction.
    If the instruction is "aim at the next place which is 0 or 1 step from the center", then no matter how the torturer unfolds the set of instructions, we'll always be safe.

  36. A wikipedia-sized proof partially solves Erdos Discrepancy Problem

    Terence Tao: Hold my glasses

    Well, Tao did it with the help of other people, especially Uwe Stroinski, but he was the man who finally solved it.

Leave a Reply

Your email address will not be published. Required fields are marked *