don't do that if you do they'll buly a smart kid to solve it and when the kid tells them the victim must always die they'll make it in real life where you're the victim
i really like how you give us a chance to work at the problem before telling us the answer, it was so rewarding to deduce it was impossible myself first :D
Thanks for explaining this in such a way. before that by reading articles, didnt really understood the problem. but without this puzzle explanation ,i still wouldnt be able to understand it again
"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." Well apparently you did, because your explanation is almost EXACTLY the approach the paper takes :-D The automaton is an imaginary machine that reads and executes the instructions it gets. Each instruction brings him to a new state, left or right from its current state. If an instruction takes the machine further than C steps in one direction (C=2, so 3 steps or more) it goes to S_B (the state at the bottom of the cliff) where it can never recover from. The automaton is for all intents and purposes the guy in your torturous trap. The phi-formula is a Boolean representation of this automaton and basically says: For a given instruction sequence length L and a discrepancy C and obeying every d-th instruction: You start in the middle (S0) AND each instruction to go right moves you one step to the right AND each instruction to go left moves you one step to the left AND if you are on the right edge and get an instruction to go right, you die AND if you are on the left edge and get an instruction to go left, you die. The second phi-formula says: You don't die AND you try the game for every possible instruction gap AND you obey the rules (you don't move without getting the instruction to do so) Now, this second equation is fed into a SAT-solver (satisfiability-solver) which tries to find the sequences of instructions that keep you safe. It does this in exactly the same way you do: It fixes one instruction (you fixed the first) and deduces everything it can about it. When deduction doesn't yield a complete instruction sequence, the SAT-solver chooses an undecided instruction and fixes it once in each direction (brute force) When contradictions are deduced, the SAT-solver learns what caused these contradictions, and uses this information to prune the search space (so: a clever kind of brute force) They did this clever brute force SAT-solving for several different instruction sequence lengths until they found that no sequence of length 1161 satisfies the equation and thus will certainly get you killed, but at least one of length 1160 does satisfy the equation and thus is able to get you out of your predicament safely. They did change the encoding of the automaton states to eliminate a sparse matrix. And this would most certainly affect the speed of the SAT-solving drastically but it doesn't change anything fundamental to the proof. I really enjoyed the video and I'm glad I read the paper too. It's nice to see that some computer science concepts can be explained so simple. And it's funny how smart people such as yourself sometimes don't realise how close they are to understanding these concepts. You may think you only explained the problem and a simple strategy to solving it (you didn't even need much maths) but you actually explained how the proof worked in rather great detail :-D
Oh this is great. Thank for this full explanation, and it's nice to see that the computer is doing what I would do with pen and paper in slightly different language.
Haven't watched the rest of the video yet, but I think I'm about to give up. Here's my progress: I've broken it down into a Math(s) problem by giving "move forward" a value of 1, and "move backward" a value of -1. I then input my instructions into a spreadsheet. On a separate cell, I retrieved the total sum of the columns. If that cell's absolute value is greater than or equal to 2, the cell background goes red, indicating a failure. Of course, I can't just test for that, so I also tested for numbers divisible by 2,3,4 and so on. Then, I realized that the sum of the steps must also never reach 2 (or -2), so I entered several tests for that. I've managed to find some close ones, but it seems that most of the movements are set. For example, 6 must always be the opposite of 12, 1 must be the opposite of 2, and so on. There are only a few values where variations actually matter. I still can't find a perfect solution, and any time I believe that I've reached a solution, I end up discovering another fail condition that I've forgotten to test. I'm almost convinced that this puzzle is impossible, but I'm not a Math(s) genius, so it's more likely that I'm just missing something, somewhere. My best solution, thus far, is this: _back, back, back, back, back, back, back, back, back, back, back, back_ This will ensure that you fall off the cliff. Although I'm not scared of snakes, I _am_ quite frightened by halitosis.
So, I just watched the rest of the video. I don't want to admit how long I spent trying to figure this out. I even wrote a small program to try and solve it. I blame the Dunning-Kruger effect. I know just enough to _suspect_ what the answer might be, but not enough to actually commit to that answer. I'm still trying to work out the minimum number of conditions that one has to test for in order to make a program to test potential solutions to this problem. I'm also looking at means of making the current test conditions more efficient or eloquent. So I learned a few new programming tricks, and that makes it time well-spent. Anyway, considering what he said "after the flash", can we infer that James doesn't like his RU-vid viewers? :)
I will remember that 13700 sequence so that if I am ever put in that situation with a torturer putting me 4 spaces away from harm (either side) and make me write a 13700 sequence, I will survive that.
You mean I just spent the last hour writing a program to calculate every possibility only to turn up with 0 applicable solutions *_just_* to be told two seconds later in the video that this is an impossible problem?... Fuck my life...
+Kaitlyn Amanda so basically it had to test 2^12 different scenarios for each of 6 different styles (every, every other, every third, every fourth, every fifth, every sixth). How long did it take to run?
Ryan Koski It could calculate this specific puzzle in a couple seconds, not too difficult. Adding more steps exponentially increases the calculation time, however, but I wasn't going for speed. My method was a brute force method, but I could have designed it to be more modular with more thought, using a similar method as to how he explains how to know whether it's true or not.
Please do not perpetuate the myth that Wikipedia is inaccurate. While it is not something that you would want to quote in an academic paper, it is well curated and for the most part very accurate.
I love how enthusiastic you are about math and logic. Like a sneeze it's contagious. I wish more people understand the beauty and the art of math. Most people I see today couldn't care less about math, because they have a computer that does the logic and calculations for them. They don't understand the importance and are like zombies when it comes to making decisions. They do whatever the computer tells them to. They do not understand that the person that made the software/hardware uses math. I had a friend watch this video recently and he turned it off half way through. He told me that the computer will do the math for us, lol. I think he got a headache too, probably he had the computer think for him his whole life. The older generation appreciates the math, they call it the "foundation of understanding/life"; which I agree. You have encouraged me to go back to school to continue my undergrad studies in mathematics (dropped out before). Keep up the good work, and keep posting videos. Excuse any grammar or spelling error, English is not my best subject.
Does anyone notice that at the end the dashes in between the plus signs look to me to be curved downwards as they scroll up? Like if it was a rope held by the plus signs. Pretty cool optical illusion!
btw, the sequences are valid brainf*ck-code. You can compile with a bf-compiler to an executable which ACTUALLY DOES what the sequence is meant to be: it moves (the pointer in memory) forward and backward... esotheric programming languages... an interesting topic for a computerphile-video, isn´t it?
You sort of forgot to mention that it is an easy problem to solve, but a hard problem to solve efficiently. It is not hard at all to write a program that solves this problem, but it would take an awful lot of time using a brute-force approach. The SAT solving approach used by the authors is smart approach compared to brute force, but SAT-solvers are still far from efficient (they're still NP-hard programs).
As an interesting (and belated...) extension to the original puzzle: if your torturer is a little more generous and says that the gap between the instructions he makes you follow will be a power of 2 (so you'll have to follow every step, or every other step, or every fourth or eighth step, etc) then you can survive no matter how long a list of instructions he makes you write, even if the snake and cliff are only 2 away from you. Moreover, the sequence you (have to) use has a name - the Thue-Morse sequence. It has some weird self similarity properties. en.wikipedia.org/wiki/Thue%E2%80%93Morse_sequence
I realized at 1:20 that your accent reminds me of the cabbie in _Sherlock_'s "A Study in Pink". Specifically the part where he says, "Is it a bluff? Or a _double_ bluff? Or a _triple_ bluff?"
singingbanana Well, to an English person I'm sure they must sound a lot more distinct, but I'm not English, so to me they sound very similar. XD But it's mostly at 1:20 that a sense of similarity strikes me, since it's not just the accent but the words and intonation. XD
And when quantum computing becomes a thing, proofs like this will be commonplace. Next up a version of Windows that actually works. That may be a bit trickier though.
The next number in sequence could be very, very large. However, my intuition tells me that regardless of how many steps the torturer leaves on either side of you, he can make you walk off the cliff or into the pit of snakes in a finite number of moves. Now I'm off to wikipedia to read about this problem.
I'm not convinced with the "we do it because it helps the world" argument. Admit it. We do it because we want to do it and someone wants to see us do it and will pay for it. That sounded better in my head.
partha sarathy i agree with Christophe L, he was presistant to find the solution not because he thought it would help the world or might actually thought it would, but he did mainly to satisfy his curiosity.
Ko Kaian Wow, I don't know where you got that from; you'll need to brush up on your reading skills. All I'm saying is that we don't need additional incentives to discover things and make science other than it makes us feel good. The fact that it helps the world is just a nice side effect. Partha Sarathy got it right.
From Newton's Law of Gravity to the Black-Scholes model used by bankers to predict the markets, equations and math problems, are everywhere - and they are fundamental to everyday life.
1:stand still 2:follow the instructions 3:stand still 4:follow the instructions 5:stand still 6:follow the instructions 7:stand still 8:follow the instructions 9:stand still 10:follow the instructions 11:stand still 12:follow the instructions Maybe?
I was having some insomnia issues. Thanks for helping out with that. I'll replay and see if I can stay awake. Not being snarky, I was really having trouble sleeping. You must have a soothing voice.
What makes you think so? I would be very suprised to find some kind of multiplicative structure in the boundary. Also when have primes ever been fundamentally involved in combanitorial problems? One can think of the sequence of +1 and -1 as a 2 dimensional random walk, and nothing I know about random walks uses primes. But: I am not very literate in these kind of problems. If you could give me a combinatorial problem involving prime you would really make my day, since I love primes =D
tabularasa0606 You're thinking about Eratosthenes's sieve. But this problem really isn't related to that. This problem involves taking the sum of element whose index is a multiple of N while Eratosthenes's sieve involves ignoring multiples of N (excluding N).
Alcesmire Ah, yes that's the one. There are similarities, since both revolve about the tables of multiplication. You need either the sum of the elements at that position or you remove that element from the list of possible primes.
I believe the solution to the erdos discrepancy problem would necessarily be a fractal equation. That is, an equation that results in a self-related data set that has a non-repetitive progression.
+singingbanana I'm just wondering, is there someone who's working on the same problem, but in two dimensions? So instead of two steps forward and two steps back, you would have 2 forward, 2 back, 2 left, and 2 right?
Yes there's no difference. Moving right could, without loss of any generality, be considered the same the same thing as moving forward (and left the same as backward).
I think you're safe then, because when you get stuck in one dimension, you can repeat the process in the second dimension, then you can go back to the other dimension when you're stuck in the second, the real question is, how would you do it efficiently, as when you rule out moving in one direction, you still have 3 other possible solutions
Thank you for all your work on this channel and numberphile and thank you for commenting on our lecture blog by professor Weber on non transitive dice! You're one of my inspirations and I hope you lecture us one day. I'm a IA mathmo at peterhouse if you were wondering.
The original problem is 1-dimensional, being only a line. If you were to scale it up to 3 dimensions, you're then dealing with a 4x4x4 cube with 36 hazardous surface vertices and 24 safe interior vertices. The central vertex has 6 paths in which to move, the 6 vertices branching from each of the central vertex has 5 safe paths, the corner vertices have 3 and the edge vertices between each corner has 4. Unless there are further limiting rules for movements, there is literally no end to the possible number of safe movements. So, this was just a long-winded lead-up to say that your question was stupid.
Leif Anderson Not a stupid question, but a long-winded lead-up to a stupid answer. :P You wrote "there is literally no end to the possible number of safe movements" after clearly numbering the finite amounts of safe moves from every vertex. Did you not read what you typed? :) You could create as complicated path as you wish, to keep safe, but the torturer could still mess that up by taking every other instruction, every third, and so forth. Idealldeas100 seemed to think about how the complexity of the problem would increase, and in what way that would affect the result. The added dimensions would allow the person a far longer sequence before they perished, but i have no idea about the order of magnitudes higher that would be.It may be as easy as adding the same number of safe steps for every axis, thereby making the answer exactly three times that of the original answer.
Since we know that you have to have the pattern 1, -1, -1, 1 to start with, we have to realize the pattern must be the same for if we're counting by 2s or 3s or 4s, so you can calculate 6 must be a step forward, and 8 must be a step back. 9 must be as step forward, and 12 must be a step back. So 1 -1 -1 1 e 1 g -1 1 j k -1. Now if we look at the pattern by 2s, we have -1 1 1 -1 j -1, which means that J must be a 1. But if it's a 1, then the e and the g have no real way to prevent you from being fed to the snake, when we're left with 1 -1 -1 1 e 1 g -1 1 1 k -1. We also know that to survive the longest, we have to make e=-1. So the pattern is 1 -1 -1 1 -1 1 g -1 1 1 k -1. If g is -1 then h kills you, and if g is 1 then j kills you. You have no way of guaranteeing survival.
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.
singingbanana OMG you replied to me!! I have to say you are my inspiration for just about everything but mainly math...and hopefully one day in my life i want to meet you and ask you many many math questions...thank you :)
" One of the sequences of length 1160 of discrepancy 2 can be found in Appendix A for reader’s amusement." i love the paper thanks you for this video, showing again how we can work on problems using computers
for the problem with 2 steps the critical instructions are 12 = 2x2x3 for the problem with 3 steps the critical instructions are 1164 = 2x2x3x97 Also the maximum possible instructions are 11 (for 2 steps), 1163 (for 3 steps) are also primes. My guess is the for 4 steps the critical instructions will be 2x2x3x97xP where P is a prime, one or two orders of magnitude greater then 97.
Some Random Fellow *450 yard drop into shark-ridden sea and spiky rocks* *No shore for literal days* *No shelter, food source, anything* Yeah whatevah bro
ilikebiskits *finds Doctor Who, takes me to the time period where the elixir of life is discovered, drinks, goes back in time to take cliff/snake test* U mad bro?
"Hopefully more accurate than wikipedia", my deep rooted wikipedian apologist self is angered! But seriously, I will trust wikipedia over a majority of other sources. I firstly check to see if I can read an original journal article and if not, check wikipedia for the summary.
singingbanana Haha yeah I understand. But wikipedia has the advantage of being able to edit articles. A large percentage of the media will not do that when presented with the correct answer; most likely due to a lack of time on the journalist's part, which is understandable. I go in assuming any wrinkles have been straightened out and errors removed. Which obviously isn't always the case as is seen in this example...
Jimmy De'Souza Hey, we all fall on hard times from time to time. No need to call yourself a garbage hole ;) Edit: Oh no, you fixed the typo. That's so unfair! ;)
Jepp, the last printed work I bought were clearly 'influenced' by commercial forces. As the cookbook delivered to children in the Norwegian school system claiming that mayonnaise were an important ingredient in guacomole. With 'donations' from a major Norwegian producer of mayonnaise.
And as I see you fill in "your version' of the puzzle, you take a completely different methodology towards the problem, yet you still get the same result as I! Very interesting!
Really nice video. I looked up this problem because it talked about it in New Scientist but didn't explain it properly. Then I looked in a few other places like Wikipedia, and it was still completely unclear. This video explains it very well.
singingbanana Apologize, I wasn't paying attention, I was under the impression that it was 4 steps we were looking for. I make a poor mathematician, can't even follow directions! Love the videos! Way over my head, mostly, but very enjoyable to watch.
Awesome video! :) One insignificant comment though, Hungarian is a pretty weird language, so Erdős, is actually pronounced with an "e" as in egg, and a long "ő" as a long sounding ea in earl. :) You rock!
Two questions: (1) Is the Torturer is constrained with modulus step of instructions? For example, the torturer only stick to every 2nd step of instructions when the game begin and to end -- and can't interchange from 2nd step of instructions to 4th steps of instruction during the game. (2) Where does the Survivor land and begin? Does it start at the middle, the left, or the right? Regardless, if the condition is true that the Torturer is constrained with modulus step of instructions per game AND the Survivor begin at the middle position. Then if the Torturer is in control of EVEN instruction place -- the chance of surviving is 50:50 because Torturer is in control of the left side and the right side position -- deciding to either dump you to death or let you live back into the center position. However if the Torturer only control ODD instructions -- then you are 100% survivable because the Torturer is in control of ONLY in middle position, dumping you either the left side or the right side safe position and never in danger. Whereas the Survivor is in control of both the left and right side position, deciding its own fate to either live or to die. (But assuming the Survivor is not suicidal then it will survive the rest of the game). Check the closed sequence: i.imgur.com/LvGxlbs.jpg
True, though to be fair it's Grime's formulation of the problem. Mathematicians themselves don't conceive of it in terms of cliffs and snakes; the problem itself is normally stated in a way laypeople couldn't understand.
1) Go forward once. 2) Go forward once. 3) Tame the snakes and brush their teeth. 4) Go for a stroll with the snakes 5) Feed the snakes 6) Watch the snakes get old 7) Watch one of them die 8) Mourn the death with the other ones 9) Watch the other ones die 10) Meet the woman of your dreams 11) See her get old and watch her die in your hands 12) Die from schizophrenia, alzheimer's,and dementia so severe that you vomit blood Nailed it
"This problem is actually one of those impossible problems so give it to someone you don't like" .... You just gave this question to all of us. It's ok, we can take a hint ;)
Pi is a rather small number. If these were representations of binary digits, the decimal number would massive. Maybe Pi x 10^n, where n is somewhere in the thousands.
Pi is approximately 11.0010010000111111011010101000100010000101101000110000100011010011000100110001100110001010001011100000001101110000011100110100010010100100000010010011100000100010001010011001111100110001110100000000100000101110111110101001100011101100010011100110110010001001 in binary.
Interesting, with your analogy you basically showed how this puzzle could be generalized in the way that the maximal possible "steps forwards/backwards" don't need to be the same.
When I couldn’t do it starting at the origin, I moved the starting point half a step forwards so you could take one Aye forward and up to two steps back safely. That made it possible using the conditions he originally set.
Another way to prove it can't be done is look at it this way: When a step is an even-numbered step in the sequence, it must be starting one step forward or back from the middle, thus the previous step must be different. #12 is an even numbered step 4 times, and the previous steps in those cases are 6, 9, 10, and 11. That means all of those must be the opposite of what 12 is, forcing you to put the same value in for 9, 10, and 11 which you can tell will not work. 12 is the only number that forces you to create an unworkable pattern, so you can see that removing it from the list makes the solution workable.
Wait... unless I misunderstood something we can have two steps forward or back if we are not located in the center. (lets use numbers for position, letters for moves) Our location can only be -1, 0 or 1 but if we are at -1 we can move two forward -1+F+F=1. The puzzle is still impossible suppose we solve the 6th's, the solutions force alternating, suppose we choose 6th=F then 12th=B (lets abbreviate 6F 12B). Now we solve the thirds, we have 12B, if we alternate it would be 3F6B9F12B but we contradict what we had at 6. So we are forced to have repeats 3F6F9B12B this is only possible if we start at position -1 but this contradicts that we start at position 0 thus the puzzle is impossible.
