How did Fibonacci beat the Solitaire army?
Vložit
- čas přidán 8. 06. 2024
- Fibonacci and a super pretty piece of life-and-death mathematics. What can go wrong?
00:00 Intro
02:20 Solitaire
03:12 Survivor challenge
05:32 Invasion
11:41 The triangles of death
20:22 Final animation
21:43 Thank You!
Here is an online version of Marty and my newspaper article about the possible positions of one remaining peg when playing peg solitaire on various boards
www.qedcat.com/archive_cleane...
Marty and my new book "Putting two and two together"
bookstore.ams.org/mbk-141/
Martin Aigner's paper "Moving into the desert with Fibonacci". Bit of a pain to access it for free, possible though via this site.
www.jstor.org/stable/2691046
This paper contains the proof that I am focussing on in this video. It also has Conway's golden ratio based proof.
An implementation of the solitaire army game by Mark Bensilum. Use it to play solitaire army general. Note that this implementation starts with all of the bottom squares occupied by pegs. Please read carefully how you are supposed to play the game using this app :)
www.cleverlearning.co.uk/blog...
The paper "The minimum size required of a solitaire army" by George I. Bell, Daniel S. Hirschberg, Pablo Guerrero-Garcia considers all sorts of variations of the basic solitaire army game. The animation and challenge at the end of the video is based on some of the findings in this paper. Highly recommended.
arxiv.org/pdf/math/0612612.pdf
Reaching row 5 in Solitaire Army using infinitely many pegs (featuring a pretty spectacular animation at the bottom of the page) by Simon Tatham and Gareth Taylor
www.chiark.greenend.org.uk/~s...
A page of very interesting solitaire-army puzzles by Luciano Gualà, Stefano Leucci, Emanuele Natale, and Roberto Tauraso
www.isnphard.com/g/solitaire-...
Numberphile videos on "Conway's checkers" starring the mathematician Zvezdelina Stankova
• Conway Checkers - Numb...
• Conway Checkers (proof...
Today's t-shirt: teeherivar.com/product/funny-...
Today's music: I promise by Ian Post
Enjoy!
Burkard
More than 12 hours after I put up this video and still no correct answers to the challenge at 5:20 :( Anyway here is an animated solution on Mathologer 2 for those of you desperate.
czcams.com/video/v-J1-0EQ8tY/video.html
The winner of Marty and my book Putting Two and Two together is Alexander Svorre Jordan. Congratulations. :) Thank you again to everybody who submitted an implementation of the mathematical dance that I talked about in the last video. Here are five particularly noteworthy submissions:
(Kieran Clancy) kieranclancy.github.io/star-animation/ (this was the very first submission submitted in record time :)
(Liam Applebe) tiusic.com/magic_star_anim.html (an early submission that automatically does the whole dance for any choice of parameters)
(Pierre Lancien) lab.toxicode.fr/spirograph/ (with geared circles)
(Christopher Gallegos) gallegosaudio.com/MathologerStars (very slick interface)
(Matthew Arcus) www.shadertoy.com/view/7tKXWy (implements the fact that BOTH types of rotating polygons are parts of circles rolling around DIFFERENT large circles)
congrats ! :D
Man.... i used to cry because of math....
I am now crying because of you...
Amazing... and thank you
do you have a math model like this for diagonal moves?
Tell us instead where to get that t-shirt!! The best thing in the whole video 😍
@@timlindberg3833 If the t-shirt is the best thing of the whole video that would be cause for depression :( Anyway, link in the comment as usual.
There is another sequence that goes 2, 4, 8, 20, infinity: the number of faces of a regular polyhedron made of triangles. The first one is a degenerate case with 2 triangles sharing all vertices, then tetrahedron, octahedron, icosahedron, and finally an infinite tiling when you attempt to meet 6 triangles at each vertex.
Nice observation :)
@@Mathologer Is it possible to use regular polyhedra to prove solitaire army?
Is advancing to row 1 somehow related to a triangular dihedron?
Is advancing to row 2 somehow related to a tetrahedron?
Is advancing to row 3 somehow related to an octahedron?
Is advancing to row 4 somehow related to an icosahedron?
Is advancing to row 5 somehow related to an infinite triangular tiling?
Yes.... your right....
@@ValkyRiver this is giving me river crossing puzzle cube vibes
True that 😃💡.
I'd be really interested in that "infinite soldiers and moves" solution
nvm just found it in the description 😅
I don't think he has enough hard drive space to make an animation of that.
megawhoosh
@@sedfer411 megawoosh indeed that was a super interesting read!
I was expecting to be Rickrolled by that link...
Instant classic. This just feels like the perfect “Mathologer-y” topic! It also had the possibility for some great animations, which I’m so happy you delivered on flawlessly. I’ll probably watch this a few times throughout the future to enjoy it again!
Yeah
A few years ago, a friend of mine participated in a popularization event for high school students (Maths en Jeans, Paris) and we offered an iPad to any student that would come up with a working solution for the 5th row. We had kids waiting in line to try, and they did not mind (nor go away) after we showed up that it was impossible. It’s one of my fondest memories as a teacher.
Whenever you feel marooned in a parallel universe and nothing seems to remind you of Kansas, five words will snap you back into familiar territory, the land of reason and kindness - "Welcome to another Mathologer video!" Or three notes for that matter.
I love this video. When you mentioned the problem, I first thought that it sounded familiar, then realised that I've heard of it before, including the fact that it is not possible to move 5 steps past the line. However, I have never seen a proof of it before, and I thoroughly enjoyed the proof.
Numberphile has a video on this featuring Zvezdalina Stankova with a proof.
The proof is rather abstract, though. Here's an attempt at a simpler explanation:
1 - You can get a man up 3 squares.
2 - You can get a man up 4 squares.
3 - If you could do both simultaneously, you can get a man up 5 squares.
4 - But here's the catch: After moving a man up 4 squares, look at all the empty space you carved out behind and you'll notice how there are no men within 4 squares of him, which means to get a second man behind him (i.e. "up 3 squares") _they_ would also have to move at least 5 squares in some direction, which is just a recursion of the original problem.
5 - Thus, the original problem is impossible.
What a joy it is to have you on the interwebs! I miss math from 35 years ago when I used to be smart and a chemistry student. Your channel as made me understand things I never really understood before. Bravo!
The vid has been up for 15 minutes. 1000+ views. 100+ likes. Just an ordinary fantastic Mathologer vid.
... and 2 weeks 96K, brilliant !
Jaw-dropping proof! I love each and every one of your videos, but this one really caught me off guard. Thank you Burkard! 🙏🏻
This one was so great! I can’t remember the last time I smiled so genuinely (at maybe anything in the last year) as catching the a-ha moment a couple seconds before the reveal. This was such a perfect Mathologer topic :) Thank you as always!
I'm still not over the fact that Conway is no longer with us. Its appauling how little online presence he had by today's standards. Or its just my greed talking, one of the two
True. I'm thankful that Numberphile talked with him a few time. czcams.com/play/PLt5AfwLFPxWIL8XA1npoNAHseS-j1y-7V.html
Who was Conway?
@@Exotic3000 Perhaps the greatest game theorist ever...
@@tcadityaa Thanks!
When I was young this game was being sold under the name "Hi-Q" by one of the big game/toy companies (Hasbro? Ideal?). A quick search reveals several companies were in on it.
This was long before haiku become a thing in North America, though Hi-Karate (after-shave, etc.) was being marketed.
The elegance of simplicity shines once again. Thank you for this delightful video.
So much improvement in the sound effect department. Kudos
1:34 I first did it with an example to get a feel for it and then proved it using induction.
For example F1 + F2 + F3 + F4 + F5 should be equal to F7 - 1. (7=5+2) I started expanding F7 in such a way that I get the terms from the left hand side. F7 = F6 + F5 = F5 + F4 + F4 + F3, now the first two terms are already good so I only expand the last two: ... = F5 + F4 + F3 + F2 + F2 + F1. Now we have reached the base case F1 = 1 and F2 = 1 so there is no way to expand F1 and F2 further by the recursive definition Fn=F(n-1) + F(n-2). But there is one F2 too much so we can move it to the other side to get F7-F2 which is F7-1 as it should be.
The proof by induction is very simple:
What is required to prove is that the sum from k=1 to n of Fk is equal to F(n+2) -1
Checking n=1 is easy: F(1+2)-1 = F3-1 = F1+F2-1 = 1+1-1 = 1 = sum from k=1 to 1 of Fk = F1
Now assuming it's true for n, we have to show that it also holds for n+1 i.e. sum from k=1 to n+1 of Fk = F(n+3)-1
We can split the sum such that the first part is the sum from 1 to n and then the remaining term is F(n+1). Using the assumption the first part yields F(n+2) -1 and added with F(n+1) we get by the recursive definition F(n+3) -1 as required. Q.E.D.
The answer to the puzzle at 5:20 is "B D and E". Only E can survive if you need the final peg to end in the centre, but the final peg can finish multiples of 3 away from the starting hole. That allows D to be final, finishing on the right, and B to survive ending at the top.
Just finished the code to solve solitaire problem for a game. I nearly cried to see all these maths envolved in it. You are amazing
Yes a new video from mathologer ! you never fail to satisfy my mathematical palate
Very nice. When one consider that the pins reflect the resources of an army, that is soldiers, transport, fuel, food, etc., than it reflects how far an army can conquer land. Without logistics, as the pin game is, it will starve out. That's why Napoleon lost its expedition to conquer Russia.
Happy new year mr mathologer!
For once, I was able to follow it all the way through, which doesn’t often happen. Nicely explained!
Ike its so engagingly enjoyable
Thank you for this very elegant explanation. I've heard about this impossible game in university and I remember different solution with powers of two. But the idea was the same - some non increasing function we called "potential".
Yeah! A new Mathologer video.
And a great shirt
When I think of solitaire, I think of the peg thing. Klondike is the very specific patience game that you would otherwise think, not the only patience game. I've been playing mod3 quite a lot recently.
This was fun to watch!
So, proving that fib(1) + fib(2) + ... + fib(n) = fib(n+2) - 1 (where fib(n) denotes the n-th Fibonacci number):
Just doing induction on n, by the induction hypothesis, fib(1) + fib(2) + ... + fib(n-1) = fib(n+1) - 1
So, fib(1) + fib(2) + ... + fib(n) = fib(n) + fib(n+1) - 1 = fib(n+2) - 1
(in the last equation I've used the recursive definition of Fibonacci numbers). Together with the trivial base case, this proves the statement.
Wow released on my bday !!!, great video !!
Such an interesting and well produced video and topic. Your animation efforts are wonderful. Thank you! I hope someone can make a nice 3D animation of the Fibonacci tower and soldiers advancing uphill.
The fibonacci connection that game? Wow yes, it seems so obvious now, after 30 years. I remember as a kid solving the grid by realising there was the 3 step pattern that knocked out shapes, so all you have to do to solve it is 'tile' the grid and solve it in order via those L-shapes. But then you point out that it's 3+5=8 and that the whole thing is numbers? And a Fibonacci sequence too?! That brought the same joy as solving the grid 30 years ago. Thank you so much!
One of the prettiest ideas I remember from long ago and never forgot. Phi is everywhere.
To contribute a tiny gem, in N dimensions you can get at most 3N-2 positions into enemy terrain.
Such a clever proof and simple enough for me to understand!
wow i was just reviewing a Mathologer video from 2 years ago and this came up. very nice
This helps motivate me to study for my maths exams next month.
The peg solitaire article is so cool! An unexpected real world application of the Klein four group :)
Yes! For anybody reading this here is the online version of Marty and my newspaper article about the possible positions of one remaining peg when playing peg solitaire on various boards
www.qedcat.com/archive_cleaned/212.html
I happen to join very late. However, in southern India we used to have centuries old game of tiger and goats, whose figure is like an equilateral triangle, (10x) on the top 10x3 size rectangle. Thanks a million.
It's amazing how much more intuitive this proof is over Conway's even though at heart the two are very similar.
Yes, I've known Conway's proof for at least 30 years and always thought it was the best thing ever ... until I found out about this Fibonacci powered variation :)
Interesting approach on this problem. Having already seen Numberphile's two videos on Conway Checkers I don't think I would have thought to use a monovariant that doesn't involve exponentiating a constant.
at 17:53 I laughed so hard that people came in to check on me. Absolutely phenomenal proof delivered wonderfully, as only Mathologer can do!
Super-duper! Thank you!
Back to back bangers.
do you consider doing a video on graph theory? i think there are some really intereseting puzzles anyone could understand which have a beautiful and not so obvious explanation. should be really fun
I'm halfway through and sooo excited for it to all come together!!
WOW
Glad that it worked so well for you. According to CZcams you've been subscribed for 5 years already :)
@@Mathologer I can't say I've been good about watching every video, but I've thoroughly enjoyed the ones I have! And I appreciate your replies to comments, whether something as mundane as this or something more complex like the circle-multiplication program a friend and I made in response to a video of yours a few years ago. Thank you for your content, the subscription continues to be well-earned 😊
Always a treat!
The proof was really nice, thanks a lot!
You are outstanding sir
At 5:20: the original marble you consider cannot be the final marble simply because it’s movement is always in steps of two. If you label all possible places it can move on the board, you see that the center is not one of those spots. Using the same argument for the other marbles, only marble ‘e’ can survive.
Correct :) Maybe also watch this .... czcams.com/video/v-J1-0EQ8tY/video.html
This was a really nice proof!
Very nice!
Now, what about the video on Mathologerized Galois theory you were talking about a couple of years ago? I'm really looking forward to it :-)
This is 😌🤌🏽 *chef's kiss*
A new record for me tapping out of a Mathologer video early. This time at 1:50 because I was so proud of myself for pausing and noticing that 1+2+1=4, 2+4+1=7, 4+7+1=12 etc., only to find out this was the wrong thing to notice, and that I failed to notice the correct thing, which was a relationship to the first column, thus once again proving math is not for me because I just don't see what is there to see.
What you noticed is essentially equivalent to the correct thing-we know that the right column turns out to be the sequence of numbers one less than a corresponding Fibonacci number. (Specifically R(i) = F(i+2) - 1) Because Fibonacci numbers have the add the last two to get the next relationship, adding R(i) = F(i+2) -1 and R(i+1) = F(i+3) - 1 gives F(i+4) - 2 and so adding one does give exactly F(i+4)-1 = R(i+2).
Don't be discouraged! There's plenty of interesting patterns to see in Fibbonacci (one reason it's so popular). I for one didn't see what you saw and think it's fascinating now that I see it. Just because your mind went to a pattern that Marty wasn't looking for this time doesnt mean it was wrong. He just happens to be using his pattern later in the video :)
@@hedgechasing I was wondering if there was a connection there! Thanks for sharing
Noticing an unintended pattern might be even better than seeing the 'trick' the author intended. The world is full of data and patterns, everyone sees it differently. Some of my favorite math experiences have been noticing a detail like that and thinking about it over the rest of the day, trying to figure out if it means anything.
My 1st thought on what the Fibonacci series and Fibbinnacci SUM series had in common is that the consecutive ratios of pairs of adjacent numbers both approach the golden ratio...but the video provided a different answer that was much richer!
Great video and explanation. There is a same topic in the numberphile Channel but this one is better
i love this video so much
Sir you are a genius teacher
Delightful proof!
The wait is over! :')
Thank you
Stopping the video and going downloading a peg solitaire app to get in touch... Be back soon!!
I'm a brazilian olympiad student, the time I traveled to where I was going to participate in Conesul (South America Olympiad) there was a training during 3 days before the test. One of the problems that my professors showed was this one, pretty fun problem, by the way. My solution at the time was, without loss of generality fix the point that's gonna be reached by the soldiers, and say it has an energy of 1. And then, the natural ideia that came in my mind was to say that any square that was K squares apart from the square we're going to has an enery of (phi)^{-K}. Like this, as well as your solution, the energy of the whole table is always, at least, preserved, and summing the energy of every square below the red line equals something less than 1 (which you can easily compute by some infinite power sum tricks). It's always great to watch your videos! thanks🇧🇷
Very nicely :)
You can get an easy intuition for the fact that it must be impossible at some point by looking at a straight line of pegs: Moving them all makes a 101010… pattern, so you would have to fill half the spaces back in just to just advance once. Coming in from all three direction just gives you space for O(n²) pegs, but you need O(2^n) to advance. And you cannot just grow out sideways arbitrarily, because then you need that many pegs just to get into the middle.
Mindblowing!!
19:14 - I thought I had a hair on my screen for a solid minute, but it was just the white silhouette from the last slide xD
The peg solitaire kept me happy when I was 6-7 years old visiting Grandma's bungalow, then I inherited it and played from time to time and occasionally it worked, though I don't think I ever memorized the strategy!
I wonder if the soldier version could be adapted to give the soldiers that are 'jumped over' more than one life so they only disappear after being jumped over twice or 3 times or n times? It could advance a lot further?!
Or how many wars might be prevented if the leaders battle it out individually with armies of small plastic (or wooden?!) soldiers instead of real people?!
Yes, with variations you can get a greater overall distance -- e.g. if diagonal jumps are allowed you can apparently get up to 8 or so squares away but there is still a limit.
5:57 Oh this one! I just recently watched a Vsauce2 video on it. It still feels surprising to me even after knowing the reasoning.
Still waiting the insane video about Galois Theory.
Hey Mathologer! Is it possible to do a follow-up on Conway's balance sheets, esp. how Conway perceived them (if possible) and how they are used to arrive at various impossibility arguments? Many thanks!
Finally!!! Ok now time to watch ☺️
Interestingly (and perhaps not too surprisingly), while there is an infinite solution to Conway's Soldiers in a certain sense, there is no well-founded solution. That is, every solution involves sequences of steps which are forwards-infinite (no final move) and also ones which are backwards-infinite (no initial move). You can't do it in the intuitive way of having some function f(α) on the ordinals α≤κ (where κ is some large countable ordinal), where f returns a legal position for each ordinal in its domain, each proceeding from the last by a legal move, where f(0) is the starting position and f(κ) is the winning position.
If we do allow arbitrary forwards- and backwards-infinite sequences in a solution, we can actually do better. We can make a soldier appear anywhere on an empty board! That's clearly not acceptable, so an additional requirement is necessary. Specifically, there is some number N such that no space on the board flips from empty to occupied more than N times. With that extra condition, the best we can do is reach row 5, using up every soldier in the process.
Yes, anybody reading this also check out the following (from the description of this video):
Reaching row 5 in Solitaire Army using infinitely many pegs (featuring a pretty spectacular animation at the bottom of the page) by Simon Tatham and Gareth Taylor
www.chiark.greenend.org.uk/~sgtatham/solarmy/
So many interesting ideas to follow after this. I’d be very interested if you were to delve into 2-player mathematical games like Hackenbush and Nim.
I'm sure @mathologer did Nim years ago when most videos had movie or tv hooks (How Not To Die Hard and The Futurama Theorem come to mind). The film to show off Nim was called Last Year in Marienbad. I have no idea what happened to the video though. I can't find it on the channel but I'm sure I watched it...
There is an excellent hackenbush video that was an entry in a competition by 3blue1brown. If you find their channel and look at the video about the competition, is the description is a playlist of the entries, and it is in there.
The music “I Promise” is by Ian Post.
It's awasome
You should do a video on s-power series. They're kind of like Taylor series but approximate a function from two points instead of one.
I think the original paper was "s-power series: an alternative to Poisson expansions for
representing analytic functions".
Professor great video as always!. I wanted to clarify. The first case, a rectangle whose area is equal to the product of an even and an odd number - it's clear how to find the odd one :). The second case is a rectangle whose area is an odd number, how to correctly determine the divisor ((2n + 1) and ((2n + 1) + 2). Probably a bicycle, but very interesting. Thank you.
What part of the video are you referring to?
@@Mathologer Oh, I must be confused :). I just keep thinking about your cube video. Interestingly, (1;2) is (1×2) and 2×4+1=9, then (1×2+1)^2=9. (2;3) is (2×3) and 6x4+1=25, then (2×2+1)^2=25. (3;5) is (3×4) and (4×5). Etc. Straight mystic :).
@@Mathologer all the same, there is probably a mistake :(. you can draw it, considering the golden ratio - the diagonal of the constructed square.
Please give a pause so I don't have to run up and press pause to spot the pattern.
Some of us are in the middle of winter sitting wrapped in blankets, so it can take a few seconds to get up.
But I got it before continuing in a minute or so.
(difference between the two columns is one less than two up.
It is interesting how you open comments section to Mathologer's video and see all these comments, 2-3 sentences long, with correct punctuation - you can say a lot about auditory even without reading them. Like a nice calm conversation between good people. Going to be the part of it apparently.
Survivor Challenge answer- Only 'e' can survive because the range of a stone is determined is evenly divided by 1 square.
1:30 also take a number from the right column it's equal to the sum of the number below it and to the left of it.
Very nice proof. I used to play solitaire with pegs but never knew the math behind it. Very illumunating.
Nice one. I understood ALL of it, for once....
Ps. RIP John Conway.
Mission accomplished :)
Remember playing it as a kid on long car trips.
Almost like a game of heads and tails. Cuts down large groups fast.
He looks and sounds like an Austen Powers villain. "ONE MILLLLLION DOLLARZZ!"
Long days back I was seeing your video.. but still I was understanding.. the debate this video very clearly thanks 🙏 Mr.mathologer..but what happened to mathologer.2.0???
I wonder if the fact that you can‘t reach the 5th row have also something to do with the fact that there is no equation with redicals to find the zeros of an 5 degree polynomial ?
Amazing 😁🤯
What is the max position we can achieve if we play in n dimensions? for n=2 its 4, for n=3 its 7, etc. Is there a nice closed form for it?
The general formula is 3d - 2, where d is the dimension :) This is proved in Martin Aigner's paper that I flash in the video.
thank you for another wonderful explication of a proof that even my block-headed self can at least taste -- and BTW: great T-Shirt.
The brief discussion of higher-dimensional lattices makes me wonder if anyone has considered, for any purpose (not just jumping pegs), an infinite number of dimensions
In topology I’ve seen infinite dimensional spaces be used to describe spaces of functions, though this isn’t something I know much about
1:32 oh interesting. I noticed it was also taking the 2nd 1 in fibonacci was x2 + (3 numbers below on the other side) and it repeats up.
came for the t shirts, stayed for the maths
I was wondering why the triangle of death needs to not only contain the starting formation but also every square the starting formation could possibly reach. I think it's because the weights of the triangle would become negative and then it's no longer guaranteed that, if the total weight of the formation is less then the weight of the target square, then there is no subset of the formation which has enough weight.
Here a suggestion: make a vídeo about the relationship between the brownian movement and the riemman hypothesis...I know the theme also belongs to physics' universe, but it's an great oportunity to do a collaborative video...anyway, I think it would be awesome!
I think I got it, now to restart the discussion ...
At the beginning, when you showed the sequence 1,2,4,7,12…
I noticed that they have a recursion relation of an = 2an-1 - an-3
Not sure if this is interesting but just thought I’d mention it :)
Aw man, I used to love peg solitaire! [wanders off to find a set] …
Kind of besides the point, but interestingly i've never seen the grid version of peg solitaire - only the triangle version called "tricky triangle"
Seeing the pattern of the summed fibonacci numbers reminded me of Gauss' sum a little.
If a soldier jumps an empty square backwards to create a soldier, then the additive remains....but question is, can you still get to the fifth by allowing it?