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.
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.
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.
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!
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.
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!
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.
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!
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
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.
9:29 should’ve called it the N dragons problem because the king+rook is the same way a dragon in Shogi moves. In Shogi, the way pieces promote is different. Each piece promotes to a specific other piece, and most pieces can promote. If you move the rook to a promotion square, it promotes to a dragon which can move like a rook but also 1 space diagonally, which is a king+rook so we can just call it a dragon. Similarly the bishop’s promotion is the horse (different from the knight) which moves like a king+bishop
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)
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...
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!
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! ;)
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.
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!
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.
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.
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!
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.
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.
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
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.
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!
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
Like you, i first concieved of this problem as a child, and also in terms of n=5... although in my formulation it was always just about ways of arranging the numbers while separating consecutive numbets. I then spent all of last summer quarter working out the answers for up to n=8... by creating an adjacency graph, counting the allowable hamiltonian paths and circuits on those graphs, and then using some symmetry to get the final counts (there are as many ways to start at 1 and end at 2 as there are ways to start at n and end at n-1; you can go either direction on a path, and you can start at any point on a path that is a closed loop) Probably doesn't help my attempts that i apparently undercounted, at least in the case od n=6, where I only found 76 ways to do it... [Insert mathematically flavored profanity here]
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
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.
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.
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.
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 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 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.
Another way to justify nC0=1 is that nCk could be interpreted as Given a set with n elements, how many subsets are there with k elements. Every set has the empty set as a subset, and since a set is only defined by its elements, there is exactly one empty subset.
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
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.
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.
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
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!
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.
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.
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.
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
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
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.
This reminds me greatly of the puzzle where a ring of lights (or some other thing that can be toggled between two distinct states) are in some randomized configuration and they all need to be turned on (or off) by traversing between them. Generally the puzzles will disallow moving to a direct neighbor, and in larger cases will disallow moving to the 2nd neighbor over on either side as well. With a ring of seven points, that leaves the allowable options as +3 and +4, or in modular arithmetic, +/- 3, for example. Of course the problem posed in the video doesn't include going "around the corner" so to speak, and so the difference in solution between the modular version and the non-modular one would have to account for that [n, 1] pair being either allowed or not. I think that the modular view of the question might be the more simple view, though, and that it may be easier to solve the principal question in the video by first solving that modular arithmetic version, and then accounting for the difference created by the two possible treatments of the [n, 1] pair. Anyway, back to the video...
Have you looked into Gosper/Zeilberger techniques to find a closed form? Or conclude that there isn't one... At the very least an asymptotic approximation seems in order. I enjoy your enthusiasm, keep it up!
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
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.
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)
12:40 it strikes me here that this is tangentially, or perhaps even more than just that, related to the P vs NP clique problem. (Best optimization for finding an answer for a graph that I could think of was to apply forbidden pairs to the brute force search, so as to minimize the amount of checks that have to be performed) Ofc. now that I'm looking at the wikipedia entry for the clique problem, it seems like it could be somewhat of an inverse of the one in the video, as it doesn't want vertices with connected edges, while the clique problem only wants connected edges.
My discrete class used cookies and children instead of balls and bins. I know the latter is the canonical example, but cookies and children is so much more fun
This reminds me of some other problem I did in discrete math, also about adjacent numbers in a sequence (I don't remember what the specific rule was). Basically, we first took the set of all sequences, and then we subtracted all the possible ways that the rule could be broken. This sadly overcounts rule breaks, since if the rule is broken twice by a single sequence, it would have been subtracted twice. To fix that, you add back all the cases where the rule is broken twice. Then subtract the cases where the rule is broken thrice, add quadrice, subtract quice, add sense, etc. until you have covered all the possible cases. Given an n valued sequence, you have to do n-2 corrections (the sum is n-1 long). I don't know how much easier calculating the arrangements where a particular pair breaks the rule is in this context, but it does seem relevant.
I had the same problem in my mind for quite a long time, thanks for the closure! Next: how to do the same thing, considering that your pinky is adjacent to your thumb? (30 more years of problem solving… you're welcome)
I love when I realize something silly I thought about as a child turns out to be something with solid math that I,was able to figure out as an adult. I used to stare at regular square floor tiles and ask if there was any direction from a corner that would never hit another corner, imagining that it was infinite, and later realized that I was imagining irrational numbers
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.
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)
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.
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?
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?
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.
😮
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!
I beat through the fire and the flames on expert and I'm still impressed by your dexterity
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
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.
9:29 should’ve called it the N dragons problem because the king+rook is the same way a dragon in Shogi moves. In Shogi, the way pieces promote is different. Each piece promotes to a specific other piece, and most pieces can promote. If you move the rook to a promotion square, it promotes to a dragon which can move like a rook but also 1 space diagonally, which is a king+rook so we can just call it a dragon. Similarly the bishop’s promotion is the horse (different from the knight) which moves like a king+bishop
Alex's introduction is absolutely true: lots of interesting steps, perfectly detailed as always. A very beautiful enumeration problem... Thanks!
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)
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...
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
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! ;)
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?
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.
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!
Bro when you cycled through the possible combinations you made a sick beat 😂
Yes, AnotherRoof, I will come with you on this journey.
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.
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.
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
How do you not have 1 million subscribers yet?? This channel is a not a gold mine, but a DIAMOND mine
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!
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 is, without exaggerating, one of the best videos I've ever watched on TH-cam.
Another great video ! This channel is really underrated
This may be my favorite video on TH-cam to date.
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
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.
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.
It's beautiful that with such simple tools you can solve challenging problems. Very elegant solution
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!
you just described my childhood but in my case it was the bulgarian solitaire problem
Because of the difference in strength of your fingers, its clear and audible at 4:30 tgat each solution is uique
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"
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.
Like you, i first concieved of this problem as a child, and also in terms of n=5... although in my formulation it was always just about ways of arranging the numbers while separating consecutive numbets.
I then spent all of last summer quarter working out the answers for up to n=8... by creating an adjacency graph, counting the allowable hamiltonian paths and circuits on those graphs, and then using some symmetry to get the final counts (there are as many ways to start at 1 and end at 2 as there are ways to start at n and end at n-1; you can go either direction on a path, and you can start at any point on a path that is a closed loop)
Probably doesn't help my attempts that i apparently undercounted, at least in the case od n=6, where I only found 76 ways to do it...
[Insert mathematically flavored profanity here]
@@zachrodan7543 I just want to say that I love that you're working your way through my catalogue and I'm enjoying reading all of your comments!
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
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.
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.
I THOUGHT I WAS THE ONLY PERSON WHO DID THIS :’) i was so happy when i came across this
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.
Commenting for the Algorithm and also to say that this was a blast of a video, love them crunchy combinatorics
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.
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 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.
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
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.
That's hard work. I'm tired after watching this halfway through, but I can keep going. Feel the burn!
The cliff hanger was too much, so I joined the patreon- and the extended cut was amazing!
Another way to justify nC0=1 is that nCk could be interpreted as
Given a set with n elements, how many subsets are there with k elements.
Every set has the empty set as a subset, and since a set is only defined by its elements, there is exactly one empty subset.
Excellent and clear explanation. Thank you for your effort in presenting your solution to a wide audience.
This is probably the best math video I've ever watched.
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
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.
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’m so happy for you. 😊❤ and i liked this long video
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
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!
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.
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.
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.
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
In many ways this reminded me of the mathematical puzzles of Raymond Smullyan fun and whimsical
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
Now take the gamma function and extend the problem to all numbers (including imaginary ones)
GENERALIZE
So much maths on youtube is "pop maths" where they don't really explain the proofs. This is really something special!
4:22 wow that looks like an amazing piano exercise!
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.
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
Your finger fidget rhythm is awesome!
It took me awhile, but I did work out the ALL the solutions for the case with 1 building before you even showed it!
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...
This reminds me greatly of the puzzle where a ring of lights (or some other thing that can be toggled between two distinct states) are in some randomized configuration and they all need to be turned on (or off) by traversing between them. Generally the puzzles will disallow moving to a direct neighbor, and in larger cases will disallow moving to the 2nd neighbor over on either side as well. With a ring of seven points, that leaves the allowable options as +3 and +4, or in modular arithmetic, +/- 3, for example. Of course the problem posed in the video doesn't include going "around the corner" so to speak, and so the difference in solution between the modular version and the non-modular one would have to account for that [n, 1] pair being either allowed or not.
I think that the modular view of the question might be the more simple view, though, and that it may be easier to solve the principal question in the video by first solving that modular arithmetic version, and then accounting for the difference created by the two possible treatments of the [n, 1] pair.
Anyway, back to the video...
4:02 I'm impressed that you can lower each finger fully independently, I can't do that.
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
32:56 small problem, taking the alternating sum of the top row clearly doesn't equal 0
Have you looked into Gosper/Zeilberger techniques to find a closed form? Or conclude that there isn't one... At the very least an asymptotic approximation seems in order. I enjoy your enthusiasm, keep it up!
4:23 we need this guy to start playing piano
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
This seems intimately related to toric permutation classes, which were a part of my undergraduate capstone project.
I love how many comments (this one too) are basically, "I thought about this when I was a kid too!"
Oh i am glad that I found your channel. Love your long videos and enjoy going deep here 👍
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.
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)
Nice explanation, you make complex maths easy to understand. You're doing an awesome job.
12:40 it strikes me here that this is tangentially, or perhaps even more than just that, related to the P vs NP clique problem.
(Best optimization for finding an answer for a graph that I could think of was to apply forbidden pairs to the brute force search, so as to minimize the amount of checks that have to be performed)
Ofc. now that I'm looking at the wikipedia entry for the clique problem, it seems like it could be somewhat of an inverse of the one in the video, as it doesn't want vertices with connected edges, while the clique problem only wants connected edges.
My discrete class used cookies and children instead of balls and bins. I know the latter is the canonical example, but cookies and children is so much more fun
OMG I DID THIS IS AS A CHILD AS WELL! Thanks for reminding me!
This reminds me of some other problem I did in discrete math, also about adjacent numbers in a sequence (I don't remember what the specific rule was). Basically, we first took the set of all sequences, and then we subtracted all the possible ways that the rule could be broken. This sadly overcounts rule breaks, since if the rule is broken twice by a single sequence, it would have been subtracted twice. To fix that, you add back all the cases where the rule is broken twice. Then subtract the cases where the rule is broken thrice, add quadrice, subtract quice, add sense, etc. until you have covered all the possible cases. Given an n valued sequence, you have to do n-2 corrections (the sum is n-1 long).
I don't know how much easier calculating the arrangements where a particular pair breaks the rule is in this context, but it does seem relevant.
I had the same problem in my mind for quite a long time, thanks for the closure! Next: how to do the same thing, considering that your pinky is adjacent to your thumb? (30 more years of problem solving… you're welcome)
I love when I realize something silly I thought about as a child turns out to be something with solid math that I,was able to figure out as an adult. I used to stare at regular square floor tiles and ask if there was any direction from a corner that would never hit another corner, imagining that it was infinite, and later realized that I was imagining irrational numbers
Excited.