Equivalently you can think this way: the glasses are automatically inversed and each time you choose one glass not to get inversed. Remark that for a glass to get inversed, it needs to get inversed odd times. Therefore, if you choose one glasses at a time for four inversions, every glass gets inversed three times and gets inversed!
Example in detail (order doesn't actually matter) Starting uuuu invert all but the first uddd invert all but the second dduu invert all but the third uuud invert all but the forth dddd Generalizing: The number of glasses equals the number of moves.
alternatively you can think about it as invertin one glass then and inverting up and down. to invert all glasses you need to have inverted all glasess and have up and down in the same way as in the begining
There is a solution that works for any number of glasses and requires only 0 inverting steps... you take all the glasses and carefully, without reverting any of them, travel to the exact opposite point of the Earth's surface. DISCLAIMER: doesn't work for flat earthers.
yeah it's not even a puzzle really is it? I mean, the first move whichever 3 you turn over you end up equivalent to 0000 to 1110, 3 of them will be upside down one the right way up. This is the same as 0000 to 0111 or 0000 to 1011 and so on. There's no puzzling about move 1 it's a given. For your 2nd move. If you turn the same 3 back over, you'd just end up back at the start. So the only other choice is to turn 2 upside down back and the one you didn't touch on your first move upside down. So 1110 goes to 0011. So far we've done 2 moves and had no real choice over either of them. Now we're in a position with 2 upright and 2 upside down. The only 2 moves are, turn 2 of the upright and 1 upside down, or 2 upside down and 1 upright . One of which 0011 goes to 1110 which is going backwards to a previous state. So we must go from 0011 to 1000. I'd accept that this move requires a bit of thought. Our last move is now trivial. We just turn the 3 upright glasses upside down achieving our goal 1000 to 1111. So, it's puzzle insofar as you had to do a bit of analysis for move 3. The other moves are either just obvious or they're the only moves you can make.
I did this with my fingers, different moves, but same amount, nice. Edit: for those who want my moves 1: fingers up, 0: fingers down 1111 - start position 0010 - move 1 0101 - move 2 1011 - move 3 0000 - move 4 / final position
Every position is just a linear combination on Z/2Z of the 4 possible moves, since moves are commutative. The question is then "find the coefficients given the basis".
@@Horopter Z/2Z is the residual class ring to 2, so the natural numbers modulo 2; so all values are either 0 or 1 (normal or flipped); which glass you move first is irrelevant since you could just rearrange them the important part here is that inverting glasses is basically adding +1 in the Z/2Z so 0+1 = 1 and 1+1 = 2 = 0
It takes two moves to reach a position where two of the glasses are upside down. This is a symmetrical situation which could be reached from either the initial position or the desired final position. That means the minimum number of moves is four.
It is even simpler You have 4 glasses, but can only turn 3 of them each round. To turn everything you must turn total number of glasses equal to number that is simultaneously divisible by 3 and 4. Smallest such number is 12. Meaning you will turn total 12 glasses, aka 4 rounds of 3 glasses. If you turn 6 glasses you will get 6/4=1|2, aka 2 glasses in wrong position.
@@MichaelDarrow-tr1mn Ok, in THAT case it was much easier. In general rule is much more complicated and take in account unique combinations and even/odd nuances. Rule of smaller divisible will only work on unique combinations where difference between number of glasses and number of turning glasses is odd. In case when difference between numbers is even, number of steps will ALWAYS be 3 [unless allowed to turn number is less than third of total]. (for example 9 to 7 or 9 to 5 or 9 to 3) This task also will fail if number of total glasses is odd, but you can only turn even glasses at a time. Because even if you would be able to make difference in one or more glasses glass, you will always return them to upside glasses turn on each "odd" step, meaning you wouldn't be able to make it asymmetric. (for example 9 to 4, 9 to 6 and 9 to 8)
The simples terms to think of this is, there is in each situation until the final move only one possible move that doesn’t recreate a previous situation
This is exactly how I thought of it. Aside from the first move, you always have two options in each move. One of those options makes you go backwards to the previous position, which obviously cannot be how you achieve the minimum number of moves.
copying my comment here for you as you are completely right! this is a really great puzzle I remember solving this when i was a teen - as part of comp sci A-lvl - its an example of heuristic hill climbing algorithm (an algorithm that looks ahead x steps to a better solution to find a final solution) - this sort of algorithm was used in early chess AI (and most modern AI pathing in modern video games) Seems Im getting old though (now 45) because I couldn't for the life of me solve it now - and had to watch the vid. (yes it was the proof bit i struggled with, not mentally flipping glasses). Interestingly its also the same problem(well very related) as the old board game 'mastermind' also the 'lights out' puzzle (a 2d version, rather than 1d) - something I used to happily solve in my head in fast time due to it being part of a puzzle in the video game Dungeons and dragons online as part of a raid. yep.. DEFINITELY getting old, my brain has slowed down so much.
you are completely right! I remember solving this when i was a teen - as part of comp sci A-lvl - its an example of heuristic hill climbing algorithm (an algorithm that looks ahead x steps to a better solution to find a final solution) - this sort of algorithm was used in early chess AI (and most modern AI pathing in modern video games)
Since glass position does not matter only the Up or Down positioning, this is a simple state model where the initial state is 4U0D and you want to get to 0U4D by changing a total 3 U to D or D to U each round. Sideways and backward state changes to prior states are not allowed. So it goes 4U0D, 1U3D, 2U2D, 3U1D, 0U4D .. done, 4 is the minimum possible with not duplications of states.
This elegance can be seen better if you swap the U and D after each step, as in the case of 6 or more cups. Instead of - 6U0D, 1U5D, 4U2D, 3U3D, 2U4D, 5U1D, 0U6D It would be - 6U0D, 5D1U, 4U2D, 3D3U, 2U4D, 1D5U, 0U6D Using this, you can know the orientation of cups in any step for n cups. x move for y cups (y-x)DxU for all x that is odd (y-x)UxD for all x that is even ie. 53rd move for 80 cups = 27D53U 40th move for 90 cups = 50U40D
1: lemme fiddle with this 2: wait this might be impossible 3: lemme check by thinking about possible states 3.5: wait the state of the glasses only depends on the number of downs and ups 4: ah wait its not impossible 5: finds solution 6: yippie *clicks video*
I solved this using some advanced linear algebra: Firstly, note the isomorphism between the state of the glasses and the *F*_2-vector space *F*_2^n: for a vector (a_1, ..., a_n) in *F*_2^n, the term a_i = 0 if the glass is not inverted, and 1 if it is. Applying the move "invert all but the i-th glass" is equivalent to adding the vector e_i := (1, 1, ..., 1, 0, 1, ..., 1), where only the i-th term is 0. Since the initial state of the glasses is the zero vector (0, ..., 0), we wish to find nonnegative integers c_1, ..., c_n such that c_1 e_1 + ... + c_n e_n = (1, 1, ..., 1). Taking the c_i modulo 2, and noting that we are after the minimum of c_1 + ... + c_n, we can assume that each c_i is either 0 or 1, and then treat them as elements of *F*_2. Let v = e_1 + e_2 + ... + e_n, and notice that v = (n-1, n-1, ..., n-1) (mod 2). When n is even, v = (1,1, ..., 1). In this case, noting that v-e_i = (0,0, ...,0, 1, 0, ..., 0), we see that the standard basis vectors lie in the span of the set {e_1, ..., e_n}. This implies that {e_1, ..., e_n} forms a basis of *F*_2^n, and therefore (1,1, ..., 1) is uniquely expressed as the *F*_2-linear combination e_1 + ... + e_n. Thus the minimum is 1 + ... + 1 = n. When n=4, we have the initial case. On the other hand, if n is odd, then v = e_1 + e_2 + ... + e_n = (0,0, ..., 0), which implies that the e_i are not linearly independent. Hence the above argument no longer applies. For this case, let us consider the linear map T: *F*_2^n --> *F*_2 given by T(a_1, ..., a_n) = a_1 + ... + a_n. Notice that T(e_i) = 0 for each i (since n is odd), hence every e_i lies in ker(T). But T(1, 1, ..., 1) = 1. This implies that (1, 1, ..., 1) is not in ker(T), hence is not in the span of {e_1, ..., e_n}. Therefore when n is odd, it is impossible to reach a state where all glasses are inverted.
@@VeryGoodDeals ker(T) is a subspace of *F*_2^n, since T is a linear map, and the kernel of a linear map between any two vector spaces is always a subspace of the domain. Because every e_i lies in ker(T), the span of the e_i must be a subset of ker(T), since span({e_i}) is by definition the smallest subspace containing the {e_i}.
I think the simplest solution for N glasses would be more like… Every two moves, the net number of glasses that have been flipped is either 0 or 2. So when N is even, it will take N/2 pairs of moves to flip N glasses, so N moves in total. It can’t be less than N if the number of moves is even, because the most the number of flipped glasses can increase each pair of moves is 2. If the number of moves is odd, and all glasses were flipped, then you could make one more move, and so have a set of paired moves where the total number of flips would need to be even, and that contradicts that you would have flipped the N glasses already . Therefore there can be no solution with an even number of moves.
I didn't watch the video yet, only saw the video thumbnail. I was able to do it in four steps: 1. Flip 3 cups, that are in up position. 2. Flip 1 cup that is in up position, and 2 cups that are in down position. 3. Flip 1 cup that is in up position, and 2 cups that are in down position. 4. Flip the three cups that are in up position.
@@Ruskettle I got even more confused but I decided to just try the steps with actual water bottles, I was able to understand hooray!!! I was mostly confused because I thought we had 3 turns TOTAL that's why 😭 but yeah I get it now
I found a rather fun (and in the end simple) way of solving this problem: In this problem, the order of operations does not matter because the final result we want to achieve (all glasses turned down) depends solely on the total number of flips each glass undergoes. Specifically: If a glass has been flipped an odd number of times, it will end up facing down. If a glass has been flipped an even number of times, it will remain facing up. This means that instead of tracking every individual flip, we only need to track the total number of flips for each glass. Let’s simplify further by introducing a new perspective: Tracking Flips Through Missed Flips: Suppose you have n glasses and perform k rounds of flipping. For each glass, define C_i as the number of times it is not flipped during the process, where i is the index of the glass (1 to n). Then: The total number of flips for a glass is given by k - C_i. To determine if a glass is facing down, we only care whether this total is odd. That is: If k - C_i is odd, the glass is down. If k - C_i is even, the glass is up. Summing the Missed Flips: The total number of rounds k is the same for all glasses, so we can express it as the sum of all C_i values. Let’s denote this sum as S = ∑ C_i (the sum of all missed flips). Then, for any glass i, its flip count can be rewritten as: k - C_i = S - C_i. To ensure all glasses are facing down, we require the flip count for every glass to be odd. This means we need to satisfy one of two conditions: Case 1: The sum S is even, and all C_i values are odd. Case 2: The sum S is odd, and all C_i values are even. In Case 1, for S (the sum of all missed flips) to be even, the number of odd C_i values must also be even (since the sum of odd numbers is even only if there is an even count of them). Therefore, n must be even. In Case 2, if all C_i values are even, their sum S would also be even. This contradicts the requirement that S is odd. Thus, Case 2 is impossible. From the analysis above, the only scenario where it is possible to flip all glasses down is when n is even. Therefore, n must be even to achieve the desired outcome. Finally, consider the minimum number of flips required. Since each glass must be flipped at least once (i.e., no glass can have C_i = 0, as this would leave the glass unflipped), the total number of turns is bounded below by n. Hence, the minimum number of turns required is n.
Curiously though, any human that could perform a similar task of superpowered pattern matching and prediction would be considered pretty damn intelligent.
So why are tasks that if I human did them they would be considered highly intelligent, are also evidence of a LLM not being intelligent when those same tasks are done by it?
@@SmoMo_ because we reason things out. LLMs literally just try to predict the next word over and over. If you ask it to explain how it arrived at an answer, the response will simply be, again, a series of words it's trained to predict as the most likely to be a response. It's why they're so prone to "lying" -- they have no concept of truth, they're just outputting the words that the model has been trained to predict as most likely to occur. Don't get me wrong, they're very impressive in their ability to fake intelligence. But they're not intelligent.
Nice question on parities and xors. If you encode glass up as a 0 and glass down as a 1, you are basically asking how to get 1111 from 0000 by xoring with only 0111,1110,1101 and 1011. Notice that there are only 4 and you need to use each one exactly once to get the result. If you use two sequences at any time, that would be a redundancy as they cancel. This can be generalized to any even n as well.
Saying this puzzle "stumps" ChatGPT or Google AI plays into the myth that these applications are capable of thought - they are not. They're using statistical modeling to choose words and phrases. Stop it.
How do you know *you* are capable of thought? What exactly is it? And how can you know that a logical "thought" process does not arise through the artificial neurons, just as it arises in our natural ones? No one knows that - both the brain and neural networks are black boxes.
Something that interests me is when you include a non-integer number of steps, and this would allow for solutions for odd numbers with a minimum of half of that odd number. (where in half a step you move half as many glasses) Example: (111), Step 1: (010), Step 1.5: (000). I know this is not actually how a "step" works, however I find it interesting that using this definition gives exactly half of the odd number as a minimum number of moves.
As a general rule, when mathematical explanation says "it can be easily shown" means a student can do it in a weekend. On the other hand, "it can be shown" means that a student may accomplish it in a couple of years of studies but sometimes it can refer to stuff like Fermat's Last Theorem where "it can be shown" took over 350 years of trial and error to finally accomplish the "can be shown" part.
This seemed suspiciously easy, so I was surprised to see it was actually correct: A sure-fire way to do is to just reverse the glasses in order, skipping back to the beginning when the end is reached. So first 1, 2 and 3. Then 4, 1 and 2, etcetera. That results in 4 moves. And that 4 is the correct answer can be easily checked mathematically: 4 glasses but you must move 3 at a time, that simply means you must find the lowest multiplication of 3 and 4 that are greater than 0 (unless all of them are already in the proper position, which isn't the case here) and are the same answer. In other words: 3 x 4 = 12 and vice-versa. Meaning that with 3 glasses each time, you need 4 moves.
The way I though about it is that for the glass to end upside down it needs to be inverted an odd number of times. Most likely the same number of times for each glass given the scenario. So the total inversions is going to be an odd multiple of the number of glasses. For an even number of glasses n-1 is odd, and the least common multiple is n(n-1) which will always be an odd multiple. For an odd number of glasses n-1 is even, so there will never be an odd multiple of n that matches with multiples of n-1.
It's even simpler than that: for every move, you flip n-1 cups, which means it's n-1modn cups flipped. When it'll be 0, it'll be the answer, and since n-1modn=-1modn, to get 0 mod n, or -nmodn, you'd have to make n moves.
@@cwldoc4958 You're right! The reason why it doesn't hold is the fact that if you have an odd number of non inverted cups and you flip an even number of them at a time, no matter how many moves you'll make it won't work. Simply put 2nmod3≠0 4nmod5≠0 for every n because 2n, 4n, 6n, etc. are 2k, while 3,5,7, etc. are 2k+1
I solved this problem by breaking it down into two problems: Instead of thinking of inverting n-1 glasses, think of it as two steps to be performed at each turn: 1. Invert only 1 glass in a turn 2. At the end of the turn invert all glasses Forgetting about step 2 for now, if you can invert only one glass at a time it is obvious that you need a minimum of n moves to invert all n glasses, regardless of n being even or odd. Now for step 2: Inverting all glasses an even number of times is equivalent to not inverting anything at all. This explains why it works for n when n is even: effectively only one inversion takes place from step 1 and zero inversions from step 2. Inverting all glasses an odd number of times is equivalent to inverting all the glasses just once. So if n is odd, you will have two effective inversions: one from step 1 and one from step 2, so in the end you'll have returned to the initial state. You cannot perform step 1 even number of times because there is an odd number of glasses.
In even number positions you always need as many moves as there are glasses: first move turn around all glasses except the most left one, next invert all glasses except the one right next to it, next turn around the glass right next to the last one and so on and so on. This way every glass will turn an odd number of times resilting in an inverted position. For an odd numbers of glasses i turned the glasses into zeroes and ones: 00000 is the starting position, 11111 the ending position. Since we have an odd number of glasses, we will have an even amount of moves so i will split the moves in pairs of 2. In the starting position we can see that the sum of all the zeroes is zero, an even number. The sum of the ending position will be an odd number (in the example from earlier: 5). Now we will look at what happens when we execute a pair of moves: There are generally 4 positions that can be made out of 2 glasses that have 2 states 00, 01, 10 and 11. Now we will look at the change of the sum if we invert these pairs: 00 -> 11 sum changed by 2, 01 -> 10 and 10 -> 01 sum changed by 0, 11 -> 00 sum changed by -2. Since we will change the sum by an even number, that means we can never reach an odd number as the sum. That was the most neat solution i came up with :) really enjoyed puzzling this stuff.
Nice ltl problem. There's a simpler solution (for me at least) whicch can be done w/o paper: The game is equivalent to inverting all glasses and then re-inverting 1 glass, which together counts as one move. This, in return, is equivalent to the following game: - Just invert 1 glass per move. -The game can be won in 2 ways: (A) after an odd number of moves, all glasses are normal OR (b) after an even number of moves, all glasses are inverted. For parity reasons, (a) is impossible to achieve, while (b) is possible exactly if n is even, with n trivial moves to make.
I did it similarly. Once you know that (a) is impossible, you can consider (b) as a sequence of 2 moves. 2 moves either flip all the same glasses (and are consequently useless), or they differ by 1 glass, the net result being flipping 2 glasses. Knowing that you can flip 0 or 2 glasses with 2 moves pretty easily shows the minimum is n moves
if 1 is 'up'd and 0 is 'down', and the set of indistinguishable glasses is not ordered then: 1. there are 4 equivalent 1st moves: 1111 -> 0001 2. there are 3 equivalent 2nd moves: 0001 -> 0110; and one move that reverts the 1st move: 0001-> 1111 3. there are two pairs of equivalent 3rd moves: flipping two 'up' and one 'down' glasses reverts the 2nd move, only option left is to flip any two 'down' and one 'up': 0110 -> 1011 4. last move is trivial: 1011 -> 0000 Either you perform at least one reverting move, or solve in 4 moves hence 4 moves is the minimum.
i just took an induction proofs course last semester, it was absolute hell, past me would never believe that i watched and solved another one of these devilish problems for fun.
Stop using AI prompts and pretending that it can answer questions. It is a waste of everyone's time as well as being a huge waste of natural resources.
I was not as interested in the general case where for n glasses, move n-1 glasses. But I was interested in the AI answers. What mistake of logic did the AI make that it couldn't figure this out? Presh proved it in a brute force way: he considered all possible moves and discarded the ones that did not take him closer to the goal. What elegance caused the AI to "hallucinate."
For the first question it is just the lights out game and the proof to that is nice. Then you gave the problem for N glasses flipping n-1 of them. That isn't the lights out problem but definitely similar. I liked the proof
I went with an inverted gray code where a link between two nodes exists if there's one glass in common. This gives a 4 dimensional cube and the shortest path between the starting point and the desired result can only be reached in 4 steps.
Proving there is no solution in the odd case is easy using modular arithmetic. To get the glasses flipped down, you must flip each glass 1 time modulo 2 (ie an odd number of flips). Since you must flip an odd number of glasses, the total number of flips is 1*1 = 1 modulo 2. On the other hand, each flip changes an even number of glasses. QED.
there's a much simpler solution: count glass flips. in total, you'd have a multiple of n-1 glass flips, because that's how many you flip at each moves, and you'd have a multiple of n, because there's n glasses. n and n - 1 being coprime, there's gonna be a minimum total of n(n-1) glass flips (the lowest common denominator or whatever it's called). since a move flips n-1 glasses, n move flips n(n-1) glasses, so n moves is the minimal amount. For numbers n that can or can't flip all glasses, count glass flips again. If there is a solution, then there is a solution that takes n(n--1) flips, we just proved that You can rearrange those flips in each moves as: flip all glasses, then "undo" one flip, to get your n-1 moves Now, a n move solution can be seen as flipping all glasses n times first, then dealing with the undoing of one flip. To get all glasses in the same up or down state, you have no choice but to spread those "undo" accross all glasses, meaning they all unflip once. Meaning in total, each glass flipped n-1 times. this means they're up if n-1 is even, so if n is odd, and down if n is even. so the solution actually only works when n is even.
this rests on the assumption that each glass will have the same number of flips in total (thus a multiple of n). But it doesn't exclude the option where one glass has 1 flip and another has 3, for example
First puzzle like this I got right away, including that n must be even, the minimum moves is n, and each glass must be turned exactly (n - 1) times after n moves. Since n - 1 is odd, each glass is now facing down. I didn't work out a proof that it's optimal in the general case. That was really elegant. I slept a lot last night.
There is an error in logic in this video. The answer is always N. This is the same logic as the tower of Hanoi and uses the same solving technique. In every case, because the difference is N-1, there will always be one less glass flipped then the total. Repeat this for all glasses, and all glasses will be flipped. We can model this by shifting the glass we leave untouched all the way across the number. This iterated step will take N moves every time. Whether the glasses are even or odd doesn't matter.
I think your answer can easily be proven wrong. For example, if we do a test to prove this answer, because n=1 cannot be done, we try with the next odd number, namely n=3. If it is repeated, after 2nd move, the glass can only return to the first move
@@brurydeardomartin1800 No, N=1 is trivially easy. You flip one glass and the glass is flipped. job done. You cannot flip 0 glasses because 0 is not a quantity. N must be a quantity or the question doesn't make sense. N = 2 you flip one glass, then you flip the other. That solves N = 2, and so on.
Each glass must be inverted at least 3 times, since if one glass is inverted only once, the other three will be in an infinite loop, and 2 inversions don’t put a glass upside down. If each glass is inverted 3 times, the least number of moves must be 4.
I missed the part where you invert n-1 glasses and solved for inverting 3 glasses. Here is the solution for that problem: 4 is a special case since it leaves little room for possible moves so it is 4 moves. But for all other cases, you want to make the amount of unflipped glasses to be divisible by 3. The first case is where it is already divisible by 3, so just divide n by 3 for minimum moves. If you have 1 extra glass, flip 3, then unflip 1 and flip 2, (4 are flipped now, which is 3+1) so in 2 moves you have reduced the problem to the first case, so divide n by 3 and round up. If you have 2 extra glasses, flip 3, then unflip 2 and flip 1 (2 are flipped now) and again in 2 moves you have reduced the problem to the first case, so divide n by 3 and round up but add 1.
there is a similar puzzle in the video game 'path of exile' to which the easy to remember answer is to 'click each pillar once' which translates in this case to avoid inverting any given glass each once
Another way to think why an odd number of glasses cannot all face down: - Represent a glass facing up as 1 and facing down as -1. Flipping a glass is like multiplying its state by -1. - The system state is the product of all glasses. Initially, for an odd number of glasses, the state is (1)^odd = 1. The goal is to flip all glasses face down, achieving a state of (-1)^odd = -1. - However, each step flips n - 1 glasses. Since n is odd, n - 1 is even, so flipping n - 1 glasses multiplies the state by (-1)^even = 1. - This means the system state always remains 1 after each step, and it is impossible to reach -1.
For n is an even number: -> n-1 is an odd number. Each cup needs to be flipped an odd number of times (NBoT). You can only flip (n-1) cup at a time so there’s aways 1 cup unflipped. Each cup can only remain unflipped once otherwise you repeat a previous step ( which makes it not the fastest solution ). If number of step (s) < n then there are away 2 cups: cup A get flipped (s) times and cup B get flipped (s-1) times, which can’t be true since between two numbers (s) and (s-1) there’s an even number. Each cup can only be flipped an odd number of times so s must be = n (each cup gets flipped exactly n-1 times).
For N where N is even, there's an easier way to show that N moves are required. Step 1: Show that the number of moves will always be an even number, using the same sort of parity argument used to show that an odd N is impossible. Step 2: Now that we know the number of moves will certainly be even, consider moves in pairs. A pair of moves can have only 2 outcomes. Either it leaves the pattern unchanged (because you did the same move twice, or exactly two glasses have been inverted, because all but two glasses were inverted and then inverted back. Obviously, to make two moves but leaving the pattern unchanged is just a waste of moves, so we need only consider the second choice. Step 3. In order to invert all the glasses, you need N/2 pairs of moves, or 2 * N/2 = N.
I got to step 2 and realized it’s so easy with the right insight. Every turn inverts all but 1 glass. 3 inversions will result in an inverted cup. So do 4 turns with each glass excluded. Order doesn’t matter. Each glass will get inverted 3 times. Done!
since 1 and n-1 are just opposites. you can select 1 cup to not flip. the sequence for solving is just selecting each cup in order from one end to the other to not be flipped. in the n is odd case. you can get everything but the last glass. and any other change is further away.
This was my technique as well. If the rule had been “flip one cup per move”, you would obviously just do that rule once for each cup. Based on parity, this is equivalent to your solution, basically “flip the complementary set of each cup”, which achieves the same end.
This one looks complicated but is so simple and easy it's almost insulting. for any even number 'n' glasses, when inverting (n-1) glasses per move, the minimum number to invert all glasses is always 'n' moves. this is because inverting (n-1) glasses always leaves 1 glass un-inverted, so inverting (n-1) glasses optimally will leave 1 more glass each move un-inverted, therefore after (n-1) moves there will be (n-1) glasses left to invert, allowing the final nth move to invert the remaining glasses. There is no solution for odd number 'n' because optimal moves will result in an even number of inverted glasses after each move. inverting an odd number of glasses plus one of the opposite orientation will still result in an even number inverted because one of the larger group will cancel one from the smaller group.
1) I have stopped the video to try myself and found a proof which does not require the case distingtion between an even and an odd number of glasses: Since the glasses are identical objects, there are only two possibilities in each move: (1) Invert all glasses with exception of an upright one (2) invert them with exception of an upside-down one. One of these two possibilities "reverts" the previous move, so if you want the minimum solution, there is only one "allowed" possibility in each move. Now you can prove - using induction - that if you have N glasses, the number of upside-down glasses (ni) after the i-th step is: n1=N-1, n2=2, n3=N-3, n4=4, n5=N-5, n6=6 ... For even values of N, the only element in this sequence having the value N is n(N), so you need N steps to invert all glasses. For odd values of N, the series contains only even values, so it does not contain the number N, so it is impossible to invert all glasses. 2) Have you heared about the cases when lawyers trusted fake cases invented by a KI? If yes, you surely were aware that the "proofs" made by a KI would be nonsense.
Define the following mapping: When the number of inverted glasses is even, replace each upright glass by 0 and each inverted glass by 1. If it is odd, replace each upright glass by 1 and each inverted glass by 0. Observe this mapping is bijective. Observe that inverting 3 glasses flips exactly the digit corresponding to the glass that was not inverted (we constructed it that way). Also, the initial configuration is 0000 and the final configuration is 1111. The minimum number of moves is their Hamming distance as each move flips exactly one digit. So the minimum number of moves is 4 and it is obtained by any sequence that omits each glass exactly once from inverting, so every glass is inverted exactly 3 times (corresponding to flipping each of the digits exactly once). Note that this works for any even n. For odd n, the task is actually impossible: every move then inverts an even number of glasses. But this means the number of inverted glasses always remains even.
Do the rules prevent you from flipping a single glass multiple times in each round? If so round 1 you could flip glass 1 upside down, then back up, then down addressing the 3 flips for the first round. Then round 2 flip glass 2, 3, & 4 so 2 rounds of moves?
The product of two adjacent positive integers is always an even number. This fact is at the core of this puzzle. Otherwise ChatGPT is not so bad, just you need to be patient with it. If it gives a wrong answer to the problem first, and you see the error in it, then you can educate it by pointing at the error and asking it to rethink.
Flipping all but one glass os equivalent to flipping one and then inverting all the glasses. in order for all the glasses to be upside-down, they must all be in the same state, and therefore the single flips must have been applies to all the glasses the same number of times, and thst number plus the number of inversions must be odd. If all glasses had been fliped 0 times, then nothing changes and they're upside-up, and flippings more than one are multiplying the total number of both flips and inversions by a constant, which is useless because parity is all that matters. Therefore, they must all be flipped once individually and and inverted together an even number of times. In order to flip n glasses individually once, you must do flipping n times, and that comes along with n inversions. If n is odd, then n+1 is even and everything is upside-up, but if n is even, n+1 is odd and you've done it in n steps.
For the 4-glass case, the proof that 4 moves is minimum is that for each move you must reach a state not equivalent to a previous state (number of glasses up and down). In practice this always only leaves one move available to proceed; there is only one way to reach the goal without back-tracking.
You did the prompt wrong in ChatGPT. I did that for 4 glasses with this prompt: I transformed that problem to having a binary number where a digit is 1 if the glass is inverted and 0 is standing normally: Imagine we are in a 4 bit space and have first 0000. A move is adding one of the elements of the set {1110, 1101, 1011, 0111}. Can you make with that the bits 1111? What moves do I need?
chatgpt can't do basic arithmetic without a chance of making errors so I wouldn't ask chatgpt for help with math or logic problems. and the reason for that is that chatgpt is it's basically an advanced text predictor. So when it appears to do math it's not actually doing any math but predicting text.
And in the even more general case, if you have n glasses and every move flips exactly k of them, then (spoiler alert) it's possible to flip all the glasses if and only if k2 and U
Step one can easily be checked, as the solution said: Without loss of generality, move one and two has to flip 1, 2, 3 and 2, 3, 4, respectively, to not end up in the starting position. After reaching this position, it is obviously not possible to have all glasses flipped after the third move. (This would be good enough for Olympiad standards, no need to tediously explain every possible move at every step)
Paused at 1:06. Not writing out a proof. I got 12 moves, counting each inversion as a move or 4 moves, counting each set of 3 as 1 move. The solution of n would be n(n-1) . Will edit if I'm wrong. I did not consider the case for odd numbers. I was too hasty.
Gee, this is easy! Four moves, three glasses per move, each glass is eventually turned three times: VVVV --{1}--> AAAV --{2}--> AVVA --{3}--> VAVV --{4}--> AAAA (At step {3}, we have essentially two choices: either [two Vs, one A] , or [two As, one V] . Since [two Vs, one A] is actually a reversal of step {2}, it doesn't help us forward; so the choice must naturally be [two As, one V] .)
My solution to the general case, before watching the rest of the video (Unfortunately, I did hear you say it is impossible for odd n before pausing): It is easier (for me) to visualise the parity by flipping the camera upside down each move. That way flipping all but 1 glass, looks like only flipping that glass. And solving the question looks like flipping all glasses DOWN after an even number of moves, or flipping all glasses UP after an odd number of moves. Doing that camera trick on the example with 4 glasses turns the solution at 5:50 into UUUU UUUD* UUDD UDDD* DDDD Here * is the odd-numbered moves. So from now on I am going to talk about only flipping 1 glass, and the goal is to have 0 glasses facing up after an even number of moves, or n facing up after an odd number of moves. For the general case, with this way of visualising things: you change 1 glass every move, so the parity of Up glasses flips (evenodd). So all even moves have the same parity as n, and all odd moves have the opposite parity as n. If we start with EVEN n glasses up at move 0, all odd moves will have an odd number of glasses up, so we can NEVER get EVEN n up after an odd-numbered move. However, all EVEN moves will have an EVEN number of glasses pointing up, so we CAN have 0 (which is even) glasses up after an even number of turns. This is possible: by flipping one glass every turn we do it in n turns which is even. We can not do it faster, since we need at least n turns to flip all glasses once. So even n can be solved in n turns at the fastest. the fastest we can do that is by flipping one glass each turn, which will take n moves. If we start with an odd number of glasses n UP, we will always have an ODD number on glasses after an EVEN number of turns, so we can NEVER have 0 (which is even) up. And on ODD numbered moves will have an EVEN number of glasses up, so we can NEVER have n (which is odd) glasses up. So we can not solve this in an odd or even number of moves, so odd n is impossible. AFTER WATCHING THE VIDEO My solution was not as rigorous, but I still think it works, it is likely the same as the real solution, from another point of view.
Pausing at @1:16 to give my solution and logic. I approach this from the viewpoint of "parity" each round we are changing the parity of the glasses. If we have swapped the parity an even number of times, then the parity is unchanged, if we swap it an odd number of times it is in the changed state. We want everything in the changed state. So the question is "What is the minimum number of times we need to change the parity of three out of four numbers so that all of their parity has been changed an odd number of times?" The answer is 4. Because the first move will always leave one untouched, the second will make at least two have an even number of changes, and the third will allow us to change at least one of those to the desired state. So lets look at it as adding 1 to a place. 0000 is our starting form, we add 1 to three places leaving us with 1110. We then add 1 to two of the 1s and the remaining 0 giving us 2211 we can then change the two ones and one two giving us 3222 then change the remaining 2s to 3333. And this strategy will work for ANY even numbered value of "n" we can use the first n-1 moves to change the parity such that we have 1 unit that has had its values changed an odd number of times, and then the nth move changes them all to have an odd number of changes. This strategy will NOT, however work for an odd numbered value of "n" as after "n" moves all units will have been changed an even number of times.
The case of n wine glasses: Starting with n wine glasses upright, inverting (n - 1) at a time, is it possible to reach a state in which all the glasses are upside down, and if so, what is the minimum number of inversions necessary to reach that state? Each inversion consists of inverting all the glasses except for one. In each inversion, the glass that is not inverted is either among the upright glasses or the upside-down glasses. Let f denote the act of inverting all the glasses except for one which is upright, and let g denote the act of inverting all glasses except for one which is upside down. Mathematically, let f(k) = the number of glasses that are upright after applying f to a state where k glasses are upright, for 1
I really liked your solution for showing that n is the minimum number of moves for even n. It was quite elegant. Mine was a little too messy to be worth posting. However, the way I showed that n could not be odd was as follows. Assume there is a solution for odd value of n, so that after m moves all glasses are facing down. For a glass to go from U(up) to D(down), it must be inverted an odd number of times. N_i = number of inversion for glass i T = Total number of inversions Adding all these inversions, we get: T = N_1 + N_2 + ... + N_n Since each of N_1, N_2, ... , N_n must be odd, and we have odd amount in the sum (since n is odd), and since the sum of an odd # of odd integers is odd, then we get T = odd But on each of the m moves we invert n-1 glasses, where n-1 is even. So we also get T = m(n-1) = even But T cannot be both odd and even. So our assumption (that a solution exists for odd n) must be false.
My intuition is telling me this: If Si is the inversion of all glasses but glass number i, and you repeat that action, it takes you back to a configuration equivalent to a previous configuration in the sequence of flips and thus will add steps to get closer to the solution, so the most efficient solution is to perform each Si once for each i, 1 to n. I fear it would take a long time to prove that.
Waaay back in first grade, we were taught (and made to understand why) then when it comes to Odd and Even numbers, if you add two from any category, the answer is Even. When you add two from different categories, the answer is Odd. We could help remember this because odd means weird and different in non-math context, so if we want an Odd answer, we need two different types of numbers. But Even is balanced and same-like, so any two numbers from the same category (O+O or E+E = E). For this puzzle, it follows that you can't make an Odd number if your only operands are Even. Q.E.D. for the case n=Odd. For the n=Even case, I know that it CAN be done in any case. One possible solution that works for every Even n is that you flip all but the first glass, then invert all but the second, and on down the line. It is not hard to show that this always works, and will always succeed in n moves (each glass is omitted exactly once, so moves=glasses). It is intuitive for me to see that this is also the minimum solution, but I do not know how to prove it rigorously. I'm watching the rest of the video now.
0.41 at first i just did for 4 glasses but as soon as you said case n I paused again and decided to try numbers up to 12 for f3 I got 1 obviously, 111 -> 000 f4 = 4, 1111 -> 0001 -> 0110 -> 1011 -> 0000 f5 = 3, 11111 -> 00011 -> 01101 -> 00000 f6 = 2, 111111 -> 000111 -> 000000 f7 = 3, 1111111 -> 0001111 -> 0010011 -> 000000 f8 = 4, 11111111 -> 00011111 -> 00000011 -> 00001101 -> 00000000 f9 = 3, 111111111 -> 000111111 -> 000000111 -> 000000000 f10 = 4, 1111111111 -> 0001111111 -> 0000001111 -> 0000010011 -> 0000000000 f11 = 5, 11111111111 -> 00011111111 -> 00000011111 -> 00000000011 -> 00000001101 -> 00000000000 f12 = 4, 111111111111 -> 000111111111 -> 000000111111 -> 000000000111 > 000000000000 One thing I knew from the start was that when n is a natural number >= 3 for fn if 3|n then fn = n/3 another thing I noticed for n ≠ 4 fn = floor(n/3) + n mod 3, as in you divide n by 3 and then add the remainder, oddly enough 4 is the only breaker of this quality and to prove there won't be another as you can see the last 5 digits always come down to 01111 00111 or 00011 with 00111 being solvable in 1 step and the others being solvable in 2, however with only 4 spaces f4 doesnt have enough room to solve in 2 steps, and since every other natural number being >= 3 is either divisible by 3 or >= to 5, 4 is the only one to follow this property.
My idea of the lowest possible solution was if the moves were divisible by 4. Because it's impossible to flip 4 glasses over if the total number of glasses you flipped was not divisible by 4. You can also think of the solution another way, since 3 glasses are flipped and 1 STAYS UPRIGHT. This problem is logically the same as if you were to flip 1 glass over at a time (which can be seen in the solution to the original problem).
1:00 mark guess. When n is even. Flip all glasses but the first. Flip all glasses but the second. Flip all glasses but the third. .... Flip all gasses but the nth. Each glass will have been flipped an odd number of times.
On a hunch, I tried this and it worked: Move #1: Flip all glasses except the first one. ( uuuu -> unnn ) Move #2: Flip all glasses except the second one. ( unnn -> nnuu ) Move #3: Flip all glasses except the third one. ( nnuu -> uuun ) Move #4: Flip all glasses except the fourth one. ( uuun -> nnnn )
Am I missing something here? How is there no solution if "n" is odd? If you have to turn 3 cups each move, then the minimum number of moves for odd "n" that are divisible by 3 is that number divided by 3. Isn't it? ie. 9 cups would take 3 moves, 15 = 5, 21 = 7 moves, and so on... Explain how I'm wrong please. Thanks.
Well, it's not in fact 3 out of n, but n-1 out of n glasses that need to be flipped. Meaning for 1 it's impossible as you wouldn't flip any glass and for any larger odd number you'd either get stuck in loop at some point or even go back to the start. For example for 3 I'm writing which glass doesn't get inverted each turn separated by commas… 3⃣,1⃣,1⃣/3⃣→stuck or 3⃣,1⃣,2⃣→loop/beginning For example with 5 I'm writing the actual orientation (arrowhead pointing towards opening)… move #0123(4) 🍷#1: ↑ ↓ ↑ ↓ (↑) 🍷#2: ↑ ↓ ↑ ↓ (↑) 🍷#3: ↑ ↓ ↑ ↓ (↑) 🍷#4: ↑ ↓ ↓ ↓ (↓) 🍷#5: ↑ ↑ ↓ ↑ (↓) …with turn #4 we either reach the upward position for all of the glasses again or return to move #2. Note that this cannot be avoided as move #1 is already the same as #3, meaning we've exhausted all unique moves there are. (Remember, the exact position of the untouched glass doesn't matter). Hope this helps. 😉
@@inudragoon2 No problem. Hope my explanation was straight to the point. Below the first paragraph[s] was just a demonstration. I think the proof is something along the lines of the number of minimum turns being equal to the number of glasses, but only an even number of turns nets a valid result; which thus is impossible for odd amounts. Could be wrong though. For example with two glasses you'd leave in place one after the other and with four or more always the next in line that was moved every previous turn.
if capital letters are upright and lower case letters are upside down, the solution can be described as such: (Putting in a paragraph break to hide spoilers...) *A B C D* = starting positions. *A b c d* = the first is untouched and remains upright (capitalized) while the other 3 are inverted (lowercase), A is A, B becomes b, C turns into c, and D becomes d. Now, you obviously cannot just flip the same lower case letters to uppercase, since that puts you back into your starting position, so break it up and try to flip two upright (capitalized) and two upside down (lowercase). *a B c D* = the first, second, and fourth are inverted (lowercased, capitalized, and capitalized) while the third remains the same (lowercase) A becomes a, b is B, c stays as c, and d becomes D ...At this point you have to move 3, but in order to get all 4 upside down, your next-to-last position needs just 1 to remain upside down, because your final move needs to be turning three that are right-side up to upside down. Except if you leave one upside-down, you'll end up with 3 upside down (lowercased) and one right side up (capitalized). That's the *opposite* of your next-to-last position! That's the exact same as the second positioning you made, after making your very first move! So what you *actually need* to do is leave one *right side up (capitalized)* and invert the others, like this: *A B C d* = you have kept B right side up as B, and inverted a to A, c to C, and D shrinks down to d...leaving you with 1 upside down (lowercase) and 3 right side up (capitalized)...which means your last step is exactly what you want: *a b c d* = by inverting A to a, B to b, and C to c, while leaving d as d. In the course of solving this puzzle, these cups have taken on on 5 different configurations, starting with all upright and ending in the result you wanted, all upside down within just 4 steps, moving only 3 cups at a time.
I like when he says" pause the video to give this problem a try,and when you are ready (to admit you can not solve it) watch the video to learn how to solve it"😅
![Noob To Max With DRAGON REWORK In Blox Fruits [FULL MOVIE]](http://i.ytimg.com/vi/LnBMOinoOvA/mqdefault.jpg)
Equivalently you can think this way: the glasses are automatically inversed and each time you choose one glass not to get inversed. Remark that for a glass to get inversed, it needs to get inversed odd times. Therefore, if you choose one glasses at a time for four inversions, every glass gets inversed three times and gets inversed!
Brilliant!
I was typing up my own independent comment on this before looking at yours and realizing that yep, that's basically how I solved it.
Yeah, which I think means the problem can only be solved if n is even.
Example in detail (order doesn't actually matter)
Starting uuuu
invert all but the first uddd
invert all but the second dduu
invert all but the third uuud
invert all but the forth dddd
Generalizing: The number of glasses equals the number of moves.
alternatively you can think about it as invertin one glass then and inverting up and down. to invert all glasses you need to have inverted all glasess and have up and down in the same way as in the begining
I got so excited when I solved it without looking at the video then immediately humbled when I saw the question was MUCH more complicated.
SAME :(
I'm just chuffed I could solve *something* on this channel
Yeah did it in 20 seconds but then saw I actually asked for more.
I did it in 4 moves intuitively and was satisfied when the proof supported my answer.
There is a solution that works for any number of glasses and requires only 0 inverting steps... you take all the glasses and carefully, without reverting any of them, travel to the exact opposite point of the Earth's surface. DISCLAIMER: doesn't work for flat earthers.
😅
that's called thinking out of the box and i personally love the dig at flat earthers too, 10/10 comment
Gotta love how people who don't understand Flat Earth Theory mock it 😂. Same as it ever was, sadly
Save the cost of the plane ticket and just wait 12 hours
@@MS-sv1tr You mean there are people that take Flat Earth Theory seriously?
move 0 (or just the starting position):0000
move 1:1110
move 2:1001
move 3:0010
move 4:1111
0=up-right
1=upsidedown
I got the exact same outcome in about a minute of thinking lol
same here, not really hard
and the general solution is:
step 1) invert all but glass 1
step 2) invert all but glass 2
...
step n) invert all but glass n
yeah it's not even a puzzle really is it? I mean, the first move whichever 3 you turn over you end up equivalent to 0000 to 1110, 3 of them will be upside down one the right way up. This is the same as 0000 to 0111 or 0000 to 1011 and so on. There's no puzzling about move 1 it's a given.
For your 2nd move. If you turn the same 3 back over, you'd just end up back at the start. So the only other choice is to turn 2 upside down back and the one you didn't touch on your first move upside down. So 1110 goes to 0011. So far we've done 2 moves and had no real choice over either of them.
Now we're in a position with 2 upright and 2 upside down. The only 2 moves are, turn 2 of the upright and 1 upside down, or 2 upside down and 1 upright . One of which 0011 goes to 1110 which is going backwards to a previous state. So we must go from 0011 to 1000. I'd accept that this move requires a bit of thought.
Our last move is now trivial. We just turn the 3 upright glasses upside down achieving our goal 1000 to 1111.
So, it's puzzle insofar as you had to do a bit of analysis for move 3. The other moves are either just obvious or they're the only moves you can make.
I did this with my fingers, different moves, but same amount, nice.
Edit: for those who want my moves
1: fingers up, 0: fingers down
1111 - start position
0010 - move 1
0101 - move 2
1011 - move 3
0000 - move 4 / final position
Funny, we did this in 4th grade in the 1990's in a game called "Math castle" but it was light-switches instead of glasses.
Every position is just a linear combination on Z/2Z of the 4 possible moves, since moves are commutative. The question is then "find the coefficients given the basis".
@@Horopter Z/2Z is the residual class ring to 2, so the natural numbers modulo 2; so all values are either 0 or 1 (normal or flipped); which glass you move first is irrelevant since you could just rearrange them
the important part here is that inverting glasses is basically adding +1 in the Z/2Z so 0+1 = 1 and 1+1 = 2 = 0
It's not obvious that the four moves form a basis though.
It takes two moves to reach a position where two of the glasses are upside down. This is a symmetrical situation which could be reached from either the initial position or the desired final position. That means the minimum number of moves is four.
It is even simpler
You have 4 glasses, but can only turn 3 of them each round.
To turn everything you must turn total number of glasses equal to number that is simultaneously divisible by 3 and 4. Smallest such number is 12. Meaning you will turn total 12 glasses, aka 4 rounds of 3 glasses.
If you turn 6 glasses you will get 6/4=1|2, aka 2 glasses in wrong position.
@@DimkaTsvno. you can do 8 and 6 with 3 moves, turning over a total of 18.
UUUUUUUU
UUDDDDDD
UDUUUUUD
DDDDDDDD
@@MichaelDarrow-tr1mn
Ok, in THAT case it was much easier.
In general rule is much more complicated and take in account unique combinations and even/odd nuances. Rule of smaller divisible will only work on unique combinations where difference between number of glasses and number of turning glasses is odd.
In case when difference between numbers is even, number of steps will ALWAYS be 3 [unless allowed to turn number is less than third of total]. (for example 9 to 7 or 9 to 5 or 9 to 3)
This task also will fail if number of total glasses is odd, but you can only turn even glasses at a time. Because even if you would be able to make difference in one or more glasses glass, you will always return them to upside glasses turn on each "odd" step, meaning you wouldn't be able to make it asymmetric. (for example 9 to 4, 9 to 6 and 9 to 8)
@@DimkaTsv Cool story. The explanation you replied to is 4 times shorter and infinitely easier 😂
@@MichaelDarrow-tr1mn On your second turn you inverted n-2 glasses. The condition was to invert n-1 glasses
The simples terms to think of this is, there is in each situation until the final move only one possible move that doesn’t recreate a previous situation
This is exactly how I thought of it. Aside from the first move, you always have two options in each move. One of those options makes you go backwards to the previous position, which obviously cannot be how you achieve the minimum number of moves.
It looks like a dynamic programming question. Good one!
copying my comment here for you as you are completely right!
this is a really great puzzle
I remember solving this when i was a teen - as part of comp sci A-lvl - its an example of heuristic hill climbing algorithm (an algorithm that looks ahead x steps to a better solution to find a final solution) - this sort of algorithm was used in early chess AI (and most modern AI pathing in modern video games)
Seems Im getting old though (now 45) because I couldn't for the life of me solve it now - and had to watch the vid. (yes it was the proof bit i struggled with, not mentally flipping glasses).
Interestingly its also the same problem(well very related) as the old board game 'mastermind' also the 'lights out' puzzle (a 2d version, rather than 1d) - something I used to happily solve in my head in fast time due to it being part of a puzzle in the video game Dungeons and dragons online as part of a raid.
yep.. DEFINITELY getting old, my brain has slowed down so much.
you are completely right!
I remember solving this when i was a teen - as part of comp sci A-lvl - its an example of heuristic hill climbing algorithm (an algorithm that looks ahead x steps to a better solution to find a final solution) - this sort of algorithm was used in early chess AI (and most modern AI pathing in modern video games)
Yes. N* (2**N) time complexity if we use dp, constant time complexity if we directly use odd even solution
Damn you are god damn right
Since glass position does not matter only the Up or Down positioning, this is a simple state model where the initial state is 4U0D and you want to get to 0U4D by changing a total 3 U to D or D to U each round. Sideways and backward state changes to prior states are not allowed. So it goes 4U0D, 1U3D, 2U2D, 3U1D, 0U4D .. done, 4 is the minimum possible with not duplications of states.
This elegance can be seen better if you swap the U and D after each step, as in the case of 6 or more cups.
Instead of - 6U0D, 1U5D, 4U2D, 3U3D, 2U4D, 5U1D, 0U6D
It would be - 6U0D, 5D1U, 4U2D, 3D3U, 2U4D, 1D5U, 0U6D
Using this, you can know the orientation of cups in any step for n cups.
x move for y cups
(y-x)DxU for all x that is odd
(y-x)UxD for all x that is even
ie.
53rd move for 80 cups = 27D53U
40th move for 90 cups = 50U40D
1: lemme fiddle with this
2: wait this might be impossible
3: lemme check by thinking about possible states
3.5: wait the state of the glasses only depends on the number of downs and ups
4: ah wait its not impossible
5: finds solution
6: yippie *clicks video*
I thought about this in terms of boolean algebras and got to the solution pretty quickly
Me too!
Didn't you get the answer is n whether n is even or odd..that doesn't seem to.hold up that with odd there areno solutions
I solved this using some advanced linear algebra:
Firstly, note the isomorphism between the state of the glasses and the *F*_2-vector space *F*_2^n: for a vector (a_1, ..., a_n) in *F*_2^n, the term a_i = 0 if the glass is not inverted, and 1 if it is. Applying the move "invert all but the i-th glass" is equivalent to adding the vector e_i := (1, 1, ..., 1, 0, 1, ..., 1), where only the i-th term is 0. Since the initial state of the glasses is the zero vector (0, ..., 0), we wish to find nonnegative integers c_1, ..., c_n such that c_1 e_1 + ... + c_n e_n = (1, 1, ..., 1). Taking the c_i modulo 2, and noting that we are after the minimum of c_1 + ... + c_n, we can assume that each c_i is either 0 or 1, and then treat them as elements of *F*_2.
Let v = e_1 + e_2 + ... + e_n, and notice that v = (n-1, n-1, ..., n-1) (mod 2). When n is even, v = (1,1, ..., 1). In this case, noting that v-e_i = (0,0, ...,0, 1, 0, ..., 0), we see that the standard basis vectors lie in the span of the set {e_1, ..., e_n}. This implies that {e_1, ..., e_n} forms a basis of *F*_2^n, and therefore (1,1, ..., 1) is uniquely expressed as the *F*_2-linear combination e_1 + ... + e_n. Thus the minimum is 1 + ... + 1 = n. When n=4, we have the initial case.
On the other hand, if n is odd, then v = e_1 + e_2 + ... + e_n = (0,0, ..., 0), which implies that the e_i are not linearly independent. Hence the above argument no longer applies. For this case, let us consider the linear map T: *F*_2^n --> *F*_2 given by T(a_1, ..., a_n) = a_1 + ... + a_n. Notice that T(e_i) = 0 for each i (since n is odd), hence every e_i lies in ker(T). But T(1, 1, ..., 1) = 1. This implies that (1, 1, ..., 1) is not in ker(T), hence is not in the span of {e_1, ..., e_n}. Therefore when n is odd, it is impossible to reach a state where all glasses are inverted.
I like your funny words magic man.
Dang u actually solve the problem in the most complicated way I've seen
At the end: why does T(1,1,1,...,1)=1 not being in ker(T) mean that (1,1,...,1) is not in the span of (e1,e2,...,en)?
Nice, but why in such a complicated way?
@@VeryGoodDeals ker(T) is a subspace of *F*_2^n, since T is a linear map, and the kernel of a linear map between any two vector spaces is always a subspace of the domain. Because every e_i lies in ker(T), the span of the e_i must be a subset of ker(T), since span({e_i}) is by definition the smallest subspace containing the {e_i}.
He sounds so proud when he proves it. I meant this in most sincere way!
I think the simplest solution for N glasses would be more like…
Every two moves, the net number of glasses that have been flipped is either 0 or 2.
So when N is even, it will take N/2 pairs of moves to flip N glasses, so N moves in total.
It can’t be less than N if the number of moves is even, because the most the number of flipped glasses can increase each pair of moves is 2.
If the number of moves is odd, and all glasses were flipped, then you could make one more move, and so have a set of paired moves where the total number of flips would need to be even, and that contradicts that you would have flipped the N glasses already . Therefore there can be no solution with an even number of moves.
I didn't watch the video yet, only saw the video thumbnail.
I was able to do it in four steps:
1. Flip 3 cups, that are in up position.
2. Flip 1 cup that is in up position, and 2 cups that are in down position.
3. Flip 1 cup that is in up position, and 2 cups that are in down position.
4. Flip the three cups that are in up position.
I don't really understand this
@@DoopenEvery time you flip you swap the left over cup for a cup that is the other way up.
@@Ruskettle I got even more confused but I decided to just try the steps with actual water bottles, I was able to understand hooray!!!
I was mostly confused because I thought we had 3 turns TOTAL that's why 😭 but yeah I get it now
I also have the habit of solving the thumbnails. Usually, the problem is nicely summarized there. Not it this case though :-)
Go figure language AI models aren't math AI tools. Who would have thunk it.
First time hearing “thunk” from a human being in genuine conversation
@@Axcyantol.😂
I found a rather fun (and in the end simple) way of solving this problem:
In this problem, the order of operations does not matter because the final result we want to achieve (all glasses turned down) depends solely on the total number of flips each glass undergoes. Specifically:
If a glass has been flipped an odd number of times, it will end up facing down.
If a glass has been flipped an even number of times, it will remain facing up.
This means that instead of tracking every individual flip, we only need to track the total number of flips for each glass. Let’s simplify further by introducing a new perspective:
Tracking Flips Through Missed Flips:
Suppose you have n glasses and perform k rounds of flipping. For each glass, define C_i as the number of times it is not flipped during the process, where i is the index of the glass (1 to n). Then:
The total number of flips for a glass is given by k - C_i.
To determine if a glass is facing down, we only care whether this total is odd. That is:
If k - C_i is odd, the glass is down.
If k - C_i is even, the glass is up.
Summing the Missed Flips:
The total number of rounds k is the same for all glasses, so we can express it as the sum of all C_i values. Let’s denote this sum as S = ∑ C_i (the sum of all missed flips). Then, for any glass i, its flip count can be rewritten as:
k - C_i = S - C_i.
To ensure all glasses are facing down, we require the flip count for every glass to be odd. This means we need to satisfy one of two conditions:
Case 1: The sum S is even, and all C_i values are odd.
Case 2: The sum S is odd, and all C_i values are even.
In Case 1, for S (the sum of all missed flips) to be even, the number of odd C_i values must also be even (since the sum of odd numbers is even only if there is an even count of them). Therefore, n must be even.
In Case 2, if all C_i values are even, their sum S would also be even. This contradicts the requirement that S is odd. Thus, Case 2 is impossible. From the analysis above, the only scenario where it is possible to flip all glasses down is when n is even. Therefore, n must be even to achieve the desired outcome.
Finally, consider the minimum number of flips required. Since each glass must be flipped at least once (i.e., no glass can have C_i = 0, as this would leave the glass unflipped), the total number of turns is bounded below by n. Hence, the minimum number of turns required is n.
Remember: LLMs being called intelligent is marketing hype. They're a superpowered autopredict, not intelligent.
Curiously though, any human that could perform a similar task of superpowered pattern matching and prediction would be considered pretty damn intelligent.
Just as, if you could do mental arithmetic, as fast and as accurately as a simple $1 calculator, you’d be considered a genius in mental arithmetic.
So why are tasks that if I human did them they would be considered highly intelligent, are also evidence of a LLM not being intelligent when those same tasks are done by it?
@@SmoMo_ because we reason things out. LLMs literally just try to predict the next word over and over. If you ask it to explain how it arrived at an answer, the response will simply be, again, a series of words it's trained to predict as the most likely to be a response.
It's why they're so prone to "lying" -- they have no concept of truth, they're just outputting the words that the model has been trained to predict as most likely to occur.
Don't get me wrong, they're very impressive in their ability to fake intelligence. But they're not intelligent.
@@phasm42 Artificial intelligence doesn't actually have to be intelligent to ruin your life. It just needs to convince your boss that it is.
Nice question on parities and xors. If you encode glass up as a 0 and glass down as a 1, you are basically asking how to get 1111 from 0000 by xoring with only 0111,1110,1101 and 1011. Notice that there are only 4 and you need to use each one exactly once to get the result. If you use two sequences at any time, that would be a redundancy as they cancel. This can be generalized to any even n as well.
That's how I did it as well.
Saying this puzzle "stumps" ChatGPT or Google AI plays into the myth that these applications are capable of thought - they are not. They're using statistical modeling to choose words and phrases. Stop it.
Yes they are a different version of the same search engine we had from 90s
@@ralanham76 they go back to an application called Niall from the Amiga era
How do you know *you* are capable of thought? What exactly is it? And how can you know that a logical "thought" process does not arise through the artificial neurons, just as it arises in our natural ones? No one knows that - both the brain and neural networks are black boxes.
@@thefirstuwu8874 👎
"Stop it."
Something that interests me is when you include a non-integer number of steps, and this would allow for solutions for odd numbers with a minimum of half of that odd number. (where in half a step you move half as many glasses) Example: (111), Step 1: (010), Step 1.5: (000). I know this is not actually how a "step" works, however I find it interesting that using this definition gives exactly half of the odd number as a minimum number of moves.
the little gray cells - best part of the vid
As a general rule, when mathematical explanation says "it can be easily shown" means a student can do it in a weekend. On the other hand, "it can be shown" means that a student may accomplish it in a couple of years of studies but sometimes it can refer to stuff like Fermat's Last Theorem where "it can be shown" took over 350 years of trial and error to finally accomplish the "can be shown" part.
I can hear Jean-Luc Picard now... "There are FOUR glasses!"
This seemed suspiciously easy, so I was surprised to see it was actually correct: A sure-fire way to do is to just reverse the glasses in order, skipping back to the beginning when the end is reached. So first 1, 2 and 3. Then 4, 1 and 2, etcetera. That results in 4 moves. And that 4 is the correct answer can be easily checked mathematically: 4 glasses but you must move 3 at a time, that simply means you must find the lowest multiplication of 3 and 4 that are greater than 0 (unless all of them are already in the proper position, which isn't the case here) and are the same answer. In other words: 3 x 4 = 12 and vice-versa. Meaning that with 3 glasses each time, you need 4 moves.
Just invert your face so all the glasses will be inverted by 0 moves
Your the god
Or flip your phone upsidedown
Tried that, but it still counted as a move.
@@a_Generic_User It's not a move from the glass's perspective as you never moved any of the glasses. It's in Einstein's Theory of Glass Relativity.
"Hey this is press Chalker" ahh captions 😭😭😭🙏
The way I though about it is that for the glass to end upside down it needs to be inverted an odd number of times. Most likely the same number of times for each glass given the scenario. So the total inversions is going to be an odd multiple of the number of glasses. For an even number of glasses n-1 is odd, and the least common multiple is n(n-1) which will always be an odd multiple. For an odd number of glasses n-1 is even, so there will never be an odd multiple of n that matches with multiples of n-1.
I don't really understand your logic here. n(n-1) will NEVER be odd, no matter what n is, since either n or n-1 has to be even.
@@holgerchristiansen4003
n(n-1) is even, but if n is even it is an odd multiple of n. That meaning it is n times an odd number.
a more general version of the original question: given m glasses, all upward initially, each time you choose n (n
It's even simpler than that: for every move, you flip n-1 cups, which means it's n-1modn cups flipped. When it'll be 0, it'll be the answer, and since n-1modn=-1modn, to get 0 mod n, or -nmodn, you'd have to make n moves.
Then why doesn't that hold for odd values of n?
@@cwldoc4958 You're right! The reason why it doesn't hold is the fact that if you have an odd number of non inverted cups and you flip an even number of them at a time, no matter how many moves you'll make it won't work. Simply put 2nmod3≠0 4nmod5≠0 for every n because 2n, 4n, 6n, etc. are 2k, while 3,5,7, etc. are 2k+1
I solved this problem by breaking it down into two problems:
Instead of thinking of inverting n-1 glasses, think of it as two steps to be performed at each turn:
1. Invert only 1 glass in a turn
2. At the end of the turn invert all glasses
Forgetting about step 2 for now, if you can invert only one glass at a time it is obvious that you need a minimum of n moves to invert all n glasses, regardless of n being even or odd.
Now for step 2:
Inverting all glasses an even number of times is equivalent to not inverting anything at all. This explains why it works for n when n is even: effectively only one inversion takes place from step 1 and zero inversions from step 2.
Inverting all glasses an odd number of times is equivalent to inverting all the glasses just once. So if n is odd, you will have two effective inversions: one from step 1 and one from step 2, so in the end you'll have returned to the initial state. You cannot perform step 1 even number of times because there is an odd number of glasses.
0, flip the paper upside down. Done.
In even number positions you always need as many moves as there are glasses: first move turn around all glasses except the most left one, next invert all glasses except the one right next to it, next turn around the glass right next to the last one and so on and so on. This way every glass will turn an odd number of times resilting in an inverted position.
For an odd numbers of glasses i turned the glasses into zeroes and ones: 00000 is the starting position, 11111 the ending position. Since we have an odd number of glasses, we will have an even amount of moves so i will split the moves in pairs of 2. In the starting position we can see that the sum of all the zeroes is zero, an even number. The sum of the ending position will be an odd number (in the example from earlier: 5).
Now we will look at what happens when we execute a pair of moves: There are generally 4 positions that can be made out of 2 glasses that have 2 states 00, 01, 10 and 11.
Now we will look at the change of the sum if we invert these pairs: 00 -> 11 sum changed by 2,
01 -> 10 and 10 -> 01 sum changed by 0,
11 -> 00 sum changed by -2.
Since we will change the sum by an even number, that means we can never reach an odd number as the sum.
That was the most neat solution i came up with :) really enjoyed puzzling this stuff.
Can't you just do lcm(3,4)÷3 to get 4?
Nice ltl problem. There's a simpler solution (for me at least) whicch can be done w/o paper:
The game is equivalent to inverting all glasses and then re-inverting 1 glass, which together counts as one move. This, in return, is equivalent to the following game:
- Just invert 1 glass per move.
-The game can be won in 2 ways:
(A) after an odd number of moves, all glasses are normal OR
(b) after an even number of moves, all glasses are inverted.
For parity reasons, (a) is impossible to achieve, while (b) is possible exactly if n is even, with n trivial moves to make.
I did it similarly. Once you know that (a) is impossible, you can consider (b) as a sequence of 2 moves. 2 moves either flip all the same glasses (and are consequently useless), or they differ by 1 glass, the net result being flipping 2 glasses. Knowing that you can flip 0 or 2 glasses with 2 moves pretty easily shows the minimum is n moves
Smash one of the glasses so there’s one less glass to worry about
It's quite obvious, inverting all but one is the EXACT same as inverting just one. Just with more complexity.
if 1 is 'up'd and 0 is 'down', and the set of indistinguishable glasses is not ordered then:
1. there are 4 equivalent 1st moves: 1111 -> 0001
2. there are 3 equivalent 2nd moves: 0001 -> 0110; and one move that reverts the 1st move: 0001-> 1111
3. there are two pairs of equivalent 3rd moves: flipping two 'up' and one 'down' glasses reverts the 2nd move, only option left is to flip any two 'down' and one 'up': 0110 -> 1011
4. last move is trivial: 1011 -> 0000
Either you perform at least one reverting move, or solve in 4 moves hence 4 moves is the minimum.
This looks like incrementing numbers in mod 2 and would be interesting to see what it would happen for other modules
i just took an induction proofs course last semester, it was absolute hell, past me would never believe that i watched and solved another one of these devilish problems for fun.
Stop using AI prompts and pretending that it can answer questions. It is a waste of everyone's time as well as being a huge waste of natural resources.
Lol, not the end of the world lad
Still better use of resources compared to most things on the internet.
I was not as interested in the general case where for n glasses, move n-1 glasses. But I was interested in the AI answers. What mistake of logic did the AI make that it couldn't figure this out? Presh proved it in a brute force way: he considered all possible moves and discarded the ones that did not take him closer to the goal. What elegance caused the AI to "hallucinate."
2:30 How do you turn 1 glass upside down in 1 move?
I don't see how that could be solved at all, as you only can invert 0 glasses each turn.
For the first question it is just the lights out game and the proof to that is nice. Then you gave the problem for N glasses flipping n-1 of them. That isn't the lights out problem but definitely similar. I liked the proof
I went with an inverted gray code where a link between two nodes exists if there's one glass in common. This gives a 4 dimensional cube and the shortest path between the starting point and the desired result can only be reached in 4 steps.
Proving there is no solution in the odd case is easy using modular arithmetic. To get the glasses flipped down, you must flip each glass 1 time modulo 2 (ie an odd number of flips). Since you must flip an odd number of glasses, the total number of flips is 1*1 = 1 modulo 2. On the other hand, each flip changes an even number of glasses. QED.
there's a much simpler solution: count glass flips.
in total, you'd have a multiple of n-1 glass flips, because that's how many you flip at each moves, and you'd have a multiple of n, because there's n glasses.
n and n - 1 being coprime, there's gonna be a minimum total of n(n-1) glass flips (the lowest common denominator or whatever it's called).
since a move flips n-1 glasses, n move flips n(n-1) glasses, so n moves is the minimal amount.
For numbers n that can or can't flip all glasses, count glass flips again.
If there is a solution, then there is a solution that takes n(n--1) flips, we just proved that
You can rearrange those flips in each moves as: flip all glasses, then "undo" one flip, to get your n-1 moves
Now, a n move solution can be seen as flipping all glasses n times first, then dealing with the undoing of one flip.
To get all glasses in the same up or down state, you have no choice but to spread those "undo" accross all glasses, meaning they all unflip once.
Meaning in total, each glass flipped n-1 times.
this means they're up if n-1 is even, so if n is odd, and down if n is even.
so the solution actually only works when n is even.
this rests on the assumption that each glass will have the same number of flips in total (thus a multiple of n). But it doesn't exclude the option where one glass has 1 flip and another has 3, for example
I was like "wait this is easy"without clicking on the vid till i realized,inverting the glasses counts as a move
First puzzle like this I got right away, including that n must be even, the minimum moves is n, and each glass must be turned exactly (n - 1) times after n moves. Since n - 1 is odd, each glass is now facing down. I didn't work out a proof that it's optimal in the general case. That was really elegant.
I slept a lot last night.
There is an error in logic in this video. The answer is always N. This is the same logic as the tower of Hanoi and uses the same solving technique. In every case, because the difference is N-1, there will always be one less glass flipped then the total. Repeat this for all glasses, and all glasses will be flipped. We can model this by shifting the glass we leave untouched all the way across the number. This iterated step will take N moves every time. Whether the glasses are even or odd doesn't matter.
I think your answer can easily be proven wrong. For example, if we do a test to prove this answer, because n=1 cannot be done, we try with the next odd number, namely n=3. If it is repeated, after 2nd move, the glass can only return to the first move
@@brurydeardomartin1800 No, N=1 is trivially easy. You flip one glass and the glass is flipped. job done. You cannot flip 0 glasses because 0 is not a quantity. N must be a quantity or the question doesn't make sense. N = 2 you flip one glass, then you flip the other. That solves N = 2, and so on.
@@rambysophistry1220 you do realize that we have to flip n-1 cup? And 1-1 isn't 1?
Took me about 10 seconds from the thumbnail alone 😅
I really like these kind of riddles/puzzles
Each glass must be inverted at least 3 times, since if one glass is inverted only once, the other three will be in an infinite loop, and 2 inversions don’t put a glass upside down.
If each glass is inverted 3 times, the least number of moves must be 4.
I missed the part where you invert n-1 glasses and solved for inverting 3 glasses. Here is the solution for that problem: 4 is a special case since it leaves little room for possible moves so it is 4 moves. But for all other cases, you want to make the amount of unflipped glasses to be divisible by 3. The first case is where it is already divisible by 3, so just divide n by 3 for minimum moves. If you have 1 extra glass, flip 3, then unflip 1 and flip 2, (4 are flipped now, which is 3+1) so in 2 moves you have reduced the problem to the first case, so divide n by 3 and round up. If you have 2 extra glasses, flip 3, then unflip 2 and flip 1 (2 are flipped now) and again in 2 moves you have reduced the problem to the first case, so divide n by 3 and round up but add 1.
there is a similar puzzle in the video game 'path of exile' to which the easy to remember answer is to 'click each pillar once' which translates in this case to avoid inverting any given glass each once
0 is up, 1 is down, this may not be optimal but before seeing solution this is my attempt
0. 0000
1. 0111
2. 0101
3. 1000
4. 1111
Another way to think why an odd number of glasses cannot all face down:
- Represent a glass facing up as 1 and facing down as -1. Flipping a glass is like multiplying its state by -1.
- The system state is the product of all glasses. Initially, for an odd number of glasses, the state is (1)^odd = 1. The goal is to flip all glasses face down, achieving a state of (-1)^odd = -1.
- However, each step flips n - 1 glasses. Since n is odd, n - 1 is even, so flipping n - 1 glasses multiplies the state by (-1)^even = 1.
- This means the system state always remains 1 after each step, and it is impossible to reach -1.
Great question and solution! 🔥💯
Isn't inverting three just the symmetry to inverting one ( + changing you point of view)?
2:42 the minimal glasses number is 2. You cannot have the case of 1 glass. It would mean that n=1 and you have to flip n-1 glasses in one move.
3:12 solution for 4 glasses
6:08 generalization
For n is an even number: -> n-1 is an odd number.
Each cup needs to be flipped an odd number of times (NBoT). You can only flip (n-1) cup at a time so there’s aways 1 cup unflipped.
Each cup can only remain unflipped once otherwise you repeat a previous step ( which makes it not the fastest solution ).
If number of step (s) < n then there are away 2 cups: cup A get flipped (s) times and cup B get flipped (s-1) times, which can’t be true since between two numbers (s) and (s-1) there’s an even number. Each cup can only be flipped an odd number of times so s must be = n (each cup gets flipped exactly n-1 times).
Aside from giving the wrong answer, Google Bard’s base case makes no sense because for one glass you are allowed to invert 0 glasses each turn.
Awesome .Thank you professor.
For N where N is even, there's an easier way to show that N moves are required.
Step 1: Show that the number of moves will always be an even number, using the same sort of parity argument used to show that an odd N is impossible.
Step 2: Now that we know the number of moves will certainly be even, consider moves in pairs. A pair of moves can have only 2 outcomes. Either it leaves the pattern unchanged (because you did the same move twice, or exactly two glasses have been inverted, because all but two glasses were inverted and then inverted back. Obviously, to make two moves but leaving the pattern unchanged is just a waste of moves, so we need only consider the second choice.
Step 3. In order to invert all the glasses, you need N/2 pairs of moves, or 2 * N/2 = N.
I got to step 2 and realized it’s so easy with the right insight. Every turn inverts all but 1 glass. 3 inversions will result in an inverted cup. So do 4 turns with each glass excluded. Order doesn’t matter. Each glass will get inverted 3 times. Done!
Thanks for making me feel smart! That was refreshingly easy
since 1 and n-1 are just opposites. you can select 1 cup to not flip. the sequence for solving is just selecting each cup in order from one end to the other to not be flipped. in the n is odd case. you can get everything but the last glass. and any other change is further away.
This was my technique as well.
If the rule had been “flip one cup per move”, you would obviously just do that rule once for each cup.
Based on parity, this is equivalent to your solution, basically “flip the complementary set of each cup”, which achieves the same end.
This one looks complicated but is so simple and easy it's almost insulting. for any even number 'n' glasses, when inverting (n-1) glasses per move, the minimum number to invert all glasses is always 'n' moves. this is because inverting (n-1) glasses always leaves 1 glass un-inverted, so inverting (n-1) glasses optimally will leave 1 more glass each move un-inverted, therefore after (n-1) moves there will be (n-1) glasses left to invert, allowing the final nth move to invert the remaining glasses. There is no solution for odd number 'n' because optimal moves will result in an even number of inverted glasses after each move. inverting an odd number of glasses plus one of the opposite orientation will still result in an even number inverted because one of the larger group will cancel one from the smaller group.
8:43 I may be missing something, but I think that you proved that Ui+Di is odd, not that Ui alone is odd.
1) I have stopped the video to try myself and found a proof which does not require the case distingtion between an even and an odd number of glasses:
Since the glasses are identical objects, there are only two possibilities in each move: (1) Invert all glasses with exception of an upright one (2) invert them with exception of an upside-down one.
One of these two possibilities "reverts" the previous move, so if you want the minimum solution, there is only one "allowed" possibility in each move.
Now you can prove - using induction - that if you have N glasses, the number of upside-down glasses (ni) after the i-th step is:
n1=N-1, n2=2, n3=N-3, n4=4, n5=N-5, n6=6 ...
For even values of N, the only element in this sequence having the value N is n(N), so you need N steps to invert all glasses.
For odd values of N, the series contains only even values, so it does not contain the number N, so it is impossible to invert all glasses.
2) Have you heared about the cases when lawyers trusted fake cases invented by a KI?
If yes, you surely were aware that the "proofs" made by a KI would be nonsense.
Define the following mapping:
When the number of inverted glasses is even, replace each upright glass by 0 and each inverted glass by 1. If it is odd, replace each upright glass by 1 and each inverted glass by 0. Observe this mapping is bijective. Observe that inverting 3 glasses flips exactly the digit corresponding to the glass that was not inverted (we constructed it that way). Also, the initial configuration is 0000 and the final configuration is 1111. The minimum number of moves is their Hamming distance as each move flips exactly one digit. So the minimum number of moves is 4 and it is obtained by any sequence that omits each glass exactly once from inverting, so every glass is inverted exactly 3 times (corresponding to flipping each of the digits exactly once).
Note that this works for any even n. For odd n, the task is actually impossible: every move then inverts an even number of glasses. But this means the number of inverted glasses always remains even.
Do the rules prevent you from flipping a single glass multiple times in each round? If so round 1 you could flip glass 1 upside down, then back up, then down addressing the 3 flips for the first round. Then round 2 flip glass 2, 3, & 4 so 2 rounds of moves?
The product of two adjacent positive integers is always an even number. This fact is at the core of this puzzle. Otherwise ChatGPT is not so bad, just you need to be patient with it. If it gives a wrong answer to the problem first, and you see the error in it, then you can educate it by pointing at the error and asking it to rethink.
Flipping all but one glass os equivalent to flipping one and then inverting all the glasses. in order for all the glasses to be upside-down, they must all be in the same state, and therefore the single flips must have been applies to all the glasses the same number of times, and thst number plus the number of inversions must be odd. If all glasses had been fliped 0 times, then nothing changes and they're upside-up, and flippings more than one are multiplying the total number of both flips and inversions by a constant, which is useless because parity is all that matters. Therefore, they must all be flipped once individually and and inverted together an even number of times. In order to flip n glasses individually once, you must do flipping n times, and that comes along with n inversions. If n is odd, then n+1 is even and everything is upside-up, but if n is even, n+1 is odd and you've done it in n steps.
For the 4-glass case, the proof that 4 moves is minimum is that for each move you must reach a state not equivalent to a previous state (number of glasses up and down). In practice this always only leaves one move available to proceed; there is only one way to reach the goal without back-tracking.
You did the prompt wrong in ChatGPT. I did that for 4 glasses with this prompt:
I transformed that problem to having a binary number where a digit is 1 if the glass is inverted and 0 is standing normally:
Imagine we are in a 4 bit space and have first 0000. A move is adding one of the elements of the set {1110, 1101, 1011, 0111}. Can you make with that the bits 1111? What moves do I need?
chatgpt can't do basic arithmetic without a chance of making errors so I wouldn't ask chatgpt for help with math or logic problems.
and the reason for that is that chatgpt is it's basically an advanced text predictor. So when it appears to do math it's not actually doing any math but predicting text.
And in the even more general case, if you have n glasses and every move flips exactly k of them, then (spoiler alert) it's possible to flip all the glasses if and only if k2 and U
Havent watched the video yet, but i did it in 4 steps.
0. XXXX (Starting Position)
1. YYYX
2. YXXY
3. XXYX
4. YYYY
Step one can easily be checked, as the solution said:
Without loss of generality, move one and two has to flip 1, 2, 3 and 2, 3, 4, respectively, to not end up in the starting position. After reaching this position, it is obviously not possible to have all glasses flipped after the third move.
(This would be good enough for Olympiad standards, no need to tediously explain every possible move at every step)
Interesting thing about odds, if the amt of glasses that need to be moved is oddN -2.. is the solution always 3 moves?
Paused at 1:06. Not writing out a proof. I got 12 moves, counting each inversion as a move or 4 moves, counting each set of 3 as 1 move. The solution of n would be n(n-1) . Will edit if I'm wrong.
I did not consider the case for odd numbers. I was too hasty.
Gee, this is easy!
Four moves, three glasses per move, each glass is eventually turned three times:
VVVV --{1}--> AAAV --{2}--> AVVA --{3}--> VAVV --{4}--> AAAA
(At step {3}, we have essentially two choices: either [two Vs, one A] , or [two As, one V] . Since [two Vs, one A] is actually a reversal of step {2}, it doesn't help us forward; so the choice must naturally be [two As, one V] .)
My solution to the general case, before watching the rest of the video (Unfortunately, I did hear you say it is impossible for odd n before pausing):
It is easier (for me) to visualise the parity by flipping the camera upside down each move. That way flipping all but 1 glass, looks like only flipping that glass.
And solving the question looks like flipping all glasses DOWN after an even number of moves, or flipping all glasses UP after an odd number of moves.
Doing that camera trick on the example with 4 glasses turns the solution at 5:50 into
UUUU
UUUD*
UUDD
UDDD*
DDDD
Here * is the odd-numbered moves.
So from now on I am going to talk about only flipping 1 glass, and the goal is to have 0 glasses facing up after an even number of moves, or n facing up after an odd number of moves.
For the general case, with this way of visualising things: you change 1 glass every move, so the parity of Up glasses flips (evenodd).
So all even moves have the same parity as n, and all odd moves have the opposite parity as n.
If we start with EVEN n glasses up at move 0, all odd moves will have an odd number of glasses up, so we can NEVER get EVEN n up after an odd-numbered move.
However, all EVEN moves will have an EVEN number of glasses pointing up, so we CAN have 0 (which is even) glasses up after an even number of turns.
This is possible: by flipping one glass every turn we do it in n turns which is even.
We can not do it faster, since we need at least n turns to flip all glasses once.
So even n can be solved in n turns at the fastest.
the fastest we can do that is by flipping one glass each turn, which will take n moves.
If we start with an odd number of glasses n UP, we will always have an ODD number on glasses after an EVEN number of turns, so we can NEVER have 0 (which is even) up.
And on ODD numbered moves will have an EVEN number of glasses up, so we can NEVER have n (which is odd) glasses up.
So we can not solve this in an odd or even number of moves, so odd n is impossible.
AFTER WATCHING THE VIDEO
My solution was not as rigorous, but I still think it works, it is likely the same as the real solution, from another point of view.
Pausing at @1:16 to give my solution and logic. I approach this from the viewpoint of "parity" each round we are changing the parity of the glasses. If we have swapped the parity an even number of times, then the parity is unchanged, if we swap it an odd number of times it is in the changed state. We want everything in the changed state. So the question is "What is the minimum number of times we need to change the parity of three out of four numbers so that all of their parity has been changed an odd number of times?" The answer is 4. Because the first move will always leave one untouched, the second will make at least two have an even number of changes, and the third will allow us to change at least one of those to the desired state. So lets look at it as adding 1 to a place. 0000 is our starting form, we add 1 to three places leaving us with 1110. We then add 1 to two of the 1s and the remaining 0 giving us 2211 we can then change the two ones and one two giving us 3222 then change the remaining 2s to 3333.
And this strategy will work for ANY even numbered value of "n" we can use the first n-1 moves to change the parity such that we have 1 unit that has had its values changed an odd number of times, and then the nth move changes them all to have an odd number of changes.
This strategy will NOT, however work for an odd numbered value of "n" as after "n" moves all units will have been changed an even number of times.
Would it be correct in saying that it takes as many moves as there are glasses?
I did it in one move, I just wore 3 pairs of glasses upside down. Now everything is inverted.. please help!
The case of n wine glasses: Starting with n wine glasses upright, inverting (n - 1) at a time, is it possible to reach a state in which all the glasses are upside down, and if so, what is the minimum number of inversions necessary to reach that state?
Each inversion consists of inverting all the glasses except for one. In each inversion, the glass that is not inverted is either among the upright glasses or the upside-down glasses. Let f denote the act of inverting all the glasses except for one which is upright, and let g denote the act of inverting all glasses except for one which is upside down.
Mathematically, let f(k) = the number of glasses that are upright after applying f to a state where k glasses are upright, for 1
I really liked your solution for showing that n is the minimum number of moves for even n. It was quite elegant.
Mine was a little too messy to be worth posting.
However, the way I showed that n could not be odd was as follows.
Assume there is a solution for odd value of n, so that after m moves all glasses are facing down.
For a glass to go from U(up) to D(down), it must be inverted an odd number of times.
N_i = number of inversion for glass i
T = Total number of inversions
Adding all these inversions, we get:
T = N_1 + N_2 + ... + N_n
Since each of N_1, N_2, ... , N_n must be odd, and we have odd amount in the sum (since n is odd),
and since the sum of an odd # of odd integers is odd, then we get
T = odd
But on each of the m moves we invert n-1 glasses, where n-1 is even. So we also get
T = m(n-1) = even
But T cannot be both odd and even. So our assumption (that a solution exists for odd n) must be false.
My intuition is telling me this: If Si is the inversion of all glasses but glass number i, and you repeat that action, it takes you back to a configuration equivalent to a previous configuration in the sequence of flips and thus will add steps to get closer to the solution, so the most efficient solution is to perform each Si once for each i, 1 to n. I fear it would take a long time to prove that.
Waaay back in first grade, we were taught (and made to understand why) then when it comes to Odd and Even numbers, if you add two from any category, the answer is Even. When you add two from different categories, the answer is Odd. We could help remember this because odd means weird and different in non-math context, so if we want an Odd answer, we need two different types of numbers. But Even is balanced and same-like, so any two numbers from the same category (O+O or E+E = E). For this puzzle, it follows that you can't make an Odd number if your only operands are Even. Q.E.D. for the case n=Odd.
For the n=Even case, I know that it CAN be done in any case. One possible solution that works for every Even n is that you flip all but the first glass, then invert all but the second, and on down the line. It is not hard to show that this always works, and will always succeed in n moves (each glass is omitted exactly once, so moves=glasses). It is intuitive for me to see that this is also the minimum solution, but I do not know how to prove it rigorously. I'm watching the rest of the video now.
0.41 at first i just did for 4 glasses but as soon as you said case n I paused again and decided to try numbers up to 12
for f3 I got 1 obviously, 111 -> 000
f4 = 4, 1111 -> 0001 -> 0110 -> 1011 -> 0000
f5 = 3, 11111 -> 00011 -> 01101 -> 00000
f6 = 2, 111111 -> 000111 -> 000000
f7 = 3, 1111111 -> 0001111 -> 0010011 -> 000000
f8 = 4, 11111111 -> 00011111 -> 00000011 -> 00001101 -> 00000000
f9 = 3, 111111111 -> 000111111 -> 000000111 -> 000000000
f10 = 4, 1111111111 -> 0001111111 -> 0000001111 -> 0000010011 -> 0000000000
f11 = 5, 11111111111 -> 00011111111 -> 00000011111 -> 00000000011 -> 00000001101 -> 00000000000
f12 = 4, 111111111111 -> 000111111111 -> 000000111111 -> 000000000111 > 000000000000
One thing I knew from the start was that when n is a natural number >= 3 for fn if 3|n then fn = n/3 another thing I noticed for n ≠ 4 fn = floor(n/3) + n mod 3, as in you divide n by 3 and then add the remainder,
oddly enough 4 is the only breaker of this quality
and to prove there won't be another as you can see the last 5 digits always come down to 01111 00111 or 00011 with 00111 being solvable in 1 step and the others being solvable in 2, however with only 4 spaces f4 doesnt have enough room to solve in 2 steps, and since every other natural number being >= 3 is either divisible by 3 or >= to 5, 4 is the only one to follow this property.
I didn't do what he meant by doing different n, but I think my discovery is cool anyways
My idea of the lowest possible solution was if the moves were divisible by 4. Because it's impossible to flip 4 glasses over if the total number of glasses you flipped was not divisible by 4.
You can also think of the solution another way, since 3 glasses are flipped and 1 STAYS UPRIGHT. This problem is logically the same as if you were to flip 1 glass over at a time (which can be seen in the solution to the original problem).
n if n is even, impossible if n is odd. Claude 3 gets there without help, but it takes a couple attempts to get it right.
1:00 mark guess.
When n is even.
Flip all glasses but the first.
Flip all glasses but the second.
Flip all glasses but the third.
....
Flip all gasses but the nth.
Each glass will have been flipped an odd number of times.
On a hunch, I tried this and it worked:
Move #1: Flip all glasses except the first one. ( uuuu -> unnn )
Move #2: Flip all glasses except the second one. ( unnn -> nnuu )
Move #3: Flip all glasses except the third one. ( nnuu -> uuun )
Move #4: Flip all glasses except the fourth one. ( uuun -> nnnn )
Am I missing something here? How is there no solution if "n" is odd? If you have to turn 3 cups each move, then the minimum number of moves for odd "n" that are divisible by 3 is that number divided by 3. Isn't it?
ie. 9 cups would take 3 moves, 15 = 5, 21 = 7 moves, and so on...
Explain how I'm wrong please. Thanks.
Well, it's not in fact 3 out of n, but n-1 out of n glasses that need to be flipped.
Meaning for 1 it's impossible as you wouldn't flip any glass and for any larger odd number you'd either get stuck in loop at some point or even go back to the start.
For example for 3 I'm writing which glass doesn't get inverted each turn separated by commas…
3⃣,1⃣,1⃣/3⃣→stuck
or
3⃣,1⃣,2⃣→loop/beginning
For example with 5 I'm writing the actual orientation (arrowhead pointing towards opening)…
move #0123(4)
🍷#1: ↑ ↓ ↑ ↓ (↑)
🍷#2: ↑ ↓ ↑ ↓ (↑)
🍷#3: ↑ ↓ ↑ ↓ (↑)
🍷#4: ↑ ↓ ↓ ↓ (↓)
🍷#5: ↑ ↑ ↓ ↑ (↓)
…with turn #4 we either reach the upward position for all of the glasses again or return to move #2. Note that this cannot be avoided as move #1 is already the same as #3, meaning we've exhausted all unique moves there are.
(Remember, the exact position of the untouched glass doesn't matter).
Hope this helps. 😉
Ooooh, I totally missed the part for "n" glasses you're supposed to flip "n"-1 glasses, instead of 3 across all "n"
Thank you!
@@inudragoon2 No problem. Hope my explanation was straight to the point. Below the first paragraph[s] was just a demonstration.
I think the proof is something along the lines of the number of minimum turns being equal to the number of glasses, but only an even number of turns nets a valid result; which thus is impossible for odd amounts. Could be wrong though.
For example with two glasses you'd leave in place one after the other and with four or more always the next in line that was moved every previous turn.
if capital letters are upright and lower case letters are upside down, the solution can be described as such:
(Putting in a paragraph break to hide spoilers...)
*A B C D* = starting positions.
*A b c d* = the first is untouched and remains upright (capitalized) while the other 3 are inverted (lowercase), A is A, B becomes b, C turns into c, and D becomes d. Now, you obviously cannot just flip the same lower case letters to uppercase, since that puts you back into your starting position, so break it up and try to flip two upright (capitalized) and two upside down (lowercase).
*a B c D* = the first, second, and fourth are inverted (lowercased, capitalized, and capitalized) while the third remains the same (lowercase) A becomes a, b is B, c stays as c, and d becomes D
...At this point you have to move 3, but in order to get all 4 upside down, your next-to-last position needs just 1 to remain upside down, because your final move needs to be turning three that are right-side up to upside down.
Except if you leave one upside-down, you'll end up with 3 upside down (lowercased) and one right side up (capitalized). That's the *opposite* of your next-to-last position! That's the exact same as the second positioning you made, after making your very first move!
So what you *actually need* to do is leave one *right side up (capitalized)* and invert the others, like this:
*A B C d* = you have kept B right side up as B, and inverted a to A, c to C, and D shrinks down to d...leaving you with 1 upside down (lowercase) and 3 right side up (capitalized)...which means your last step is exactly what you want:
*a b c d* = by inverting A to a, B to b, and C to c, while leaving d as d.
In the course of solving this puzzle, these cups have taken on on 5 different configurations, starting with all upright and ending in the result you wanted, all upside down within just 4 steps, moving only 3 cups at a time.
I like when he says" pause the video to give this problem a try,and when you are ready (to admit you can not solve it) watch the video to learn how to solve it"😅