ไม่สามารถเล่นวิดีโอนี้
ขออภัยในความไม่สะดวก
New Wikipedia sized proof explained with a puzzle
ฝัง
- เผยแพร่เมื่อ 23 ก.พ. 2014
- A new mathematical proof was in the news this week, which partially solves the Erdos Discrepancy Problem. The proof was described as "bigger than Wikipedia". I attempt to explain the problem using a puzzle which you can try at home.
The puzzle was my idea to explain it to you - that's not really how the problem is stated.
New Scientist: www.newscientist.com/article/d...
The Independent: www.independent.co.uk/life-sty...
Tim Gowers Blog: gowers.wordpress.com/2014/02/1...
PolyMath Project: michaelnielsen.org/polymath1/i...
The paper: cgi.csc.liv.ac.uk/~konev/SAT14...
Boris Konev's webpage: cgi.csc.liv.ac.uk/~konev/SAT14/
One page proof that a sequence of twelve has discrepency of 2 www.dpmms.cam.ac.uk/~ardm/erdo...
*gives me the puzzle*
"Give this to someone you don't like"...
Message received James :/
+Liam Dienemann
I was going to mention that....
:p
I don't understand neither the puzzle nor James
If you're being bullied by bigger boys.....Give them this problem.
666th like right here
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
"If your torturer makes you write 1,161 instructions..." sounds torturous enough, Mr. Torturer.
I'll take my chances with the snakes mate. I usually have sóme mints on me, so I might not have that much of a problem with their breath
So you give us the impossible version, then tell us to give the impossible version to someone we don't like. I see how it is!
"snakes with really bad breath and stuff..."
damn, this guy really is british
That sounds like a dragon xD
Look up hognose snakes. They are the snakes with really bad breath. It's a tactic to make themselves seem rotten to predators.
Yes. Yes he is.
"give it to someone you don't like"
You just gave it to everyone watching your video seconds ago!
He meant "give it to someone you don't like without the solution"
QuantumSigma QED
r/woooosh
@@KasabianFan44 oh look . An intellectual wooshing someone who commented 3 years ago .
Apurva Nayak
Better late than never. (S)he deserved the whoosh.
@@KasabianFan44 Sbeve
If Bond villains were mathematicians...
XD
Who's to say he's not a bond villain. I think he is one.
I'd watch that movie.
How do you like my centrifuge, Mister Bond? When I throw this lever, you will feel centrifugal force crush every bone in your body.
minerguy31 centripetal*
Solution: shrink step size to smaller than what the torturer expected.
First loophole suggestion that wasn't just "stand still", so for that you get my +1
+Chris Stone Yup.
If a joke seems obvious, don't comment it.
Exponential learning rate decay, hence step size decay
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
Nice one :)
Stay, stay, stay, stay, stay, stay, stay, stay, stay, stay, stay, stay
liucyrus22 yea but how long does each "stay" instruction take? :P
liucyrus22 I've been loving you for quite some time, time, time, time, time, time, time, time, time, time, time, time
Go
+ipodceiling You think that it's funny when i'm mad, mad, mad, mad, mad, mad, mad, mad, mad, mad, mad, mad.
jump jump jump jump jump...
This should be called The Waiting at the DMV Problem.
"give it to someone you don't like" you just gave it to me! what the hell man!
He also gave you the solution...
...noitulos eht uoy evag osla eH
Walks to the right. Survives.
Thug life
julius groenjes it's a very narrow cliff; that way is also falling and death
l
julius groenjes Sounds like we need to invent sideways numbers ( ͡° ͜ʖ ͡°)
SpamDestroyer Sounds like a job for "i." :)
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
Thank you!
But what if you have Listerine to fight off bad breath?
For anyone wondering, Terence Tao submitted a proof of the Erdos Discrepancy Problem today.
So the sequence length is finite for all C.
"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.
Thanks for your deduction of the paper so I wouldn't have to torture myself reading it :P
true
I did not read this but I feel it deserves a like nonetheless.
Does anyone else see the optical illusion of the +'s and-'s bending?
standstill standstill standstill standstill standstill...
Exactly what I was thinking =)
Dam it , half threw typing that and I look down to see I'm not the only troll out here!
Give this guy a medal
James easy to understand style & manner brings math to us non-math types. Thanks James....keep up the great work.
I just love you the way you explain complex things with just so ease its amazing.
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 *ARE YOU KIDDING ME?! THAT WAS THE VERY FIRST INSTRUCTION SET I TRIED!! GRRR!!*
+Kaitlyn Amanda Not going to lie.. I laughed a lot xD hahaha I guess laziness does have some perks
Alex Talbot On the bright side, I now have a program that will brute force calculate solutions to the problem.
+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.
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!
They seem like that to me as well, but I paused and they were straight. It is a nice optical illusion though.
Yiannis Kaparos Me too. Awesome that I'm not going crazy. :P
Noticed that as well. Must be some kind of optical illusion. The illusion disappears if you pause the video.
it didnt work for me :(
It’s possibly caused by the fact that the dashes are positioned slightly below the horizontal lines within the plus signs, maybe?
Anytime I have a problem with a snake, I solve it with a gun.
Hmm... gives us a problem and asks us to solve it. Then, he says it's impossible and, at 1:51, tells us to "... give it to someone you don't like."
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.
Lol Okay
Phew! We can all sleep just that bit more soundly tonight for knowing there's at least one thing we don't need to worry about.
You should use brown paper :)
Your youtube channel is really one of my favorite, thank you for all the great content you offer us
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.
No problem! I hope the course is going/went well.
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 TH-cam viewers? :)
Brilliant :)
Also, This gives me an idea of making an interactive game of the puzzle he described. :D
I've made a little interactive mini-game based on his puzzle! Check it out!
i.imgur.com/bLLLWiC.png
gmc.yoyogames.com/index.php?showtopic=612382
Re
Very nice!
Roy Prins Thanks :)
‘hopefully more accurate than Wikipedia’
shots fired!
Did he say snakes with really bad breath?? Hahahahahaha
It must be British.
Sharath K Menon well... look down and smell your own snake, bad, isn't it?
As this is all imaginary I think I'd just go for a +i and avoid the problem altogether.
You know what you did.
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?
Wow, you're a good teacher. People should appreciate that you shot this in only like, 3-4 takes at most. Such charisma!
I really enjoy your videos and you aren't on numberphile enough. So thanks for keeping this up!
Yeah, I think you made a typo at 8,008 step of the final 4 step problem. You fall of the cliff.
8,009
FTFY
there is a snake pit in front of you, a cliff behind you. Where do you go ?
Sideways
Its in a 2 d world
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.
I think you may have experienced some ASMR
:-D
-Give this to someone you don’t like
*proceeds to try to solve it*
Aren't you the guy from numberphile?
Dodgy Turk Yes. Can't you tell from my face?
I only watched the Futurama episode a while back and remembered your face. I will now watch all your videos :D
+singingbanana i thought i was on numberfile still :/ well then
+Dodgy Turk
At first I thought you meant you remembered his face from an episode of Futurama ._.
Dodgy Turk He is not Brady, the channel owner. He works with Brady on Numberphile.
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.
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.
I also found it hard to find a good explanation! Glad this helped!
your videos are awesome, it's cool to keep up with math news and actually understand the solved problems !!!
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).
*falls off cliff*
*survives*
Problem?
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?
Some Random Fellow Yeah, except the TARDIS malfunctions way too often for it to be reliable. But, whatevah.
ilikebiskits Which is why I brought my handy dandy pair of energizer batteries!
Some Random Fellow back, back, deploy chute
BASE jumping FTMFW
It's great to see you're making videos again ! :D Interesting as always :p
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
+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?
Sasha sokolov this would boil down to the same problem. You could always just walk one line and get the same result.
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
What happens if the cliff and the snake are not equal distances from you? Say the snake is 2 steps forwards and the cliff is 3 steps back?
You know the plough, the constellation?
Well, that's about how far above my head this video is but I find it very interesting and enjoyable.
For some reason, I'm wondering about periodicity in the biggest safe sequences. Also does allowing +2 steps ever help or is it useless?
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?
ENDR SLIM3R 2recursive4me
+ENDR SLIM3R this made my day...!!! lmao... :-)
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?"
NoriMori That particular actor is Phil Davis, he's great. Not sure about our accents though.
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
+NoriMori Isn't the OnYomi for 典 （テン）？ I'm not getting anything for no ri, but I may be wrong
+William Barnes One of the on'yomi is テン, but one of the nanori (name readings) is のり. It's also read that way in the word meaning "rule" or "law".
Knowledge for the sake of knowledge always has the possibility of a real application. Thank you.
This problem seems related to a random walk between boundaries (or Brownian motion). You could also extend the problem to 2 or more dimensions.
"Give this to people you don't Like".
Not so subtle:(
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.
Ko Kaian That doesn't contradict anything I said.
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.
Ada Repli Yes, science is useful.
you said you get a sequence to save the guy from 3 steps either way of 1160 instructions, but wouldn't there be two sequences dependant on if you started +1 or -1?
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!
I spoted a mistake in the line 235 at 9:52. that sequence can't work.
First go to the line i said, then run your finger till the 15th step. There. if you look up there will be a giraffe over your head.
macacalocaedoida I concur. Seems pretty obvious to me.
Linushz k
What? That's stupid. How can there be a giraffe above our heads?
That's easy. In reality, this cliff is in 3 dimensions. Simply walk perpendicular to this snapshot, and you will go free.
You're finally back :)
"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.
Cheap joke. No actual criticism behind it. Although, the proof needs to contain no mistakes. Wikipedia can't claim that.
singingbanana As long as it doesn't suddenly say "penis" in the middle of the proof, I'm good.
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.
Now what happens if we brought this problem to a 3 dimensional world instead of a 2 dimensional world?
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 Now that is one devastating answer! LOL
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.
If I stare at the sequence at the end and then look above my monitor I can see rain on my wallpaper
James - Next time you need to have an epilepdic warning before showing a sequence of 30000 pluses and minuses! :-)
Btw ... very good video!!
It seems like regardless of how many steps there are between the start and one of the traps, the largest sequence that actually has a solution would always have exactly two solutions, which are mirror images of each other. Is that right?
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.
It's quantum physics, not quantum miracles!
***** Even miracles can't fix windows. =(
Windows XP!
Somehow I feel prime numbers need to be involved in the proof.
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
Rene Roundthecorner It looks like a algorithm to calculate primes using a grid.
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.
same, I also felt there was prime number involvement for some reason :o no reason, just a feeling
Something neat I noticed: the sequence of 1's and -1's make the Fair Share Sequence (if you don't know what that is, go watch that numberphile video)!
If you were to do this on a two axis version (x,y) how many steps would you have to do?
LOL Snakes with a really bad breath :P
What if the instruction is to stand still? %)
Why would you start deriving your sequence from 1? Would it not make more sense to start at 6 (or more generally floor(steps/2) ) and work backwards?
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.
At the end I imagend a dancer going backwards and forward synced with the music :)
Tao referenced your video in a talk he gave: watch?v=QauoO0j9Y9Y, at around 9:30
+deadeaded That's so cool. Thanks for showing this to me.
fiziks
Some websites don't let you post links, so I got into the habit of just copying the end of the url, since it's almost never blocked or censored.
But I'm watching in mobile app and can't copy 😭
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.
If you didn't know the question that the sequence was used for, could you give a degree of randomness on the order of plusses and minusses?
easiest solution: 0 0 0 0 0 0 0 0 0 0 0 0
That's not one step forward or back
+GloveSlapnz What if you're "stepping" (don't know the right word) upwards? Or into the 4th dimension?
+RnDn. El Ferko you would only have to step into the third dimension I guess lol.
GloveSlapnz 4th dimension makes everything looks cool.
+RnDn. El Ferko If you can step into the 4th dimension you torturer isn't going to get you anyway.
What makes this an Interesting Problem?
Saw VII
Please do another video explaining what program they used (hol, coq, isabell?) and preferably roughly how it works.
How many A4-sized pages of font 12 Aerial text sized information in the form of variables and functions etc. would that amount of mathematical data occupy exactly?
man that credits section had some weird names.
I did recognize the 101 boy
LOL snakes with bad breath LOL
Thank you for your example which helped to explain the absolute value sign in the formal expression of the theorem. Your video was very entertaining and easy to grasp unlike the written commentaries. You are a great combination of stage actor and university prof. Which is it? Or both?
I'm definitely an academic. I was sure there must be an easier way to explain it than what I had seen in the news stories.
singingbanana As far as my retired friend with an MA in EE and myself with a mere MA in the social sciences, you succeed handsomely. I am traveling to the UK to take your math class. five thumbs up.
Three questions:
(i) Are the solution sequences at 11 and 1160 moves unique (bar the trivial swapping of -1 for 1)? Are all solution sequences expected to be unique/non-unique?
(ii) Can this be generalised to unit moves on a 2D cartesian grid? What about in more dimensions?
(iii) Why is this problem hard? It's reasonably trivial to understand and express, but is there a reason that one could spot, on asking, that it was not in fact a trivial problem?
if you made all into binary, you could possibly make some cool art or word or something
Anyone else catch the error in that sequence at the end? Number 6382 should have been a +, not a -. I assume it was a transcription error.
Did you...check?
Very interesting video, James! Thanks for the information about this! :D
" 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
I'm glad I'm not a mathematician.
Why can't we give conditional instructions? If x>0 then -1 else +1
Because of the wish of the torturer. He can make you follow every n th instruction. With the condition you propose the normal set of instructions would be: 1, -1, 1, -1, 1, -1... but if he ordered you to follow the 2nd instructions you would have to follow the 2nd, 4th, 6th, 8th instructions, and those would be -1, -1, -1, -1, -1... and you would fall
Luís Miguel Those are not my instructions. I meant, literally conditional instructions. Anyway, I think it's not worth arguing about; it's just about the way he represented the problem(without any explicit constraints on the instructions), my first thought was, OK, "at each step I'll measure my position and move towards the center." That is the instructions I would use. After listening to the whole video it becomes clear that they meant explicit list of steps, therefore conditional rules are probably not allowed😀
Seyed Ali Hamed Mousavian
Yah... Conditional instructions would mean you'd never fall off the cliff for any size bigger than 1, which kinda ruins the fun of the whole thing. It also seems like it'd be a pain to get any interesting results from sets of conditional statements.
Luís Miguel He was saying torturer?! I couldn't understand what that t-word was, I just figured it was some word I didn't know lol
Baga Jr heheh I had to go back a couple of times too :-P
My first attempt was trying to implement the Thue-Morse sequence into it, and it worked well for every [n] number of instructions, except for every 3.
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!
Just by intuition, this problem would differ if your starting point was not in the middle of the two end points. Say your starting point was 1 step away from the snakes or 1 step away from the cliff. Does that change the 11 step max that guarantees safety?
in the last example, I saw many sequences of 5.
+Thomas Gunkler Can you work out why that's ok?
+Ethan Cooper Exactly
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.
4 steps to the snake and 4 steps to the cliff so there are 9 steps in the safe zone
+baileyboy125 no, there are 7 safe zones (4th steps are lethal) which allows us a maximum number of steps in the same direction of 6 (from -3 to 3).
I might have not been paying attention but... can't you just NOP each instruction?
+Greg McCarthy then he just shoots you
only 1 step forward or backwards are the Only moves, learn to listen.
In the stated problem, with the cliff behind you and the snakes in front, it sounded like facing was a thing, so just turn 180 each time.
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.
@singingbanana did you see that Terry Tao talked about your interpretation of the Erdos discrepancy problem in his new MasterClass course? Pretty cool