Stones on an Infinite Chessboard

Stones on an Infinite Chessboard - Numberphile

Рет қаралды 353,375

2 жыл бұрын

Another curious puzzle and number sequence from Neil Sloane. More of our videos with Neil: bit.ly/Sloane_Numberphile
More links & stuff in full description below ↓↓↓
Neil Sloane is founder of the On-Line Encyclopedia of Integer Sequences: oeis.org
More of our videos with Neil Sloane: bit.ly/Sloane_Numberphile
Pebbling a chessboard with Zvezda Stankova: • Pebbling a Chessboard ...
Patreon: / numberphile
Numberphile is supported by the Mathematical Sciences Research Institute (MSRI): bit.ly/MSRINumberphile
We are also supported by Science Sandbox, a Simons Foundation initiative dedicated to engaging everyone with the process of science. www.simonsfoundation.org/outr...
And support from The Akamai Foundation - dedicated to encouraging the next generation of technology innovators and equitable access to STEM education - www.akamai.com/company/corpor...
NUMBERPHILE
Website: www.numberphile.com/
Numberphile on Facebook: / numberphile
Numberphile tweets: / numberphile
Subscribe: bit.ly/Numberphile_Sub
Videos by Brady Haran
Numberphile T-Shirts and Merch: teespring.com/stores/numberphile
Brady's videos subreddit: / bradyharan
Brady's latest videos across all channels: www.bradyharanblog.com/
Sign up for (occasional) emails: eepurl.com/YdjL9
Thanks to all our Patreon supporters, including:
Ben Delo
Juan Benet
Jeff Straathof
Ken Baron
Yana Chernobilsky
Andy B
Michael Dunworth
James Bissonette
Jubal John
Jeremy Buchanan
Steve Crutchfield
Adam Savage
Ben White
Andrei M Burke
RAD Donato
Matthew Schuster
Nat Tyce
Ron Hochsprung
Ubiquity Ventures
John Zelinka
Gnare
Kannan Stanz
OnlineBookClub.org
Tracy Parry
Ian George Walker
Arnas
Bernd Sing
Valentin
Alfred Wallace
Charles Southerland
Bodhisattva Debnath
Alex Khein
Kermit Norlund
Mirik Gogri
Doug Hoffman
Xavier F. G.
Avi Yashchin

Пікірлер: 758

@numberphile 2 жыл бұрын

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.

@naman4067 2 жыл бұрын

@pkmkb 2 жыл бұрын

@willemvandebeek 2 жыл бұрын

Haha, I was about to make that comment :)

@imveryangryitsnotbutter 2 жыл бұрын

Oaky

@dotintegral 2 жыл бұрын

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...

@jeremyr6034 2 жыл бұрын

Hi this is Jeremy Rebenstock, Co-creator of this puzzle. Thanks so much for sharing it!

@tomladouceur3241 2 жыл бұрын

No way bro funny seeing you here

@serbestianmilo1477 2 жыл бұрын

Sweet 👍

@qeithwreid7745 2 жыл бұрын

If you place one brown can’t you just do 4 lines of 1s of into infinity NESW? Edit: no

@qeithwreid7745 2 жыл бұрын

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.

@serbestianmilo1477 2 жыл бұрын

@@qeithwreid7745 wow what a weirdo; no, you cant - there can only be one of every numbered tile.

@fangjiunnewe3634 2 жыл бұрын

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

@SurrealMath1 2 жыл бұрын

lol

@oncedidactic 2 жыл бұрын

The alas slays me 😂

@oldcowbb 2 жыл бұрын

same

@adityakhabiya5348 2 жыл бұрын

Blurst of times

@thaer_me 2 жыл бұрын

Lol, I thought I was the only one who misheard that

@pasunurusaivineeth3739 2 жыл бұрын

I am more impressed by how clearly he was able to explain the expressions for bounds than the actual problem. Excellent, professor!

@bernardobuffa2391 2 жыл бұрын

so elegant and revealing

@jamielondon6436 2 жыл бұрын

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 …

@renmaddox 2 жыл бұрын

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.

@jamielondon6436 2 жыл бұрын

@@renmaddox Maybe at the beginning, yes, so you could start off a couple rounds in or, as you said, place more brown stones …

@esajpsasipes2822 2 жыл бұрын

@@renmaddox with a limit on brown stones otherwise it could go on forever - see the minimum stones part

@esajpsasipes2822 2 жыл бұрын

but actually snakes and ladders could also go on forever so it's maybe not that important for the game to definitely halt

@Phlarx 2 жыл бұрын

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.

@johnchessant3012 2 жыл бұрын

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!

@hansdieter4537 2 жыл бұрын

Shut it

@General12th 2 жыл бұрын

@@hansdieter4537 Excuse me?

@hothi92 2 жыл бұрын

@@hansdieter4537 fite me irl

@evanbelcher 2 жыл бұрын

A really interesting problem! It's surprising to me that the solution was proven to be linearly bounded.

@nod2009 2 жыл бұрын

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.

@QuantumHistorian 2 жыл бұрын

@@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.

@Valkhiya 2 жыл бұрын

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!

@robinhammond4446 2 жыл бұрын

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!

@bernhardkrickl3567 2 жыл бұрын

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

@charlottedarroch 2 жыл бұрын

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 2 жыл бұрын

I added your new bound to A337663!

@charlottedarroch 2 жыл бұрын

@@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

@asheep7797 2 ай бұрын

Mathematician at work

@sicapanjesis3987 2 жыл бұрын

When u see there is an infinite chess board and Neil Sloane in it, it is a great video

@konstantinkh 2 жыл бұрын

To be fair, "somewhere between 5n-4 and 714n" is not that bad of a constraint for such a problem.

@NoNameAtAll2 Жыл бұрын

5n-4 and 185n now

@erikbrendel3217 2 жыл бұрын

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...

@fplancke3336 2 жыл бұрын

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.

@guillaumelagueyte1019 2 жыл бұрын

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.

@kindlin 2 жыл бұрын

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.

@AutomaticHourglass 2 жыл бұрын

Another argument is that the bound might be invalid for 6 dimensions as every stone would have 728 neighbors. wdyt?

@fplancke3336 2 жыл бұрын

@@AutomaticHourglass Sure, but another bound would work instead, with just another number instead of 714.

@sakkikoyumikishi 2 жыл бұрын

Always excited when there's a new Neil Sloane video 😊

@Bleighckques 2 жыл бұрын

I love his voice and the way he speaks

@d30few 2 жыл бұрын

@@Bleighckques reminds me of the scientist character from futurama

@bringbringish 2 жыл бұрын

This was very interesting, clear and the professor has a relaxing voice too, which is a plus in my book!

@adamplace1414 2 жыл бұрын

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.

@wrong1man 2 жыл бұрын

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.

@chillsahoy2640 2 жыл бұрын

Referencing Everest, Neil knows how to peak Brady's interest.

@mercer5888 2 жыл бұрын

Is that a pun or a spelling mistake 🤔

@chillsahoy2640 2 жыл бұрын

@@mercer5888 It's a pun, and that's the height of my comedic ability.

@ooc6233 2 жыл бұрын

Its all down hill from here

@vez3834 2 жыл бұрын

@@chillsahoy2640 Peak? Height? You must feel like you are on top of the world with these puns!

@murphygreen8484 2 жыл бұрын

@@chillsahoy2640 sure it's not the pique of your comic abilities? I'll show myself out

@aspuzling 2 жыл бұрын

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.

@beeble2003 2 жыл бұрын

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.

@EebstertheGreat 2 жыл бұрын

@@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.

@beeble2003 2 жыл бұрын

@@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.

@EebstertheGreat 2 жыл бұрын

@@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.

@beeble2003 2 жыл бұрын

@@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.

@mazza420 2 жыл бұрын

videos with neil are always absolutely wonderful!

@Triantalex 5 ай бұрын

false.

@TaranovskiAlex 2 жыл бұрын

I love videos with Neil Sloane, he manages to explain things in the best possible way)

@matthewwhiteside4619 2 жыл бұрын

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.

@danielyuan9862 2 жыл бұрын

Yes, the linear lower bound already proves your question.

@isavenewspapers8890 2 жыл бұрын

@@danielyuan9862 Yes, that has already been stated.

@GreenMeansGOF 2 жыл бұрын

I get the feeling that this video will lead towards progress being made on this problem.

@idjles 2 жыл бұрын

Neil was making that really obvious. Someone will find a(7) no doubt very soon.

@Wecoc1 2 жыл бұрын

He made that statement even clearer on his KZfaq 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.

@alexpotts6520 2 жыл бұрын

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.

@Dysiode 2 жыл бұрын

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

@LilZombieFooFoo 2 жыл бұрын

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.

@kenhaley4 2 жыл бұрын

I loved this one! Finding a simple proof for something that initially seems almost impossible to prove is very satisfying and insightful!

@PattyManatty 2 жыл бұрын

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

@CoteMoretz 2 жыл бұрын

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

@sebastianorellana3912 2 жыл бұрын

I agree completely! I found a solution to this math problem I'd been working on because I realized it was basically a quadratic!

@dg7815 2 жыл бұрын

I wish my actual math classes were as pleasant as these videos.

@MonsieurNab 2 жыл бұрын

I love the way he stacks his big books, writing on the side what they are about

@filipsperl 2 жыл бұрын

or he could just turn them around

@reidflemingworldstoughestm1394 2 жыл бұрын

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.

@PeterFreese 2 жыл бұрын

Love the videos with Neil Sloane. He's one of my favorite Numberphile guests.

@General12th 2 жыл бұрын

7:39 The most ominous "very cunning" I've _ever_ heard in my life.

@QuantumHistorian 2 жыл бұрын

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!

@oncedidactic 2 жыл бұрын

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 😜

@astromus 2 жыл бұрын

The videos with Neil are always great!

@noblevi3623 2 жыл бұрын

wow this guy is really cool, like a more chilled version of Cliff.

@ScorieDivine 2 жыл бұрын

Cliff?

@noblevi3623 2 жыл бұрын

@@ScorieDivine Cliff Stoll, the guy with a 1,000 Klein Bottles under his house.

@ScorieDivine 2 жыл бұрын

@@noblevi3623 Thanks, mate.

2 жыл бұрын

This video just kept getting better and better!

2 жыл бұрын

I loved every minute of this, and now I want to play it so bad!

@WeArePharmers 2 жыл бұрын

I, for one, would love a Neil Sloane ASMR video

@tactical1981 2 жыл бұрын

Happy new year, Neil!

@wesleythomas6858 2 жыл бұрын

Appears to be similar to a surface area to volume problem. Enjoyed that, thank you

@Matthew-bu7fg 2 жыл бұрын

one of the few numberphile videos I understood all the way through! Haha. Fantastic video! Very instructive. And a great problem too!

@WhirlingSteel 2 жыл бұрын

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.

@austinbutts3000 2 жыл бұрын

I was originally going to say n log(n) sounds like a better upper bound because it's smaller for all positive integers < e^714, but then I realized that's only a finite set against the infinite set of positive integers greater than that value. So well done on that upper bound, well done.

@danielyuan9862 2 жыл бұрын

That's why people think about big O notation. Because 714n beats n*log(n) for large n.

@Mephisto707 2 жыл бұрын

I wonder if the sequence values up to n=6 were found by computer brute force or they were proven mathematically.

@beeble2003 2 жыл бұрын

Almost certainly a combination of a smarter-than-brute-force computer search and mathematical proof that the search covered all the cases.

@nanamacapagal8342 2 жыл бұрын

@@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.

@tomladouceur3241 2 жыл бұрын

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.

@TruthNerds 2 жыл бұрын

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. 🙂

@peace2652 2 жыл бұрын

The legend returns. I love Neil.

@macronencer 2 жыл бұрын

Really enjoyed this proof. Very interesting game!

@JohnnyLeven 2 жыл бұрын

I loved this one. Very well explained.

@daskut. 2 жыл бұрын

Man, I love this channel

@alanshand829 2 жыл бұрын

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...

@jaggajasoos5067 5 ай бұрын

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

@descuddlebat 2 жыл бұрын

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.

@iPrint3D 2 жыл бұрын

"For that I need another piece of paper." 😁

@Sakanakao 2 жыл бұрын

Surprised we got through a Neil video without a mention of the OEIS! Though sequence A337663 does appear, of course.

@PopeGoliath 2 жыл бұрын

Infinite space, a balance of procedure and freedom of choice, golfing for upper and lower bounds... This is recreational mathematics at its finest.

@gurkiratsingh7tha993 2 жыл бұрын

As always great video

@Czeckie 2 жыл бұрын

great video! I'm so glad this is not yet another base dependent sequence, but an actually interesting mathematical problem

@filipsperl 2 жыл бұрын

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

@LukaszWiklendt 2 жыл бұрын

Fantastic video. Computer science style complexity theory in a simple game.

@triple16 2 жыл бұрын

Reminds me of Minesweeper 🚩

@EddyGurge 2 жыл бұрын

Wasn't expecting to care about this video. Was totally spellbound. Super cool!

2 жыл бұрын

I love Neil so much.

@PunmasterSTP 2 жыл бұрын

Infinite chessboard? More like "I want to know more!" Another fabulous Numberphile video that answers some questions but leads to many others; keep up the great work!

@ZachGatesHere 2 жыл бұрын

I'm a simple man. I see Neil Sloane, I watch and I like.

@shrimpstance 2 жыл бұрын

Neil's voice is so soothing!

@IamFluffY90 2 жыл бұрын

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

@metallsnubben 2 жыл бұрын

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)

@david-hogarty 2 жыл бұрын

@@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.

@metallsnubben 2 жыл бұрын

@@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

@PlutoTheSecond 2 жыл бұрын

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.

@kevina5337 2 жыл бұрын

Gotta love the Parker powers of 2 at 12:54 😂🤣

@elmiraguth 2 жыл бұрын

I really like the upper and lower bounds (the way they were derived).

@fejfo6559 2 жыл бұрын

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

@lesbianaconda2971 2 жыл бұрын

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)

@fejfo6559 2 жыл бұрын

@@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

@danielyuan9862 2 жыл бұрын

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

@clilhuseynov1364 2 жыл бұрын

Videos made with this man encourage me to study mathematics instead of IT in University.

@shigekax 2 жыл бұрын

You'll get plenty of both in both tbh

@Valvex_ 2 жыл бұрын

The picture at 5:40 is sadly incorrect, the 15 and 16 needed to be 1 place higher.

@beeble2003 2 жыл бұрын

The pinned comment now says this, but it was probably posted after you opened the page.

@TheSmegPod 2 жыл бұрын

I'm convinced that this guy is a long-lost twin of Arthur C. Clarke

@geraldsnodd 2 жыл бұрын

Neil Sloane is the kind of person everyone likes for a grandpa 👴. Atleast I do.

@PrimeCarrot Жыл бұрын

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.

@waynewelshans1172 2 жыл бұрын

This guy's voice is amazing. He should do audio book reading.

@danwoodward23 2 жыл бұрын

I was going to comment the exact same thing. 😊

@paulkennedy8701 2 жыл бұрын

I HATE his voice. I'm struggling to get through the video. I would have to drop a subject if he was the lecturer.

@andrewmirror4611 7 ай бұрын

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

@gilnims 2 жыл бұрын

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!

@magica3526 2 жыл бұрын

anyone as enthusiastic with math and learning as he is will eventually be as smart

@harcovanhees394 2 жыл бұрын

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....🙂

@zackattack2235 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.

@tomladouceur3241 2 жыл бұрын

The same nlog(n) upper bound would hold for any dimension I believe

@expiredoatmeal6176 2 жыл бұрын

Would love to see a website with a simultation to play around with this idea!

@jansenart0 2 жыл бұрын

Mathematicians: "infinite 2d area, got it." Every other human: **loading infinity* *please wait** "...uhhhhhh."

@orang1921 2 жыл бұрын

a great numberphile host!

@MrRyanroberson1 2 жыл бұрын

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...

@thelocalsage 2 жыл бұрын

also love videos with neil 🥰🥰🥰

@TheTechAdmin 2 жыл бұрын

My goodness. You can hear how much paper/dust is in this room.

@dbneptune 2 жыл бұрын

Very chill episode :)

@additionaddict5524 2 жыл бұрын

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.

@asabovesobelow8901 2 жыл бұрын

More Neil Sloane plz

@statelyelms 11 ай бұрын

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..

@detectivejonesw 2 жыл бұрын

This is a fascinating little problem

@reinatheomni-panda7028 2 жыл бұрын

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.

@precumming 2 жыл бұрын

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.

@tomladouceur3241 2 жыл бұрын

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.

@frognik79 2 жыл бұрын

I love his ominous confirmation. "Building in order... yes."

@celebrim1 2 жыл бұрын

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)!

@DeadJDona 2 жыл бұрын

6:12 Neil, you definitely know Primegrid... It would be nice collab if they create some OEIS project, where you can crunch some sequences of your choice. BOINC have everything for this.

@TheMA5B 2 жыл бұрын

great video! can you please link the papers where they prove the upper bounds?

@tbpotn 2 жыл бұрын

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.

@beeble2003 2 жыл бұрын

The pinned comment now says this, but it was probably posted after you opened the page.

@thomasanderson9383 2 жыл бұрын

Awesome video full of fascinating ideas. The pigeonhole principle strikes again!

@BenjaminEhrlich272 2 жыл бұрын

I was stressed but thanks to this soothing narrator, I am calm.

@Golinth 2 жыл бұрын

This man’s voice is a joy to listen to

@davidsteinhour5562 2 жыл бұрын

Animations are off the chain in this one

@hwangsaessi2335 2 жыл бұрын

Will there be a closed-form expression for the maximum number as a function of n (i.e., the number of brown stones)? If yes, it must be a linear function, since the upper and lower bounds are both linear, and the function must be strictly increasing, right? If not, can that even happen? Since you need the sequence to be strictly-increasing, positive integer-valued and between two linear functions...?

@beeble2003 2 жыл бұрын

Very unlikely to be a closed-form expression for something like that, though there could be a closed form for is limit as n goes to infinity. The function must be strictly increasing because, if it's possible to get to height h from n brown stones, it's also possible to get to h from n+1 brown stones, just by putting the last brown stone far away from the others. Strictly increasing isn't implied by the pair of linear bounds. 0,2,2,6,4,10,6,... where the i'th term is 2i if i is even and i if i is odd is bounded above by 2i and below by i, but is not strictly increasing. The actual answer is not necessarily a linear function: it could be something like i + log i.