The Christmas Tree Algorithm Puzzle

[@kanashisa0]

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.

[@eduardoxenofonte4004]

floating point being floating point

[@fhudufin]

how have i gone my entire life without knowing that there was a closed form version of fibonacci sequence

[@rafiihsanalfathin9479]

@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).

[@rafiihsanalfathin9479]

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

[@NStripleseven]

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.

[@fandango5673]

I don't understand how you don't have thousands of subscribers. My guess for the worst case scenario is (2^12)-1 presses

[@ritzkid76]

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 :)

[@samarendra109]

Question is, how do you know when to stop

[@mdashrafulahmed2820]

you will know when to stop when the Christmas lights are on

[@NStripleseven]

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.

[@ritzkid76]

@@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

[@TarenNauxen]

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!

[@shashankbhatt4609]

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]

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.

[@shashankbhatt4609]

@@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.

[@DEMEMZEA]

8:50 The error isn't in the formula, it's in the fact that computers can't have infinite data

[@danielrhouck]

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.

[@VanVlearMusic]

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

[@dani-rybe]

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.

[@LittleCloveredElf]

Solved it using some weird binary method this is way cleaner, Great Christmas present

[@lilium724]

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.

[@dev-asya]

great video as always - thank you for the work you've put into this

[@crafti55]

7:10 Me already writing code: "Nah, I'd win".

[@rotflmaopmpqxyz]

It’s the ABACABADABACABA sequence! 2^12-1 moves

[@portobellomushroom5764]

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

[@elunedssong8909]

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.

[@Ashebrethafe]

@@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.)

[@elunedssong8909]

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.

[@wavejumper3]

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!

[@DavidMcCabe-i8c]

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.

[@marendor9087]

The fact that he said general solution for fibonacci is an aproximation is crazy

[@landsgevaer]

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).

[@tcoren1]

10:57 why are you assuming that consecutive terms in an exponentially growing series are close to one another?

[@miroaja1951]

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)

[@tcoren1]

@ 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

[@miroaja1951]

@@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

[@HeavyMetalMouse]

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.

[@bloom945]

Fun puzzle, and rilliantly explained Happy holidays 🌟🎄

[@DaleBagley-g8m]

I got the answer almost immediately Edit: the simple answer that requires you to go through each of them

[@Omega_3301]

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]

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.

[@Omega_3301]

@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

[@tylerduncan5908]

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.

[@miguelangelguillenhernande8647]

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.

[@paologat]

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.

[@Czeckie]

it's actually the parts proportional to 1 that cancel out; mind the formula has a sqrt(5)

[@paologat]

@ 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.

[@GrindelTF]

are there any plans of a discord server or smth similar to discuss puzzles like this?love the videos

[@YATAQi]

@@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 :)

[@ReinhardHahn-vs2dh]

111111111111 interpreted as Grey-Code gives the result: Binary 101010101010 or Decimal 2730

[@danmerget]

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".)

[@nicomuller3125]

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

[@Ryan_Thompson]

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).

[@nicomuller3125]

@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

[@Andre_Mations]

Awesome Video! Keep on going!

[@fatih3806]

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

[@Owclj]

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)

[@Nat-fw8kl]

How do you prove its the optimal result ? It seems to be the case but i don't exactly get why

[@dani-rybe]

I think I've proved it. See my other comment for explanation

[@owlmanac]

Mathematics is beautiful This is just like retracting piston extenders in Minecraft

[@Sven_vh]

Interesting video! What video editing program do you use to make these? Just Premiere Pro?

[@YATAQi]

Mainly Premiere Pro, yeah. Although I do use Manim (Visual Studio) to create all the equations (and geometry elements from my other videos).

[@jennaxolotl6275]

Once you showed the procedure in the algorithm section of the video i realized it was just binary counting, great video

[@eofirdavid]

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.

[@RuntaTQ]

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.

[@targetabc]

Thats the maximum aproches you need. Minimum is 0 if by any chance they are already all on

[@TahsinHossain-u9f]

U got a new sub

[@mekaindo]

I love the clicking

[@MrConverse]

4:35, your next to last switch array is incorrect. It should be G G G G R. Hope it helps. Good video!

[@MrConverse]

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). ;-)

[@nicholacastriota]

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

[@ALISTAIRIVANSIAHINGCO]

The answer is 2^n-1+2^n-3+2^n-5..... until n minus the other number is equal to 0 or 1

[@QuaziAymanUzayr]

2^12. - 1 moves?

[@thephysicistcuber175]

From the title I expected AoC 2024 day 24 part 2 💀.

[@qipengliu2627]

Seems the same as the Chinese 9 ring puzzle

[@Looking-for-More]

Sounds like an advent of code problem

[@eriksteffahn6172]

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

[@zPieEater]

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

[@rsvdark_main]

4:35 that last move wouldn't work, the third to last one should be at the end

[@YATAQi]

Oh good catch - that’s definitely a mistake from my end: The second-to-last set of switches should be GGGGR.

[@rsvdark_main]

@@YATAQi Still the same amount of moves, so not a big issue

[@SysFan808]

initial guess: 2^12

[@richodude5455]

just return the tree 😂

[@esphix]

12:24 12 moves?

[@YATAQi]

@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 :)

[@esphix]

@@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.

[@samarendra109]

​@@YATAQiif the indicators are broken, how do we know when to stop? There needs to be something that says all the indicators are on.

[@JoaoVitorBarg]

Worst case for any amount of buttons n!

[@pekkaplayspiano]

For the algorithm

[@HexaBurger]

Wooo

[@Leon-r7y]

Under 5 mins gang

[@tau93]

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