8:50 Fibonacci sequence closed form is *exact*; it is 100% accurate. The formula always give the correct integer number, not an approximation. The error is likely due to machine precision, not the formula.
@fhudufin Many sequences have a closed form formula, if you think about it, sequences equation is like differential equation but in discrete world. So, many of the differential equation tehnique can be use to solve this kind of equation (with little bit of tweak ofc).
In fact, there is a branch of mathematics that make a connection between discrete and continous, its called umbral calculus, there is derivative and integral in discrete world too
You could probably create a representation of integers with an extra sqrt(5) element (all representations would be a polynomial in sqrt5) and get an exact answer that way. Would be slow as balls but you could do it.
I believe you are correct. The worst case is to go through every possible combination of button toggles before landing on the right one. there are 2^n combinations of buttons, and the start was known to be incorrect. This means the generalized answer is 2^n - 1, and for 12 its what you said :)
Yea you’d have to just binary iterate through every possible combination until you hit the one that works. Probably there’s some optimal way to do that where you don’t have to flip multiple bits per change, but I don’t know it.
Wrote out the steps just as you described! Got 1, 2, 5, 10, 21, 42, then skipped the formula part and just came up with the recursive definition. Manually calculated out to 2730. Great puzzle!
A computer can easily solve that without infinite data; you don’t need infinite data to represent √5. I just did it there in two Unicode code points and it probably takes only slightly more for a computer algebra system. The problem is that computers by default use floating-point values and you have to look harder if you want exact representation of anything, especially of anything not rational.
For the bonus puzzle, you can assume WLOG that you start with all switches off and need to reach all possible arrangements of on and off switches. This can be done in 2^12 - 1 moves by using the Gray code ordering.
@@targetabc It asks for the minimum in the worst case, and since it's possible that the last arrangement you try is the correct one, the answer is 2^n - 1.
Really cool video, well explained and animated, nice work! What's even more amazing to me, is that as a tried solving this problem from a programmers perspective, i made a quick script in processing, and after implementing the rules, tried the most basic algorithm i could think of: pressing all the buttons in order, from left to right, over and over again until they're all lit up. I never expected it to actually work, it was just to test things out. Here's the thing: not only did it work, but when i counted only the moves that actually did something, i arrived at the same solution: 2730. which is just insane.
My recursive formula was M(n) = 2^N + M(n-2), with the same initial conditions. It follows that for even N > 2, M(n) is the sum from i=1 to N/2 of 2*4^(i-1) and for odd N > 2 M(n) is the sum from i=1 to (N+1)/2 of 1*4^(i-1) Which, using Faulhabers Formula for exponential sums, gives us the same closed form solutions.
Great video! Here's a way to prove that 2730 is the optimal number of moves: Write 1 above every lamp that's turned on. Write 0 above every lamp that's turned off. Now, going from left to right, if a lamp is turned on, switch all the numbers above the lamps to the right of it. Do it for all the lamps from left to right and you end up with a binary value. It can be easily shown that any valid switch of a lamp, either increases that value by one or decreases it by one. The starting configuration corresponds to the value of 0. The end configuration corresponds with the value of 2730. That means that any algorithm that goes from all lamps off to all lamps on will have at least 2730 moves. Edit: this I'm pretty sure also answers the bonus question at the end. Just calculate the value of your given configuration and the value of a desired configuration and the absolute value of their difference will be the number of moves needed to go from one to the other. Edit 2: This also shows that the hardest configuration to reach from all lamps off is the one where just the leftmost lamp is on and it takes 2^n -1 moves Edit 3: I now know that this interpretation is called the Grey-Code.
The answer does grow exponentially, not polynomially, but unfortunately it's not as simple as 2^(n-1). The reason is because the preceding switches don't turn off when a new one turns on
Close, it's the binary sequence of the switches, where every other number is a 1. In our example of 12 switches, that means 101010101010 in binary, or 12^11+12^9+ .... What you did only turns on the left 2 most switches. We then need to turn on the next two left most switches, which is why it ends up being this every other binary pattern.
@@elunedssong8909 Yes - in fact, any state of the switches can be represented as a 12-bit number, where the first bit is 1 if the leftmost switch is off or 0 if it’s on, and each subsequent bit is different from the last if the next switch in line is off or the same if it’s on. Then pressing the next switch in the sequence reduces the number by 1. So 2^12 - 1 (i.e. 4095) moves is correct for the worst case, which is that all the switches except the leftmost one are on. (This also means that 4095 is the correct answer for the bonus problem, obtainable by following the same sequence of moves.)
This won't give you an answer to any optimal solution, but I think you could turn them all on by running your hand from left to right over and over until everything is all in the on position. I'm not perfectly sure about this, but it seems like at any given point, you want to flip the left-most switch that can be flipped, inclusive to multiple flips in each pass (meaning if you flip switch 6 you continue pressing 5 4 3 2 1 instead of jumping back to 12) The system i mentioned seems to work for up to n=5, but i dont know if a problem occurs further down the line.
i imediatly tried the same thing! but i dont think it works if the starting condition is 10101 (1 is the switch being on, 0 is off) also im curious about what do you do when hitting the 1st/last one, that is, when your mashing "bounces"
Before video: We may observe that to get the left two most switches turned on follows 2^(n-1) Therefore the general pattern for any set of even switches is number of switches recusively put into 2^(n-1) where n is deducted by 2 each recursion till it fits. In our example this is 2^11 + 2^9 + 2^7... or the binary pattern 101010101010 To check it follows our rule we may observe the first few results. 1 switch = 2^0 2 switches = 2^1 3 switches = 2^2+2^0 4 switches = 2^3 + 2^1 .... Simply plug in 1 in binary every other number for the general solution. After video: Uhhhh we had different solutions? Closed form? Wow, okay i'll try and learn what you're talking about, but the binary solution is correct. I'm pretty sure it works for odd numbers too, and is completely generalized, but I'm too lazy to verify. Edit2: Wow, this is like using a sledge hammer to press a key stroke. Impressive, and wonderful for sure. Way higher level math than my brain can intuitively understand, but I'll keep it in mind the next time I need to try and figure out an exact solution to a recursive pattern.
This is simply silly limit stuff, but essentially: given n -> ∞, then: n + a -> ∞ | a ∈ ℝ then, for certain compositions m of n, such that: m(n) -> c then: m(n + a) -> c the composition M shown in the video is a recurance, for which we know exists a common limit due to the monotonic growth of the relationship, as so, we do know that for an arbitrarily large n, the window of error is also arbitrarily small. You are right to assume that this doesn't always work, for example the composition sin(n), would not be right as no limit exists for sin(n) at infinity. The real takeaway here is that limits at infinity are weird, and you can do powerful stuff like eliminate random offsets if you use them correctly. (emphasis on correctly)
@ I have a problem with the underlying assumption that a limit exists, since the solution is exponential. The presence of a fixed point actually proves that the limit exists for some starting conditions, but the argument he used in the proof is very flawed
@@tcoren1 I agree that it would be if you examine the problem simply from the perspective of the recurrence itself. However since he formed a inhomogeneous relationship formula, the compositor M no longer reflects the plain definition of the recurrence, and instead is used to examine its asymptotic behavior. I.e. its "total", rather than consecutive terms. In this form its specifically possible to make this inference because of its exponential nature, essentially its not that the terms are "close" to one another, and instead that they all tend to infinity (as per my previous comment). Very similar mechanisms are used to examine differential equations (which themselves are a sort of special case of recurrence relations), and specifically their solutions' (the values of M here) asymptotic behavior. I get that this all may seem a little strange, but a lot of it goes away once you think of the equation not as consecutive terms, and instead like any other function
It seems like, for the finding of the a particular solution, we'd be better off thinking of it less as a limit to large values of N, and more abstracting it and considering a 'fixed point'. In the source problem, it is impossible for a term to take "-1/2 moves". However, in the abstract, M(x) = -1/2 is a 'fixed point' of the given recurrence relation - that is, if M(1) = M(2) = -1/2, then all M(n) = -1/2. Fixed points, if they exist, are a convenient way to find particular solutions for recurrence problems (which then combine with the general homogeneous solution as mentioned). The use of limiting behaviour is *also* a useful tool for finding particular solutions, and the methods are related enough to often be conflated.
Yes, that part is just nonsense. All one really needs in this step is any (concrete) sequence that solves the equation. So naturally one would start by trying out some really simple sequences and it turns out a constant one already works. That's all there is to it, it has nothing to do with limits.
To turn on the nth light (counting from right to left) takes 2^(n-1) moves. When n > 1, you get the (n-1)th light for free. So to turn on all the lights up to n you need to, from left to right, turn on each of the same-parity lights, which will take the sum of the opposite-parity powers of 2 less than n. So M(12) = 2^11 + 2^9 + 2^7 + 2^5 + 2^3 + 2^1 = 2730.
Watching this at 5AM, didn’t pause at the solving time, I jumped straight to a closed form solution but all I figured was there was going to be a 2^n and it matters if n is odd or even, and didn’t pause to think a bit longer. Sleepy brain forgot to go the recursive route to actually figure out answers not just form
5:46 I think Manim allows you to specify which part of the equation you want to transform (or rather, stays the same between transformation). seeing the entire equation morph when only the last part changed is a bit jarring. the same happened at 5:505:58
If you only keep the exponential term with the positive root - ((1+√5)/2)^n/√5 from memory - thén you get an approximation (because the other term goes exponentially towards zero).
I handled it by grouping the switches two at a time and pushing them to the left. To turn on the two leftmost switches while turning all the others off, you need 2048 presses. Then, for the next two switches, it’s a quarter of that-512 presses-followed by 128, 32, and so on. At the end, only the last four switches are off, and I calculated manually that this requires 10 presses. Adding everything together gives a total of 2730 presses. For the problem mentioned at the end of the video, my guess would be to use an algorithm that ensures all the switches are off first. After that, you could apply the original algorithm. However, I’m not entirely sure how to achieve that and need to think about it more. It might not even be the right approach! I’m hoping for a follow-up video or an explanation in the comments. :D
Hint/clarification for the second problem: you can toggle each switch at will--the requirement for the switch to the right to be on is no longer a requirement. The challenge is that the state of each switch can't be observed, the initial state is random, so you only know if you're done if the Christmas lights light up (i.e., all switches are now ON).
@Ryan_Thompson wait are you sure? Got to watch the end again later, I thought the requirements still apply. If they don't the problem is pretty easy, just "count up" in binary as if all buttons were 0 (ok this won't be the best solution, a different order is better, for example the order 1 3 2 is better than 1 2 3 in order of presses but my points stands, just find a way to cycle through every config once, slowest solution would be 2^n -1
I don't understand why with the 5 switches you can not go from move 9: rggrg to move rggrr, then to rgrrr, and then to ggrrr. Here r stands for red, and g stands for green light on. That us if you can taggle the rightmost switch at any time. Then for n=5 you'll get 17 moves, and consequently for n=12 only 122 moves. Am I wrong?
The switches have 2^12=4096 different permutations, and we can start a path to get to every other permutation exactly once each, the worst case scenario would be that it’s the last one, that means it’s 4096-1=4095 moves
2^(12) - 1: Use a Gray code to go through all 2^(12) states in 2^(12) toggles. If you're lucky, it's already in the correct state. If you're unlucky, you won't get to the correct state until it's the last one out of 2^(12) checked. So 2^(12) - 1. Brute force, but it's the best brute force you can do.
Ok, I scrolled down in the comments to see if this had been mentioned before I made my comment but it seems that I needed to scroll just a little bit more to find an earlier comment about this (and your reply). ;-)
There's a quicker way. You need to turn on 2 buttons at a time, starting from the left. If you have n off buttons, it takes 2^n-1 moves to do so. (Trivially verified by induction). So for 12 buttons, it's 2^11 + 2^9 +2^7... +2^1 = 2730 For the n=5 case, it's 2^4 +2^2 + 2^0 = 21 as expected. No need fof closed form stuff, which is probably more complicated
@cheshire1 yeah, that works too basically 2(4^0+4^1+...4^5) but personally just calculating is faster for 12 buttons. definitely easier when the button count gets higher though
Right when you said "it's too late to go out and buy another set of lights" I intuitively thought "it's probably too late to turn on the lights on time for Christmas... 2025" Well, maybe that's a bit extreme, but it's the kind of recursion problem that looks fine for small numbers and then grows at an absurd rate, like the Hanoi stacks.
A very nice video, however you have a couple of problems in it. First, the statement that n, n-1 and n-2 converge to one another as n goes to infinity is a horrible statement, in particular when these are parameters inside another function. I have personally seen many students lose lots of points for making such wrong statements , and unfortunately I also saw such mistakes in research papers. The thing is, if you remove this statement, your proof works fine - you just look if there is a solution with a constant, and there is. The second problem, is that while you showed that you can turn all the switches on, you did not show that this is the minimum number.
It's crazy that I had to scroll so far before anyone mentioned Gray code; it should be the #1 response. (Minor nit: it's spelled "Gray code", not "Grey code", since it was developed by a guy with the last name "Gray".)
Funnily enough, the procedure enforced in the main problem is actually a valid algorithm for the bonus problem, just continue until only the left button is “pressed”. Keep track of pressed/unpressed instead of on/off. Min 4095 (2^n-1)
You can only toggle the rightmost button in 2 cases: all buttons are off the leftmost button is on and all other buttons are off This is because you can toggle the switch to the immediate left of the first ON button from the right (if any)
The closed formula for Fibonacci numbers is exact and always results in an integer value. All powers of (A+B*sqrt(5)), where A and B are integers, are themselves numbers of the same form. And given that the left and right half of the Fibonacci formula only differ by the sign of B, it turns out the parts proportional to sqrt(5) cancel out exactly, leaving an integer result.
@ it’s the parts that are proportional to 1 in the numerator, which become the parts proportional to sqrt(5) in the full formula (and vice versa). The point is, claiming that the Fibonacci closed formula is merely an approximation is a major oops.
So, without looking at the answer: Two things I noticed while brute-forcing smaller examples: 1- In order to turn on N switches, at some point you must have all N-1 switches turned on. 2- The number of steps to turn on all N switches is equal to the number of steps to turn them all off. So, the algorythm to turn N switches on is: 1- Turn N-1 switches on 2- Turn N-2 switches off 3- Turn the Nth switch on 4- Turn N-2 switches on And a formula arises for the number of steps: F(N) = F(N-1) + 2*F(N-2) + 1, with F(0) = 0 and F(1) = 1. With this, F(12) = 2,730 steps. I cannot demonstrate this is the minimum number of steps, though.
think button that been pressed as 1 and the other as 0, press the buttons right to left just like when you count in binary. then it will pass all case in 000000000000 to 111111111111. that will be 2^12 presses but all-0 means 0 presses so 2^12-1 press will be needed
For the ending problem, you have no information, other than figuring out whether they’re all green or at least one isn’t. In the worst case you’re gonna have to go through all possible bad states before finally reaching the good one. Using a Gray code allows you to do it in 2^12 total presses (every press gets you to a new state)
i did it for the first few, saw the pattern. I'm kinda obsessed w/ binary logic and such, this is exactly my type of problem. I got... 500 in hex? or 2660. formula 2^(n-1)+2^(n-3) no clue if its right or why it is if it is. Time to see if im right!
You find really cool problems man I have found Mn= Mn-1+2Mn-2+1 and calculated 2730 but didn’t work for finding a general form because I just didn’t need to, nice that you have included that part The interesting thing with the general formula you have found is that it generalizes the “Xmaslight-numbers” to reals, just like how bidet formula expands the Fibonacci numbers; even if turning on pi lights doesn’t make any sense per say
Answer (my attempt) to the question (2^12)-1, since we have to check every possible configuration, because if we didn’t check this particular combination(Lets call it Y) than it is possible, that initial state was reverse of Y, and we didn’t check Y. So we have to check every possible combination of binary switches.
I think I would cut the wires and use wire nuts/solder on a normal wall plug/power supply and call it a day. Christmas saved. Signed, an engineer who's bad at math. :(
i don't know how *good* it is but i found a formula that isn't the one you used it is M(n) = 2M(n) + (n mod 2), i don't know how valid my solution is but it works really great, since i realised that every odd numbers had a +1 and every even number was only 2M(n-1)
10:50 The result is good, but the argument is wrong. You can't just turn M(n-1) into M(n) by saying that (n-1)/n gets arbitrarily close to one. What matters is what happens between M(n+1) and M(n) as n approaches infinity. And if we look at your final closed form, we clearly get M(n-1) = M(n)/2 (as n approaches infinity) What you could say instead is, "we try and look for a special solution of the form M(n) = c, and solve for c". You don't need to justify why you use this form. If it works (and it did!) you have your special solution. If it doesn't, you try something else.
2^13 -1 is the worst case scenario, if you count up as if it was a binary number you can easily see: rightmost switch is switched every move 2dn rightmost switch is switched half of the moves etc. so we get 2^12(1 + 1/2 + 1/4 + ... + 1/2^12) = 2^13-1
10:48-11:00 this part just makes no sense all we really want is any concrete solution to the non-homogenious equation, so we consider the simplest case, a constant sequence, which turns out to work for c = -1/2 letting n go to inifinity is neither necessary nor useful
Stepped up to solve for 2730, i dont understand why even to odd is 2n+1 while odd to even is just 2n yet Edit: rule is turn up to n-1 on, then turn up to n-2 off, turn n on, then turn up to n-2 on Even numbers take even steps: odd + even + 1 + even Odd numbers take odd steps: Even + odd + 1 + odd
@esphix 1 move would be the minimum in the BEST case scenario - meaning all the switches are on except for one of them - which you just so happen to toggle correctly with some luck (we’re assuming 0 isn’t included because the lights are off to begin with). But for the WORST case, this doesn’t mean that all the switches are off (which would just require 12 moves like you mentioned). The switch configuration is arbitrary. So we need to devise an algorithm that will eventually turn on all the switches no matter what the configuration looks like. This algorithm could be successful after just 1 toggle (BEST case), or it could be pushed to its limit and you’d have to carry it out in its entirety (WORST case). I hope that makes sense :)
@@YATAQi Yes, I understand, and I think the answer you're looking for is 2^12-1, but "worst case scenario" is pretty vague and the question could therefore be interpreted as the maximum amount of toggles the game could force out of you (you could get lucky otherwise), which would imply that the switches are all off, like you mentioned. I think your definition of *worst* is dependent on the algorithm (that determines the answer) that you're asking for. That is, the worst case scenario would be the state of the toggles where the algorithm would do worst on. Though, posing your question like this seems unfair in a way. Wouldn't I be able to say that my algorithm is *dependent* on state of the toggles of the worst case scenario, and wouldn't that lead to the answer being less than or equal to 12 again? SN: I think there's some connection with the halting problem that does not allow you to pose and answer questions like that (or when you do it, that the result would be 12 and not the intended answer) Edit: even though you might think that the dependency on the algorithm's performance on all states is removed when you try to argue that there is a worst case (with your desired answer) for each algorithm, you realize that that is a circle definition or still dependent on the algorithm.
for the last question at 12:23, it's 2^12, you have to test ever configuration, and there is 2^12, to get a new configuration in only one move you use gray code en.wikipedia.org/wiki/Gray_code
holy crap i came up with a method in my head and thought it would work. turns out i started with 2¹² rather than 2¹¹ so my end result was wrong. But my method was right, that feels good first guess: 4096+1024+256+64+16+4+1=5461 correct answer: 2048+512+128+32+8+2=2730
8:50
Fibonacci sequence closed form is *exact*; it is 100% accurate. The formula always give the correct integer number, not an approximation.
The error is likely due to machine precision, not the formula.
floating point being floating point
how have i gone my entire life without knowing that there was a closed form version of fibonacci sequence
@fhudufin Many sequences have a closed form formula, if you think about it, sequences equation is like differential equation but in discrete world. So, many of the differential equation tehnique can be use to solve this kind of equation (with little bit of tweak ofc).
In fact, there is a branch of mathematics that make a connection between discrete and continous, its called umbral calculus, there is derivative and integral in discrete world too
You could probably create a representation of integers with an extra sqrt(5) element (all representations would be a polynomial in sqrt5) and get an exact answer that way. Would be slow as balls but you could do it.
I don't understand how you don't have thousands of subscribers. My guess for the worst case scenario is (2^12)-1 presses
I believe you are correct. The worst case is to go through every possible combination of button toggles before landing on the right one. there are 2^n combinations of buttons, and the start was known to be incorrect. This means the generalized answer is 2^n - 1, and for 12 its what you said :)
Question is, how do you know when to stop
you will know when to stop when the Christmas lights are on
Yea you’d have to just binary iterate through every possible combination until you hit the one that works. Probably there’s some optimal way to do that where you don’t have to flip multiple bits per change, but I don’t know it.
@@NStripleseven flipping only one bit each time is known as gray code, and it is very similar to the problem solution outlined in the video
Wrote out the steps just as you described! Got 1, 2, 5, 10, 21, 42, then skipped the formula part and just came up with the recursive definition. Manually calculated out to 2730. Great puzzle!
If you made an hour long video of just the finger pushing switches and running through the entire solution of 12, I would watch that over and over
8:50 The error isn't in the formula, it's in the fact that computers can't have infinite data
A computer can easily solve that without infinite data; you don’t need infinite data to represent √5. I just did it there in two Unicode code points and it probably takes only slightly more for a computer algebra system.
The problem is that computers by default use floating-point values and you have to look harder if you want exact representation of anything, especially of anything not rational.
Solved it using some weird binary method this is way cleaner, Great Christmas present
For the bonus puzzle, you can assume WLOG that you start with all switches off and need to reach all possible arrangements of on and off switches. This can be done in 2^12 - 1 moves by using the Gray code ordering.
He is searching for the minimum. The minimum is 0: the switches are already all on by random chance. Maybe the definition of the riddle was bad.
@@targetabc It asks for the minimum in the worst case, and since it's possible that the last arrangement you try is the correct one, the answer is 2^n - 1.
7:10
Me already writing code: "Nah, I'd win".
Really cool video, well explained and animated, nice work!
What's even more amazing to me, is that as a tried solving this problem from a programmers perspective, i made a quick script in processing, and after implementing the rules, tried the most basic algorithm i could think of: pressing all the buttons in order, from left to right, over and over again until they're all lit up. I never expected it to actually work, it was just to test things out.
Here's the thing: not only did it work, but when i counted only the moves that actually did something, i arrived at the same solution: 2730. which is just insane.
My recursive formula was
M(n) = 2^N + M(n-2), with the same initial conditions.
It follows that for even N > 2,
M(n) is the sum from i=1 to N/2 of 2*4^(i-1) and for odd N > 2 M(n) is the sum from i=1 to (N+1)/2 of 1*4^(i-1)
Which, using Faulhabers Formula for exponential sums, gives us the same closed form solutions.
Great video! Here's a way to prove that 2730 is the optimal number of moves:
Write 1 above every lamp that's turned on.
Write 0 above every lamp that's turned off.
Now, going from left to right, if a lamp is turned on, switch all the numbers above the lamps to the right of it. Do it for all the lamps from left to right and you end up with a binary value. It can be easily shown that any valid switch of a lamp, either increases that value by one or decreases it by one. The starting configuration corresponds to the value of 0. The end configuration corresponds with the value of 2730. That means that any algorithm that goes from all lamps off to all lamps on will have at least 2730 moves.
Edit: this I'm pretty sure also answers the bonus question at the end. Just calculate the value of your given configuration and the value of a desired configuration and the absolute value of their difference will be the number of moves needed to go from one to the other.
Edit 2: This also shows that the hardest configuration to reach from all lamps off is the one where just the leftmost lamp is on and it takes 2^n -1 moves
Edit 3: I now know that this interpretation is called the Grey-Code.
This is an _exceptionally_ clever proof! How did you come up with this idea?
@Zephei I knew binary numbers were involved somehow. The rest is luck I guess.
Your channel is fantastic how do you not have more subscribers wtf
It’s the ABACABADABACABA sequence! 2^12-1 moves
The answer does grow exponentially, not polynomially, but unfortunately it's not as simple as 2^(n-1). The reason is because the preceding switches don't turn off when a new one turns on
Close, it's the binary sequence of the switches, where every other number is a 1. In our example of 12 switches, that means 101010101010 in binary, or 12^11+12^9+ ....
What you did only turns on the left 2 most switches. We then need to turn on the next two left most switches, which is why it ends up being this every other binary pattern.
@@elunedssong8909 Yes - in fact, any state of the switches can be represented as a 12-bit number, where the first bit is 1 if the leftmost switch is off or 0 if it’s on, and each subsequent bit is different from the last if the next switch in line is off or the same if it’s on. Then pressing the next switch in the sequence reduces the number by 1. So 2^12 - 1 (i.e. 4095) moves is correct for the worst case, which is that all the switches except the leftmost one are on. (This also means that 4095 is the correct answer for the bonus problem, obtainable by following the same sequence of moves.)
great video as always - thank you for the work you've put into this
This won't give you an answer to any optimal solution, but I think you could turn them all on by running your hand from left to right over and over until everything is all in the on position.
I'm not perfectly sure about this, but it seems like at any given point, you want to flip the left-most switch that can be flipped, inclusive to multiple flips in each pass (meaning if you flip switch 6 you continue pressing 5 4 3 2 1 instead of jumping back to 12)
The system i mentioned seems to work for up to n=5, but i dont know if a problem occurs further down the line.
i imediatly tried the same thing! but i dont think it works if the starting condition is 10101 (1 is the switch being on, 0 is off)
also im curious about what do you do when hitting the 1st/last one, that is, when your mashing "bounces"
Before video:
We may observe that to get the left two most switches turned on follows 2^(n-1)
Therefore the general pattern for any set of even switches is number of switches recusively put into 2^(n-1) where n is deducted by 2 each recursion till it fits.
In our example this is 2^11 + 2^9 + 2^7... or the binary pattern 101010101010
To check it follows our rule we may observe the first few results. 1 switch = 2^0 2 switches = 2^1 3 switches = 2^2+2^0 4 switches = 2^3 + 2^1 ....
Simply plug in 1 in binary every other number for the general solution.
After video: Uhhhh we had different solutions? Closed form? Wow, okay i'll try and learn what you're talking about, but the binary solution is correct. I'm pretty sure it works for odd numbers too, and is completely generalized, but I'm too lazy to verify.
Edit2: Wow, this is like using a sledge hammer to press a key stroke. Impressive, and wonderful for sure. Way higher level math than my brain can intuitively understand, but I'll keep it in mind the next time I need to try and figure out an exact solution to a recursive pattern.
10:57 why are you assuming that consecutive terms in an exponentially growing series are close to one another?
This is simply silly limit stuff, but essentially:
given n -> ∞, then:
n + a -> ∞ | a ∈ ℝ
then, for certain compositions m of n, such that:
m(n) -> c
then:
m(n + a) -> c
the composition M shown in the video is a recurance, for which we know exists a common limit due to the monotonic growth of the relationship, as so, we do know that for an arbitrarily large n, the window of error is also arbitrarily small.
You are right to assume that this doesn't always work, for example the composition
sin(n), would not be right as no limit exists for sin(n) at infinity. The real takeaway here is that limits at infinity are weird, and you can do powerful stuff like eliminate random offsets if you use them correctly. (emphasis on correctly)
@ I have a problem with the underlying assumption that a limit exists, since the solution is exponential.
The presence of a fixed point actually proves that the limit exists for some starting conditions, but the argument he used in the proof is very flawed
@@tcoren1 I agree that it would be if you examine the problem simply from the perspective of the recurrence itself. However since he formed a inhomogeneous relationship formula, the compositor M no longer reflects the plain definition of the recurrence, and instead is used to examine its asymptotic behavior. I.e. its "total", rather than consecutive terms. In this form its specifically possible to make this inference because of its exponential nature, essentially its not that the terms are "close" to one another, and instead that they all tend to infinity (as per my previous comment). Very similar mechanisms are used to examine differential equations (which themselves are a sort of special case of recurrence relations), and specifically their solutions' (the values of M here) asymptotic behavior. I get that this all may seem a little strange, but a lot of it goes away once you think of the equation not as consecutive terms, and instead like any other function
It seems like, for the finding of the a particular solution, we'd be better off thinking of it less as a limit to large values of N, and more abstracting it and considering a 'fixed point'.
In the source problem, it is impossible for a term to take "-1/2 moves". However, in the abstract, M(x) = -1/2 is a 'fixed point' of the given recurrence relation - that is, if M(1) = M(2) = -1/2, then all M(n) = -1/2. Fixed points, if they exist, are a convenient way to find particular solutions for recurrence problems (which then combine with the general homogeneous solution as mentioned).
The use of limiting behaviour is *also* a useful tool for finding particular solutions, and the methods are related enough to often be conflated.
Yes, that part is just nonsense.
All one really needs in this step is any (concrete) sequence that solves the equation. So naturally one would start by trying out some really simple sequences and it turns out a constant one already works.
That's all there is to it, it has nothing to do with limits.
To turn on the nth light (counting from right to left) takes 2^(n-1) moves. When n > 1, you get the (n-1)th light for free. So to turn on all the lights up to n you need to, from left to right, turn on each of the same-parity lights, which will take the sum of the opposite-parity powers of 2 less than n.
So M(12) = 2^11 + 2^9 + 2^7 + 2^5 + 2^3 + 2^1 = 2730.
Watching this at 5AM, didn’t pause at the solving time, I jumped straight to a closed form solution but all I figured was there was going to be a 2^n and it matters if n is odd or even, and didn’t pause to think a bit longer. Sleepy brain forgot to go the recursive route to actually figure out answers not just form
5:46 I think Manim allows you to specify which part of the equation you want to transform (or rather, stays the same between transformation). seeing the entire equation morph when only the last part changed is a bit jarring. the same happened at 5:50 5:58
The fact that he said general solution for fibonacci is an aproximation is crazy
If you only keep the exponential term with the positive root - ((1+√5)/2)^n/√5 from memory - thén you get an approximation (because the other term goes exponentially towards zero).
I handled it by grouping the switches two at a time and pushing them to the left. To turn on the two leftmost switches while turning all the others off, you need 2048 presses. Then, for the next two switches, it’s a quarter of that-512 presses-followed by 128, 32, and so on. At the end, only the last four switches are off, and I calculated manually that this requires 10 presses. Adding everything together gives a total of 2730 presses.
For the problem mentioned at the end of the video, my guess would be to use an algorithm that ensures all the switches are off first. After that, you could apply the original algorithm. However, I’m not entirely sure how to achieve that and need to think about it more. It might not even be the right approach! I’m hoping for a follow-up video or an explanation in the comments. :D
Hint/clarification for the second problem: you can toggle each switch at will--the requirement for the switch to the right to be on is no longer a requirement.
The challenge is that the state of each switch can't be observed, the initial state is random, so you only know if you're done if the Christmas lights light up (i.e., all switches are now ON).
@Ryan_Thompson wait are you sure? Got to watch the end again later, I thought the requirements still apply.
If they don't the problem is pretty easy, just "count up" in binary as if all buttons were 0 (ok this won't be the best solution, a different order is better, for example the order 1 3 2 is better than 1 2 3 in order of presses but my points stands, just find a way to cycle through every config once, slowest solution would be 2^n -1
I don't understand why with the 5 switches you can not go from move 9: rggrg to move rggrr, then to rgrrr, and then to ggrrr. Here r stands for red, and g stands for green light on. That us if you can taggle the rightmost switch at any time. Then for n=5 you'll get 17 moves, and consequently for n=12 only 122 moves. Am I wrong?
The switches have 2^12=4096 different permutations, and we can start a path to get to every other permutation exactly once each, the worst case scenario would be that it’s the last one, that means it’s 4096-1=4095 moves
2^(12) - 1: Use a Gray code to go through all 2^(12) states in 2^(12) toggles. If you're lucky, it's already in the correct state. If you're unlucky, you won't get to the correct state until it's the last one out of 2^(12) checked. So 2^(12) - 1.
Brute force, but it's the best brute force you can do.
4:35, your next to last switch array is incorrect. It should be G G G G R. Hope it helps. Good video!
Ok, I scrolled down in the comments to see if this had been mentioned before I made my comment but it seems that I needed to scroll just a little bit more to find an earlier comment about this (and your reply). ;-)
@@MrConverse I was looking for that comment and I saw yours first!
There's a quicker way. You need to turn on 2 buttons at a time, starting from the left. If you have n off buttons, it takes 2^n-1 moves to do so. (Trivially verified by induction). So for 12 buttons, it's 2^11 + 2^9 +2^7... +2^1 = 2730
For the n=5 case, it's 2^4 +2^2 + 2^0 = 21 as expected.
No need fof closed form stuff, which is probably more complicated
we can also determine a closed form of 2^11 + 2^9 +2^7... +2^1 using the geometric sum formula, which yields the same result.
@cheshire1 yeah, that works too
basically 2(4^0+4^1+...4^5)
but personally just calculating is faster for 12 buttons. definitely easier when the button count gets higher though
Right when you said "it's too late to go out and buy another set of lights" I intuitively thought "it's probably too late to turn on the lights on time for Christmas... 2025"
Well, maybe that's a bit extreme, but it's the kind of recursion problem that looks fine for small numbers and then grows at an absurd rate, like the Hanoi stacks.
A very nice video, however you have a couple of problems in it.
First, the statement that n, n-1 and n-2 converge to one another as n goes to infinity is a horrible statement, in particular when these are parameters inside another function. I have personally seen many students lose lots of points for making such wrong statements , and unfortunately I also saw such mistakes in research papers. The thing is, if you remove this statement, your proof works fine - you just look if there is a solution with a constant, and there is.
The second problem, is that while you showed that you can turn all the switches on, you did not show that this is the minimum number.
3:50 rip to those who paused the video and tried it without listening to the remaining part😂
I got the answer almost immediately
Edit: the simple answer that requires you to go through each of them
111111111111 interpreted as Grey-Code gives the result: Binary 101010101010 or Decimal 2730
It's crazy that I had to scroll so far before anyone mentioned Gray code; it should be the #1 response. (Minor nit: it's spelled "Gray code", not "Grey code", since it was developed by a guy with the last name "Gray".)
Funnily enough, the procedure enforced in the main problem is actually a valid algorithm for the bonus problem, just continue until only the left button is “pressed”. Keep track of pressed/unpressed instead of on/off. Min 4095 (2^n-1)
You can only toggle the rightmost button in 2 cases:
all buttons are off
the leftmost button is on and all other buttons are off
This is because you can toggle the switch to the immediate left of the first ON button from the right (if any)
is your UA-cam channel for sale? I'd love to buy it.
This is a lot like Gray Code.
Cool stuff!!
Bonus points for ending with SAT!!!
Gold star!
The closed formula for Fibonacci numbers is exact and always results in an integer value.
All powers of (A+B*sqrt(5)), where A and B are integers, are themselves numbers of the same form. And given that the left and right half of the Fibonacci formula only differ by the sign of B, it turns out the parts proportional to sqrt(5) cancel out exactly, leaving an integer result.
it's actually the parts proportional to 1 that cancel out; mind the formula has a sqrt(5)
@ it’s the parts that are proportional to 1 in the numerator, which become the parts proportional to sqrt(5) in the full formula (and vice versa).
The point is, claiming that the Fibonacci closed formula is merely an approximation is a major oops.
So, without looking at the answer:
Two things I noticed while brute-forcing smaller examples:
1- In order to turn on N switches, at some point you must have all N-1 switches turned on.
2- The number of steps to turn on all N switches is equal to the number of steps to turn them all off.
So, the algorythm to turn N switches on is:
1- Turn N-1 switches on
2- Turn N-2 switches off
3- Turn the Nth switch on
4- Turn N-2 switches on
And a formula arises for the number of steps:
F(N) = F(N-1) + 2*F(N-2) + 1, with F(0) = 0 and F(1) = 1. With this, F(12) = 2,730 steps.
I cannot demonstrate this is the minimum number of steps, though.
think button that been pressed as 1 and the other as 0, press the buttons right to left just like when you count in binary. then it will pass all case in 000000000000 to 111111111111. that will be 2^12 presses but all-0 means 0 presses so 2^12-1 press will be needed
sorry for bad english btw
Fun puzzle, and rilliantly explained Happy holidays 🌟🎄
For the ending problem, you have no information, other than figuring out whether they’re all green or at least one isn’t. In the worst case you’re gonna have to go through all possible bad states before finally reaching the good one. Using a Gray code allows you to do it in 2^12 total presses (every press gets you to a new state)
Mathematics is beautiful
This is just like retracting piston extenders in Minecraft
The 12 matches the block push limit, too. Funny.
i did it for the first few, saw the pattern. I'm kinda obsessed w/ binary logic and such, this is exactly my type of problem.
I got...
500 in hex?
or 2660.
formula 2^(n-1)+2^(n-3)
no clue if its right or why it is if it is.
Time to see if im right!
You find really cool problems man
I have found Mn= Mn-1+2Mn-2+1 and calculated 2730 but didn’t work for finding a general form because I just didn’t need to, nice that you have included that part
The interesting thing with the general formula you have found is that it generalizes the “Xmaslight-numbers” to reals, just like how bidet formula expands the Fibonacci numbers; even if turning on pi lights doesn’t make any sense per say
Awesome Video! Keep on going!
Answer (my attempt) to the question
(2^12)-1, since we have to check every possible configuration, because if we didn’t check this particular combination(Lets call it Y) than it is possible, that initial state was reverse of Y, and we didn’t check Y. So we have to check every possible combination of binary switches.
Thats the maximum aproches you need. Minimum is 0 if by any chance they are already all on
are there any plans of a discord server or smth similar to discuss puzzles like this?love the videos
@@GrindelTF That’s a really cool idea actually! I’ll try setting one up at some point in the near future so stay on the lookout for an announcement :)
I think I would cut the wires and use wire nuts/solder on a normal wall plug/power supply and call it a day. Christmas saved. Signed, an engineer who's bad at math. :(
i don't know how *good* it is but i found a formula that isn't the one you used it is M(n) = 2M(n) + (n mod 2), i don't know how valid my solution is but it works really great, since i realised that every odd numbers had a +1 and every even number was only 2M(n-1)
10:50 The result is good, but the argument is wrong. You can't just turn M(n-1) into M(n) by saying that (n-1)/n gets arbitrarily close to one. What matters is what happens between M(n+1) and M(n) as n approaches infinity. And if we look at your final closed form, we clearly get M(n-1) = M(n)/2 (as n approaches infinity)
What you could say instead is, "we try and look for a special solution of the form M(n) = c, and solve for c". You don't need to justify why you use this form. If it works (and it did!) you have your special solution. If it doesn't, you try something else.
How do you prove its the optimal result ? It seems to be the case but i don't exactly get why
I think I've proved it. See my other comment for explanation
I love the clicking
Interesting video! What video editing program do you use to make these? Just Premiere Pro?
Mainly Premiere Pro, yeah. Although I do use Manim (Visual Studio) to create all the equations (and geometry elements from my other videos).
U got a new sub
2^13 -1 is the worst case scenario, if you count up as if it was a binary number you can easily see:
rightmost switch is switched every move
2dn rightmost switch is switched half of the moves
etc.
so we get 2^12(1 + 1/2 + 1/4 + ... + 1/2^12) = 2^13-1
10:48-11:00 this part just makes no sense
all we really want is any concrete solution to the non-homogenious equation, so we consider the simplest case, a constant sequence, which turns out to work for c = -1/2
letting n go to inifinity is neither necessary nor useful
From the title I expected AoC 2024 day 24 part 2 💀.
This is very similar to the tower's of Hanoi puzzle
Sounds like an advent of code problem
Seems the same as the Chinese 9 ring puzzle
2^12. - 1 moves?
Anyone ever had the Spin It! puzzle? That's this exactly.
The answer is 2^n-1+2^n-3+2^n-5..... until n minus the other number is equal to 0 or 1
4:35 that last move wouldn't work, the third to last one should be at the end
Oh good catch - that’s definitely a mistake from my end:
The second-to-last set of switches should be GGGGR.
@@YATAQi Still the same amount of moves, so not a big issue
Stepped up to solve for 2730, i dont understand why even to odd is 2n+1 while odd to even is just 2n yet
Edit: rule is turn up to n-1 on, then turn up to n-2 off, turn n on, then turn up to n-2 on
Even numbers take even steps:
odd + even + 1 + even
Odd numbers take odd steps:
Even + odd + 1 + odd
just return the tree 😂
Once you showed the procedure in the algorithm section of the video i realized it was just binary counting, great video
initial guess: 2^12
For the algorithm
12:24 12 moves?
@esphix 1 move would be the minimum in the BEST case scenario - meaning all the switches are on except for one of them - which you just so happen to toggle correctly with some luck (we’re assuming 0 isn’t included because the lights are off to begin with).
But for the WORST case, this doesn’t mean that all the switches are off (which would just require 12 moves like you mentioned). The switch configuration is arbitrary. So we need to devise an algorithm that will eventually turn on all the switches no matter what the configuration looks like.
This algorithm could be successful after just 1 toggle (BEST case), or it could be pushed to its limit and you’d have to carry it out in its entirety (WORST case). I hope that makes sense :)
@@YATAQi Yes, I understand, and I think the answer you're looking for is 2^12-1, but "worst case scenario" is pretty vague and the question could therefore be interpreted as the maximum amount of toggles the game could force out of you (you could get lucky otherwise), which would imply that the switches are all off, like you mentioned. I think your definition of *worst* is dependent on the algorithm (that determines the answer) that you're asking for. That is, the worst case scenario would be the state of the toggles where the algorithm would do worst on.
Though, posing your question like this seems unfair in a way. Wouldn't I be able to say that my algorithm is *dependent* on state of the toggles of the worst case scenario, and wouldn't that lead to the answer being less than or equal to 12 again?
SN: I think there's some connection with the halting problem that does not allow you to pose and answer questions like that (or when you do it, that the result would be 12 and not the intended answer)
Edit: even though you might think that the dependency on the algorithm's performance on all states is removed when you try to argue that there is a worst case (with your desired answer) for each algorithm, you realize that that is a circle definition or still dependent on the algorithm.
@@YATAQiif the indicators are broken, how do we know when to stop? There needs to be something that says all the indicators are on.
Wooo
Worst case for any amount of buttons n!
Under 5 mins gang
for the last question at 12:23, it's 2^12, you have to test ever configuration, and there is 2^12, to get a new configuration in only one move you use gray code
en.wikipedia.org/wiki/Gray_code
holy crap i came up with a method in my head and thought it would work. turns out i started with 2¹² rather than 2¹¹ so my end result was wrong. But my method was right, that feels good
first guess:
4096+1024+256+64+16+4+1=5461
correct answer:
2048+512+128+32+8+2=2730