I initially heard him say two hundred graduates instead of two undergraduates and was impressed by the level of coordination that was needed, and also the infinite monkeys and infinite typewriters was only 200 graduates to get a new math proof. But alas
I can very much see this as a board game, where players take turns to place the next higher number until one can't and loses. They could try to 'snooker' each other by blocking possible squares for the opponent's next move(s) or try to create squares for their own ones as strategies …
Perhaps the player to place the 50-stone is the winner. If the next white move is not possible, place a brown stone. If browns are placed for 3 consecutive turns (1 * number of players + 1), the highest valued white stone wins. Depending on how the move-not-possible logic plays out, maybe the highest white stone loses, you try to lure your opponent into placing the highest stone.
In our mad dash to learn higher levels of math _quickly_ we often miss that there are so many interesting problems to solve if we just think about the simplest concepts a bit more creatively. This video is a great example of that!
The upper bound mentioned on the OEIS can actually be improved to a(n) 1. Then k has a neighbour which is at most k/2. Suppose we continue this for d steps. Then there is a square no larger than max(1,k/2^d) within distance d of the number k. Then the n ones along with the numbers in [2,k/2^d] cover all numbers in [2,k] within a distance of d. The argument for the a(n) < 714n continues by saying that each square covers at most (2d+1)^2 numbers. However, this can be improved by observing that any number x in [2,k/2^d] is within distance 1 of a smaller number y in that same set, or a one. So x's square heavily overlaps with the square of y. In fact, there can be at most 4d+1 numbers covered by x which aren't covered by y, which occurs when x and y are diagonally adjacent. This gives that the n ones cover at most (2d+1)^2 numbers each and the numbers in [2,k/2^d] cover at most 4d+1 numbers each, but that these cover all of [2,k]. So we obtain the inequality n(2d+1)^2+(k/2^d-1)(4d+1) >= k-1. This becomes k 0, so provided 2^d > 4d+1, which is true for all d >= 5. Then to obtain the best bound with this method, we minimise the linear coefficient of n, subject to the constraint that d >= 5. This is minimised for d = 6, so we obtain k
@@neilsloane2512 I really wish I had spotted this earlier, but I've just improved my bound with another simple tweak. When I mention that any number x in [2,k/2^d] is within distance 1 of a smaller number y, I should have realised that x is in fact within distance 1 of at least two numbers smaller than it (the numbers which sum to x), y and z. And the overlap is slightly higher as a result, so x only has at most 2d+1 squares which aren't covered by smaller numbers, for any x in [2,k/2^d]. This involves checking all the ways that both y and z can be adjacent to x, but you'll find a maximum non-overlap of 2d+1 cells for x. So in fact we obtain that each of the n ones cover at most (2d+1)^2 numbers, each of the numbers in [2,k/2^d] cover at most 2d+1 numbers, yet all numbers in [2,k] are covered. Hence n(2d+1)^2+(k/2^d-1)(2d+1) >= k-1. This becomes k 0, which happens for d >= 3. Then the optimal choice of d is d = 5, which gives k
I'm surprised about that too. I could easily guess that it would grow exponentially. The fact that it's linear makes it "not-too-difficult" to look for the next steps.
@@nod2009 I'm not sure that last comment follows from the linearly bound. The game tree will still explode super-exponentially (something like factorially), just in the "wide" direction rather than the "tall" one.
I was really expecting it to be like the TREE sequence and other sequential puzzles like that, that have reasonably trivial and low first few terms and then explode to absurd numbers really fast... But those bound proofs were really elegant, so I was pleasantly surprised!
That surprised me as well. First he said the bound is n*log(n) which didn't surprise me after the long explanation but then, suddenly, we jump down to 714*n. =O
This man reminds me so much of my grandfather. The calm yet excited manner in which he is presenting this riddle. And my grandfather loved riddles, he was an engineer so he loved math and was always teasing me with riddles and questions. He would have loved this one. I miss him.
I really expected the upper bound to be at least quadratic in n, maybe even exponential. I did definitely not expect the upper bound to be linear as well. Crazy! It seems that having two dimensions at hand doesn't help much. Now, I am curious whether the upper bound is still linear in higher-dimensional cases (e.g. 3D). But I suspect it is...
The proof of the 714n upper bound is given in the OEIS notes on the sequence. I haven't worked out the details, but it looks to me it should work to prove a similar linear upper bound for any finite dimension.
I suppose it's possible to systematize the proof to a higher dimension, except you'll be working with e.g. a cube of size n instead of a square of side n, so you'll always be able to find a bound big enough that your n^d (d for dimension) will be too small. If you're still working with 65000, th cube would have to be of side 15 as well, and 15*15*15 = 3375, which is smaller. That's not rigorous, but I suppose it does extend to 3D and any higher dimension as well.
The linear upper bound comes from the linear increase in the number of the squares you can _ever possibly_ fit near brown square. You can't come close to filling a whole square around a brown stone because each new stone you add in the square can only grab so many nearby stones before it would be a new maximum, making the task even harder. The completed pattern for the B=6's value is 60, which has a 'max' radius R=5.9squares=log(60)/log(2). If you go (2R)^2, you would need 139 nearby squares to fill up the entire area around the brown stone for polynomial increase, but the actual answer is 60/6 = 10, way way off from 139. The are so constraining that it's actually quite hard to approach the bound.
I love puzzles like this, because it's so easy to play around with at home and the rules are understandable in a few minutes, but the math is so deep that they haven't even proven the best total for 7 yet.
Hi. I'm the guy who found the argument for 85.4n+32 as an upper bound. We're currently working on an improvement to that argument and hope to get the upper bound down to 54.4n+C. There's a lot more edge cases to consider this time tho, so it might end up slightly higher than 54.4n+C. And of course we want to find C as well.
There are many trees to investigate (lots of possible initial positions for 8 brown stones) and 60 moves is pretty deep. Even a branching factor of 1.25 (i.e., having, on average 1.25 legal moves per position) means you have to consider over a million positions per tree.
@@beeble2003 I think it's much worse than that. The branching factor increases with its depth n, so the size of the game tree is superexponential in n. In fact, I think it's more like n! than e^n. And the depth of the average game tree increases linearly with k, the number of huts, so you end up with a game tree of size (ak)! (where 5 < a < 714) for each arrangement of k huts. And like you say, there are many, many such arrangements. For a given arrangement of (k-1) huts, we have to consider placing the kth hut in each open square adjacent to the largest number in any leaf of the game tree for that (k-1)-hut arrangement. There's something like sqrt((a(k-1))!) of those. So we wind up with a product of factorials, which is never good news.
@@EebstertheGreat I don't think it's nearly that bad. You're thinking of each move as being place the next white stone, or the next brown stone (if available), which is a nice idea. It seems that, typically, there are only a couple of places where the next white stone can be placed. The next brown stone must be placed at most distance 2 from the highest white stone. If you want to place it somewhere else then either it's close to an existing stone (so you could have played it when that stone was the highest) or it's far from the existing stones and it will have no impact until you have something within two squares of it, so you can wait until then before placing it. So, at each move, there are a constant number of brown options and it looks like a small number of white moves, so it looks likely to be a simple exponential relationship to me.
@@beeble2003 I guess that's true, now that I think about it. The number of new opportunities placing a stone can create definitely has a hard upper bound of 8, and a practical upper bound of something like 3 or 4 in constructions likely to get big. So the game tree clearly can't grow faster than 8^n in the long term, and in practice probably something like 1.5^n. You still have the problem that the number of k-hut arrangements you need to check depends on the distance you can reach with each (k-1)-hut start, which also increases with k. So if the first hut always starts at the origin, there are five essentially different nontrivial 2-hut arrangements. Each of these can result in a variety of possible games, some of which push the boundaries of where a relevant third hut can be placed pretty far. After eliminating symmetric variations, all of these new placements constitute essentially different 3-hut arrangements. These can each push the boundary much farther, because you can reach a higher number with a 3-hut arrangement. In general, you can reach the value f(k) = θ(k) from an optimal k-hut start, and the diameter of the largest k-hut start is also g(k) = θ(k), but the diameter of the average k-hut start is θ(k^.5). It seems obvious to me that the number of new relevant places a kth hut can be placed increases with k, though I'm not sure I have a proof. But if it does, then the number of relevant, essentially different k-hut arrangements (i.e. the number you need to check) is ω(a^k) for all a > 0.
@@EebstertheGreat Yes, but if you think of placing huts as a kind of move, too, you always start with just one hut, so there's only one start position. Assuming that there are only a constant number of legal white-stone moves in any position, that's enough to give a k^{714n} bound on the size of the search problem for n brown stones. Not a practical way of doing it, but it does give the bound.
Well the bounds aren't very tight. The numbers is between 5n and 714n which is pretty wide. But of course the fact that the upper and lower bounds are both linear at least proves that the sequence grows O(n) at the limit which is definitely a cool result
I love how excited he gets over these numbers, it reminds me of how I get when I’ve got a problem I’m trying to sort out and figure out a clever way to do it. I get so excited solving it, this is an awesome video
I was about to write that I wondered if it had been proven that you can reach any arbitrarily high number given enough brown stones, but then I remembered the zigzag construction which literally already proves that. Very interesting video, loved it.
These are the best. I love Neil's method. He shows you enough to follow his logic without ever repeating himself, and he's got all kinds of excitement about the topic.
He made that statement even clearer on his TH-cam channel where he talked about this problem among others. He said it's probable new things will be found soon because not many people had tried to solve these yet.
I recall a few months ago Matt Parker set a challenge to the maths community to find periodic tilings for various hypercube nets. Within twenty-four hours correct solutions for all 100-plus hypercube nets had been submitted to his website.
Am I the only one who thinks that this would make an excellent 2 player game? Players take turns to place sequential numbers, first one who doesn't have a valid move loses. So not only do you have to place your tile, you want to try and block the other player. With lots of different initial set ups of huts, the replayability would be huge!
Kinda like Hive but all numerical and no differentiation of pieces. But it could be fun to (selectively) add special moves. e.g. once a game, a player can place a -1 blue hut before they move. Or whatever. Would really blow up the game tree even more 😜
@@beeble2003 Almost like how God's number was squeezed out. It was mostly computer search but it was definitely doing it more efficiently than a brute force search.
The first few (n= 1 through 4) were trying every possible position accounting for rotational and reflection symmetry. The higher couple used some more clever symmetries but were still mostly brute force.
I don't think you meant it that way but it sounds a bit dismissive of computer-assisted proofs. They aren't the most elegant necessarily, but once they are independently verified, they are every bit as valid as manual proofs. Specifically, I have vivid memories of people dismissing the computer-assisted proof of the four color theorem and loudly claiming to have found a counterexample. In reality, every last one of them turned out to be fallacious, to my non-existent shock. 🙂
For the lower bound: Assuming you place the first stone at (0,0), and the second at (2,2), by placing the 3rd at (3,-1) you could wrap around to the 1st stone again , using just 4 of the spaces around stone 3, and 4 of the unused spaces around stone 1 to get to 14. Continuing out as in the video would increase the lower bound to 5n-1 for n>2. I think...
A curiosity to note is that for the first few terms, not only do the terms increase, but the gaps between them also increase; However, the upper bound is proven to be linear.
Edit: with a friend we got the new minimum up to 6n with 3 or more stones You can get (n-1)*6 by having a line of 1001001001001, 2 is placed above and to the left of the leftmost 1 with another 1 to the left. Then just go along the line 3 4 5 6 7 ... and at the end loop around and go on the underside.
Just add if you want: 5:02 Gradshteyn and Kornshell - 6:07 The Maple Handbook - 6:47 The Enceclopedia of integer sequence - 6:49 Handbook of integer sequence....🙂
I wonder if there is a small modification you can make to rules such that the number of stones grows quickly in function of the number of huts. Maybe allowing to place stone if it's the sum of it's neighbors divided by their common divisor
Wonder what would happen if you made the rules “can add any stones within the neighboring range to get the new value” rather than “all stones in the range must add to new value”; ie, allowing 412 53x (where x is an empty square)
@@lesbianaconda2971 That wouldn't change much as you are still guaranteed to have a stone less then H/2 next to stone H. You would have to allow for a way to let large stones go relatively far away from small stones while not allowing them to go infinitely far
That doesn't change the proof of the upper bound that was mentioned in the video. In fact, even if you say you can add a stone as long as the sum of the neighboring stones is _at least_ the number of the recent stone, then the proof in the video holds. Nvm I got it the wrong way around
well you can argue it is just as dependant on the shape of the grid and the number of dimensions of the board as other sequences are dependent on number bases. Pretty sure the result of this would change if you had a hexagonal chessboard or other types
I love the visuals on this one. I was thinking showing the white numbered tiles as slightly higher on the graph based on relative size would much better help illuminate the concept visually. Well done.
decided to quickly draft up a program to work it out, haven't looked at it smartly yet but there are 32 configurations for 2 tiles to land on 16 if we dont account for rotations and reflections
What happens when you extend the game up into higher dimensions? Obviously, you could just do the same sequences as a uniplane within the 3D space, but you've also got extra spaces now "above" and "below" that that you can expand into. I wonder if anyone has worked on that.
Has this been extrapolated to different grid shapes (triangles/hexagons) or higher dimensions? Or other limits (like no diagonals, or at least 3 neighbors)? Lots of cool things you could do with this game
That upper bound should still apply since it doesn't rely on grid shape at all (just the fact that to make a number you need to add at least 2 previous tiles). The lower, probably not since that relies on finding a particular construction Also for triangles you'd have to decide if adjacency means sharing a side or if corner is enough (which is true of squares as well to be fair, and absolutely with/without diagonals is interesting)
@@metallsnubben i think the upper bound does depend on grid shape, because the number of cells at distance log2 N needs to be asymptotically less than N. This is certainly true of planar, non overlapping grids, and may even be true of euclidean n-dimensional non overlapping grids, but is not necessarily true of hyperbolic grids.
@@david-hogarty The real nasty question then is what... I don't even know what to call it, "level of hyperbolic" do you need to go infinitely high with N starting pieces
About n*log(n), there is probably a significant decrease like almost to (n-1)log(n-1) or smth due to the requirement that for any working configuration it's required to have two 1-pointers in a square of 3x3, since otherwise you simply can't place #2
Using this same argument, can we show that if instead of a 2-D board we had an N-D board, we still would have an upper limit on the number of stones we can place? I think the fact that 2^x >>> x^N is relevant there, as well.
You could actually modify the zigzag structure a little bit to place more stones around the first two before adding more browns to continue the zigzag, and then the lower bound becomes 5n-1 instead of 5n-4. In fact, just using the optimal arrangement from two browns, you can start building the zigzag on that with more browns and then the lower bound becomes 5n+6.
Here's a bit of a generalization of the puzzle: for some list of numbers (like the fibonacci numbers), what is the highest number N of which you can place x0 instances, with x1 instances of N-1, and x2 instances of N-2....; so: 1 of N, 1 of N-1, 2 of N-2, 3 of N-3, 5 of N-4...
We've all had those lectures where we thought we understood, walked out the lecture with notes that look like that brown paper, and later find we aren't able to recreate the arguments.
As an engineering undergraduate student, I see a numerical solution to this using matrix arrays. Consider the board to be a matrix of N by N size. Set X cells to be equal to 1 in random positions (these are the brown stones). For each i:N column and j:N row, detect if the sum of any two adjacent cells is equal to the cell value at the current index. If true, set the current cell as the new value. If repeated enough times, the results for the final value could be mapped out as a distribution, with the maximum being the highest achievable value (the answer we are looking for). I'm sure there are plenty of kinks that need to be worked through, but those are my preliminary thoughts. Has anyone tried this? I plan on doing it as soon as I finish my coursework.
Actually I'm not even sure if this would prove anything in either direction but in any case it'd be pretty computationally intensive to brute-force: Say you're looking for boards with 20 huts and you've already figured out that those boards can't be larger than 60x60 Then in order to test all possibilities, you would have to test (3600 choose 20) configurations for the huts, and then solve all of them That's not happening unless you can astronomically shrink the search space
The reason you can't do nearly as well as 714n is that stone placement is constrained. For example, if you have 3 huts, but no two are within 2 of each other, then each position has the same problem as with a single stone - there is no valid '2' position anywhere. So in fact, the size of the board we have to fit 'Everest' into is much smaller, than is constrained by the argument in the construction. I'm not a mathematician with the skill to solve that problem, but I think it would be possible to show how close each new stone must be to the existing 'hill' and define the actual maximum size of the board we must fit 'Everest' into much more closely. For example, I think the 2nd stone likely must be within 2 of the first, and the 3rd stone likely must be within three of the 'hill' formed by the first 2 stones, so the best you could do for 3n is most certainly smaller than 75 which is much less than 3 x 714. I found the video really interesting because even though the answer isn't known, what is known about it proves very counterintuitive. I would have first guessed that once N was sufficiently large that the answer was infinity - and I wouldn't have guessed N needed to be very large. But, having seen the proof that it can't be infinity, I would have next guessed that it grew geometrically (if even at a small rate). After all, there seems to be a slow upward trend on even the known terms. But that the upper bounds grows linearly is a pretty astounding result to me and suggests that for some N, there becomes a regular pattern (similar to the +5 pattern of the lower bound)!
There is a mistake in the graphic at 5:33, thanks to the comment of @Michal Karas. The 15 has to be placed one higher, as otherwise the 16 is in fact neighbouring 30. (1 + 14 + 15). Neil did it correct in real life.
Indeed at 5:25 the graphic should show the 15 and 16 stones one square higher - Neil's "real life" board is, of course, correct.
Ok
Ok
Haha, I was about to make that comment :)
Oaky
For a moment I felt smart as I wanted to type "You can totally put 17 in there"... Seconds later I realised that the graphic had an mistake...
Hi this is Jeremy Rebenstock, Co-creator of this puzzle. Thanks so much for sharing it!
No way bro funny seeing you here
Sweet 👍
If you place one brown can’t you just do 4 lines of 1s of into infinity NESW? Edit: no
This puzzle is as dangerous as crosswords, Toki Pona, or bubblewrap for people like me. I am consciously disengaging from it so I can study my degree.
@@qeithwreid7745 wow what a weirdo; no, you cant - there can only be one of every numbered tile.
I initially heard him say two hundred graduates instead of two undergraduates and was impressed by the level of coordination that was needed, and also the infinite monkeys and infinite typewriters was only 200 graduates to get a new math proof. But alas
lol
The alas slays me 😂
same
Blurst of times
Lol, I thought I was the only one who misheard that
I am more impressed by how clearly he was able to explain the expressions for bounds than the actual problem. Excellent, professor!
so elegant and revealing
I can very much see this as a board game, where players take turns to place the next higher number until one can't and loses. They could try to 'snooker' each other by blocking possible squares for the opponent's next move(s) or try to create squares for their own ones as strategies …
I think it might be a bit too easy to snooker, but may when that happens, the snookered player has to place a new brown stone.
@@renmaddox Maybe at the beginning, yes, so you could start off a couple rounds in or, as you said, place more brown stones …
@@renmaddox with a limit on brown stones otherwise it could go on forever - see the minimum stones part
but actually snakes and ladders could also go on forever so it's maybe not that important for the game to definitely halt
Perhaps the player to place the 50-stone is the winner. If the next white move is not possible, place a brown stone. If browns are placed for 3 consecutive turns (1 * number of players + 1), the highest valued white stone wins.
Depending on how the move-not-possible logic plays out, maybe the highest white stone loses, you try to lure your opponent into placing the highest stone.
In our mad dash to learn higher levels of math _quickly_ we often miss that there are so many interesting problems to solve if we just think about the simplest concepts a bit more creatively. This video is a great example of that!
Shut it
@@hansdieter4537 Excuse me?
@@hansdieter4537 fite me irl
The upper bound mentioned on the OEIS can actually be improved to a(n) 1. Then k has a neighbour which is at most k/2. Suppose we continue this for d steps. Then there is a square no larger than max(1,k/2^d) within distance d of the number k.
Then the n ones along with the numbers in [2,k/2^d] cover all numbers in [2,k] within a distance of d. The argument for the a(n) < 714n continues by saying that each square covers at most (2d+1)^2 numbers. However, this can be improved by observing that any number x in [2,k/2^d] is within distance 1 of a smaller number y in that same set, or a one. So x's square heavily overlaps with the square of y. In fact, there can be at most 4d+1 numbers covered by x which aren't covered by y, which occurs when x and y are diagonally adjacent.
This gives that the n ones cover at most (2d+1)^2 numbers each and the numbers in [2,k/2^d] cover at most 4d+1 numbers each, but that these cover all of [2,k]. So we obtain the inequality n(2d+1)^2+(k/2^d-1)(4d+1) >= k-1.
This becomes k 0, so provided 2^d > 4d+1, which is true for all d >= 5. Then to obtain the best bound with this method, we minimise the linear coefficient of n, subject to the constraint that d >= 5. This is minimised for d = 6, so we obtain k
I added your new bound to A337663!
@@neilsloane2512 I really wish I had spotted this earlier, but I've just improved my bound with another simple tweak. When I mention that any number x in [2,k/2^d] is within distance 1 of a smaller number y, I should have realised that x is in fact within distance 1 of at least two numbers smaller than it (the numbers which sum to x), y and z. And the overlap is slightly higher as a result, so x only has at most 2d+1 squares which aren't covered by smaller numbers, for any x in [2,k/2^d]. This involves checking all the ways that both y and z can be adjacent to x, but you'll find a maximum non-overlap of 2d+1 cells for x.
So in fact we obtain that each of the n ones cover at most (2d+1)^2 numbers, each of the numbers in [2,k/2^d] cover at most 2d+1 numbers, yet all numbers in [2,k] are covered. Hence n(2d+1)^2+(k/2^d-1)(2d+1) >= k-1.
This becomes k 0, which happens for d >= 3. Then the optimal choice of d is d = 5, which gives k
Mathematician at work
A really interesting problem! It's surprising to me that the solution was proven to be linearly bounded.
I'm surprised about that too. I could easily guess that it would grow exponentially. The fact that it's linear makes it "not-too-difficult" to look for the next steps.
@@nod2009 I'm not sure that last comment follows from the linearly bound. The game tree will still explode super-exponentially (something like factorially), just in the "wide" direction rather than the "tall" one.
I was really expecting it to be like the TREE sequence and other sequential puzzles like that, that have reasonably trivial and low first few terms and then explode to absurd numbers really fast... But those bound proofs were really elegant, so I was pleasantly surprised!
It would have been interesting to see the derivation of n log(n), and the linear bound. I think we got deprived of the best bits!
That surprised me as well. First he said the bound is n*log(n) which didn't surprise me after the long explanation but then, suddenly, we jump down to 714*n. =O
When u see there is an infinite chess board and Neil Sloane in it, it is a great video
This man reminds me so much of my grandfather. The calm yet excited manner in which he is presenting this riddle. And my grandfather loved riddles, he was an engineer so he loved math and was always teasing me with riddles and questions. He would have loved this one. I miss him.
This was very interesting, clear and the professor has a relaxing voice too, which is a plus in my book!
Always excited when there's a new Neil Sloane video 😊
I love his voice and the way he speaks
@@Bleighckques reminds me of the scientist character from futurama
videos with neil are always absolutely wonderful!
false.
I really expected the upper bound to be at least quadratic in n, maybe even exponential. I did definitely not expect the upper bound to be linear as well. Crazy! It seems that having two dimensions at hand doesn't help much. Now, I am curious whether the upper bound is still linear in higher-dimensional cases (e.g. 3D). But I suspect it is...
The proof of the 714n upper bound is given in the OEIS notes on the sequence. I haven't worked out the details, but it looks to me it should work to prove a similar linear upper bound for any finite dimension.
I suppose it's possible to systematize the proof to a higher dimension, except you'll be working with e.g. a cube of size n instead of a square of side n, so you'll always be able to find a bound big enough that your n^d (d for dimension) will be too small. If you're still working with 65000, th cube would have to be of side 15 as well, and 15*15*15 = 3375, which is smaller.
That's not rigorous, but I suppose it does extend to 3D and any higher dimension as well.
The linear upper bound comes from the linear increase in the number of the squares you can _ever possibly_ fit near brown square. You can't come close to filling a whole square around a brown stone because each new stone you add in the square can only grab so many nearby stones before it would be a new maximum, making the task even harder.
The completed pattern for the B=6's value is 60, which has a 'max' radius R=5.9squares=log(60)/log(2). If you go (2R)^2, you would need 139 nearby squares to fill up the entire area around the brown stone for polynomial increase, but the actual answer is 60/6 = 10, way way off from 139. The are so constraining that it's actually quite hard to approach the bound.
Another argument is that the bound might be invalid for 6 dimensions as every stone would have 728 neighbors. wdyt?
@@AutomaticHourglass Sure, but another bound would work instead, with just another number instead of 714.
I love puzzles like this, because it's so easy to play around with at home and the rules are understandable in a few minutes, but the math is so deep that they haven't even proven the best total for 7 yet.
I love videos with Neil Sloane, he manages to explain things in the best possible way)
Hi. I'm the guy who found the argument for 85.4n+32 as an upper bound. We're currently working on an improvement to that argument and hope to get the upper bound down to 54.4n+C. There's a lot more edge cases to consider this time tho, so it might end up slightly higher than 54.4n+C. And of course we want to find C as well.
Super cool!
Referencing Everest, Neil knows how to peak Brady's interest.
Is that a pun or a spelling mistake 🤔
@@mercer5888 It's a pun, and that's the height of my comedic ability.
Its all down hill from here
@@chillsahoy2640 Peak? Height? You must feel like you are on top of the world with these puns!
@@chillsahoy2640 sure it's not the pique of your comic abilities? I'll show myself out
It's interesting that the maximum lengths of the stone sequence we have found are so low. The search tree must be very broad rather than deep.
There are many trees to investigate (lots of possible initial positions for 8 brown stones) and 60 moves is pretty deep. Even a branching factor of 1.25 (i.e., having, on average 1.25 legal moves per position) means you have to consider over a million positions per tree.
@@beeble2003 I think it's much worse than that. The branching factor increases with its depth n, so the size of the game tree is superexponential in n. In fact, I think it's more like n! than e^n. And the depth of the average game tree increases linearly with k, the number of huts, so you end up with a game tree of size (ak)! (where 5 < a < 714) for each arrangement of k huts. And like you say, there are many, many such arrangements. For a given arrangement of (k-1) huts, we have to consider placing the kth hut in each open square adjacent to the largest number in any leaf of the game tree for that (k-1)-hut arrangement. There's something like sqrt((a(k-1))!) of those. So we wind up with a product of factorials, which is never good news.
@@EebstertheGreat I don't think it's nearly that bad. You're thinking of each move as being place the next white stone, or the next brown stone (if available), which is a nice idea. It seems that, typically, there are only a couple of places where the next white stone can be placed. The next brown stone must be placed at most distance 2 from the highest white stone. If you want to place it somewhere else then either it's close to an existing stone (so you could have played it when that stone was the highest) or it's far from the existing stones and it will have no impact until you have something within two squares of it, so you can wait until then before placing it. So, at each move, there are a constant number of brown options and it looks like a small number of white moves, so it looks likely to be a simple exponential relationship to me.
@@beeble2003 I guess that's true, now that I think about it. The number of new opportunities placing a stone can create definitely has a hard upper bound of 8, and a practical upper bound of something like 3 or 4 in constructions likely to get big. So the game tree clearly can't grow faster than 8^n in the long term, and in practice probably something like 1.5^n.
You still have the problem that the number of k-hut arrangements you need to check depends on the distance you can reach with each (k-1)-hut start, which also increases with k. So if the first hut always starts at the origin, there are five essentially different nontrivial 2-hut arrangements. Each of these can result in a variety of possible games, some of which push the boundaries of where a relevant third hut can be placed pretty far. After eliminating symmetric variations, all of these new placements constitute essentially different 3-hut arrangements. These can each push the boundary much farther, because you can reach a higher number with a 3-hut arrangement. In general, you can reach the value f(k) = θ(k) from an optimal k-hut start, and the diameter of the largest k-hut start is also g(k) = θ(k), but the diameter of the average k-hut start is θ(k^.5). It seems obvious to me that the number of new relevant places a kth hut can be placed increases with k, though I'm not sure I have a proof. But if it does, then the number of relevant, essentially different k-hut arrangements (i.e. the number you need to check) is ω(a^k) for all a > 0.
@@EebstertheGreat Yes, but if you think of placing huts as a kind of move, too, you always start with just one hut, so there's only one start position. Assuming that there are only a constant number of legal white-stone moves in any position, that's enough to give a k^{714n} bound on the size of the search problem for n brown stones. Not a practical way of doing it, but it does give the bound.
To be fair, "somewhere between 5n-4 and 714n" is not that bad of a constraint for such a problem.
5n-4 and 185n now
I loved this one! Finding a simple proof for something that initially seems almost impossible to prove is very satisfying and insightful!
Well the bounds aren't very tight. The numbers is between 5n and 714n which is pretty wide.
But of course the fact that the upper and lower bounds are both linear at least proves that the sequence grows O(n) at the limit which is definitely a cool result
I love how excited he gets over these numbers, it reminds me of how I get when I’ve got a problem I’m trying to sort out and figure out a clever way to do it. I get so excited solving it, this is an awesome video
I agree completely! I found a solution to this math problem I'd been working on because I realized it was basically a quadratic!
New videos with Neil Sloane are more exciting than most holidays in my home. Always a joy to see what new mathematical toys he's got in the chest.
That was extremely fascinating! Neil is both a great orator and a great explainer! The explanation of the upper and lower bounds was really intuitive
I love the way he stacks his big books, writing on the side what they are about
or he could just turn them around
I was about to write that I wondered if it had been proven that you can reach any arbitrarily high number given enough brown stones, but then I remembered the zigzag construction which literally already proves that. Very interesting video, loved it.
Yes, the linear lower bound already proves your question.
@@danielyuan9862 Yes, that has already been stated.
I wish my actual math classes were as pleasant as these videos.
These are the best. I love Neil's method. He shows you enough to follow his logic without ever repeating himself, and he's got all kinds of excitement about the topic.
I get the feeling that this video will lead towards progress being made on this problem.
Neil was making that really obvious. Someone will find a(7) no doubt very soon.
He made that statement even clearer on his TH-cam channel where he talked about this problem among others. He said it's probable new things will be found soon because not many people had tried to solve these yet.
I recall a few months ago Matt Parker set a challenge to the maths community to find periodic tilings for various hypercube nets. Within twenty-four hours correct solutions for all 100-plus hypercube nets had been submitted to his website.
7:39 The most ominous "very cunning" I've _ever_ heard in my life.
wow this guy is really cool, like a more chilled version of Cliff.
Cliff?
@@ScorieDivine Cliff Stoll, the guy with a 1,000 Klein Bottles under his house.
@@noblevi3623 Thanks, mate.
Am I the only one who thinks that this would make an excellent 2 player game? Players take turns to place sequential numbers, first one who doesn't have a valid move loses. So not only do you have to place your tile, you want to try and block the other player. With lots of different initial set ups of huts, the replayability would be huge!
Kinda like Hive but all numerical and no differentiation of pieces. But it could be fun to (selectively) add special moves. e.g. once a game, a player can place a -1 blue hut before they move. Or whatever. Would really blow up the game tree even more 😜
Love the videos with Neil Sloane. He's one of my favorite Numberphile guests.
Infinite space, a balance of procedure and freedom of choice, golfing for upper and lower bounds... This is recreational mathematics at its finest.
I, for one, would love a Neil Sloane ASMR video
I wonder if the sequence values up to n=6 were found by computer brute force or they were proven mathematically.
Almost certainly a combination of a smarter-than-brute-force computer search and mathematical proof that the search covered all the cases.
@@beeble2003 Almost like how God's number was squeezed out. It was mostly computer search but it was definitely doing it more efficiently than a brute force search.
The first few (n= 1 through 4) were trying every possible position accounting for rotational and reflection symmetry. The higher couple used some more clever symmetries but were still mostly brute force.
I don't think you meant it that way but it sounds a bit dismissive of computer-assisted proofs. They aren't the most elegant necessarily, but once they are independently verified, they are every bit as valid as manual proofs.
Specifically, I have vivid memories of people dismissing the computer-assisted proof of the four color theorem and loudly claiming to have found a counterexample. In reality, every last one of them turned out to be fallacious, to my non-existent shock. 🙂
For the lower bound: Assuming you place the first stone at (0,0), and the second at (2,2), by placing the 3rd at (3,-1) you could wrap around to the 1st stone again , using just 4 of the spaces around stone 3, and 4 of the unused spaces around stone 1 to get to 14. Continuing out as in the video would increase the lower bound to 5n-1 for n>2. I think...
But what we rally are looking at is asymptotics. So improving 5 would be the main goal. If we improve n then that would be even better
2:03 Because of symmetry, it doesn't matter.
I fail to see the use of it, but I am happy that he was so happy about it.
Well, puzzles don't always have an application. Or perhaps the application of puzzles is recreation?
Ah yes, reverse minesweeper
A curiosity to note is that for the first few terms, not only do the terms increase, but the gaps between them also increase; However, the upper bound is proven to be linear.
Videos made with this man encourage me to study mathematics instead of IT in University.
You'll get plenty of both in both tbh
What happens if you first put down 3 blue stones and 1 brown?
You instantly summon a certain mathematician TH-camr to help you with your next three moves
Mathception
I loved every minute of this, and now I want to play it so bad!
Wasn't expecting to care about this video. Was totally spellbound. Super cool!
The picture at 5:40 is sadly incorrect, the 15 and 16 needed to be 1 place higher.
The pinned comment now says this, but it was probably posted after you opened the page.
This guy's voice is amazing. He should do audio book reading.
I was going to comment the exact same thing. 😊
I HATE his voice. I'm struggling to get through the video. I would have to drop a subject if he was the lecturer.
Appears to be similar to a surface area to volume problem. Enjoyed that, thank you
The legend returns. I love Neil.
Edit: with a friend we got the new minimum up to 6n with 3 or more stones
You can get (n-1)*6 by having a line of 1001001001001, 2 is placed above and to the left of the leftmost 1 with another 1 to the left. Then just go along the line 3 4 5 6 7 ... and at the end loop around and go on the underside.
You're right. I believe it is 6n-7 when I drew it up. You should email Dr. Sloane to submit an edit for you so you can get your name in the problem.
This video just kept getting better and better!
I love the collection of books behind him. It’s exactly what I am interested in, from Bash/AWK to Mathematica! I just wish I was as smart as him!
anyone as enthusiastic with math and learning as he is will eventually be as smart
Just add if you want: 5:02 Gradshteyn and Kornshell - 6:07 The Maple Handbook - 6:47 The Enceclopedia of integer sequence - 6:49 Handbook of integer sequence....🙂
I wonder if there is a small modification you can make to rules such that the number of stones grows quickly in function of the number of huts.
Maybe allowing to place stone if it's the sum of it's neighbors divided by their common divisor
Wonder what would happen if you made the rules “can add any stones within the neighboring range to get the new value” rather than “all stones in the range must add to new value”; ie, allowing
412
53x
(where x is an empty square)
@@lesbianaconda2971 That wouldn't change much as you are still guaranteed to have a stone less then H/2 next to stone H. You would have to allow for a way to let large stones go relatively far away from small stones while not allowing them to go infinitely far
That doesn't change the proof of the upper bound that was mentioned in the video. In fact, even if you say you can add a stone as long as the sum of the neighboring stones is _at least_ the number of the recent stone, then the proof in the video holds.
Nvm I got it the wrong way around
Surprised we got through a Neil video without a mention of the OEIS! Though sequence A337663 does appear, of course.
great video! I'm so glad this is not yet another base dependent sequence, but an actually interesting mathematical problem
well you can argue it is just as dependant on the shape of the grid and the number of dimensions of the board as other sequences are dependent on number bases. Pretty sure the result of this would change if you had a hexagonal chessboard or other types
I love the visuals on this one. I was thinking showing the white numbered tiles as slightly higher on the graph based on relative size would much better help illuminate the concept visually. Well done.
Neil's voice is so soothing!
decided to quickly draft up a program to work it out, haven't looked at it smartly yet but there are 32 configurations for 2 tiles to land on 16 if we dont account for rotations and reflections
Theres going to be 8 symmetric answers for each with rotations, so it looks like 4 unique boards, but I dont recall if that is correct or not
@@tomladouceur3241 I'm going work it out a bit more tomorrow and filter out the symmetries and I'll get back at you
@@wollf92 There are a number of programs linked on the OEIS page if you want some tips and tricks, best of luck!
What happens when you extend the game up into higher dimensions? Obviously, you could just do the same sequences as a uniplane within the 3D space, but you've also got extra spaces now "above" and "below" that that you can expand into. I wonder if anyone has worked on that.
Has this been extrapolated to different grid shapes (triangles/hexagons) or higher dimensions? Or other limits (like no diagonals, or at least 3 neighbors)? Lots of cool things you could do with this game
That upper bound should still apply since it doesn't rely on grid shape at all (just the fact that to make a number you need to add at least 2 previous tiles). The lower, probably not since that relies on finding a particular construction
Also for triangles you'd have to decide if adjacency means sharing a side or if corner is enough (which is true of squares as well to be fair, and absolutely with/without diagonals is interesting)
@@metallsnubben i think the upper bound does depend on grid shape, because the number of cells at distance log2 N needs to be asymptotically less than N. This is certainly true of planar, non overlapping grids, and may even be true of euclidean n-dimensional non overlapping grids, but is not necessarily true of hyperbolic grids.
@@david-hogarty The real nasty question then is what... I don't even know what to call it, "level of hyperbolic" do you need to go infinitely high with N starting pieces
Animations are off the chain in this one
I'm a simple man. I see Neil Sloane, I watch and I like.
I love the recording of Neil's voice. Sounds like I'm being talked through a puzzle by a mathematically-inclined G-man. Very soothing..
This is a fascinating little problem
About n*log(n), there is probably a significant decrease like almost to (n-1)log(n-1) or smth due to the requirement that for any working configuration it's required to have two 1-pointers in a square of 3x3, since otherwise you simply can't place #2
This man’s voice is a joy to listen to
Mathematicians: "infinite 2d area, got it."
Every other human: **loading infinity* *please wait** "...uhhhhhh."
Using this same argument, can we show that if instead of a 2-D board we had an N-D board, we still would have an upper limit on the number of stones we can place? I think the fact that 2^x >>> x^N is relevant there, as well.
The same nlog(n) upper bound would hold for any dimension I believe
Would love to see a website with a simultation to play around with this idea!
Fantastic video. Computer science style complexity theory in a simple game.
I was stressed but thanks to this soothing narrator, I am calm.
His voice is so smooth, he sounds like John Hurt and David Attenborough
It’s a little easier if I take 65,000- I love Neil. After professor Eisenbud he has the best voice; so soothing.
Neil Sloane is the kind of person everyone likes for a grandpa 👴. Atleast I do.
You could actually modify the zigzag structure a little bit to place more stones around the first two before adding more browns to continue the zigzag, and then the lower bound becomes 5n-1 instead of 5n-4. In fact, just using the optimal arrangement from two browns, you can start building the zigzag on that with more browns and then the lower bound becomes 5n+6.
Here's a bit of a generalization of the puzzle: for some list of numbers (like the fibonacci numbers), what is the highest number N of which you can place x0 instances, with x1 instances of N-1, and x2 instances of N-2....; so: 1 of N, 1 of N-1, 2 of N-2, 3 of N-3, 5 of N-4...
Gotta love the Parker powers of 2 at 12:54 😂🤣
We've all had those lectures where we thought we understood, walked out the lecture with notes that look like that brown paper, and later find we aren't able to recreate the arguments.
When you are a serious mathematician and "Sloane" on TH-cam gives you ASRM. Major educator.
Ooh, and when the brown paper comes in at one. AND I got Adam Savage on there just now. :D
I love his ominous confirmation.
"Building in order... yes."
My goodness. You can hear how much paper/dust is in this room.
I'm convinced that this guy is a long-lost twin of Arthur C. Clarke
Neil Sloane's voice is so relaxing. I'd fall asleep, but I'm too interested in what he has to say.
second time a charm
He sounds like an evil genius and I love it
Man, I love this channel
Really nice. Basically the game of lifes lost cousin
He is my favorite numberphile guest
Players take turns placing brown stones until one player decides to play a 2 stone instead. The last player to be able to play a stone wins.
I really like the upper and lower bounds (the way they were derived).
As an engineering undergraduate student, I see a numerical solution to this using matrix arrays.
Consider the board to be a matrix of N by N size. Set X cells to be equal to 1 in random positions (these are the brown stones). For each i:N column and j:N row, detect if the sum of any two adjacent cells is equal to the cell value at the current index. If true, set the current cell as the new value. If repeated enough times, the results for the final value could be mapped out as a distribution, with the maximum being the highest achievable value (the answer we are looking for).
I'm sure there are plenty of kinks that need to be worked through, but those are my preliminary thoughts.
Has anyone tried this? I plan on doing it as soon as I finish my coursework.
Actually I'm not even sure if this would prove anything in either direction but in any case it'd be pretty computationally intensive to brute-force:
Say you're looking for boards with 20 huts and you've already figured out that those boards can't be larger than 60x60
Then in order to test all possibilities, you would have to test (3600 choose 20) configurations for the huts, and then solve all of them
That's not happening unless you can astronomically shrink the search space
"For that I need another piece of paper." 😁
The videos with Neil are always great!
The reason you can't do nearly as well as 714n is that stone placement is constrained. For example, if you have 3 huts, but no two are within 2 of each other, then each position has the same problem as with a single stone - there is no valid '2' position anywhere. So in fact, the size of the board we have to fit 'Everest' into is much smaller, than is constrained by the argument in the construction.
I'm not a mathematician with the skill to solve that problem, but I think it would be possible to show how close each new stone must be to the existing 'hill' and define the actual maximum size of the board we must fit 'Everest' into much more closely. For example, I think the 2nd stone likely must be within 2 of the first, and the 3rd stone likely must be within three of the 'hill' formed by the first 2 stones, so the best you could do for 3n is most certainly smaller than 75 which is much less than 3 x 714.
I found the video really interesting because even though the answer isn't known, what is known about it proves very counterintuitive. I would have first guessed that once N was sufficiently large that the answer was infinity - and I wouldn't have guessed N needed to be very large. But, having seen the proof that it can't be infinity, I would have next guessed that it grew geometrically (if even at a small rate). After all, there seems to be a slow upward trend on even the known terms. But that the upper bounds grows linearly is a pretty astounding result to me and suggests that for some N, there becomes a regular pattern (similar to the +5 pattern of the lower bound)!
It occurred to me at some point that Neil sounds like Professor Farnsworth from Futurama, and now I can't unhear it.
Reminds me of Minesweeper 🚩
I would like Neal to be on Computerphile talking about all those books behind him!
Somebody please give this man a new sharpie
It's like Consecutive Number Plate Spotting: you've got to do it in order
Happy new year, Neil!
There is a mistake in the graphic at 5:33, thanks to the comment of @Michal Karas. The 15 has to be placed one higher, as otherwise the 16 is in fact neighbouring 30. (1 + 14 + 15). Neil did it correct in real life.
The pinned comment now says this, but it was probably posted after you opened the page.