Do you understand this viral very good math movie clip? (Nathan solves math problem X+Y)
Вставка
- Опубліковано 15 жов 2021
- Recently one of you requested that I explain the math(s) in this clip which recently went viral.
• X+Y (Clip) - Nathan so...
It's a clip taken from the movie X+Y aka A brilliant young mind. The math(s) problem that Nathan, the main character in this movie, is working on in this clip is a simplified version of the first part of a problem that was shortlisted for the 2009 International Mathematical Olympiad. Here is a link to the shortlist.
www.imo-official.org/problems...
The problem in question is problem C1 (the number 50 in the problem has been replace by the number 2 in the clip). This problem was suggested to the makers of the movie by Lee Zhao one of the maths consultants of the movie. This Note that the file I've linked to ere also includes solutions.
This problem was invented by Michael Albert who is a mathematician and computer scientist working at the University of Otago in New Zealand.
en.wikipedia.org/wiki/Michael...
The 4-colour puzzle that I am challenging you with at the end of this video was invented specifically for the movie X+Y by the U.K. mathematician Geoff Smith who was another math consultant for the movie.
en.wikipedia.org/wiki/Geoff_S...)
Geoff Smith also served for many years as the leader of the United Kingdom team at the International Mathematical Olympiad and is the current president of the IMO board. He also appears in a cameo role in the movie. He is sitting next to Nathan's mother in the corridor outside the hall in which the math(s) olympiad is taking place at the end of the movie.
imgur.com/a/cjWLHKi
Here is scan of the fictional IMO questions that the students dealing with at the end of the movie.
imgur.com/a/C1Uxkbd
Actually they adapted the first problem a little bit to make it fit in better with the story
imgur.com/a/9lP4zKe
These questions and their solutions also appear in the book by Geoff Smith, A Mathematical Olympiad Companion UK Mathematics Trust
www.ukmt.org.uk/product/95
Here is my presentation of an animated solution of the 4-color problem on Mathologer 2.
• Solution to the four-c...
Please also check the description of that video for more information and the announcement of the winner(s) of the t-shirt.
Thank you very much to my colleague Norman Do for digging out all this info about the origins of these problems.
Marty and my MMDB (Mathematical Movie Data Base) lives here
www.qedcat.com/moviemath/
Here is the preview of Marty and my book Math goes to the movies on Google books (features a couple chapters)
tinyurl.com/f57wr72v
The music accompanying my Thank you at the end is I Promise by Ian Post (just like for the last video)
Enjoy!
Burkard
P.S.: Here is a great account featuring an ex IMO participant who contributed to the making of X+Y.
ncs6mathssociety.wordpress.co...
His name is Lee Zhou Zhao. He also made a cameo appearance in the movie
imgur.com/a/uFwS8Yv
Your proof is decent, Mathologer, but Nathan's proof is by descent.
:)
😂😏👍
I came to vote for Nathan's proof because I identified with the nerdy guy in a movie. But this rationale has much to be treasured.
Reminding us that the pun is the lowest form of humor -- so once again the trip to zero raises its head.
@@TheDavidlloydjones In the time of Shakespeare this was not so. Verily, forsooth it ne'er be fonder, when forked tongue makes meaning wander.
This video is a bit of an experiment. For quite a while it's been pretty long videos every four or five weeks. I am thinking of every once in a while slipping shorter very accessible videos in between the monsters. What do you think?
👍
I would love it, if you would continue with this concept! 🙌
Ja bitte!
As long as you don't start to follow the UA-cam "shorts" trend everything is fine;)
Good idea
I liked the binnary solution because not only is it "elegant", it also shows intuitively why the number always gets smalller.
Or bigger if you switch zeros to ones.
@@kaltziferYT the only moves that can switch a zero to a one also turns a one to zero the number always stays neutral or goes down.
@@AsheLeclair he meant switching the definition
7:17 Actually, I would argue that neither you nor the young man in the clip missed out on that oversight, because there was no oversight to miss. The coach never stipulated that all of the cards had to end up being face-up, only that the sequence of moves had to terminate. In other words, the task was simply to show that there is no possible infinitely long sequence of moves, or to put it in yet another way, once you apply a move to any arrangement of cards, it is impossible to apply any combination of moves to the resulting arrangement such that the result is the original arrangement. Therefore, the answer to the question of what to do if only the right most card is face down is to do nothing. Such an arrangement simply represents a terminating condition.
Also, about the shorter video, I actually enjoy this format very much and would enjoy more shorter videos.
Rightly pointed out 👏🏻. This comment need to be pinned 📌
In a circular arrangement of cards, you could chase a face-down card around and around forever. I wouldn't assume that the set of cards were meant to wrap around if I saw this on a test, but that was still the first thing I thought of when watching the clip :p
@@Platanov I mean, they did say 20 cards _in a row_ , but I get what you mean.
@@danielyuan9862 20 cards face down in a row on a sphere could be both a straight line and a circular arrangement at the same time.
Is that a basic assumption? I didn't compete in the Math Olympiad, but it doesn't seem self-evident to me. Surely in a formal context, you should at least say something like "In the trivial case where the rightmost card is selected, the game terminates immediately"?
Geoff Smith, who wrote the problems for this film (and some of the Olympiad questions) was my lecturer in first year. When the film came out they were extras for our problem sheets.
Check the description of the video :)
Please make a video on Monty hall problem....it also comes in movie...
Wow, just realized Sir Geoff Smith is my friend on Facebook, amazing person indeed!
@@hemantjakhar8497 Monty hall actually makes an appearance in a couple of different movies :)
@@28aminoacids No knighthood I am afraid
Two 3b1b AND a Mathologer upload? I am almost in heaven...
let's start bugging numberphile for a video then
I am overwhelmed!
Indeed! And a Veritasium one also.
mee tooo!
And BlackPenRedPen, and Dr Peyam
10:05: To be precise, Nathan did not argue that it has to become zero. He only argued that you can't keep making it smaller without it turning negative. That means it could also terminate at any other positive integer. This also takes care of the border problem, because even if you argue that you can never flip the rightmost card (because there is no card to the right of it to complete the move), then the problem might terminate at 1 or 0. (Edit. just realized there is already a pinned comment saying this)
I for one really appreciate this short interlude type video. The smaller, more easily digestible content without needing to establish a large number of foundational knowledge is refreshing!
Same, I like these videos too!
Completely understood the math behind it, but I would never be able to come up with that binary analogy on the spot if you asked me to do the same.
I suppose it depends on your familiarity with switching to different bases. Most mathematics today is taught in base 10 - if you aren't encouraged to explore other bases, you'll sit with what's comfortable. My first attempt at solving the problem was using a small scale sample and noting that the left hand-most card being flipped would always result in a cascade of flips to that "end" state, resulting in all possible choices converging on a deck fully flipped, regardless of size since the solution is scalable.
The Binary solution is very elegant, but since I never really work with anything beyond base 10, 12 and 60 (or 360, I guess), it wouldn't have occurred to me.
that's interesting because although I kind of suck at conventional math I'm a proficient computer engineer and problem solver, and binary reasoning is basically my immediate intuition about it. Nathan's solution literally felt like home, which wasn't what I expected from a math video. I watch all kinds of math channels to train myself into better intuition for the abstract ideas behind it, but I've ultimately discovered that I'm actually excellent at math, but I struggle with the mindset that revels in its godforsaken notation.
I think it's a matter of exploration and the movie does a very bad job of portraying it for the sake of the drama.
When I first saw the problem, I started going through simpler cases, such as 2 cards, three cards, up to five. I was too lazy to pick up pencil an paper, or to type it in my pc so I just used my hands do describe the system, palm up for face up and vice-versa. I eventually saw the similarities between this and binary counting, so I used binary numbers just so I could process the information better in my mind.
Then I came to a similar solution, in which my sequence was strictly increasing, but had an upper bound (the largest number with 20 bits is 2^20-1). So, while I could never just close my eyes for 10 seconds and come up with it on the spot, my laziness led me to find better ways to represent the sequences and the rest came in naturally.
Well I think you would, just not so quickly
Even though I tend to switch to binary often in this case I would make proof for 1, 2 cards and then use induction
Speaking only for myself I appreciate when you explain the same problem in three or more ways. I feel like I gain a little bit of understanding with each iteration.
Helpful for me too!
Absolutely! Forming the habit of trying to look at things in more than one way is an important part of doing mathematics. It can lead to significant mathematical discoveries. (This is how we got more than 300 proofs of quadratic reciprocity--more than one a year on average since Gauss published the first correct proof.)
Agreed. Knowledge seems to solidify better for me by seeing multiple other approaches or solutions along the way and connecting with the one that resonates the most.
@@RolandHutchinson Yes I couldn't agree more. This is why I am not a big fan of the clip in that movie. Notice how he says "We need to look at the cards not as cards, but as numbers". No, we don't. Not necessarily. His solution does! The clip reinforces the sad misconception a problem only have one solution or that one solution is "more correct" than another.
It is usually better, if a problem could be looked at and understood from more than one angle, yes. "Binary," "Binary Digit," etc. refer to very technical mathematical/ computational definitions, so if you're not into things like that, you had to look them up. It's not beyond even a small child's comprehension; but again if you're not into math or computer, you had to look up technical definitions like that. However, to explain that "1" is "bigger than 0" and every time you flip two cards, either 1 or 0 will have to move to the one direction of another... then obviously, a pattern is happening, so since 2 or 8 or a finite set of cards is, well, finite... so infinity isn't going to happen... a "termination" of either all 1s or all 0s will happen... unless there's some random/strict rule saying if "there is a single card left, you can't flip it," etc.
I love your longer format videos. I'll also be very happy to watch this smaller interludes. This was really fun.
Very nice! It will spice up my days with interlude like this. This is the best UA-cam math channel I've been watching so far and I don't ask for more!!!
If you consider the right boundary of the Problem, where you interpreted the Rules to mean that you only turn over one card, then there should turn up an interesting result if the cards are layed out in a circle. That would mean that when turning over the rightmost card, you would also turn over the leftmost card. That way, the sequence would not need to terminate, i think. Because you could shift the Face Up cards infinitely to the left and looping around when they "hit the edge" of the deck.
Exactly, the pacman version of the game does not have to terminate :)
It MAY terminate if you choose wisely. But it COULD go on forever if you choose poorly. :)
Should it not depend on the initial number of face down cards being odd or even? Every move flips two cards, either 10->01 or 11->00. Thus keeping the same number of face up cards or increasing it by two. If there is a single face down card remaining the only possible flip will never lead to a state where all cards are face up.
Ludwig, as long as the number of cards in a circle is greater than two, it still doesn't have to terminate. After you flip your first card, only two are face up, right next to each other. After that, you can flip the face down cars immediately to the left of those two, leaving you with two cards face up separated by a gap. Flip the card in the gap, and you're back to step one, so you can repeat this forever
I think your argument is that with an odd number of starting cards, the process can never terminate. The earlier conversation was about whether the process must necessarily terminate.
Nathan's solution uses weights 2^19, 2^18, ..., 2^0 and argues that the total score is strictly decreasing. But we could also use weights 20, 19, ..., 1 with the same argument, and this shows the maximum number of flips is bounded by the maximum total score, 20+19+...+1 = 210; and this bound is achievable in a natural way.
Very nice alternative to the induction!
For me Nathan’s explanation, explained by you, is the best.
For the grid problem, sum up every the possible 2*2 suqare exactly once. Notice that the total amount of times red, green, yellow, purple appeared MUST BE EQUAL. The corner squares are counted once, the edge suqares are counted twice (it is calculated in 2 of the 2*2 suqare), and the squares in the middle are calculated 4 times(it is in 4 of the 2*2 squares). Since the total amount of 2*2 squares is ODD, every color must appear an ODD number of times. Ans since only the corner squares are counted an ODD number of times, each color MUST appear in the corner square. QED.
By the same argument, we can show that every color appears on the corner of the 4n*4n*4n cube, if it is colored with 8 colors such that every 2*2*2 cube consist of 8 distinct colors.
We can generalize this further to m dimentional cube with 4n as its sides.
bit late, but wonderful proof!
Very elegant proof! I treasure it! Thanks
A fun proof for the 4x4 case: make the colors prime numbers 2, 3, 5 and 7. The product of all numbers in the grid is (2*3*5*7)^4. Then divide by the numbers in the 2x2 squares between the corners (forming a cross that overcounts the middle). This gives 1. Since we divided by the middle 2x2 square one time too much, we can multiply by the middle square again to compensate, which gives 2*3*5*7. The number we are left with is the product of the numbers in the 4x4 grid, when you take away the middle cross, i.e. the corners. Since we got 2*3*5*7 for that number, the corners must be 2, 3, 5 and 7.
This is how I did it in my comment. You can generalize this to work for any 4n x 4n grid. You just need to crunch some numbers
@@BryanLu0 As you noted in another comment, my proof is essentially a number-theoretical phrasing of a set-theory approach. Tbh, I even had a venn-diagram in my head while writing it.
that's really pretty
Wow we thought of the exact same proof!!
Very elegant!
One nit: the binary argument demonstrates that the sequence of moves must terminate, however, there is an additional step required to say that it terminates specifically in 00000 == all cards face up. Consider for example if one were in the state 00001, and we know every move decreases the value, but perhaps they decrease it by 10 or something. We'd overshoot 0 and be stuck at 00001. It's important to call out that as long as there is a 1 present, there always exists a legal move that does not overshoot 0
Yes, I was wondering if I maybe just don't get it, but I think this part of the proof is missing in the movie. I was surprised it wasn't adressed by Burkhard. Or is it too obvious?
Someone in a comment below pointed out, that in the movie it was not said, all cards should be face up in the end. Seems like, this rule was added by Burkhard. So the proof in the movie would be complete.
@@jorn-jorenjorenson5028 right, that condition was introduced by mathologer (though it will always be true). But since it was introduced i would bring it into his explanation
@@jorn-jorenjorenson5028 AFAIR the rule he added to cover all cases was that when you flip over the right most card, you only turn over that card and nothing else. This by itself addresses the 0000 0001 problem while the fact that all cards end up face up is the solution we derive.
It bothered me a bit about how the odd case was not represented in the question. Calculations are similar, but it does show up unless you allow changing exclusively the last card.
Absolutely loved this small video concept!
I always understood the rules in such a way, that the rightmost card can't be turned. This also would mean that Nathan did not forget that case, since he never says that the series termiates at 0, 0 is simply a lower bound which means it must terminate at some point, but does not state when
I really loved the binary representation, though my gut instinct would have been to invert the bits (starting state is 0). The proof would have still worked since we have a maximum upper bound, but having it descending is easier :P
The other reason that I like the binary proof is that you don't have to know what happens in that right-most edge case-- even if you can't flip it, the proof still works. It doesn't reach 0, but it can't get smaller, therefore no moves can be made and therefore it terminates
Yep, also one can consider endianess, that the top bit is the right hand most bit rather than lefthand most bit (this legitimately is something we deal with in computers). The proof still works as long as we don't have wraparound carries... But this is probably something one should consider in the proof.
But true. 20 cards aka 20 powers (0 through 19) of 2 can add up to a maximum 2^20 - 1 and when strictly increasing the number with every move you must terminate eventually. I like going up cuz a 1 representing a face up feels more natural.
But you may also reverse the problem to face up to face down to achieve that.. Whatever ^^
Same here - I got very confused at first because I also immediately assigned 0 (zero) to the face-down state. And was bewildered when the movie clip showed the "wrong" binary digits, and a strictly monotonic decreasing sequence instead of a strictly monotonic increasing one.
I guess I'm getting too old for this.
I definitely agree 👌🏻.
You need to think of the colors not as colors but as numbers :)
You can just assign each color the numbers 1, 2, 4, 8. We need to show that the corners add up to 15. But that’s easy, the sum of the corners is the sum of the 4x4 grid minus the sum of the center cross.
The sum of the 4x4 must be 60 because it’s the sum of the 4 corner 2x2 squares, which add up 15 each because of the distinct coloring.
The sum of the cross is trickier but can be done by adding the 4 edge 2x2 squares and subtracting the center 2x2 (to remove the double counting). Since each of the 2x2’s adds to 15 the cross is 45 (4*15-15).
Finally, subtract the cross from the 4x4 square and we have that the sum of the corners is 60 - 45 = 15. Since there’s only one way to add 1, 2, 4 and 8 that gets us to 15 (because of the base 2 numeral system) all corner squares must have distinct coloring.
In fact that must be true for any 2m by 2n grid (m and n being positive integers), not only squares or multiples of 4: for any of such grids you can obtain the corner pieces by a linear combination of 2 by 2 squares. Just add the whole, subtract the vertical 2*(m-1) by 2*n center strip, subtract the horizontal 2*m by 2*(n-1) middle strip and add back the 2*(m-1) by 2*(n-1) core. Each of these can individually be constructed solely by stacking 2 by 2 squares (elementary to show). Hence, since each 2 by 2 block is a multiple of 15, so is the linear combination of them, which, finally, proves the sum of the corners MUST be a multiple of 15 - and since there’s only one way to get to a multiple of 15 by adding 4 numbers out of {1,2,4,8} the colors of the corners MUST be distinct in ANY 2m by 2n grid constructed by those rules.
Jesus, you are really smart.
This is simple and genius!
I think he just want tell to their lecture that he watched Mr. Bean too.
RGB as a number... Wkwkwk.. What a math jokes
The statement in the clip was only that there eventually stops being a possible move, not that all cards are face-up.
Also, my interpretation was that if following the instructions on the rightmost card is not possible, then the rightmost card is not an option.
Doesn't really mess with the validity of the statement as long as the number of cards is even.
I really enjoyed this short format, please do more.👍
Definitely love the short form video option. I have about 50 of your videos in a list to watch later, but I rarely have time for a 45 minute video. (I'm slowly getting through the "mystery of the sums" one... lovely stuff).
i feel your pain friend!=)
I always enjoy your lovely stuff. Retired physics/maths teacher.
I like these short, fun interludes, every now and again 😊.
I remember watching this video when I was younger, and it partially inspired me to get into math competitions. Glad more people will be able to see Nathan’s beautiful solution!
That's great. I only watched this movie for the first time last week :)
Recently stumbled back across mathologer videos, finding them so relaxing and interesting at the same time :) keep it up❤️
Also, the point of leaving the last card only down, if you consider either that one card only is flip, or that no move is possible it is terminated.
Exactly. This is why I prefer Nathan's proof, it doesn't assume anything not mentioned in the statement of the problem.
Burkard’s proof is still fine; it shows that eventually you reach a state where the leftmost 19 cards are face up, at which point no move is possible.
For the last puzzle: assign values 1,2,4,-7 to the four colours respectively. Now the sum in any 2n X 2m rectangle must be zero (can split in distinct 2x2). Now if we look at the sum of values of square without corners , it's a sum of two rectangles 2N - 2 X 2N minus inner square 2N - 2 X 2N -2 (due to double counting), this sum is zero, and the sum of entire square is zero. Which means remaining 4 corners sum up to zero which can only happen if they are all distinct values from the set {1, 2, 4, -7}
EDIT: interestingly this problem easily generalizes to higher dimension as well, say cubes then will have 8 distinct colours
Very nice! It is maybe even more easily seen by the fact that the total sum remains unchanged when we remove any two adjacent rows or columns. This can be done until only the original corners remain. So your method does not only work for squares with side divisible by 4, but for any even-sized rectangle.
Thank you for these videos, as a person who enjoys the stretching of my brain I appreciate the workout. You asked if one format was agreeable, short or long or both, i just want to point out that IF you and your staff are enjoying what you are doing, THEN I will likely watch like and comment. You decide budday, I like what you are doing, period
Given that you can do the operation on the final card without having to turn a card to the right (since it doesn't exist). The largest possible number of turns to terminate the sequence is equal to [n*(n+1)]/2.
edit: If you cannot perform the operation on the last card then the most turns possible to terminate the sequence is given by x=(n-1)*n/2 though the sequence may then terminate with one card left.
Very good, you crossed all the t's and dotted all the i's there. Now on to the final puzzle. That one is doable but is much more of a challenge I think :)
Regarding what happens with the right most card, note that as long as we does not flip the right most card the following things hold:
1) We start with an even number (0) of cards face up, and
2) The two legal moves either keeps the number of face up cards the same, or adds two face up cards. Thus the number of face up cards stays even.
Thus by induction we will always have an even number of cards face up.
Thus at every step we have an even number the right most card will end up flipped when we terminate without picking it as the leftmost card.
Thus the only way for the game to terminate without all cards face up is if we started with an odd number of cards and disallowed picking the right most card.
And for a proof:
If you look at the available moves, you either keep the same number of face-up cards, but move one of them a step to the left, or you create an additional pair of face-up cards, or, if it's legal, you create a lone face-up card on the far right (note the implied model here treating face-down cards as spaces or holes, and face-up cards as objects). Intuitively, it's obvious that creating face-up cards as far right as possible gives more moves, from which the triangular numbers follow - if you can create just the one face-up card on the far right, that's the same as moving it into the sequence from the right, so the first face-up card can be moved n times, the next, n-1, etc. If they have to enter in pairs, then that's n/2 creation/entrance moves, each of which has the effect of 3 moves from the single-entry version, reducing the number of possible moves by 2 per entry or 2*n/2=n moves total, reducing the total number of moves from the n'th triangular number to the (n-1)'th.
Filling in that intuitively obvious bit: number the positions from 1 at the far right to n at the far left. if you create a pair of face-up cards at k+1 and k, with k>1 (so not at the far right) then the card at k-1 is either face up or face down. If it's face up, then you're going from ...DDU... to ...UUU... in just one move, when you could instead go DDU -> DUD -> UDD -> UUU taking three moves and moving where the pair of face up cards gets created one space to the right. If, instead, the card at k-1 is face down, then you're taking one move to go DDD -> UUD, when you could instead go DDD -> DUU -> UDU -> UUD, again taking three moves instead of one, and moving the creation one space to the right.
So, if a longest possible sequence of moves were to include turning a pair of cards not at the far right face up as a single move, you could lengthen the sequence by replacing that move with three moves, without affecting the rest of the sequence. That contradicts the assumption that you started with a longest possible sequence, so any longest possible sequence must have all creation of face-up cards happen as far to the right as possible - either card 1 or cards 1 and 2 depending on the rules for that special case.
@@chrisamadei2565 One has n+1; the other has n-1, making the two equations differ by a total of n.
@@rmsgrey sorry, Maybe I should put my glasses on before posting
I solved it via expansion to "all starting states eventually result in the final one" + recursion:
1 card is trivial
when you have N cards proved and you have N+1:
-turning left-most one will never unflip it, so it becomes a N-card problem that is proven
-if you don't turn left card, you can only flip in the right N cards, so due to the N-card problem you will eventually run out of moves there, so you have to flip left-most card, thus becoming N-card proven problem, as per previous point
This also gives (rough, I think?) upper bound on max amount of moves being:
A(N+1)=A(N)+1+A(N), A(1)=1 (i.e. A(N) = 2**(N+1) - 1)
saying "expanding problem to all states terminating in final state" is just a way to skip proving that all states are achievable from starting one... but actually such proof is simple
same idea - recursion by taking away left-most card:
- if left-most card is unflipped, you don't do anything and continue to right N cards as per previous induction step
- if it is flipped, algorithm starts with flipping right-most card, then continuously flipping one-by-one to the left (thus "moving" the flipped card leftwards) until you flip the N+1th/left-most card - then continue getting right-most N cards as per induction step
This was my same though when I first watched the clip.
-Or you count in binary and you have your answer. 2^n - 1-
@@minirop Nope, not every game state admits a move that subtracts one
@@minirop how do you go from e.g. 1000 to 0111 in one move?
I loved this video and would definitely watch more. Your channel is one of my favourites, but sometimes I do kind of wander off for a bit when I don't have time for the long videos, so videos like this would make it easier to keep with it when I'm pressed for time and attention. That said, I also love the longer ones when I have the time, so I wouldn't want to see and end to those.
The clip surely has olympiad level quality in playing on the audience's emotions with the visuals, ambience, and timing in delivery of lines.
hardly. It TRIED to do that, but it was laughably bad at it. Every single "worried glance" or "dramatic musical sting" made me say "wait, THAT was supposed to be dramatic? WHY?"
I enjoyed this despite it's simplicity at a glance, your explanations are always insightful and provide different and novel perspectives on approaching problems. Please continue with these interlude videos and keep up the great work!
Given the overall positive response I'll definitely make more of these videos in the future.
Standard proof without cleverness: because the number of configurations is finite, any nonterminating sequence must return to a previous configuration. Once you turn two cards face up the previous configuration is unreachable. So you can only return to a previous configuration by a sequence of turning one card face up and one face down. However, the one you turn face down must always be to the right of the one you turn face up. There must be at least one "leftmost" move because the line of cards ends on the left. So the card turned face up in this move is never turned face down again, hence such a sequence cannot return to the previous configuration either. #
Nice proof but I don't think it requires "no cleverness". It's essentially the same argument as the first proof, just with a different argument for the 2 cards face up.
How about an inductive proof. First, prove that if a sequence of cards of size N terminates no matter how the cards started out, then a sequence of cards size N+1 also terminates no matter how the cards started out. Then prove that a sequence of cards size 1 terminates no matter how the card('s') started out. From these, a forteriori any sequence of all face-down cards must terminate. The 1-case is trivial. As to the induction step, suppose a sequence of N cards terminates (we'll take 'no matter how the cards started out' as understood from here). Now add an additional card to the left. You now have the leftmost card plus the original sequence. The leftmost card _must_ be turned over (if it started facedown) at some point, since the original sequence terminates meaning at some point the left-most card is the only one you can choose. (If leftmost card started face up, then trivially this N+1 sequence terminates because the N sequence does.) Once you do turn over the leftmost card, it's discharged--it can never be turned over again by the rules of the game, and hence all you're now dealing with is a sequence of N cards, which by the inductive hypothesis terminates. QED I think?
Your solution is a unidirectional finite graph. You need to show its finite, which is trivial, but to prove that it is unidirectional requires a complete explanation of state transitions, which is effectively what Mathologer describes anyway.
The proof is that you cannot visit a node you already visited because you either have more up cards than before or an up is now in a further left position than it was before. In either circumstance you cannot visit the same node twice. But I guess it's not as compact a solution.
@@1vader It's standard. It requires no cleverness IF you are trained in these kind of things. I basically just wrote it down without much thought. I couldn't have done this with school level math training at all.
@@bramkivenko9912 You are replying to Kris I assume?
even though you explained your 1st method which was really good , the proof that nathan writes is like tough to understand at the first glance, your graphical representation helped me lot, i am really glad you made this video. Thanks
This experiment results in positive, mathologer!
This was the most fun mathematics video I had watched on UA-cam in a while 😀
Solution to the final problem: We have a 2Nx2N grid. Since the sides are even, we can split the whole grid into distinct 2x2 blocks, and since each block has one of each colour, the total number of blocks with a given colour is A=N^2. Now consider the grid without the top and bottom row - since this still has even dimensions, we can also split into 2x2 blocks again, this time there B=N*(N-1) of each color in this section. The same applies to columns. If we remove both the outer rows and columns, leaving the square in the middle, we still have an even dimension on each side, so again we can count that there are C=(N-1)^2 squares of each color.
We can now calculate the number of squares with a given color in the set of 4 corner squares like so: First take the whole grid, subtract the count in the inner rows & columns, and add back in the central square - this give A-2B+C as the final count. You can expand the algebra and see this is 1, or just note that the same formula gives the count of each colour, so there must be 1 of each.
BTW this proof works for 2Nx2N not 4Nx4N, maybe there's a mistake, or maybe there's just a stronger result
Yeah I think Mathologer wanted to say 2n × 2m for all n,m≥1.
Great elementary proof right there!
Damn, you beat me. There is a prettier proof for mathologers stated question but yours is stronger. Love the proof too!
I would state that you add back the inside square because it gets double counted. Took me a minute to figure out why you did that.
The final puzzle can be solved easily using SET theory. This was initially discovered in the Sudoku world, and the idea has been widely publicized thanks to the amazing youtube channel Cracking the Cryptic. Using this technique it is even easy to show that the corners of any 2m*2n grid have to be different colored!
Basically it's about keeping track of two sets of cells, which contain the same amount of numbers/colors of each value. For example, taking the cells A1,A2,B1,B2 and the cells C3,C4,D3,D4 (if you allow me to denote rows by letters and columns by numbers). These are each 2x2 squares, so by definition they must both contain one of each color, making them equal under SET. I'll call these subgrids A1~B2 and C3~D4 respectively.
SET now poses that if these two regions overlap in a cell, this cell can be removed from both groups without changing the equality condition. For example, if the overlapping cell is red, and that cell is removed from both sets, the content of both sets changed by an equal amount of red cells, making them still equal. It's also possible to keep track of parts of these sets outside of the grid, which I will do in the following.
Consider the first two rows, ie the subgrid A1~B4. This can be split into the 2x2 regions A1~B2 and A3~B4, which means our first set X=A1~B4 contains two times the whole set of red, yellow, green and blue (I'll call that rygb). Now we consider A2~B3, another 2x2 region overlapping X, and we'll also keep track of a second rygb in our head. Let's call this second set Y=A2~B3 + rygb.
But now, the cells A2,A3,B2,B3 appear in both sets, so they cancel out. We get X'=A1+A4+B1+B4 and Y'=rygb. But since SET equality was preserved, we know that X' still contains the remaining set of all the colors rygb contained in Y'. Four cells containing four colors must all be different, QED.
This was all for the simpler case of a 2x4 grid. But with a bit of clever adding/subtracting of 2x2 regions, it is almost trivial to expand this to any 2m*2n grid size.
That's pretty nice
Nice, but you didn't really prove the general case
Ayyyy, another CTC viewer. 😁
@@BryanLu0 general case 2mx2n:
rows and columns are numbered 0,1,2 ...
definitions
A := (0;1)~(m;n-1)
B := (1;0)~(m-1;n)
C := (1;1)~(m-1;n-1)
D := (0;0)~(m;n)
Corners Area = D - A + C - B
Since all the areas A,B,C,D are rectangles with even lenght it is trivial that they each contain the same number of each color.
adding and subtracting these Areas from each other doesnt change that fact, so the corners must contain the same number of each color.
@@BryanLu0 General proof:
The OP shows a base case: that the four corners of a 2x4 (and by symmetry 4x2) rectangle must be the four different colours.
Induction: for a 2mx2n rectangle, assume it's been shown that the four corners of any strictly smaller rectangle of the same type (ie 2jx2k whenever j
Love the shorter video because I don't always have a lot of time to finish your videos. I generally watch short videos like this over breakfast
I had seen a clip of this part of the film a few times, and by far the most common complaint was that it is impossible to hear what is being said because the music is to loud (directors putting art over content). Fortunately, your clip resolves this problem - thank you.
That is a pretty elegant solution!
My first instinct was to apply induction on the number of cards. Base case: game with two cards always ends (easy to show all cases). Induction step: if a game with n cards ends, a game with n+1 cards should also end. The proof relies on the fact that once the leftmost card is moved it will be stuck as face up until the end. If that card is never touched then all you have is a n card game that finishes according to our hypothesis. When you touch it you now have a n card game that should also finish because of the hypothesis.
This works but is much more verbose :D
One problem with using induction is that after some amount of moves you have a state that differs from the starting one. So you need a stronger argument that given *any* starting state the conclusion holds. If you do that then you can say that either a) the leftmost card gets picked and then use induction on the remaining n cards at that point, *or* the leftmost card never gets picked and then you can use induction on the remaining n cards as well (however this latter case doesn't work if you want to show it ends in the all face up arrangement).
This is the intuitive approach that my wife and I both arrived at. Our formalisation skills failed us at that point.
It fits the format of a proof,.
For the last problem:
Define a cell as a single colored square from the original diagram. A 2x2 square is simply 4 adjacent cells in a 2x2 formation. A grid is a rectangular set of cells, defined as having dimensions rxc or r*c, where r is the number of rows and c is the number of columns in the grid.
Consider a (2m)*(2n) (row*col) grid with the special coloring. Call the grid G.
1) We can deconstruct G into m*n 2x2 squares which don't overlap, showing that G has m*n cells of each color.
2) Consider every row of G from the second to second-last. This is a (2m-2)*(2n) grid, which we can deconstruct into (m-1)*n non-overlapping 2x2 squares. Let this grid be R. Do the same with the columns to get the 2m*(2n-2) grid C consisting of m*(n-1) non-overlapping 2x2 squares.
3) R and C clearly have an overlap -- call the (2m-2)*(2n-2) overlap grid O. O consists of (m-1)*(n-1) non-overlapping 2x2 squares.
4) R contains (m-1)*n cells of each color, C contains m*(n-1) cells of each color, and O contains (m-1)*(n-1) cells of each color. All of these lead directly from #2/#3, where we deconstruct the grids into non-overlapping 2x2 squares.
5) Now, grid M = G - R - C + O contains only the 4 corners of G. Counting the number of individual cells of each color, we get m*n - (m-1)*n - m*(n-1) + (m-1)*(n-1) = [m - (m-1)]*[n - (n-1)] = 1 * 1 = 1 cell of each color left in M.
Therefore, we know that there must be exactly 1 cell of each color in the final set M, which itself is also just the set of the 4 corners of G.
---------------------------------------------------------------------------
BONUS: The same argument works "out of the box" for literally any (am)*(bn) grid with a*b colors, as long as the cells you want to prove have unique colors all form an exploded a*b grid and as long as the cells are "spaced nicely" (ie the # of rows (or columns) between any 2 "adjacent" cells is a multiple of a (or b)).
** The original problem is just a special case: a=b=2 and the cells are separated by 2m-2 and 2n-2 cells vertically and horizontally, respectively.
An outline of the proof for a=b=3, m=n=3, and the target cells (labeled 1) are evenly spaced around the 9x9 grid:
122212221
344434443
344434443
344434443
122212221
344434443
344434443
344434443
122212221
Note: there are 3*3 = 9 unique colors in this grid
G consists of cells numbered 1, 2, 3, and 4 -- 1 set of 9x9 grid -- 9 cells of each color
R consists of cells numbered 3 and 4 -- 2 sets of 3x9 grid -- 6 cells of each color
C consists of cells numbered 2 and 4 -- 2 sets of 9x3 grid -- 6 cells of each color
O consists of cells numbered 4 -- 4 sets of 3x3 grid -- 4 cells of each color
M = G - R - C + O = (1, 2, 3, 4) - (3, 4) - (2, 4) + (4) = (1) --> M is the set of all cells numbered 1
TOTAL # OF CELLS PER COLOR: 9 - 6 - 6 + 4 = 1 cell of each color
Woah
Beautiful! For anyone interested in learning more about this kind of technique, check out Set Equivalence Theory in sudoku.
The solution to the square problem is kind of very similar to the interview question "prove that you can't assemble a chess board from 2*1 elements if the resulting board is missing 2 opposite corners" - suppose you have a square 2*2, square has all different colors. The natural way to expand such field while preserving the invariant - is to "copy" the "next after neighbor" row/column. Thus you will end up with the situation when the invariant of "4 different colors in the square 2*2" is preserved for every 2*2 square, as well as the corners of your grid. Given your definition of the problem - the corners will always be different for any 2n grids - or something like that. 2*2, 2*4, 4*4, 4*6, 6*6, 6*8, 8*8 etc
Loooved this interlude. It was simple but make turn on my interior math spark. Hope this really catches on and have more small videos in between the cool ones!
Nathan's digit proof was so much more elegant. The faces (mathologer's) proof was just based on observation.
I agree, I was quite surprised by the proof and I quite liked the movie clips I watched
Which proof I would choose to explain things would very much depend on my audience. If I was dealing with a layperson with no particular interest in math I'd definitely use the first proof. With people who can appreciate some mathematical subtlety I'd mention the second way of looking at things :)
Usually, finding an elegant proof involves thinking about other proofs that are based on observation. As a math olympiad person myself, when I see a solution to a problem that was done using observation, I usually want to find a shorter and more elegant version of the proof so I can save some time writing the proof. :/
If I'm being completely honest (which is something I strive to be), I have to admit that your longer videos are oftentimes quite a test of my patience and endurance. At some point the amount of information (which is often new) is so much that it's hard to keep track of it, and it starts going over my head. Shorter snippets are much easier and nicer to digest.
Exactly! Sometimes we want a Banquet, sometimes we want a Snack.
@@qazyguy If that's so, then we have a variety. So wae can have either
I didn't know you had another channel, "Mathologer 2"! Thanks for mentioning it!
I really like these interludes and hope you will continue to do them occasionally.
Another way to solve:
If the game doesn't terminate we must have a cycle of moves that repeat. Which we don't because any move either creates new face up cards or moves one to the left, both we can only do finite times with finite cards, so we won't be able to afford either eventually.
This is essentially the reverse of the argument that was being used in the film
@@FiniteSimpleFox yeah
👍
Love the shorter format, hope to see more!
Alright so the maximum number of moves with 10 cards:
My first thought is to treat it like a binary number and simply subtract 1 each time, but I quickly realized that doing this would require moving more than 2 cards at once.
Then I realized that the maximum number of moves would be to only turn a face down card if there is a face-up card to the right. (This assumes your bound rule where turning the right-most card only turns 1 card.
It's then just a matter of turning the right-most card and then "moving" it to the left as far as it will go. Which takes 10 moves. After that, it is impossible to turn the left-most card, effectively making 9 cards. Repeating the process then takes 9 moves. Continuing the process, then will be 10+9+8+7+...+2+1 moves, which totals 55.
I then played around a bit, and realized that there's another strategy of moving the face-down cards to the right, which accomplishes the same thing in reverse, 1+2+3+4+...+9+10 moves, so 55 again.
No idea how to solve the last problem, good luck to whoever wins the T-shirt!
He said you can only turn over two face down cards at a time so wouldn’t the max moves also be 5 or did I not understand the problem?
@@michaelthomas6419 Thats way I read it
I like the shorter versions more. I was asking myself what could be the practical use of this subject besides the fun of understanding it. Thank you.
I so appreciate this.
I've got a proof for the last problem distinct from ilonachan's very elegant sudoku-style proof, inasfar as grid-puzzle proofs can be distinct, giving the same fully general 2n*2m result.
I) Any solution must have an "Alternating Orientation" (equivalent solution under reflection over a diagonal or 90° rotation) where each row alternates between two colors, and the sequence of rows alternates between two such pairs of colors.
II)
a. For an even number of columns, an alternating orientation of a solution must have different colors for the first and last columns in each row.
b. For an even number of rows, an alternating orientation trivially has different colors between the first and last rows.
c. The colors in each of the four corners of an alternating orientation must be different.
III) Reflection along the diagonal or rotation by 90° preserves both the property of being a solution, and the span of the colors in the corners. (Trivial)
Proof of I:
Ia) If the first row alternated over a pair, the second row must contain the complement pair; and that row must therefore alternate, as, trivially, two adjacent cells cannot share a color, and there are only two colors in the row. Inductively, each successive row must also contain the complement pair to the previous row, and must itself alternate. This satisfies the definition of an alternating orientation.
Suppose there is a solution which does not have an alternating orientation.
By Ia, the first row does not alternate over a pair.
Without loss of generality, it can be shown that the following configurations remain:
i. abcd[...]
ii. abcb[...]
iii. abac[...]
Where [...] represents any sequence of successive terms, for grids of more than 4 columns.
We shall first assume configurations i and ii, together.
Both configuration i and ii start with the same three colors, and we may say they both satisfy of configuration 'abcx[...],' where 'x' is undefined.
As no steps of the remaining steps do not depend on cells in columns 3 or later for this orientation, configurations will be denoted with only the first three color values.
Cell (2, 2) is part of both the top-left 2x2 square, and the top-center 2x2 square. It must therefore not be the same color as the first two or second two cells in row 1. As all three colors are represented in those three cells, cell (2, 2) must be the 4th color.
Cells (1, 2) and (3, 2) are now determined, as they each have 3 colored neighbors.
In particular, row two is now in a configuration of 'cda.'
This configuration is isomorphic to configurations i. or ii. of row one. Therefore, each row can be determined inductively.
In particular, row three is also in a configuration 'abc,' which is the same as row one.
If we look at column 1, we find it must alternate between colors 'a' and 'c.' This means that if we reflect over the diagonal, we must have a solution where the first row, equivalent to the original solution's first column, must alternate over the pair of colors 'a' and 'c.'
This satisfies the condition of Ia), and so this reflected solution must be an alternating orientation.
This means the original solution had an alternating orientation, contradicting the premise for configurations i and ii.
We may use a similar argument for configuration iii, but shifting our perspective over by 1 column. We first remove column one from the solution, and observe that we now have a configuration isomorphic to configuration i or ii. As removing a column does not alter the property of being a solution, as it does not affect 2x2 grids not intersecting that column, the argumentation for configurations i/ii follow.
If we take the resultant alternating orientation, and then reflect this solution vertically so that the top row is now at the bottom, we may notice that our new top row is also alternating, as given by Ia. If we try to replace an appropriately reoriented row at the bottom corresponding to the column we removed here, the solution must still satisfy Ia, as the new top row is not changed.
The property of having an alternating orientation is trivially preserved under horizontal and vertical reflections. As such, this re-appended row must still be alternating, and our overall solution still has some alternating orientation.
I: QED
QED
(Sorry for the haphazard alterations to the proof of I, but I realized I needed to generalize it to get the full 2n*2m result, but that proved non-trivial.)
I could've reworked 1a to make it way easier to state the case for configuration iii, but now that I've rewritten that part multiple times I'm too lazy to.
To answer the question in the title: Yes, I did understand the problem (which I haven't seen before) and the still image you showed before the clip immediately gave me the solution when I heard the explanation of the problem. I still very much enjoyed the entire video, like I always do ;).
Edit: Answer to the question for maximum number of step as a comment to prevent spoilers!
The video is meant to be super accessible, but at the same time a treat for all my cluey regulars. And for the really hardcore ones that last 4-color puzzle should be a real challenge :)
Answer to the maximum number of steps: n(n+1)/2, so 45 in the case of n=10.
Monash engineering student here, I'm a big fan of your videos and didn't even realise you taught here until now! Might have to pop in and say hi one day if covid allows haha
Wow, I’m impressed I understood that without an explanation… I never would have thought of the solution, but it made perfect sense to me.
Edit: note that for this answer I assumed you can turn over ANY two cards so long as both are face down, since that's the only rule explicitly stated. It's supposed to be a joke.
"Let's start with 10 face down cards and always turn over two face down cards." I took that literally as a new problem. Min = max = 5.
NO, min is 3 because you turn over cards 2-3, 5-6, 8-9 and you're done
Edit: oh wait I misinterpreted it, all cards have to end up face up. never mind
Min is 5, but max isn't 5. Say the right most 2 cards (#9 and #10) are flipped over first. In the next move you can then flip over cards #8 and #9. So now #8 is flipped, #9 is face down, and number #10 is flipped. Next flip #7 and #8, so now #7 and #10 are face up, and the rest are face down. Continue this pattern and it takes 9 total moves (counting the first #9 and #10 flip) to arrive at the configuration that #1 and #10 are flipped while the others are face down, which is already larger than 5 moves. I don't want to just hand over the answer but hopefully you can now see the pattern at how to find the maximum number of moves possible. Remember, each move needs to be as inefficient as possible to arrive at the maximum possible moves.
@@tobiaswagner5496 , but can't you make as many moves as you like? You just keep flipping the same two cards, or anyway go in a circle. Are there limitations on the kind of moves I may make?
@@Autosvezzamento1 Because of the rules of the card flips, every move is a move towards the solution in this problem. It isn't possible to go back to a previous state and so there aren't any cycles. Some moves though will get you to the solution faster than others.
Nathan's problem:
Prove a sequence of "1"s for face-down cards terminates in a sequence of "0"s for face-up cards.
Only valid moves are "11" becomes "00" (net of +2 face-up cards or -3 in binary) ,
"10" becomes "01" (net of +0 face-up cards or -1 in binary),
and "1" becomes "0" (net of +1 face-up cards or -1 in binary).
Each of the moves results in [0 to 2] face up cards or [-3 to -1] in binary.
Additionally, for n cards, the sequence may be completed from ceiling(n/2) to n*(n+1)/2.
For 8 cards, our minimum solutions take 4 turns while our maximum solutions take 36 turns.
// algorithm to reach a solution with a maximum amount of turns.
s = '11111111'
while '1' in s:
if s[-1:] == '1': s = s[:-1] + '0'
else: s = s[:-1-s[::-1].index('1')]+'01'+'0'*(s[::-1].index('1')-1)
The shorter relaxing video was great, so yes please do include more of these.
Thanks Mathologer - I enjoy the shorter vids from time to time, really enjoy watching your longer vids. Misses Mac's is the super pi :0)
The problem in that clip is much easier than basically every IMO problem on the test, though Nathan’s solution was much more elegant than mine, which used induction and didn’t turn the cards into numbers.
That's a Math thing, it works in a infinitely (countable) number of ways.... :)
11:29
The maximum number of steps for ten cards is 55.
The first step, when all cards are face-down, has to introduce at least one face-up card and this minimum is achieved when turning the right-most card.
This is strategically convenient, since we can only "move face-up cards" to the left, which is the only move that doesn't net an additional face-up card: i. e. adding more of these moves inbetween the net addition of face-up cards is the only way to prolong the game.
(Obviously, to stall the addition of further face-up cards like this requires there to be already one face-up card but of this is taken care by the initial step.)
Now the most we can prolong the addition of the second face-up card is to move this first face-up card all the way to the left, which takes nine steps (with the initial step ten in total).
Adding the second face-up card - again at the right-most position - is the eleventh step, and moving it as far left as it goes takes another eight, since the left-most position is already occupied by a face-up card.
So each further face-up card gives us at most one less step than the preceding one.
The first card gave us ten steps, so the total will be 10+9+8+7+6+5+4+3+2+1, the tenth triangle number, 55.
Soooo n(n+1)/2 where n is the number of cards :D
@@kubastefanski5538 Precisely.
As some one else pointed out, if we cannot turn the right-most card because it has no neighbour, we lose the first n steps (the steps involving that card) so then the answer is the (n-1)th triangle number.
Note that in this case we turn the card in the next to right-most position n-1 times.
Thus we can only reach a state of all face-up, or zero, if n-1 is odd, because turning the next to right-most card an even number of times will result in the right-most card being turned face-down for every time we turn it face-up.
Yeah, only took me a couple of seconds to figure that one out. I'm used to playing a puzzle game that it helps to know what the digits from 1 to 9 add up to, so I already knew it was 45. So I just added 10 to it and got 55. Nice explanation though.
@@roccov3614 Thank you.
Though, adding up the numbers seems trivial compared to finding out what numbers to add.
Could you describe these puzzles?
I'm not convinced by this argument (although the conclusion is correct). This shows that a greedy algorithm that maximizes face-down cards at every turn ends in n*(n+1)/2 moves, but another algorithm could conceivably get more mileage.
Ive been following mathologer for a year now. It was only last week that I found your name and realised that you are the author of "the mathematics of juggling" thank you for both the excellent videos and the excellent book!
For other gems have a look at Marty and my website www.qedcat.com :)
For the Bonus question I also have nice solution.
You can also think of it as building a 2D crystal. Though the 2x2 grid is the smallest posibble structure, the 4x4 cell is basically your unit cell describing your crystal in full. And sice you are not allowed to rotate only to translate your unit cell all the properties the grid has are being conserved, including the outer most corners always being the same colours.
The max number would be 55. First, you would start by flipping over the card all the way to the right. Move that flipped card to the left by flipping the card directly to the left of it (this will flip the card to the left so that it faces up, and flip the card all the way to the right back down, effectively moving the flipped card to the left). Keep doing this until the flipped card is all the way to the left. This takes 10 steps. Now you effectively have the same situation but with 9 cards, not 10. Do this over and over again, and you eventually reach 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1, which would equal 55.
for this you have to imagine a 11th card on the right of 10th card and you flip a imaginary card every time you flip the 10th card.
@philiphendrix7140 Exactly 🎯! I’m glad I’m not the only one, who got this solution. Gives me more confidence in mine. 🙂👍🏻
@@jagadishgajurel2597 You can, if you want to. Either way, in this video, it was agreed that turning the far-right card face up involves simply turning over that 1 card.
Longer videos are great, but this format is interesting too... and we're going to enjoy mathologer videos more frequently!
A question: do you use a particular (custom) software to create the animations of the "math autopilots"?
Pretty sure it's PowerPoint.
@@ryanodonnell2726 me too, I think Mathologer said that, or maybe 3b1b pointed this out in a video
@@ryanodonnell2726 Yep, he occassionally mentions the number of slides of the presentation, which is the video.
@@polettix yes, I think in pi is transcendental video, where he complained about having to make too many slides :D
Amazing, continue with this!
Hi , your proof was nicer :) and please make more short video. I really enjoy all your videos. Shorter videos are also nice. Thanks a lot Dr. Burkard Polster.
"Did you get it?"
Yes, I got the same answer.
My interpretation was that turning over just the right-most card was not a legal move. Even if it were, the same argument leads to termination.
With 10 cards, and assuming the rightmost card can not be flipped by itself, the maximum number of moves is 45. If you do allow the rightmost card to be flipped by itself, the answer as 55.
Sadly, I saw the answer video before this one.
I'm actually surprised and pleased with myself for being able to understand the solution from the clip alone, haha.
Of course it is such a simple that anyone should be able to understand it, was is not for he using a binary number representation, and most people being unfamiliar with binary. If, for instance, he decided for no particular reason to use 0 and 9, everyone who isn't familiar with binary would immediately have an easier time understanding it.
You can also describe the solution without using any numbers at all. You can just use the letters D and U, and show that the only two things that can happen to the sequence of letters is two Ds turn into Us, or a D swaps places with a U to its right.
As a result you either end up with two Ds next to each other, or they are separated by some run of Us. In the latter case you can move the rightmost one until its all the way to the right, at which point the only remaining option is to move the leftmost D closer to the rightmost one until you're back to the former case, meaning you must turn both Ds into Us.
I really liked this video. I majored in Philosophy in part because it allowed me to escape some math phobia. This one was both easy to understand but still mind expanding in teaching a new way to think about math.
I very much enjoyed this and would like to see more like it.
I liked this video, easier to understand than the usual one. It has one failing as a simple explanation, though. If someone doesn't know what binary numbers are, they probably also don't know that everyday, base-10 numbers are "decimal" numbers. That's a vocabulary word you only need if you also know about other base systems like binary or hexadecimal.
I'm sure the vast majority watching this have had something like computer science 101 at some point.
The assumption is that if you plan on being in the mathematical olympiad you would know how binary works.
@@alexandertownsend3291 Yeah, pretty much guarantee anyone in a Mathematical Olympiad can work in binary, my problem is doing it on the clock, not the Mathematics involved. When I did the forrunners here.
For the last problem, instead of the 4 colours we label each square with the numbers 1,2,3 or -6. Then sum of 4 squares is 0 iff the consist of 4 different numbers. Label the squares of the grid in the form (i,j) where (1,1) is the topmost leftmost square. For any i,j
Your choice of 1,2,3,-6 doesn't work, because 2+2+2+(-6)=0. But 1,2,4,-7 works.
2 + 2 + 2 - 6 = 0
use different labels
Very nice solution! It is also possible to completely analyze the possible configurations. For an n×m grid (with n,m≥2), there are 6×(2^n+2^m-4) possible configurations. Let's prove that. Call our four colors A,B,C,D. Remark first that the whole grid is determined by the upper row and the leftmost column. By permuting the colors in the grid, we can fix the colors of the cells in the upper left corner. So let's suppose the first row starts with AB and the first column starts with AC. If we put in the first row ABABABABAB... and in the first column ACACACAC..., we get a coherent grid (no contradiction when we fill it). Any other grid is obtained by modifying this "base" grid. Anyway it's a bit annoying to explain actually... I give up. We cannot modify both "rows and columns" at the same time, so we have 2^{n-2} possibilities if we modify columns, 2^{m-2} possibilities if we modify rows, and 1 possibility in the intersection. We also have a factor 4! because of the initial reduction, and this gives 4! × (2^{n-2} + 2^{m-2} - 1) = 6 × (2^n + 2^m - 4).
What about the same problem in 3d? Your solution still works but I don't know if we can understand all possible configurations.
@@IEIM64I You need the labels to be different. But anyway, this is not essential to the solution, you can also just use x,y,z,w and say that x+y+z+w=0.
@@eggegg9026 I'd argue that it is essential to the solution, as using 1,2,3,-6 in this case only tells us that the four corner squares either are all unique, or consists of 3 identically colored squares.
When solving things with invariance, never assume that just because an invariant is found, you'll end up proving precisely what is asked. In this case however, we are lucky enough that there are many sets of numbers that can prove the corners are all unique.
Edit: i didnt mean to come of as derogatory. The iff sum is 0 the tiles are unique, is whats actually important. It's just that i think people should be very careful about almost proofs, as its not always clear that the same method can get you all the way.
The explanation in the movie was very clear to me. But yours was equally well explained.
Nice format. I appreciated. I don’t always time to look at 45 mns video. Greetings from Paris ( France, not Texas… )
I like the binary-proof; because it’s elegant, and doesn’t require you to know much of the dynamic. On the other hand, your proof, Mathologer, is possibly more intuitive, once someone points it out to you. 👍🏻
First off, the video wasn't explicit about the condition of 'terminate.' This can confuse some, but you can infer it from the condition of choosing a facedown card, which infers that if there are no facedown cards there is nothing suitable to choose.
From there, it's even simpler than math[s]. It's logic. If you have a finite set, and your task is to find one thing in a certain condition, change that condition and also change the condition [regardless of what that condition is] of a related thing, eventually you will run out of things in the [unchanged] condition, because the one definitive move of every action is from unchanged to changed.
but that doesn't work though
let's say the cards are aligned in a circle, such that there's always a card to the right of any card, then it's easy to see that this does not have to terminate
but your proof doesn't distinguish between these two scenarios (so it has to be incorrect)
As Michael points out, you haven't rigorously proved it. The stumbling block is that cards can change back and forth numerous times (perhaps forever?), so you have to PROVE termination.
For this proof to work you have to prove that the graph of state changes is acyclical.
Also, logic is ofc part of maths. Every mathematical proof is essentially just logic.
7:42 I'm glad you mentioned it because I noticed it and was curious. Just flipping the one card/number makes sense.
I've never heard of this movie before. After seeing this clip, it's made me now want to watch it...
12:55 you mention your Mathologer T-shirt shop. It would be nice to have a direct link in the description. Love the short videos and the long videos.
Something missing in the proof … it isn’t really specified what happens when you get down to just the last digit .. 00001. Of course, this can only happen if there are an ODD number of cards, and all the examples chosen have an even number of cards so will always get to zero. But and odd number of cards will always finish at 0000…001. So either the question could be reposed as “for any positive even integer number of cards”, or the special case of the rightmost card as the only face-up card needs to be formally considered / have its own rule.
The last question is just a recursive argument starting with a 2x2 grid which must satisfy the different corner criteria.
Each double size grid must satisfy the criteria inductively because there are always 4 tilings (top, bottom, left, right) which preclude repetition in the corners by mirror symmetry.
Have a look at the grid again, the bottom row isn't the same as the 2nd row.
loved thaT FILM ,,,,,,,,,,,,,,,,,,,,AND LOVED YOUR VIDEO !!!
I like the quickness of this video, I don't always have time to watch the full videos that you normally do. I also imagine they are a bit easier to produce.
Oh, yes, a LOT easier to produce
On the 4 corners question:
Lemma: the 2x2s must repeat in the obvious way (no reflections, rotations, permutations)
Consider a 2x2 satisfying the condition and the 1x2 domino to the left of it. Now look at a 2x2 that is shifted one place to the left, thus containing the domino.
Since it must satisfy the condition too, it can't repeat any colors in the 1x2 domino that both 2x2's share. This only leaves the colors in the domino on the right side of the original 2x2. Thus all columns must be composed of 2x1 dominoes that contain the same 2 colors as the dominoes 2 steps to the right of them, and by the left of them by the obvious substitution. So all columns must contain the same sequence of 2x1 dominoes.
But we can repeat the same argument with the original 2x2 shifted 1 step upwards. Thus we have 2 overlapping sequences of dominoes that agree leftwards/rightwards on the set of 2 colors. This fixes not only the set of colors but also the ordering. Thus columns are identical to other columns 2 steps to the left or right.
We can also repeat the same argument vertically, so all rows match rows 2 steps up or down. This implies that not only do the columns agree left/right, they also repeat the same 1x2 domino over and over.
By the same argument, rows repeat a 2x1 domino endlessly.
But that means that any 2x2 exactly repeats the 2x2 that is 2 steps left , right, up, or down. Thus 2x2s repeat in the obvious way, Lemma QED.
Since the grids were all 4n x 4n, we can subdivide it exactly into 2x2 blocks in the obvious way. (Actually only requires 2nx2n alignment).
Since all 2x2's are identical, the corner 2x2's are identical. But the top-left corner of the grid is the top-left box of the repeated 2x2, top-right is the top-right etc, in a 1-to-1 mapping. And those are all different colors, by our original condition. So the corners of the grid are all different colors, QED.
Unless I've misunderstood, I don't think this proof is correct. Here's a counterexample:
Row 1: BRBR
Row 2: YGYG
Row 3: RBRB
Row 4: GYGY
Notice that the 2x2 in the top corners have BR in the top row and YG in the second row, but the 2x2 in the bottom corners have RB in their top row and GY in their bottom row. So I think maybe you were on the right lines for the proof but there's a special kind of permutation that's allowed when you translate by 2 steps.
@@Alex_Deam Yes, your counterexample seems to be correct. I was too hasty in assuming that I had ruled out all permutations.
Isn't the arrangement shown in the video like Alex's, with the lower squares of four being symmetric but not identical to the upper ones?
@@Tehom1 as far as I can tell, you are on the right track, and absolute repetition is much more stronger than needed to prove the needed result anyway.
Edit : actually maybe 2x2s don't repeat but 4x4s do? due to there only being 4 colors.
As far as I can see, the lemma fails when the overlapping 2x1 dominoes have the same pair of 2 colors, but that kind of repetition implies row or column copying throughout the grid. I don't think it's possible to compose two different grid layouts together in a larger grid with strong 2x2 condition.
Do love your videos. This one was especially nice. I'd even like to see short ones like this related to historical mathematics. I especially like the "non-binary" solution to this, not because binary is unfamiliar, but sometimes I just want to get away from the digital because I like trying to understand how people think about these problems. I especially like seeing how different skillsets reveal solutions to complex problems, many times without the exhaustive simulation we often resort to today.
I like the short format. Good for when I don't have a lot of time for the regular long form and just as thought provoking and educational. For me, I saw the two proofs as the same. But then, being a computer scientist for more than forty years, the up vs down state of the cards just naturally maps on to an equivalent string on ones and zeroes.
I like every vid you upload
yes please. make more such.
Would the maximum number of moves to turn all 10 cards over be 55? By flipping the digits furthest to the right on every move, you decrease the binary value by the smallest amount, and it would take 1 move for the first bit, 2 moves for the second bit, all the way until 10 moves for the 10th bit. So 1+2+3+...+10 = 55?
That's it :)
The 10th triangular number
I'm not entirely convinced by this argument (although the conclusion is correct). This shows that a greedy algorithm that seeks to always decrease the number by as little as possible terminates in 55 moves, but possibly another algorithm could get more mileage.
@@felipe970421 You can weigh each facedown card with numbers decreasing by 1. For example, with 8 cards, the weights will be, from left to right, 8, 7, 6, 5, 4, 3, 2, 1. In the binary proof, the weights were 128, 64, 32, 16, 8, 4, 2, 1, but the same exact idea applies. With the 8, 7, 6, 5, 4, 3, 2, 1 weights case, every move decreases the count by at least 1. And since we started with 8+7+6+5+4+3+2+1. There can't be an algorithm with more than 36 moves. Similarly, in the 10 card case, there can't be an algorithm with more than 55 moves.
Doing our homework from the last lecture, the answer should be 1*n choose 1 + 1* n choose 2, a more general case
Wow beautifully explained.
I know I'm very late here, but just wanted to comment regarding the special colouring question.
As others have pointed out this works for 2n×2n or even 2n×2m, not only 4n×4n.
Sketch proof, by contradiction, assuming 2 corners are red.
There are (n×m/4) -2 reds left for the rest of the grid. The ones removed belong to only 1 2×2 square each, leaving
(n-1)(m-1)-2 to cover with the remaining reds.
At most (n-2)(m-2)/4 reds can belong to the in interior cells of the original square. These can cover up to 4 2×2 subsquares each.
So, at least
(n×m/4) -2 - (n-2)(m-2)/4
reds must be on the exterior cells of the original square and only belong to at most 2 2×2 subsquares.
These facts combine to give an upper bound of
nm -n -m -2 remaining subsquares that include a red.
But there are nm-n-m-1 of these subsquares. So it's not possible to complete the colouring.
What happens is you make a circle with the cards? I guess you'd get some kind of indeterminate result (half ones and half zeros) ?? ... a probability distribution of 'n' cards after 'x' trials??
Interesting variation. In this case you can have faces travelling around the circle so that things never terminate. Would be interesting to calculate what happens if you always randomly choose a face-down card. I suspect that in the case of an even number of cards eventually all cards will be face up anyway. With an odd number of cards things will definitely never terminate :)
@@Mathologer here is an argument for evenly many cards. If you randomly choose a face up card, the process terminates with probability 1. The process is a Markov chain. If we weight the states with number of face cards, the transition matrix is upper triangular, and "all faces up" is the unique steady state.
11:00 The maximum number of moves is 5. The rules say that you always turn two *face-down* cards, which renders them face-up, removing them from play. Since there are 10 cards total, this gives you exactly 5 moves. It also does not say you have to turn two *consecutive* cards, so there is no boundary problem here. It also has no rules for what to do about face-up cards; in fact, given all of the above, if you were to be able to flip face-up cards arbitrarily, then there would be no maximum (just repeatedly flip the same card over and over again forever). We must therefore assume, given we want to end with face-up cards, that face-up cards cannot be touched.
I originally thought that as well, that it was a new game and that the "flip two face-down" cards was the rule to use for the game. I think the proper interpretation of how he stated the problem is that it is still under the card-flipping rules of the original problem, but he was pointing out that if one *chooses* to flip two face-down cards for each move it takes 5 moves to flip them all. To get this result you also must choose an even-numbered (with 0-based indexing) card as the left one of the pair to flip; otherwise you get isolated face-down cards that will require extra moves to flip.
Essentially he was saying "the minimum is 5 (here's how) but what is the maximum?"
@@kevinmartin7760 He says you always turn two face down cards up. If you have to do that five moves is the only number to finish. No other moves are allowed.
Aha I got it from another comment. He just showed how to get to the shortest solution.
Good job you make it so that it's understandable and that's important thank you
Finally, a video that i think i understand and it didnt take me a few months to muster up courage =)
Also the music is great in that movie clip