This logic puzzle stumped ChatGPT. Can you solve it?
Vložit
- čas přidán 10. 05. 2024
- The world's best AI cannot solve this simple question! Can you figure it out? Four glasses are in a row face up. What's the minimum number of moves to make them down, if you have to invert 3 glasses at a time? What if you have n glasses and you have to invert n - 1 glasses at a time? Special thanks this month to: Mike Robertson, Daniel Lewis, Kyle, Lee Redden. Thanks to all supporters on Patreon! / mindyourdecisions
0:00 problems
1:23 solution
6:08 general 1
10:49 general 2
UKMT
/ 1698954285327712365
Puzzling StackExchange solution by Caleb Stanford
puzzling.stackexchange.com/qu...
Subscribe: czcams.com/users/MindYour...
Send me suggestions by email (address at end of many videos). I may not reply but I do consider all ideas!
If you purchase through these links, I may be compensated for purchases made on Amazon. As an Amazon Associate I earn from qualifying purchases. This does not affect the price you pay.
If you purchase through these links, I may be compensated for purchases made on Amazon. As an Amazon Associate I earn from qualifying purchases. This does not affect the price you pay.
Book ratings are from January 2023.
My Books (worldwide links)
mindyourdecisions.com/blog/my...
My Books (US links)
Mind Your Decisions: Five Book Compilation
amzn.to/2pbJ4wR
A collection of 5 books:
"The Joy of Game Theory" rated 4.3/5 stars on 290 reviews
amzn.to/1uQvA20
"The Irrationality Illusion: How To Make Smart Decisions And Overcome Bias" rated 4.1/5 stars on 33 reviews
amzn.to/1o3FaAg
"40 Paradoxes in Logic, Probability, and Game Theory" rated 4.2/5 stars on 54 reviews
amzn.to/1LOCI4U
"The Best Mental Math Tricks" rated 4.3/5 stars on 116 reviews
amzn.to/18maAdo
"Multiply Numbers By Drawing Lines" rated 4.4/5 stars on 37 reviews
amzn.to/XRm7M4
Mind Your Puzzles: Collection Of Volumes 1 To 3
amzn.to/2mMdrJr
A collection of 3 books:
"Math Puzzles Volume 1" rated 4.4/5 stars on 112 reviews
amzn.to/1GhUUSH
"Math Puzzles Volume 2" rated 4.2/5 stars on 33 reviews
amzn.to/1NKbyCs
"Math Puzzles Volume 3" rated 4.2/5 stars on 29 reviews
amzn.to/1NKbGlp
2017 Shorty Awards Nominee. Mind Your Decisions was nominated in the STEM category (Science, Technology, Engineering, and Math) along with eventual winner Bill Nye; finalists Adam Savage, Dr. Sandra Lee, Simone Giertz, Tim Peake, Unbox Therapy; and other nominees Elon Musk, Gizmoslip, Hope Jahren, Life Noggin, and Nerdwriter.
My Blog
mindyourdecisions.com/blog/
Twitter
/ preshtalwalkar
Instagram
/ preshtalwalkar
Merch
teespring.com/stores/mind-you...
Patreon
/ mindyourdecisions
Press
mindyourdecisions.com/blog/press - Věda a technologie
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?
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.
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
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)
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.
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.
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.
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.
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
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 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.
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
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?
@@verygooddeal4436 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}.
a more general version of the original question: given m glasses, all upward initially, each time you choose n (n
Great question and solution! 🔥💯
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.
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.
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
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
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.
the little gray cells - best part of the vid
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.
He sounds so proud when he proves it. I meant this in most sincere way!
Took me about 10 seconds from the thumbnail alone 😅
I really like these kind of riddles/puzzles
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
for the purposes of notation, lets encode the glasses as a 1 if it is right side up and 0 if it is upside down, as such, the 4 glasses can be encoded as (1111)
for the 4 glasses, for all 4 glasses to end up flipped that means every glass must be flipped an odd number of times, therefore the total number of times a glass is flipped must be some odd number multiplied by 4.
we also know that in each move exactly 3 glasses are flipped, so for m moves we have 3m flips, and this must equal a (k+1)*4 total number of flips, therefore:
3m=(2k+1)*4
m=(2k+1)*4/3
lets test inserting some small odd numbers into the (2k+1) part of this equation.
k=0 : m=4/3 m needs to be a whole number so this isn't a solution.
k=1 : m=4
thus, the smallest number of moves we can make that theoretically could produce a solution is 4 moves. is there such a solution?
yes, as such:
1111
flip all except the 1st
1000
flip all except the 2nd
0011
flip all except the 3rd
1110
flip all except the 4th
0000
done.
thus we have proven a solution for 4 moves and we have shown that no shorter solution exists.
now, how about the general case? we have n glasses and we flip n-1 glasses each time.
obviously it's impossible for 1 glass, since each move flips 0 glasses, so the state of the board so to speak never changes.
obviously it is possible for 2 glasses, since each move flips 1 glass, just flip each glass in it's own move.
for 3 glasses it's slightly more tricky but still easy to see that we need to make, in total, an odd number of flips, but each move makes an even number of flips, so we can never get an odd total number of flips and it is therefore impossible. this logic can be extended to all odd number of glasses and they are therefore all impossible.
for even numbers of glasses we can always trivially do it by making n moves: for each glass, make a move that flips all except for that glass. this strategy always solves for an even number of glasses because every glass gets flipped once for every other glass, and since there is an odd number of "other glasses", every glass gets flipped an odd number of times.
but can we do better?
lets explore what the minimum number of moves needs to be similarly to what we did for 4 glasses, our new and more general equation is (where 2n is our even number of glasses):
(2n-1)*m = (2k+1)*2n
m = (2k+1)*2n/(2n-1)
2n/(2n-1) is an interesting fraction. by definition x and x-1 are co-prime, therefore 2n and 2n-1 are also co-prime, this tells us that the fraction 2n/(2n-1) is as simplified as it gets.
therefore (2k+1)*2n/(2n-1) is only ever a whole number if (2k+1)/(2n-1) is a whole number. the smallest whole number that this can make is 1, when k=n-1, and what does that get us?
substitute k=n-1
m = (2(n-1)+1)*2n/(2n-1)
m = (2n-2+1)*2n/(2n-1)
m = (2n-1)*2n/(2n-1)
m = 2n
and since 2n was what we defined as our even number of glasses, we have now proven that the minimum number of moves is the same as the number of glasses, and we have already proposed a strategy for how to solve even-numbered glass puzzles with that number of moves, therefore we have completed the general puzzle.
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 can hear Jean-Luc Picard now... "There are FOUR glasses!"
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
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.
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).
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.
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
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.
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.
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] .)
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.
Each 3flip is two moves A & B: (A) is just inverting all 4, (B) flipping any 1 cup.
The (A) just toggles the cups and at the end of any even turn, the (A) moves have you back to your original state.
Therefore the (B) moves have to flip all 4 cups upside down, which we can simply do going left to right.
UUUU (all up)
1- (A): invert: DDDD
(B): flip 1st: UDDD
2- (A): invert: DUUU
(B): flip 2nd: DDUU
3- (A): invert: UUDD
(B): flip 3rd: UUUD
4- (A): invert: DDDU
(B): flip 4th: DDDD
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.
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.
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.
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.
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.
Awesome .Thank you professor.
It can be proven a bit quicker and simpler.
First consider each step a combination of two transformations. One flips every glass, the other flips one glass.
If there is an even number of glasses n, each step is an odd number of flips.
Having all flipped (an even total number of flips) you need an even number of steps.
If n is even the transformations of flipping all glasses cancel out, simplifying the problem to a transformation of a single flip
So you need to flip n glasses, one at a time. Not flipping the same glass twice results in the minimum of n steps.
For n is odd you have a problem.
Using an even number of steps you have the same cancelling but can only flip an even number of glasses.
Using an odd number of steps you have one flip all part that doesn't cancel out. In addition you have an odd number of flips and flips back so you can't make them cancel out.
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)
With 4 glasses, there are potentially 16 different configurations of right side up and upside down. Not only can you achieve all inverted, you can in fact achieve ANY desired configuration of up and down glasses -- all 16 configurations are reachable by flipping glasses 3 at a time.
Assume the glasses are numbered 1 to 4, and assume U represents a right-side-up glass, and A represents an upside down glass.
Step 1, UUUU, flip 1, 3, and 4, --> AUAA
Step 2, AUAA, flip 1, 2, and 4, --> UAAU
Step 3, UAAU, flip 1, 2, and 3, --> AUUU
Step 4, AUUU, flip 2, 3, and 4, --> AAAA
All glasses inverted. This works because each individual glass has now been flipped 3 times, which leaves the glass in the opposite configuration that it was in at the beginning.
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."
The way i thought of it is rather simple.
Inverting all but one glass is the same as only inverting one glass. The minimum number of moves to get all glasses facing down while only inverting one at a time is exactly N.
Therefore, the answer is always N.
For the n being even case:
Given that there are exactly N flips, each glass is flipped n-1 times.
The only way to go from up to down is flipping an odd number of times, so if N is even, then n-1 is odd and it works! If N is odd, then n-1 is even, making it impossible, since N is _guarranteed_ to be the minimum if it exists.
Interesting thing about odds, if the amt of glasses that need to be moved is oddN -2.. is the solution always 3 moves?
You can simplify the problem as how many glasses turn every 2 moves and that is always true whatever glasses you choose.
So for even numbers it is easy. You end up with 2 after 2 moves, 4 after 4 moves and n after n moves.
For odd number you always turn even number of glasses. Which ensures alway an odd number of glasses remain up no matter what. Since 0 is even (you need to get to 0 glasses up) it is impossible to get there
1 = Correct way up
0 = Upside down
1111
0001
0110
1101
0000
Essentially if you sort it correctly it is a binary sequence that terminates a 0. But only for even numbers; Sequences and series is always really tough to work out for me.
Then using the same notation, a demonstration of the simplest odd case, illustrating its impossibility:
111
100
010 or 111, so therefore impossible. Other odd numbers would presumably get to the same stage within a few more steps
And of course the simplest even case:
11
10
00
@@mittfh Nice! really good way of putting it for the impossibility!
To be lazy, instead of flipped n-1 glasses we can just flip one glass and have a coin that records whether we need to flip them all later. So for every move flip the coin, and flip or unflip a glass.
We always start with 0 glasses flipped, and our coin set to no-flip, which we can show as (0, 0 = false/no-flip), then we can move up and down this chain:
(0, 0) (1, 1) (2, 0) ... (n, n mod 2)
It takes at least n moves to reach the end of the chain and there are no other possible moves.
This works if n is even, since the last element is (n, 0), meaning we don't have to flip the glasses and we're done. Otherwise we have (n, 1) which is equivalent to (0, 0) so we're back at the start.
this is how I'd solve this puzzle:
1) get a friend to agree to the following steps
2) pick one unique glass you don't want to invert
3) invert every other glass
4) invert your friend
5) ask your friend how many glasses are inverted relative to them
repeat steps 2-5 until either all glasses are inverted or your friend is dizzy.
from your perspective, you have inverted all-but-one glasses at a time, but your friend will have seen only one glass inverted at a time.
since your friend only sees one glass inverted per move, they would only be able to see all the glasses inverted relative to them, therefore you must take as many moves as you have glasses to flip all of them once from your friends' perspective
however you will run into a parity problem: your friend will always be able to see every glass inverted since they see glasses inverted one at a time, but that's because they are being inverted themselves. if you have an odd number of glasses, your friend will be inverted an odd number of times. your upside-down friend sees every glass as upside down from their perspective, therefore those glasses need to be upside-up from your perspective
as a result, you can invert N glasses in N moves iff N is even. otherwise, it is impossible.
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 problem is a binary problem where the cups are either up or down. You can only change the state of N-1 or basically all but 1 each time. You can easily infer that the final step of the problem will need 1 cup facing down and the other remaining N-1 cups facing up so that you flip exactly all cups that are facing up to down. Since you're flipping all but 1 cup each time, basically only all but one cup change state each move. In order to achieve the state just before the final move you need to basically flip all the cups N-1 times. So the amount of moves necessary to flip all the cups facing down is equal to N moves. This solution is impossible for the situation where there's only 1 cup, or N = 1, since you aren't allowed to flip any cups at all for that scenario.
A nice graphical way of solving this is to arrange the glasses in a circle and then flip n-1 glasses at a time, while shifting the group one spot each time. That way after n operations all the glasses get flipped n-1 times( which is odd) and thus all the glasses will be flipped over
You can prove it by induction in a slightly simpler way. Assume we can swap n glasses in n moves. Then take n+2 glasses, i.e. U....U, n+2 times.
1) Flip the first n+1 glasses in 1 move, so you get D....DU, with n+1 Ds.
2) Flip the last n+1 glasses in 1 move, so you get DU....UD, with n Us.
3) But we can already flip n glasses in n moves, so do that with the n glasses that are U....U, and you get all n+2 glasses being D....D.
So flippin' n+2 glasses takes n+2 moves. We have the base case for n=4. So for n even, it takes n moves.
Interesting to see the AI results with this one. I used the Bing Copilot, which I believe is also ChatGPT based, and it did get the correct answer and correct reasoning using parity. While I probably wouldn't formulate the proof as well, for once I was able to conceptually explain it before watching the video.
Inverting all but one glass is basically the same as inverting just one and then pretending to flip the whole setup upside down. If you make two moves, you've pretended to flip the whole thing upside down twice, so for even numbers of moves, you can just turn two glasses and it will be the same as having turned all but one twice.
Therefore, for n glasses, where n is even, n moves is the minimum number of moves and each glass gets one turn where it's not flipped.
Define a "glass-flip" as flipping a single glass. To end up with all N glasses flipped, a total of N x J glass-flips are required, where J is an odd positive integer. We are constrained to always flip N-1 glasses with each move; we'll do this in K moves, where K is a positive integer. We have a solution when N x J = (N-1) x K. Now it's just a matter of solving the equations, no need to visualize permutations of flipping glasses anymore.
The way I thought this through was if all but one gets inverted each time, you could think of it the same as only one getting inverted each time, so you just go in a line to invert each one, therefore minimum = n. Then you also have to remember that each one must be inverted an odd number of times so the answer only works for an even n.
Because the positions don't matter the only thing that logically differentiates one move from another is whether the glass you DON'T move is up (which I will denote as a U move) or down (a D move). Note that repeating the same move twice (i.e. two D moves in a row) simply cancel out. The second move simply undoes the first.
Therefore the sequence of moves MUST be a simple repeating sequence of U, D, U, D.... There are no other possible meaningful sequences of moves.
The first move must be U and results in 1 glass in the up position. With each subsequent move one additional glass is moved into the state of that move. In other words the second move is D and results in 2 glasses down; the third move is U and results in 3 glasses up, and so on. Therefore on the Nth move all the glasses will be in the same orientation and that orientation will be determined by what sort of move the Nth move was.
Because the first move must be U an odd number N will result in the Nth move being U and the glasses will all be up. But an even N will result in the Nth move being D and all the glasses will be down.
Label the glasses, from left to right, with sequencial letters A through D. Describe each move as the letter of the glass that is NOT moved. Any solution that uses all four letters an equal number of odd times is thus correct, with the simplest solution being each letter used once.
How to do it in one move--regardless of whether the number of glasses (n) is even or odd:
Use round-bottomed, bottom-weighted glasses--which will roll around until the weighted bottom is at the bottom, unless they're set perfectly upside down. (For those of you old enough to remember Weeble toys, they're kind of like flat-topped Weebles.) Place n-1 glasses upside down on the table, and then set the last glass upside down on top of one of the others. Then, turn all n-1 glasses touching the table right-side up. As you do so, the glass which was sitting on top of one of the others will fall off, onto the table--and it will right itself. Now, all n glasses are right-side up, although YOU only inverted n-1 of them, in one move!
The first interesting thing to notice is that in the general case (N glasses), at each step, only N moves are possible, each one leaving only one particular glass invariant and inverting all the others. The second interesting thing is that the result of a succession of moves does not depend of the order of moves. This is because after such a succession of moves, for each glass, its position (inverted or not) depends only of its initial position and of the parity of the number of inversions in which it was involved, and this number does not depend of the order of the moves.
A consequence of this is that in a minimal solution, no move appears twice, since changing the order so that the two eventual identical moves become consecutive results in doing nothing, so they can be ommited.
As there is only N different possible moves, if a solution exists, a solution exists in N moves or less and in this solution all moves are different.
For N even, a solution consists of a succession, in any possible order, of the N different possible moves. In this case, each glass was invariant in only one move, so each glass was inverted N-1 times, as N is even, N-1 is odd and so each glass was inverted an odd number of times, so it ends inverted.
If N is odd, doing the same thing as above (executing all the N possible moves) is not a solution, since the same reasoning shows that each glass becomes inverted an even number of times, resulting in being at its initial position at the end.
Now in both cases (N even or odd) a solution cannot be in less than N moves. If we have a succession of P different moves, with P < N, there is at least one of the N possible moves that was not used, this unused move leaving the glass number K invariant. So the glass number K was never invariant and so was inverted P times. But there is at least one move, so at least for this move some glass J was invariant and only in this move, so it was inverted P-1 times. As P and P-1 have different parity glass J and glass K are in different positions at the end, so it proves that not all the glass are inverted at end, and so this is not a solution.
This proves both things : for N even the optimality of the solution(s) shown, and the inexistence of solution for N odd.
Alternative solution:
Assign 1 to an upright glass and -1 otherwise. Consider the product. At first it's 1 and in the end it should be (-1)^n.
In each step we multiply the product by (-1)^(n-1).
This immediately shows why it's impossible when n is odd. We're trying to go from 1 to -1 while always multiplying by 1.
It also shows that we need even moves in case of n even, since we're going from 1 to 1 by multiplying by -1 at each step.
Now in the n even case name each move by the exact one glass it doesn't flip. Suppose we solve it in less than n moves. By pigeon hole principle, there should a glass that's the move named after it didn't happen, therefore it's flipped every time and since there's even number of total moves, it should be back upright which is a contradiction.
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.
Label the glasses 1,2,...,n. Label (1),(2),...,(n) the glass flips that flip all but 1,2,...,n, respectively. For example (2) would flip all glasses except for 2. Note that any glass flip applied twice results in no net action. Our objective is a sequence of flips that results in all glasses flipped. The insight is that the glasses get flipped once more if they're corresponding glass flip is not part of the sequence. For instance let n=5. The sequence of glass flips (1)(2)(3) flips glasses 1,2,3 twice and glasses 4 and 5 3 times. This implies the only possible solution is to apply all flips so everything is flipped the same number of times. When n is odd this solution flips everything an odd number of times resulting in the objective; when n is even this sequence gives us all glasses flipped the wrong way.
Problem becomes trivial when you consider that inverting n-1 glasses, is same as inverting only the omitted one and then inverting all of them. Inverting all of them an even number of times does nothing. Hence, each move of n-1 glasses is equivalent to inverting just the omitted one, and all will have been inverted in n moves as long as n is even.
My brain just said “smash one and then turn over the other 3” and then was made to panic when the guy mentioned n-1 stuff
Idk how formal the proof has to be (particularly for Part 2), but here is my attempt at it. Spoilers below if I'm right.
==================================================================================
Problem 1
NB: I replaced the glasses being up or down with binary strings for ease and convenience (up = 0, down = 1).
It takes, at minimum, *4 steps* to get all of the glasses from 0000 to 1111 and this is actually fairly trivial to prove/brute force. There are a few key insights to pick up on that help here:
1) every single arrangement of glasses that include the same amount of 0's and 1's are functionally identical since all we care about is getting all 4 flipped not which specific digits are in which slot (ie, 1101 = 1011 = 0111 = 1110 for the sake of the problem);
2) since all arrangements are identical and we are flipping all but one of the glasses each turn, the main important detail of any particular step is the state of the single glass left unturned (whether it is a 1 or 0), thus there are only 2 options for any given step after the first one (0000 must necessarily be changed into 1110). For formatting purposes from here on out, I will always leave the last glass of a particular type unflipped heading to the next step, so 1100 would become either 0111 (last 1 unchanged) or 0010 (last 0 unchanged);
and 3) there is actually only ever one "unique" flip possible at any given step, as one of those two "unturned" glass states will just result in undoing the previous step. For example, after 0000 -> 1110, leaving the 0 glass unchanged just gets us back to 0000 again.
Keeping those in mind, the only possible solution that doesn't repeat any prior steps is:
Step 0: 0000
Step 1: 1110 (0 unflipped)
Step 2: 0011 (1 unflipped)
Step 3: 1000 (0 unflipped)
Step 4: 1111 (1 unflipped)
For 4 glasses, another way to think about why this minimum is necessary comes after Step 2 (Step 1 is forced, and it is trivially easy to prove that the only two options after Step 1 either gets you back to 0000 or some arrangement two 1's and two 0's. There is absolutely no way to change only two 0's to 1's in a single step (as each Step necessarily flips three glasses), so both a Step 3 and 4 are required.
=================================================================================
Problem 2:
This one I don't know how to formalize either element via a proof (especially the minimum step count), but I am pretty sure that 1) it is only possible to solve when there are an even number of glasses (n is divisible by 2) or only a single glass (n = 1) and 2) that the amount of steps required is n itself in those cases.
The way I got there was from trying out n = 2 ("trying out" is maybe a little strong here), n = 3, n = 5, and n = 6 with the principals from Problem 1, with the following results:
=====
n = 2
Step 0: 00
Step 1: 01 (0 unflipped)
Step 2: 11 (1 unflipped)
=====
n = 3
Step 0: 000
Step 1: 110 (0 unflipped)
Step 2: Either 000 (0 unflipped) or 101 (1 unflipped)... Rearranged another way, either 000 (back to Step 0) or 110 (Step 1 repeated).
=====
n = 5
Step 0: 00000
Step 1: 11110 (0 unflipped)
Step 2: 00011 (1 unflipped)
Step 3: Either 11101 (1 unflipped) or 11000 (0 unflipped)... Rearranged another way, either 11110 (back to Step 1) or 00011 (Step 2 repeated).
====
n = 6
Step 0: 00000
Step 1: 111110 (0 unflipped)
Step 2: 000011 (1 unflipped)
Step 3: 111000 (0 unflipped)
Step 4:
001111 (1 unflipped)
Step 5:
100000 (0 unflipped)
Step 6:
111111 (1 unflipped)
Looking at these results, it seems pretty likely that every odd n solution (besides n = 1 which solves itself immeadiately) necessarily reaches a point where there is one more of the "0" glasses than there are amount of the "1" glasses, at which point either choice results in repeating a step whether it be by backtracking to the last step or just repeating the current step. Meanwhile, every even n solution necessarily reaches a point where there is an equal amount of "0" and "1" glasses which then resolves itself. It also appears like the 0 unflipped -> 1 unflipped -> 0 unflipped -> 1 unflipped (etc.) pattern is the only way to actually make progress at any given point, but... I'm not sure how to connect the dots for a rigorous proof.
My guess is that there's some clever approach to convert the n = 3 steps into their n = 5 steps equivalent and the n = 4 steps into their the n = 6 steps equivalent that scales to larger or smaller n's via the use of that forced 0 -> 1 -> 0 -> 1 pattern, but I'm too tired to work it out atm lol. Also, n = 2 and n = 6 requiring two and six steps respectively is where the step count = n thing comes in, but similarly, no clue how to formalize that :P
i abstracted the state of the glasses to an integer and a parity bit
in each step you toggle the parity bit and either add or subtract 1 to the number
you start at (N, up) and want to get to (0, up)
obviously N must be even and the minimum number of steps is N
Lots of ways of examining and solving this with higher math, but it seems to me like the simplest way to show it cannot be done with an odd number of glasses is this:
(1) If n is odd, the total number of flips must be odd.
(2) This cannot be achieved if you are flipping an even number of glasses each time.
In more detail:
Consider the number of "total flips" necessary to invert all glasses. Minimum = n (number of glasses, i.e., all get flipped once)
If you add one more flip (n+1), one glass is again upright. So it needs to be inverted again. So the number of flips necessary is simply n + 2k, where k is an integer, which is always odd if n is odd.
Isn't inverting three just the symmetry to inverting one ( + changing you point of view)?
For the general case, when n is odd: a glass is upside down when it has been inverted an odd number of times. An odd number of glasses times each requiring an odd number of inversions yields a total number of inversions that is also odd. No integer multiple of an even number will produce an odd number. Hence, no solution.
Nice! I did the process slightly differently.
Used 0 to represent the upward open, and 1 for the downward open.
So I did,
0000
1011
0101
1000
1111
4 moves!
Before watching the solution, I'd solve the case for general n as follows.
If n is odd, then in each step an even number of glasses are turned. Thus, the number of inverted glasses will remain even and can never reach n.
If n is even, an odd number of glasses are turned in each step, meaning that the number of inverted glasses is odd after each odd step and even after each even step. The state of n inverted glasses can thus only be reached with an even number of steps. Each individual glass needs to be turned an odd number of times, so there has to be at least one step in which it is not turned. As each step only leaves one glass unturned and there are n glasses, n steps is a lower bound. Finally, turning in step k all glasses apart from the k-th one shows that n steps indeed suffice.
Smash one of the glasses so there’s one less glass to worry about
You'd need 4*(2k+1) total inversions to turn all upside down. In each turn you make 3 inversions. The first 4*(2k+1) number divisible by 3 is 12. You exclude each glass once in 4 turns.
Once I realized that the generalization was "n glasses, flip n-1 at once" and not "n glasses, flip 3 at once", and odd/even parity was mentioned, then "odd n is impossible" became obvious. Consider:
* You start with an odd number of glasses facing up, you want to end with an even number of glasses facing up.
* Each set of n-1 glasses is equivalent to (n-1)/2 sets of 2 glasses.
* Flipping 2 glasses either leaves the number of glasses flipped up the same (if they were facing opposite directions) or changes it by 2 (if they were facing the same direction). Either way, you still have an odd number facing up, and thus no way to end up with an even number facing up (much less the specific even number desired, which is zero).
Similarly, if n is even, then every pair of sets of n-1 glasses is either the same set twice (which just takes you back where you started, and is thus useless), or two different sets (where two glasses are flipped once - the one omitted from the first set, and the one omitted from the second set - and all others are flipped twice). In other words, every useful pair of sets of n-1 glasses is equivalent to a single set of 2 glasses. So obviously n/2 such pairs are required to get from n glasses facing up to 0 glasses facing up.
Behind the n glasses facing up, imagine there are n glasses facing down. Each time you invert n-1 glasses in the front row, you mentally invert the same n-1 glasses in the back row. Hence you succeed as soon as the front row are facing down and the back row are facing up. Now consider what this game does if you (mentally) swap front and back rows after every move. Now you are inverting one glass every time because the front and back rows are always related by inverting all n glasses. Every solution to this problem involves inverting each glass once, plus an even number of glass inversions. However to solve the original problem, we must end after an even number of moves so that the front row returns to the front. Thus n must be even to solve the problem, and then n is the minimum number of moves.
I did it just by looking at the thumbnail
Before flipping them all down, you need to have 3 right side up glasses, and you can increase the amount of right side up glasses with shenanigans.
UUUU
DDDU
UDUD
UUDU
DDDD
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 )
It may be checked is a perfectly reasonable justification for the minimum. There’s only 3 cases to check: 1, 2, or 3 moves. 1 and 2 moves are trivial, so really only three moves needs checking.because the order of the glasses doesn’t matter there’s only about 4 sequences of flips that need checking.
Here's a pretty combinatorial solution in 7 steps:
- Let U be up glass and D be down glass
- Since we can pick which n-1 glasses to flip, order doesn't matter thus we can reorganize any sequence so the label with fewer glasses is all on the left while rest is on the right
- Let's add a divider / to highlight the sides, for example ~ UDDUU = DD / UUU
- Notice moving on any sequence picks n-1 glasses to swap leaving 1 untouched, but this is the same as swapping 1 glass first then swapping the whole sequence, for example ~ U[UU / DDDD] -> U[DD / UUUU] = [DD / UUUUU]
Do you use GPT-4 or GPT-3.5?
Binary digit parity?
0000 has even parity (number of 1s).
We can treat each turn as shuffling the digits (not affecting parity) then adding 1110, changing parity from even to odd or vice versa. (The parity of an odd number of bits changes, so the total parity changes.)
Final result also has even parity.
So an even number of moves are needed.
Now treat each move as adding 1111, shuffling, and then adding 0001. In an even number of moves all the 1111s cancel out. So we just need n moves to add the n 0001s, one for each bit.
This generalises easily to any even number.
For an odd number of glasses: we start at even parity and are always adding 111...10 (even number of 1s) which is even parity. So the parity of every state we can reach is even but the final state has odd parity, being an odd number of 1s. Hence it's impossible.
You can also simplify the question in: how many moves do you need to switch HALF of the glasses orientation, since doing the same thing onwards will finally give you all glasses switched, in double the number of rounds needed for exactly half of them. you can directly see it in the end of move 2 shown.
Also, the necessity of having a position where exactly half of the glasses are switched, it gives you the answer that you CANNOT do it with odd number of glasses, it always has to be even ;)
Well, the occurrence of the half position is true only for this "n glasses and (n-1) moves" case. You can try for smaller values of turns per move to find that half positions don't always occur. Thus, we can't conclude from the half position idea alone.
I figured that on each move you're changing the arrangement by exactly one glass. You can ignore that the arrangement is flipped because every two moves will flip the arrangement twice. So if you have n glasses, it must take n moves, if it's possible at all.
How about the fact that no matter what N is there is always only one choice for a move that doesn’t lead to a previous state? Since order does not matter, you only are choosing between leaving a glass in the “up” position or “down” position as the one not being inverted that move, so you only have two possible moves. Choosing the same as the previous move just undoes the previous move, meaning it will never be part of a fastest solution. This every move only has one possible choice - choose the opposite of the previous move. Since starting all glasses are face up, the first move can only be to leave an “up” glass. This if a solution exists it can only be by selecting “up, down, up, down…” repeating.
This also hints why n must be odd - the final step must be to leave a glass “down” (if you leave one face up by definition they’re not all face down), and odd numbered steps are always to leave one “up”, so you will always require an even number of steps.
I think I found a way to better visualize this
Say you have n (you can practice this with your fingers) list them one through n. On your first move, move everything but 1, on your second move, move everything but 2; continue this until you reach n. If n is even, everything will be down, if n is even everything will go back up. I think it is because it affects it n-1 times, meaning if n-1 is odd then it will be flipped an odd number of times and just like switching a light if it is hit an odd number of times, it will be inverse of it's initial position; the opposite is true for if n-1 is even, flip the light an even number of times and you will be back were you started. (Sorry, not good with punctuation but I try)
I am not all that bright so I couldn't follow along and came up with this method, trying to brute force test it, though it didn't take more than 2 tries to come up with this system and I only discovered how this system works in a more fundamental way when I was making the comment. Funny how things work out sometimes.
My biggest problem with the video is that I couldn't figure out what the numbers represent. I only managed to grasp a little of what he was talking about l, using my own method as a grounds
Looking at the video again, he kinda described what I was talking about at 11:48
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.
This is pretty easy to brute force. IDK if CZcams will preserve formatting, but this is all I typed looking for a solution:
```
⊥ ⊥ ⊥ ⊥
0: ⊥ ⊤ ⊤ ⊤
1: ⊤ ⊤ ⊥ ⊥
2: ⊥ ⊥ ⊥ ⊤
3: ⊤ ⊤ ⊤ ⊤
```
(The spacing is because I thought I would be drawing a tree, and would have to back-track).
At each step, you're picking one glass to *not* rotate. For the first step, without loss of generality, just pick the first glass to not modify. For the next step, picking 1, 2, or 3 are equivalent, and picking 0 again gets us back to the start. So, pick 1, without loss of generality. At this point, you can pretty much see the solution. Pick 2 (or 3), then pick 3 (or 2).
Each glass has to be inverted an odd number of times. The total number of inversions must be a multiple of 3, since we must do 3 inversions per ‘turn’. The simplest way to get this result is 3+3+3+3=12. That means we hope to be able to do this in 4 ‘turns’. If we exclude one cup each time, each cup will be affected in 3 of the 4 turns, solving the puzzle.
polyrhythms in music made this pretty easy to figure out
Im on the toilet, read the thumbnail, got 3 toothpaste tubes, set them on the bathroom floor, and did it on the floor immediately in 4 turns. Wonder how this gets turned into 16 minutes
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.