A Lifelong Mathematical Obsession
ฝัง
- เผยแพร่เมื่อ 8 ก.ค. 2024
- ⬣ LINKS ⬣
⬡ PATREON: / anotherroof
⬡ CHANNEL: / anotherroof
⬡ WEBSITE: anotherroof.top
⬡ SUBREDDIT: / anotherroof
Contact me via my personal website if you’d like to hire me as a tutor:
⬡ www.drmcgaw.co.uk
⬣ ABOUT ⬣
All my life, I have been obsessed with a counting puzzle I came up with as a child. Turns out, I’m not the first to think about it. Known as Hertzsprung’s Problem or the n-kings problem, I present an elementary proof of the general formula given by Morton Abramson and William Moser.
⬣ TIMESTAMPS ⬣
00:00:00 - Introduction and History
00:11:04 - Overview
00:17:14 - Stars & Bars
00:23:44 - Inclusion-Exclusion Principle
00:29:31 - Pascal’s Triangle
00:33:27 - Forbidden Pair Options Part 1
00:43:51 - Forbidden Pair Options Part 2
00:51:55 - Number of Permutations
00:55:52 - Putting it all Together
01:03:22 - A Cleaner Way?
01:06:40 - Outro
⬣ INVESTIGATORS ⬣
Nothing for you in this one. Sorry!
⬣ REFERENCES ⬣
M Abramson and W Moser, Combinations, Successions and the n-Kings Problem. Mathematics Magazine, Vol. 39, No. 5 (Nov., 1966), pp. 269-273.
⬣ CREDITS ⬣
Music by Danjel Zambo.
Images
Explosion:
www.vecteezy.com/video/297431...
Hertzsprung-Russell Diagram, European Southern Observatory:
commons.wikimedia.org/wiki/Fi...
Ejnar Hertzsprung and Severin Hertzsprung are public domain. - บันเทิง
![ตีสิบเดย์ [FULL] | ครอบครัวสะท้านทุ่ง "นางบี & อ้ายสติ๊ก"](http://i.ytimg.com/vi/A1rhYcxxNtA/mqdefault.jpg)
CLARIFICATIONS AND CORRECTIONS
Correction: In my efforts to simplify the derivation to make it more video-friendly, I did make a mistake. Sorry about this! The final formula is slightly wrong in that the k=0 case in the final sum should yield n!, when in fact the k=0 case as presented in the video yields 0. The k=0 case is "count all permutations which contain at least 0 forbidden pairs" which is equivalent to "count all permutations" which is of course n! but I didn't account for that in my simplification! One viewer suggested this alternate presentation, which I agree with: Take the sum from k=1 to n-1 and add n! on at the end.
Clarification: So I really should clarify, I didn't entirely come up with this proof! As I mention at 00:00:34, this problem is already solved, and at 01:05:14 I mention this is an adaptation of Abramson and Moser's proof. They go about things much more generally and *then* apply it to this problem. I took some of their ideas and adapted them specifically for this problem from the start. The idea of counting "forbidden pairs" is my own way of streamlining their solution but I don't do enough *new* stuff to take credit for deriving this formula.
although you did mention that its an adaptaion of moser's proof, you mention it at the end of an hour long video. aint nobody going to see it. for future reference i think its better to put it at the start of the video! also great video!
@@Jrakula10 He mentions it right at the start. He says he knew there already was a proof but it seemed very complex to him and for years he didn't dedicate himself to fully understand it. But now he finally made that effort.
@@christianbarnay2499 Thanks for defending me, I appreciate that -- but to be fair I think @Adam Jrakula does raise a legitimate concern and I do regret not being crystal clear about that upfront!
@@Jrakula10 Then again, references do generally go at the end of a paper anyway, and this isn't even being presented as a new proof so an interested party should be able to find the relevant information
Great video! And congratulations on being able to contribute to your lifelong obsession by proving John Keith's conjecture. But as of this writing, the OEIS still lists it as a conjecture. Did you publish your proof, or at least make it publicly available somewhere? If so, then the OEIS entry should be updated.
So... I just now realized that this is "the urinal problem" as my friend and I referred to it, where there's a line of guys waiting to use the urinals and you don't want to be that guy who walks right up to the guy just before you in line who hasn't started peeing yet, so you can't pick an adjacent urinal to the person directly before you, but can be adjacent to an already in use urinal.
mathematical pissing
One of these your friends? people.scs.carleton.ca/~kranakis/Papers/urinal.pdf
:/
:0
Almost, but there are a few more constraints. If there are 5 urinals, and the first two people go to 1 and 5 respectively, you can't go to 2. You are required to choose #3 and #3 alone.
Oh my god. At 00:03:30, I had a realization: "this is that shuffling problem!"
As a kid, I breifly became obsessed with the idea that a collection of items wasn't really, truly shuffled, unless you could do it in a way such that none of them are adjacent to one or more of their original neighbors. As a teen, I realized that it's trivially impossible to do this for 2 items, and provably impossible for 3 (i just worked through each of the 6 permutations). Never gave it much thought after that...
Haven't watched past this point yet, so I imagine you bring this equivalence up. I've never left a comment before finishing a video before, but it's been a while since I've been excited about a problem like this. I guess we were both weird kids, huh?
Thanks for this content, it's somehow always more engaging than I expect.
Ironically, shuffling it that way makes it a worse shuffle, since you know that it's impossible for two items to be adjacent to their original neighbors, whereas true random shuffling gives you no information about the order of the items!
He mentions this later as "forbidden pairs", and says it's a bijection of the original problem
now I'm still thinking about it 🤣
6:44
please do any of us comment readers know what the problem of counting the unequal shapes of n adjacent squares can be called?
This makes me curious about the asymptotic behavior of the solution for large n. If you randomly shuffle a large number of items, how likely is the resulting shuffle to have this property? Does it approach 1, or 0, or some finite number? The solution we ended up with is complicated enough that it's hard to tell.
Proving some obscure conjecture, relating it to a toy problem thought up when you were young. The process is such a cool thing.
4:24 that's got to be the best fidgeting habit. imagine some genius seeing your randomly fidget in public and calls you out for going through all the permutations.
9:17 There is indeed a piece in Shogi that moves like that, the Dragon King. The puzzle can be restated as the n Dragon King problem.
Someone else made that comment during the premiere -- really great fact! And the "n dragon kings problem" is way more badass.
In fairy chess it's sometimes referred to as the Admiral, a combination of Rook and Ferz. (Ferz being a bishop that can only move one square)
@@AnotherRoof , the piece is also known, more briefly, as the dragon. The "n dragons problem" rolls off the tongue a bit better, I think.
@@Schindlabua Very interesting, where I'm from, Ferz is just another name for the queen (and the more common one actually)
The skill with which he moves his fingers independently is really impressive.
His ring finger dexterity is phenomenal!
😏
There is where I realised I'm not psycho enough for this specific problem...
He has been practising since he was about 6. This doesn't diminish the impressiveness.
Is that how it feels to be trapped in your own body?
holy crap I used to do this as a kid. I would tap my fingers using the exact same rules you described, and would spend countless hours thinking on the patterns as well. My parents actually had a conversation with me because I would tap the patterns out during conversation and apparently that isn't okay.
😮
Man, you single-handedly reinvigorated my interest in math 10 years after I graduated (comp sci).
I can't believe how clear and concise you make it all out to be. Kudos!
Single-handedly
😂
Get it!
😂
16:54 I'm probably wrong but could not think that the function and the sum from n to 0 of the possibilities of a finger down on n?
This premier is amazing and it's really impressive that you managed to come up with a solution. While elegant simple proofs are often well liked, it's important to also appreciate problems with solutions that take a lot of skill, time, and rigor
I really should clarify that this isn't entirely my own work -- as I say in the description and at 01:05:14, this proof is an adaptation of Abramson and Moser's approach!
You have such a natural talent for teaching and balancing tangible clarity with abstract principles. I've been using the kCx equation for years for all sorts of subjects but I think only after watching this do I recognize the power of it and understand how to apply it when working out problems. I found your channel last week and literally finished every one of your videos in 2 days. Your series on numbers and set theory is among the most impactful knowledge I have ever received and sent me down an obsessive rabbit hole that has made math more exciting than it ever has been. Thank you so much for what you do.
I cannot believe the quality of this presentation and education, I believe that I actually followed and understood the whole presentation and that seriously surprises me, I mean I'm not dumb but haven't been in school for 10 years and the only math I do is what's needed in trades, addition subtraction fractions and occasionally some geometry
I'm stopped at minute 10, but I wanna take a crack at solving this my way. I'm a computer scientist, so while closed formulas and proofs that they work are interesting, I'm usually more fond of finding an algorithm that can get to the answer instead, and the moment you mentioned that in the 6 case, removing finger number 3 gives you a 2 case and a 3 case, my brain instantly latched on to a Dynamic Programming (DP) algorithm.
DP works when solving a smaller version of the problem will inform the bigger version in a way that will reduce the amount of calculations that you need to do. A common way to show this strategy is with the fibbonacci sequence: If I want to calculate f(15), I will need f(14) and f(13); the catch with DP is that I will create a "memoization" vector that will remember previous solutions, so if I calculate f(13) first, when is time to look at f(14), I already know f(13) and it is just a lookup.
This problem is a little harder than a straight forward DP, but it is still solvable, but we need 2 memoization vectors: solutions_edge, solutions_other; For convenience, imagine that the first vector will always start with the number 1, and it will be apparent why it is important soon (if not yet). The second one has all other solutions for the N sized problem (including the ones starting the other edge). My idea is:
1. Solve the case starting in pin 1; when we do that, we have exactly the case N-1 except we can't pick pin 1 again, so we have solutions_other(N-1); Save this number in solutions_edge(N)
2. Iterate through all the possible pins from 2 up until N/2 (inclusive); by removing pin I, you get 2 groups of size A and B such that A + B + 1 = N. Then you have multiple ways of solving your new situation:
2.1 solve A and B separately; if you start with A, there are solutions_other(A) possibilities to do it, and moving on to be you have solutions_edge(B)+solutions_other(B); Similarly, you may start with B, for a total of 2 * (solutions_other(A) + solutions_other(B)) + solutions_edge(A) + solutions_edge(B);
2.2 for the other cases, you have to have enough legal moves in the B side to be able to interweave A moves in the illegal possibilities, so for every B permutation, follow it and if you find move than A illegal moves, that permutation is illegal, move on to the next. For every legal legal permutation of B that you find, you can calculate how many solutions it can have as follows:
2.2.1: If you have L illegal moves in the B permutation, you can space them my with A choose L options of moves on the A group; so far the permutation has A choose L moves
2.2.2: for the remainder A-L options, you can interweave them as you'd like in the B+L locations; which give you (B+L) choose (A-L) options
2.2.3: the final part is figuring out if for a given set of A-L choices, they can be side by side instead of neighboured by B moves. I haven't figured out how to do it yet.
2.3: Save this number to solutions_other(N)
3. do solutions_other(N)
4:24-4:36 in another life you were one of the best prog drummers. That was actually a really sick beat
Another life second channel?
Bro when you cycled through the possible combinations you made a sick beat 😂
I think it would help to say "every row of pascal's triangle alternating sums to 0, except the first row. This is the key that makes the whole formula work because the permutations we're interested in, those with 0 forbidden pairs, correspond to the first row and is why the final formula counts only them. Excellent video!
0th actually
It adds up to 0^n (where the first row is n=0) :P
@@columbus8myhw but 0⁰ is usually either undefined or 1
this is crazy to see, I've had this problem in my mind since I was a kid. I wasn't thinking about buildings, just thinking about twitching my fingers
I hope you find this solution as cathartic as I did!
It’s funny, because I also conceived of something like this problem as a child. But with two caveats: I considered the CYCLIC case, so 15 and 51 are forbidden, and derived one path, but with five different starting points and two directions, so ultimately 10 paths. But I’ve never sat down and proved that list is exhaustive
I also thought about this too and it's another one of my fidgeting habits! And it is exhaustive for the 5-case but not 6-case and beyond. This is easy to see if you draw the graphs; for 5-case you get a "pentagram" graph but for the 6-case you get a "Star of David" plus some extra edges which yields more solutions!
I conceived of the problem in this way, (also with my fingers), years ago and hadn't thought of it since. Glad to have stumbled upon a video on it.
If I remember correctly trying to solve something similar, adding cyclic property means that you’re trying to position kings on a torroidal chess board so that no king is in check. Haven’t watched the video yet, this might get mentioned
@@oleg-avdeev In this case it's actually a cylindrical board because the first choice is allowed to be adjacent to the final choice. There's an amazing ebook out there with lots of problems like this for different pieces on different boards -- will edit my comment later with a link.
holy shit cyclic geometry dash
truly beautiful, thank you. the abstractions built up in "Forbidden Pair Options Part 2" are so satisfying. also, i must be that formula's mother because i think it's pretty great...
Yes, AnotherRoof, I will come with you on this journey.
I truly like this video. I think it is the best so far I have ever seen that manages to be both understandable and honest about how chaotic it often is for a mathematician to find a solution.
The stars and bars problem is the one I learned in the combinatorial class in my first year of university. I understand it, yet always forget how the solution goes the next day.
Man, this was such a pleasurable adventure! To have that come full circle since childhood must have felt amazing.
Thank you kindly random handsome mathematician for the treat. Definitely excited for your future work! Keep sharing! ;)
One of the weirdest thing I learned from this video is that I cannot independently move my fingers like he does at 4:16
The first time he did it I was like "Oh sh*t"
This is a fantastic video! I love that you didn't start with the proof but rather constructed a story about your attempts to solve it with more and more powerful tools. Awesome problem too!
I just happened to come across this channel and I'm left wondering why the algorithm gods didn't recommend this to me sooner. Another Roof, I absolutely love the longer math videos. You've gained a long-term viewer.
This video was so good in fact that I had to make a Patreon account!
Alex's introduction is absolutely true: lots of interesting steps, perfectly detailed as always. A very beautiful enumeration problem... Thanks!
Before watching more of it I feel like there has to be some sort of geometric solution to this problem. Something involving choosing vertexes of a polyhedra. I can’t think of it now off the top of my head but it *feels* like there should be.
I would love to see a proof based on this approach! I talk about path-complement graphs at some point and maybe they could tie in to the geometric interpretation...
Pascal's triangle played a large role in this proof, and also shows up a lot in geometry, so I would not be surprised in the slightest.
The 2^r((n-k)Cr) looks suspiciously similar to the formula 2^(n-m)(nCm) for finding the m-cubes on the boundary of an n-cube.
This was an extremely enjoyable journey. Very good and clear explanations, and I particularly liked that you planned your terminology to be as intuitive as possible ("cell", "bin" etc.) As a software engineer, I always love it when people take the time to choose the most meaningful words to minimise confusion.
This was such a brilliant video!! I adore your content as always, please please please keep up the great work!!!
Another great video ! This channel is really underrated
How do you not have 1 million subscribers yet?? This channel is a not a gold mine, but a DIAMOND mine
I’m so happy for you. 😊❤ and i liked this long video
Commenting for the Algorithm and also to say that this was a blast of a video, love them crunchy combinatorics
whoa this is feature length
ive only watched a few minutes
definitely gonna go back to watch some more
thats kinda wild that youve been thinking about this problem lieterally from as a child
and the fact that youre actually studying maths so you can figure the problem out...
amazing
I love the idea of you tapping out those patterns and one day some other mathematician picks up on the patterns, happens to know about the problem and its solutions, and you become good friends.
This video is amazing on every level: clear explanation of the problem, logical clear steps to solution, excellent visual aids (the stacking black cards to make the equation especially), excellent video editing (jump cutting to remove the writing on the blackboard for example), an interesting starting problem, the personal historical context, the examination of existing discussion/proofs.
Double thumbs up, if I could.
This may be my favorite video on TH-cam to date.
Amazing explanation, I just loved the way you discovered this problem in your childhood and made this problem your ambition in the upcoming years of your life
This was really really good! Thank you for presenting this video!
Deep explorations of math that anyone can enjoy are really valuable and it's one of the reasons I enjoy this channel so much :)
Comments like this make my day -- thanks for watching and glad you enjoyed!
This is, without exaggerating, one of the best videos I've ever watched on TH-cam.
that triangle plot twist at the end reminded me of how pi sometimes shows up in random and unexpected places. what a wonderful and engaging video, I hope you're proud of your skills in videomaking and teaching!
I've thought about this as a kid when trying to lay my fingers over each other without having neighboring fingers touch on a single hand, but I was just happy with one solution which I was physically flexible enough to do
3:52 I did that as too as a child. I was so happy when I found that there was only one solution (and the symmetrical) for the 4 digits case.
Oh i am glad that I found your channel. Love your long videos and enjoy going deep here 👍
I love it when you think you're a genius, then go to the oeis and discover you're problem has been torn to death
Very nice video! Love the story and style of presentation. Just browsed in by YT recommendations and was not disappointed.
The almighty algorithm must have been pleased with my offering...
Your work is amazing. Please please please keep on going. For our sake!
Thanks! As long as people continue to watch and support me, I have no intention of stopping.
Wow this was amazing! I have never even thought like this!
For those wondering, the Danish letter says:
To decide the number of ways, in which the numbers 1, 2, 3, 4 ..., n can be put in order such that, the difference the difference between adjacent numbers is everywhere different from 1.
(This is to say, that for example the number 3 is to be neither immediately to the right of or to the left of the numbers 2 or 4, 7 neither immediately to the right of or to the left of the numbers 6 or 8 etc. - For n = 4 there is only two possible solutions to be had, namely 2413 and the reverse 3142).
The grammar is archaic and lovely, kinda shakespearean
Yup, this exact problem has struct me too. I'm 3:28 in, so I think I want to stop it here and see how far I can get myself.
another nice metaphor for these kind of problems could be music, if you think of playing N notes with similar conditions
Yeah, I used to do exactly my finger fidgeting thing but on the piano!
@@AnotherRoof I wonder, were all the 14 melodies similar in some aesthetic way?
@@puzzlinggamedev To be honest it sounds kind of ugly 😂
Sounds like an even stricter version of the Twelve-tone Technique
Really cool, and i could actually follow along and understand it! That concrete example really helped, and I loved the feeling of recognising the three techniques/bits of knowledge mentioned prior to the construction of the formula.
I'll watch this in a few sittings. Looks great!
Now you should update OEIS with your proof so it doesn't say conjecture anymore
It's awaiting approval!
Excited.
Nice explanation, you make complex maths easy to understand. You're doing an awesome job.
So much maths on youtube is "pop maths" where they don't really explain the proofs. This is really something special!
This is probably the best math video I've ever watched.
This is great. Both interesting and helping me revise for the combinatorics part of my first year probability exam next term
Excellent and clear explanation. Thank you for your effort in presenting your solution to a wide audience.
I called this the bored summer problem. Where I'd shuffle games by genre, roll a dice to pick 6 games from a catalogue and skip genres on its left and right. Didn't know this was an actual thing until today. lol
It's beautiful that with such simple tools you can solve challenging problems. Very elegant solution
Loved the video! Keep up the great work
The cliff hanger was too much, so I joined the patreon- and the extended cut was amazing!
God I love your channel, thank you for the content!
you know you are a good educator when you make me think "oh its not that hard" fully knowing i would never be able to so this at my current level
I play a lot of card games so I did a similar thing trying to mix up/shuffle a small deck of cards, picking them up one at a time so that no two cards are adjacent in order.
Shockingly, when I was a kid, I had exactly the same thoughts with tapping my fingers and developed exactly the same fidget. I would also go methodically through every single combination, before moving on to other tapping patterns, maybe tapping out rhythms, and then my mind wandering elsewhere. I don't have autism and don't fidget that much anymore, so I don't really do it as an adult, but it was something I did all the time as a kid in lower and middle school. And I never told anyone about it, because it never even occurred to me as something to mention.
I also explored all possible sequences for n=5, and I paid special attention to the ones where you could get stuck. With only n=5 fingers, you don't get stuck very often. I also looked at n < 5, noticing that you can get stuck in the cases n=3 and n=4 and would always get stuck when n=2. As the number of fingers increased, it seemed like you got stuck less and less often, but I couldn't rule out that n=5 was somehow unique. When I explored n > 5 by adding one or more fingers from my left hand, I wasn't trying to count all the possible ways to do it _correctly._ I was mostly interested in how often you got stuck if you tapped at random. I had no method except picking fingers arbitrarily, like a really slow Monte Carlo simulation. At other times, particularly with n=6, I would try to include every single possible combination, though I didn't count them. It seemed like there was some obvious pattern that ought to present itself. Certainly the more fingers you add, the more often you get stuck (which is hardly surprising), but I couldn't figure out any pattern beyond that, so at some point I dropped the question. I had almost forgotten about it until I saw this video.
The fact that you understand your problem well enough to make an engaging long-form video that uses simple language that a layperson can understand is extremely impressive. I hope that you're teaching High School or Middle School in the US. We need this kind of Math education here so desperately. Not nearly as badly as we need *proper* Theological education in schools, but still.
I can read Danish, and the paragraph at 9:31 is well explained, despite being so old that nouns were capitalized, a practice abandoned in modern Danish. Also, passive voice triggers the grammar police in English. Danish provides a conjugation of the verb indicating passive voice. "For n=4 obtains thus only two... ", anyway, here's a translation into modern English.
An Assignment of Combinatorics
by S. Hertzsprung
To determine to number of ways, by which numbers 1, 2, 3, 4 ... n could be placed in a row such that the difference between each adjacent pair of numbers everywhere must be numerically different from 1.
(Meaning, that 3 must not be to the immediate left nor right of 2 or 4, 7 neither to the immediate right nor left of 6 or 8 and so on. - For n = 4, one obtains this only two possible arrangements, even 2413 and the reverse 3142.
you just described my childhood but in my case it was the bulgarian solitaire problem
Amazing video. That is passion! Thank you.
Your finger fidget rhythm is awesome!
Speaking of weird obsessions. As a tinkerer, I love to take things apart, and when assembling them back together, I always (ALWAYS!) wonder: what are the chances, that a randomly chosen screw will end up in its original place.
what confuses me most is the existence of toast racks
why not put them onto a stack so they stay warm longer?
I love how many comments (this one too) are basically, "I thought about this when I was a kid too!"
excellent video, some great exposition. really convinced me that combinatorics is excellent for teaching/explicating advanced mathematical concepts, I'll definitely try it out next time I need to explain what I do to others
The version of the five-finger problem that I came up with is a bit stronger: Touch the five fingertips of one hand to the five fingertips of the other, such that adjacent fingers on a hand don't touch adjacent fingers on the other hand, _and_ matching fingers don't touch each other (e.g. you can't touch thumb to thumb).
A solution of this version is actually a double-solution of the five-finger problem-one solution for each hand. There are only two solutions to this problem: one is 24153 one the left hand, 31524 on the right; the other solution is the same but with the hands swapped.
I've always thought that swapping which hand gets which order results in different hand shapes (notably, the middle finger is curled down in one version and extended in the other). But while writing this, I realized that it also depends on how you lay the hands against each other. It's comfortable to hold them palm-to-palm with about a 90° angle between the two hands, but you can turn them to form the angle the other way (i.e. swap which hand's thumb is close to the other hand's fingertips) to get the alternate hand-shape without swapping the ordering. You can't keep the fingers touching turning, though-they'll get tangled. This, naturally, leads us to wonder about the generalized problem of touching n m-fingered hands in k dimensions.
I THOUGHT I WAS THE ONLY PERSON WHO DID THIS :’) i was so happy when i came across this
Oh and yes I can read Severin Hertzsprung's description of the problem. It's such a nice way of talking about the problem. Saying that any part in such a sequence cannot be directly to the left or directly to the right of the previous number. Oh and it's written in such regular language that it makes modern mathematical proofs look like the ramblings of a madman.
You just made me remember of finger fidgeting I used to do. It was basically the game you described, but I would repeat the sequence over and over. My reasoning was that tapping two neighboring fingers consecutively "felt bad" in a sort of OCD-manner. This repeating meant that a sequence such as "24153" would be invalid, because repeating it would yield a 3 followed by a 2.
That's interesting that you have this form of a cyclical approach, because another comment mentions a different cyclical approach. For theirs, every number has two neighbors, so, using n=5 as an example, 1 is obviously a neighbor of 2 but also a neighbor of 5, since that is the opposite end. What's funny is that these two different approaches of being cyclical work out to the exact same ten solutions in total for n=5 (though I doubt this holds for higher values of n).
@@SgtSupaman Interesting! Maybe our games are more similar than one might think. They both introduce one extra ”pair” that has to follow the rules - mine being the first and last digits in terms of position in the sequence, while the other game checks specifically digits ”1” and ”n” against each other.
1:03:10 In the grand scheme of things, at least it has a formula that can be written on one line as a composition of relatively simple functions and summations, even if it's not quite closed form.
That's hard work. I'm tired after watching this halfway through, but I can keep going. Feel the burn!
OMG I DID THIS IS AS A CHILD AS WELL! Thanks for reminding me!
This is exactly what I mean when I say, "from here all that remains is a very tedious combinatorics problem..." And then assume I have a function for it.
I know I'm probably not even 5th person to say something like this in the comments, but you know a puzzle's lovely when you come up with the puzzle in your head during the intro, before you explain it yourself.
Great explanation and presentation as always, keep up the good work!
Danish speaker here. The two letters at 9:33 says
A combinatorics exercise (by S. Hertzsprung)
Determine the number of ways in which the numbers 1, 2, 3, 4, ..., n could be positioned in rows such that the difference everywhere between two numbers next to each other is numerically different from 1.
(This means that for example the number 3 cannot stand to the right or to the right to 2 or 4. 7 cannot be to the right or to the left of 6 or 8 and so on. For n=4 there are only two possible arrangements, which is 2413 and its opposite 3142).
(5) gives the result u_n, n
for n = 1, 2, 3, 4, 5, 6, 7, 8 .....
to be 1, 0, 0, 2, 14, 90, 646, 5242
32:56 small problem, taking the alternating sum of the top row clearly doesn't equal 0
"It's a piece that's a combination of a rook and a king". In Shogi it's just called a dragon.
I love this channel
Man i love your videos ❤
4:22 wow that looks like an amazing piano exercise!
Immediately feeling a bit hooked because i played the 5-finger game myself as a child, didnt bother to figure out how many solutions there were, but i definitely did it! So weird to think that some other random kid had a similar thought to me
Here's an interesting observation:
As n gets larger, the ratio of the number of "legal" permutations of 1-n divided by the total number of permutations (n!) gets closer and closer to about 0.1353 (the ratio as a function of n seems to be constantly increasing with a limit of about 0.1353, or at least that's what some testing up to n=2500 showed). That would mean that for sufficiently large values of n (for n>=58 according to my testing) the number of legal permutations could be approximated by: n!*0.1353
1,000 more videos like this, PLEASE!!!
4:23 we need this guy to start playing piano
One of my favorite things about this video is your description of where you gave up when you tried this post-grad. You gave up during the most complex step (how many ways can a permutation contain at least k forbidden pairs) with the thought "this is getting ridiculous, there must be an easier way to solve this."
Well, as the rest of this video shows, there really isn't. This was only solved by rolling up your sleeves and diving into that mess head first, keeping track of everything as best as you can along the way.
This is a really great lesson on the fact that while striving for elegance and simplicity is usually a good idea, and can often lead you to the right answer, it isn't always possible. Sometimes a problem really is a mess but is solvable through pure perseverance. And as a consequence of that complexity, the final formula is messy as well.
legendary maths video. Well done Alex!
i have a thing i work time to time on since 2015 (mostly with programming because i'm not good enough in maths to solve it)
i posted the no-constrain (lvl 0) version on quora and a mathematician answered me with big maths i can hardly understand but he gave me a python program with it (take care it use cmd parameters), on quora :
What is the average number of steps it takes for a mobile moving randomly forward or backward along a polygon to visit all edges/sides (=/= all vertex/summits)?
But the big question is what about if
lvl 0 is visit all edges/sides (=/= all vertex/summits) :
-lvl 1: lvl0 + return to the starting point.
-lvl 2: lvl1 + by the clockwise direction + no more than 1 backward loop
-lvl 3: lvl0 + no more than 1 round-trip for each size of round-trips
-lvl 4: lvl1 + no more than 1 round-trip for each size of round-trips
-lvl 5: lvl2 + no more than 1 round-trip for each size of round-trips
I will try to make another Quora with more detail, my goal for lvl 2 to 5 is to list all the possible path constraints create (lvl 0 and 1, there is infinites numbers of path, but we can still calcule the average number step it take, for lvl0 it's done thanks to the mathematician)