The Most Amazing Fact About Light Switching Puzzles (SoME1)
Vložit
- čas přidán 8. 06. 2024
- #SoME1 #SummerOfMathExposition
In the classic Lights Out game, you get some starting light pattern and you have to turn all the lights off, but it turns out that the game creators had to be careful to make sure that they wouldn't present you with an unsolvable starting pattern.
I'd like to show you a variation of Lights Out called Lamp Lighter, where all lights start off and you have to turn them on, but the game can challenge you with any setup. Amazingly, Lamp Lighter will always have a solution, and we can prove it from very basic principles.
The journey is totally worth it.
0:00 - Lights Out
0:30 - Lamp Lighter
1:57 - Menu
2:32 - Induction
5:03 - Exhaustion
6:24 - Construction
12:08 - Food for Thought
I loved how you used the "odd sums of odd numbers are odd" fact as an example to demonstrate induction, and then brought it back as part of the proof.
8:55 "we're still in the dark" Nice. 😄
criminally underrated channel
This is the most beautiful proof i have ever seen... despite watching such videos regularly , and knowing mostly what you told. I STILL FOUND IT SO IMPRESSING , this shouldve definitely been a winner ♥️
Best entry I've seen so far! The explanations are extremely intuitive.
Wow, your illustration of induction was just plain beautiful. I'll Definitly keep that in mind when explaining.
This was absolutely BEAUTIFULLY explained-- please, please continue to make more content!!
This is an underrated incredible video!!!
Nice! I actually was studying these and several variations recently.
This video is so damn good. Thank you for sharing this with us. :)
Nice job man, seems like soft soft has gotten a lot more complex since the fruity loops days that I rember. Very helpful, thank you.
Best tutorial ive evr seen bro ur d best!!!!!
A great channel👍❤️
It's crazy how many times in this proof you showed that if X then it's easy, so assume not X, eventually reducing the problem to a very specific sub-case!
Another way of looking at that approach is to think of it as trying to prove the opposite by finding a counter-example. Instead of "I've proved it for X, which only leaves not-X to prove", more like "X doesn't give a counter-example: I need to try not-X".
Either way, you still go through the same process of narrowing down the area of uncertainty to some very specific cases and then solving those, but sometimes it's easier to come up with X by thinking "What situations are easily proved?", and other times it's easier to think about "How might this go wrong and produce a counter-example?" to come up with not-X.
I feel 10x more confident in soft soft, thanks!
what a great video!
That's a gem.
NOICE!
complete. So I put a few videos up to show what i've got so far, and i'm hoping that soone will take the ti to watch them, let
The proof is nice but i don’t know if complete. The part of choosing a vertex with even number of neighbors assumes that we can always do so in such a way that the remaining nodes remain in a single connected component(or at least each of the components has an even number of nodes). However, this may not be the case, for example, for the following graph:
1-2
1-3
1-4
2-3
2-4
3-4
4-5
4-6
5-6
6-7
Where we numbered the nodes from 1 to 7 and the edges are the ones above. Here there is a single node with an even number of neighbors(node 5), but excluding it and its neighbors leaves 2 connected components(1-2-3 and 7)
It’s a nice proof and I’m not saying that the game may have cases where its unsolveable(the one above is easily solved), but it doesn’t look complete.
There is nothing in the proof that makes such an assumption. There is no connectedness required between the remaining components. The proof only assumes that we are in a situation where solving the light puzzle for any subset of N-1 nodes will leave the missing node unlit (because otherwise we're done). I don't know if that's true for your graph but let's assume it is. When we choose 5 and its neighbors, let's call them (456), all we're saying is that we're going to go to every node one by one, except *4, 5, and 6*, and solve for the other N-1 nodes. All the nodes besides those in (456) will be on at the end of this process since we performed the N-1 trick an even number of times and all of those nodes were excluded for lighting from one of those even times. Since the nodes in (456) were never excluded, they were toggled an even number of times and are therefore all off at the end. Now we press 5 and we're done.
@@goingnull6028 yeah, you’re right, my bad.
Thanks for the reply, it’s a very nice proof!
ikr!
Does anyone knows, why my GMS soft soft is diffrent ?
(UPD: I misunderstood a part of the video; it uses normal induction, but since I've made some other points here, I decided to leave this.)
In this video, the method you used is not normal induction, but transfinite induction. There are 4 differences between them:
- In normal induction, you prove that the statement holds for n+1, and in transfinite induction, you prove it for n. In normal induction, this doesn't really matter (I've heard another CZcamsr, Another Roof, saying that the previous element isn't defined yet so we need to go from n to n+1 and not from n-1 to n, but I disagree for 2 reasons: the previous element operation is used in the only proof for induction I know, and it's easy to construct), but for transfinite induction, it's easier
- In transfinite induction, you can use all the smaller values of n, and not just the previous one. This is the reason why normal induction can't be used to prove this or solve the square sum problem (youtube-search it if you want to know).
- Transfinite induction can be used for any well-ordered set and not just the natural numbers
- The base case is a special case of the step, but here and in my fix for a flaw I found in a proof in the Russian book Парадоксы теории множеств (Paradoxes of the Set Theory) by Ivan Yashchenko, it is considered separately
I have shown that the fact holds for a base case (0), and that if it holds for N, it holds for N + 1. It's not clear to me where you see an actual hole in this proof or why there is a need for transfinite induction.
@@goingnull6028 In the odd case, you use the solution to the problem for smaller Ns. You can't do that in normal induction. You can also fix that by adding lamps without neighbours or formulating the statement as “for every N, there is a solution for any n≤N lamps”, but I think transfinite induction is simpler
That is not correct. Even in the odd case, we are always solving subsets strictly of size N. The only difference is that in the even case, we solve for all N + 1 subsets of size N, since each of the N + 1 lamps will be chosen as the excluded lamp, whereas in the odd case, we choose fewer subsets of size N, since lamps from the separated odd section will not be chosen for an exclusion. Nevertheless, the solved subsets are always precisely of size N.
@@goingnull6028 I've re-watched that part and now think that you should have specified that the odd part has the number of nodes equal to 1. Without that, you use the fact for smaller Ns, although later you only use a weaker version of the statement you proved this way that doesn't require it. Moreover, you specified that part incorrectly, so it looks like you use the stronger version that requires smaller Ns
@@orisphera No. This is a misunderstanding. The odd section can have any odd number of nodes. But the subsets that are switched are always of size N. The size of the switched subsets is not related to the number of switched subsets.
I find it difficult to understand the reasoning in the part from 8:30 to 8:50
Yeah. I wish I would have added a bit more. So the first thing to remember is that we're in the context of a setup where every "minus one game" leaves the missing lamp unlit at the end. So we're going to choose every individual lamp for its own turn as the missing lamp, and perform every single "minus one game" solution. This section is discussing what happens in that scenario. Let me know if that helps.
4:17 I love card there is e π and also golden ratio, and 1.729 ? It is kinda close to the √3, but it isn't √3. And also 22/7 xd
en.m.wikipedia.org/wiki/Taxicab_number
@@goingnull6028 Spotted all four and stopped the video to see if anyone had commented :)
Interesting point about the Hardy-Ramanujan number, I always found it weirder that Hardy, himself a pre-eminent number theorist of the day, didn't recognise that 1729 was the sum of two cubes in two ways, both of the sums are very obvious if you know the cubes up to 12. Certainly more surprising to me than Ramanujan spotting it was.
arrow once. then you get the soft from the video
LMFAO