TL;DR I found the same solution a different and more tedious way but I'm happy about it! I'm so proud of myself that I found my own solution using group theory! When you first posed the puzzle (before mentioning graph theory) I paused and tried it on my own. Granted, it's not nearly as elegant as the graph theory solution and it's not really generalizable but it worked. I made a permutation group out of the rotational symmetries of the cube (on my paper I represented them like (GG),(RB),(YB) where each double is a front/back face pair. What I wrote as that example is cube 3 if you want to check that what I'm saying makes sense, and the permutations I used were (12),(34),(56) -> (34),(21),(56) to represent a quarter turn on the axis passing through (56) and variations of that). The second insight was that the duplications of colors meant that the top/bottom faces needed and 2Y, 3R, 1B, 2G so that the sides would have exactly 4 of each color. I treated this as a linear system (well mostly I guess and checked but tried to be methodical in ticking off every possibility) and I found only 5 ways for this to happen (I believe I covered all branching possibilities but I might have missed some IDK). Finally, I took these possibilities and my group structure and started checking off possible combinations like playing a Sudoku puzzle. I eventually came up with... well the same solution that they showed in this video. So not the most interesting result, but hey! I know nobody out there probably cares, and this explanation if far from rigorous or even clear but I'm proud of finding this solution on my own and just wanted to share that.
xiaoheidan exactly my point, if they have put the graph again there, then one can pause it there and immediately go and try it out, but as they don't, then one have to no only pause but to go and search back in the video for the graph, which add a level of annoyance to it...
Agreed. It's nice, and typical in these kinds of videos. In fact, I'm so used to that approach in puzzle videos that I waited for the cut and paused on to work it out, only to realize it was the solution not the graph.
I like how the conditions are motivated by trial and error, because, as far as i can tell, this is an important part of science, even in mathematics. People outside the field need to know that. Great vids. Keep it up.
Here's my solution for the set of cubes at the end. Notice that if we use any self-loop (edges from a color to itself), we cannot use that color again without violating Condition 3. In fact, subgraph A and B must each be composed of a set of disjoint cycles. So if we use a self-loop on, say, Yellow, we must have a disjoint set of cycles covering Red, Green, and Blue as well. But Green and Blue do not share any edges, and Blue does not have a self-loop, so we can't put {Red, Green, Blue} into a cycle. This means we can't ever use Yellow's self-loop. This leaves Yellow with four available edges; hence, they must all be used in any solution. We can quickly find one legal solution just by trial and error at this point: A: {Y -3-> G -4-> Y, R -1-> B -2-> R} B: {Y -3-> B -4-> Y, R -1-> G -2-> R} Here's another: A: {Y -3-> B -2-> R -1-> G -4-> Y} B: {Y -4-> B -1-> R -2-> G -3-> Y}
Paused the video to try myself. Would have been good at that point to see a diagram of the "combined + directed" graph (which wasn't displayed earlier). I know, 3 minutes with some pens and I could have put it together! Great video though. Thanks!
Lol, my teacher's class schedule had Instant Insanity as one of the topics covered near the end of the semester on the syllabus, and when I read through it, I was like "Oh boy, this is gonna be a fun semester"
That would have been a much less geeky admission inasmuch as it would allow for a value of zero. Do I exude geekiness? I suspect that most viewers of this video, by virtue of age or interests, could state with absolute certainty that there is not in some nook or cranny within their house a long forgotten copy of Instant Insanity. I am not one such.
kindlin Zero probability doesn't mean something will not happen. Probability that a continuous random variable equals some value is always zero. Yet it will have a value.
Cool problem and well-presented! I love it when problems like this can be reduced to mathematical analogies (from graph theory, group theory, combinatorics, etc). Bijections like these are one thing I love about math and that make it so interesting!
There are only 41,472 unique variations. I know because my code found 8 solutions with irrelevant variations (the stack rotated as a whole for 4 solutions and each of those solutions reversed for 4 more). It makes sense though: There are 3 base sequences on a cube: Front, Left, Back, Right / Front, Top, Back, Bottom / Left, Top, Back, Right. You can reverse the sequences by flipping a cube over, which doubles the permutations per cube. You can also rotate each cube in the stack, which multiplies the permutations per cube by 4. The order of the stack (cube 1 on top rather than on the bottom) doesn't matter, so we won't factor that in. Thats 24 total permutations per cube and 4 cubes so 24⁴ = 331,776 permutations. However... The facing of the stack doesn't matter (we can rotate the whole stack as a unit), only the rotation of the cubes relative to each other matters. This means that one cube shouldn't rotate. You can get every unique stack by rotating the top 3 cubes. The video correctly factored out those variations to get the ~80k number. Along the same lines, reversing the sequences only matters in relation to the other cubes, so you shouldn't reverse the order of the cube that you don't rotate. That reduces the permutations by another factor of two. Therefore, one cube only needs the three base variations. So there are only 3 × 24³ = 41,472 unique solutions.
Got this puzzle in a cereal box in 1970, when I was eight years old. In 1980, I wrote a FORTRAN program to solve it with brute force (6X4)^4 = 331776 permutations. Handed my PUNCH CARDS to my college's mainframe computer operator, and picked up my form-feed printout later. It had timed out without a solution in 5 seconds of CPU time (the maximum allowed, LOL). A few years later I bugged my girlfriend in university to use her computer time. She entered the code on a terminal, and picked up the printout. It took 35 CPU seconds, and it was solved. She chewed me out because that was 1/3 of the total time allowed for her entire computer science semester! But I was was HAPPY.
Correct me if I am wrong, but the solution seems to be wrong as in 7:22 there is an edge from B->Y labelled 3, however, in the final solution there is an edge from Y->B labelled 3.
Great video, very cool to learn about graph theory. Regarding the 2 questions you asked, I found that : 1) no other configuration 2) there are 2 configurations F/B : (R)>1>(G)>4>(Y)>3>(B)>2>(R) and L/R : (R)(R) and L/R : (R)
It is an interesting use of graph. If you only hinted us to use graph theory on the cubes, I think my search space would be from {}->{Cube1(orientation1)}->{Cube1(1)Cube2(1)}... That would be a very large tree. Look at the graph of your approach, it is genius! I think the mixed reaction of the viewers are some of them couldn’t have get this appreciation. And the finale was a bit too plain. There could be an animation showing how you pick the edges from the curvy graph, and thus we could understand the conditions better. An animation worths ten thousand words :)
As soon as the cubes were presented, with "can you find a solution," I whipped out Z3 and asked it to find a solution for me. SAT solvers are always the answer.
So once i learned the combinatorial trick behind this simple yet great puzzle, I made my own one with 8 cubes the mission is to build the perfect 6 sided cube. My little brother enjoyed it well (but of course he failed :) ) This puzzle is good case to see how our intuition sometimes could be best approach to problems without meta-level logic on our hands.
I paused before the title card and solved the first set in about 3 minutes. First I figured out which two opposite faces on each cube should be hidden by being the tops and bottoms. There were 7 red, 6 yellow, 6 green, and 5 blue faces, so we need to hide 3 red, 2 yellow, 2 green, and 1 blue. It was lucky that the answer is to hide the squares shown at the top and bottom of each diagram - none of the unwrapped cubes were permuted in a more complex way. Then starting by going left to right on the first cube, I found a starting point and direction of the rest that gave unique colors for each face of the stack. The answer is: 1. start at red going right, 2. start at blue going right, 3. start at yellow going right, and 4. start at the right side green, going left. That just means you will flip cube 4 upside down when stacking it.
This was surprisingly easy just using logic. The cubes can be considered strips of 4 sides (because the top and bottom don't matter), which can be formed in three ways from each cube's colors. You inevitably have to have the same total number of each color. I chose strips from each cube such that they compensated for any excess/lack of other cubes, wrote those in a text editor as RYGB etc. and used rotations and flips to find a permutation where it worked. Took about 5 minutes...perhaps I was lucky with my choice of strips, or perhaps most or all combinations which satisfy the color count matches work. Haven't finished the video yet, so don't know if my answer is the same or if my method is partially isomorphic to what is presented.
I paused right after you posed the question, figured it out, then unpaused and saw you made templates. That would have helped during the problem lol. As for multiple solutions, I believe there is only one (besides the same tower rotated, or the blocks' orders changed). When I was solving the puzzle, I logically deduced things that had to be true of any solution to the problem, and I ended up with only one configuration which satisfied all of them.
what i find interesting and I don't know if this was done for the purpose of the demonstration but when all of the cubes are laid out - the four faces that are used are all the ones where the four are connected in the middle. The top and bottom of the cube, how it would sit, are the square on the top and bottom of the exploded cube. Obviously the cubes could be exploded in multiple manners this was just interesting to me that it ended up that way. My guess is the early shot of the exploded cubes was actually arrived at by working backwards.
It was incredibly well-presented, I loved how straightforward and engaging your explanation was, but How many subgraphs can be drawn that satisfy the conditions?
Correct me if I'm wrong, but (taking Cube 2 as our example), can't the undirected graphs for a cube represent _two_ different cubes? One is the chiral pair of the other, and they're distinct from each other! We need the arrows to capture this distinction: flipping a single arrow gives us the chiral sibling of the cube -- unless we happened to flip along an axis that the cube _does_ have mirror symmetry on, as you slyly did at 3:10.
Also, Condition 4 arises only because of the specific set of cubes we've picked. In your example at 8:28, technically there is no problem with having red appear twice -- we do have _three_ red sides available to us. If we had a cube with two pairs of red/green sides opposing each other, with (say) blue and yellow on the third opposing pair, Condition 4 would not necessarily hold. We actually need to prove Condition 4 for each cube individually: the graph of no cube has more than one edge between vertices.
It's definitely true that in the context of Instant Insanity, we don't care about the chirality of a solution -- finding a solution with one set of cubes gives us a solution where any cube is swapped for its chiral twin. But that wasn't how it was presented in the video. I was being a bit too loose when I was talking about Condition 4 -- thanks for keeping me honest. I was more concerned with the example being given, which could give the impression that the problem is the duplicate colors, not the lack of another pair. To be fair, I probably just read too much into that line.
1. The Instant Insanity have only one GRAPHICAL solution, but for this solution exists 8 spatially different combinations of cubes positions. 2. Second set of cubes (9:22) have two graphical solutions and it is wrong puzzle. And notes from me: A. 1:09 - The first cube in the sequence is enough to be positioned in three ways, have placing it on one side of three opposite pairs of faces, accordingly: there are 3x24x24x24 = 41,472 possible arrangements of the four cubes, and 8 of these give a valid solution (alone graphical solution, but 8 spatially different combinations, see above). 82,944 is wrong number. B. 9:05 - What does the phrase "Solution due to Robin Wilson, Emeritus Professor of Mathematics at Open University" mean? - The graphical solution of four cubes problem have first been published in 1947 by "F. de Carteblanche" (pseudonym for the team of four friends - Cambridge students: R.L. Brooks, C.A.B. Smith, A.H. Stone and W.T. Tutte) in Eureka No. 9, April 1947 (the undergraduate mathematics magazine of Cambridge University) - "The Coloured Cubes Problem", pp.9-11. And here is there a respected professor? С. "Print off a template for the cubes shown in the video!" - Franz O. Armbruster completely copied the puzzle from genius Frederick A. Schossow, changing only two not visible faces from one cube. It's hard to believe that this man had an imagination, but it was he who came up with the name «Instant Insanity». How long will we replicate the same set? There are many other variations of the puzzle of the four cubes. In the android puzzle IQ'biki are over 1000.
To add to my previous comment, what happens when you replace the cubes with triangular prisms, or any regular prisms with an odd number of sides? What graph do you use? How do you define its edges?
This was wonderful! I feel like you’re finding your feet on this channel. Was a great choice of topic as you were able to explain the whole thing with no "magic", while still tying in the larger mathematical ideas.
there are 6 solutions to the challenge at the end, the limited number of blues restricts the problem a lot as blue can't be on the inside of the column, solutions spoilers below, but without explicit construction of the graphs: the insides colours must be 4 red, 2yellow and 2green and the options for insides colours for each cube are: 1 YY or GR 2 GG or GR 3 RR or GY 4 RR or GY if 1 is YY then 3 and 4 must be RR as can't have more yellows on the inside which requires 2 to be GG, if 1 is GR 2 must be GR or can't get 4 reds (odd/even issue) then we have two green inside so 3 and 4 must be RR but then we have too many redh and no yellows so 1 can't be GR by contradiction. so middle is 1YY 2GG 3RR 4RR. then 1 and 2 have two distinct possible arrangements that dons't put two of the same colour in the same column, same with 3 and 4, which pair up but one pair has 4 relative rotations that work and the other has 2: RGBR RGBR or RGBR RGBR or RGBR RGBR BRRG BRRG BRRG BRRG GRRB GRRB YYGB GBYY GYYB GBYY BYYG YBGY GBYY YYGB YBGY YYGB YBGY BYYG
Yes, there is only one solution, it was quite fun, and you could solve it like a Sudoku. For the extra question, it was quite simple actually since the blue side only appeared four times and so it made it a bit simpler
I did not follow how graph theory was useful here but I solved both puzzles in about 2 minutes with just pen and paper. For the first puzzle I had the same answer as in the video. For the second puzzle I have: 1. RRGB 2. GBRR 3. YYBG 4. BGYY
each cube has at most 6 unique orientations. 1 for each of the 3 dimensions, and a mirrored copy by flipping each dimension. in some cases flipping doesn't change the state, leaving that cube with less unique orientations. The cubes 1,2,3,4 had 4,6,4,6 unique orientations. Single and double repeats of a color in an orientation were easy to eliminate, as they required being matched with at least one orientation from the other cubes not containing that color, and contradictions showed up quick. Had a solution a lot quicker than using the graph method, but i can definitely see the graph method being ideal for bigger problems.
Each cube has at most _24_ unique orientations: Fix the face on top (or in any other position, it doesn't matter) and rotate the cube keeping the top face fixed. For each of the six faces, there are four orientations. Of course, if a cube has a pair of opposite sides that are the same colour, that reduces the number of distinct orientations.
Nillie I didn't consider rotations to be unique orientations. As for this particular problem its clear when two orientations are incompatible e.g. [G,G,R,Y] AND [B,G,R,G] Rotations will fail to make these two cubes compatible because of the G's. And that's just one of many such incompatibilities
Kadmilos Somnium When you combine cubes into stacks, the orientation of each individual cube _does_ matter, though the order of the cubes in the stack does not, nor does the orientation of the stack as a whole. As such, a stack of four cubes can have at most (24^4)/(4*2) distinct permutations, which is significantly more than the 6^4 you’re saying it can have. (Since the 24^4 only specifies the orientation of each cube, not their order, we don’t need to divide by 4!, though we do need to divide by 4 since the orientation of the cubes only matters relative to the other cubes, and we also need to divide by 2 since flipping every cube upside down doesn’t change the stack as a whole.)
When writing down the possible cycles of four sides on each cube, I noticed that there is one cycle which appears on both cube 1 and cube 4: RYGB (or YGBR or GBYR or YRBG or... you get the picture).
I admit, I solved both sets of cubes by inspection rather than by using graphs - for the second set, there are only 4 blue faces total, which drastically limits the possibilities, as does 3 and 4 being the same cube - if either of them has double red as their second pair of faces, then avoiding having a 5th red while keeping the 4 blues leaves you with 5 yellows and 3 greens, so 3 and 4 have to have their reds on top/bottom, meaning cubes 1 and 2 have to supply all 4 reds between them. The reds and yellows come in adjacent pairs, while the greens and blues are one per cube, so they can be arranged as required. I do have two corrections/suggestions for the video: Firstly, I think the 82944 is either an over- or an under-count - each cube can be oriented in 24 ways and still form a stack occupying the same space, and you can rotate the entire stack about its vertical axis to give 4-fold symmetry, which is presumably where the 82944 comes from, but you can also flip each cube about its front-back axis, effectively reflecting the stack (swapping left and right faces on every cube) since we're ignoring the top and bottom faces entirely, giving another factor of 2 (equivalently, you could flip the entire stack end for end and then reverse the order of the cubes, meaning each of the 8 rotational symmetries of the stack gives rise to a variation of the same solution), making only 41472 distinct arrangements. Secondly, when displaying the tables of colours and positions associated with graphs A and B, it's confusing to have the columns go front, back, left, right, since it means that the arrows on graph A are pointing to the left of the table (to front, from back) while the arrows on B are pointing to the right of the table (from left, to right) - it would be more natural to have the columns in order back, front, left, right so that going from source to sink moves from left to right across the table in all cases.
Now, I may well be wrong---I don't have a printer handy, so I can't really try it for myself---but it seems to me that if you hand a human these cubes and ask them to solve the problem, they probably would fairly quickly. That's not to say that the mathematical solution isn't interesting, just that I think the human intuition (read: fast subconscious pattern-matching algorithms) solution is pretty cool to think about as well.
One of the things I have always hated about graph theory, the little I know about it, is how hard it is to understand the subject at an introductory level, in large part due to the terminology used. For example, when two nodes (oddly referred to as “vertices”) of a graph are connected by a line (or curve), again oddly, such a line is referred to as an “edge.” A problem with this odd use of terminology comes up in the graph theory solution to “Instant Insanity,” the puzzle sold in the sixties by Parker Brothers. In this case, if one thinks about Webster’s definition of edge as being “a line or line segment that is the intersection of two plane faces (as of a pyramid) or of two planes,” we can see that on a six-sided cube, there are twelve of such edges. Contrary to this common understanding, in the graph theory solution to Instant Insanity, an edge is defined as being between two opposite faces of the cube. In defiance of Webster’s definition of an edge, the opposite faces of a cube do not share or intersect at any actual edges at all. Similarly, on a cube, the vertices of the cube are defined by the eight points where certain ones of the edges meet one another, and thus, there are eight of such vertices. However, in the graph theory solution to Instant Insanity, the vertices are defined by lines that extend between the opposite faces of the cube, and there are only three of such vertices, as opposed to the actual reality of there being eight of such vertices. In fact, in graph theory, as noted in this video, it is possible to have an isolated “vertex” with no “edge” connected to it at all, but how does an isolated vertex exist in any geometrical figure in real life? Again, Webster’s defines vertex as being “a point (as of an angle, polygon, polyhedron) that terminates a line or curve or comprises the intersection of two or more lines or curves,” so it’s impossible to have a vertex without having anything connected to it, whereas in graph theory, a lone vertex can just be out there all by itself with nothing connected to it at all. Leave it to mathematicians to make things much more difficult than they need to be. If you are going to use a commonly used term with a given understanding in ordinary life or in another mathematical concept such as geometry, do not use a term which has another meaning that your use of the term contradicts. This should have been an easy one, for “vertex” you could have used the word “node,” and for “edge” you could have used the word “line” or “segment.”
Not sure if it will be seen but I just realized I have a math question I have no idea how to approach that seems up the alley of this channel (general relativity's finite but unbounded universe idea made me think of it). Could a space have properties such that traveling in a straight line can never either take you to some boundary or back to your starting point? Or does an unbounded space always mean you will reach your starting point eventually if you travel far enough in a geodesic?
Interesting video. The solution uses graphs. To me, the interesting part is the part that is left out. Of all the possible graphs you could use to describe the situation, how did you arrive at using colors for vertices, and opposite faces for edges? To me, that choice of graph was not at all obvious, and is only justified because it works. Could you please do another video on how to chhose which graph to use to solve a problem?
The choice of graph comes from thinking about what choices you have when you put a cube on the stack. If you put a particular face on the front side, then you have no control over what face ends up on the back side. You can still rotate the cube to change what is on the left side, but that will immediately fix the face on the right side. The top and bottom are "discarded" since they don't matter to the puzzle. So trying to encode the cubes with graphs focused on opposite faces, and then trying to make the correct choices based on those graphs, is a reasonable approach.
There's something here that you glossed over a bit that I had to stop and think about before realizing it's fine. I was confused where in your construction you guaranteed that just because (for example) red and green are opposite each other and blue and yellow are opposite each other, that you could arrange the cube such that red was left and blue was front. After a while, I realized such a configuration is guaranteed to be possible given my example, provided that you don't care which of the remaining two sides is up and which is down. If you had made a claim about the orientation of the last pair of opposite sides as well, then you wouldn't be able to guarantee such a configuration existed whilst still being an orientation-preserving symmetry of the cube. Background: I'm used to group theoretical problems, so I was considering the groups of cube symmetries, orientation preserving or otherwise.
got a solution for 9:22 I think. But how to express it? SPOILERZZZ - I don't use any of the opposed pairs with matching colour. spoilers, maybe. #1 green at front; blue on left. Remaining 2 relevant sides red. #2 blue at back; UNPAIRED green (ie the green-red) one on the right. Remaining 2 relevant sides red. #3 blue at the front; green on the left- remaining two relevant sides yellow; and #4 green at the back, and blue on the right; remaining two sides yellow. Unused are the yellow-yellow pair of cube 1, the green-green pair of 2, and both red-red pairs in 3 and 4.
Lastly, 9:16 - "Is this the only solution?" Reasonably sure it's the only unique solution, yes. That diagonal of Cube 2's is unusable with the rules. The remaining two "2" lines only obey in the manner demonstrated. But I say unique because you could reverse the arrows (turning the cubes upside down), or swap which mean front/back and left/right (rotating the stack 90°). But these don't add anything per se. they're variants on what's already shown.
the problem has no solution if one of the cubes has one color of two oppsite faces and that color does not appears again on another face. i.e. a cube C has two faces colored by color X (and no more faces colored by X), and those two faces are opposite.
Hi, thanks for the video. Is it a mean to determine a set of cubes than can solve the problem? In other words, who determine the set of cube conbinaison witch have a solution?
ok... without watching past the explanation here is my idea there are 6 ways to orient the first cube (which face is up) rotation does not matter at this point as the rotation will be relative to the first cube then there is 6*4=24 ways to place the second block interate through the 6(first cube) * 24(second cube) = 144 possibilities and remove any that has duplicate colors on the stack sides then go through the N(remaining valid cube1+2) * 24(third cube) = ? posibilities again removing any that have duplicate colors on a side and repeat one more for the last cube Not the most efficient idea but more efficiant than going through every possible combination because in a stack of 4 cubes without duplicate colors on a side any combination of 2 also has no duplicates so why even include the third or fourth block if the first 2 have the same color on the same side
82,944 is the total number of possible configuration, or called search space in graph theory. A “naive brute force” approach is to examine all of them. What you described a “smarter” approach is called pruning. It means exactly to not consider further in the search if a subproblem (2 cubes) already fails any condition.
Henry Miller similar to what you said, but we rotate all blocks on top together with the first block instead of only the first block rotates. This reduces the # of configs by 4 because they are considered the same. Rotation along the up axis of the whole thing does not matter
even with the "cube with all different colored sides as a tool for counting" how many orientations cannot be rotated along the vertical axis into another 6... the answer is 6
Is one supposed to use the non-directed graph, and then just randomly assign the direction (subject to one-in/one-out rule)? That was confusing - I was trying to solve using the directed graph but couldn't, because out of 6 connections, only 1 was in (or only 1 was out, if the convention was reversed). That led to a contradiction that once the edge was used, it couldn't be used again, but would have needed to be to complete both subgraphs. If that correct (that the solution comes from the undirected graph) then I'm curious if there is an application involving using the directed subgraph instead?
Nice. I'm stupid so i'm gonna have to watch every episode of Infinite Series like 10 times, but here I'm wondering if I could use graph theory to train a neural network. Or maybe I could train a neural network to use graph theory to train a neural network...
I got 2 unique solutions for problem 1 and 12 unique solutions for problem 2 (4x if you count flipping all four cubes upside-down or front to back, x24 more if you mix up the cube order). If you number the faces 2 up, 3,4,1,5 , 0 down as shown and rotations 0 none, 1 L, 2 Upside-down, 3 R. Cube:Front-face,rotation {space} next {space} next {space} next 1:1,1 2:3,3 3:4,0 4:4,2 1:4,0 2:5,2 3:3,3 4:1,3 set 2 1:1,1 2:0,0 3:0,3 4:2,3 1:1,1 2:0,0 3:4,1 4:4,3 1:1,1 2:3,2 3:0,1 4:5,1 1:1,1 2:3,2 3:0,3 4:5,3 1:1,1 2:3,2 3:2,1 4:4,3 1:1,1 2:3,2 3:2,3 4:4,1 1:4,0 2:0,2 3:4,1 4:0,1 1:4,0 2:0,2 3:4,3 4:0,3 1:4,0 2:0,2 3:5,1 4:2,3 1:4,0 2:0,2 3:5,3 4:2,1 1:4,0 2:3,0 3:2,3 4:0,3 1:4,0 2:3,0 3:5,3 4:5,1
It doesn't necessarily have to have every color on every cube if you also double up colors on a different cube. It doesn't state that the order of each pattern must be unique. I had the same initial reaction to the first set, because cube 4 didn't have an obvious "different color on each side" arrangement, either.
what about chirality ? The way you show the cubes they each could be folded in two different way. Surely that would affect the existence of solution(s)
I don't understand your reply ? Are you pointing out my comment is stupid ? did I miss something ? I'd be happy if you explained to me why it doesn't impact the result.
In this case chirality does not matter. When you flip let's say left and rigth you also have to flip top and bottom to keep front and back fixed. Top and bottom do not affect the solution so you can freely flip them. Thus chirality does not matter. (I think this should have been explained in the video...)
@Henry Miller, I thought about it a lot and I think he is right, even though you end up with different cube, it doesn't affect the solution or the puzzle. Here is why : in any solution, each cube only display 4 faces (relevant to the solution) 2 are hidden (top and bottom) if the cube is mirrored it actually only change thing for these two hidden faces, which doesn't affect the puzzle
I disagree, only 4 faces are relevant to the solution, the mirror image can always be put such that these 4 faces are the same, only the top and bottom would be swapped, which doesn't affect the solution
I don’t know if I did it right; my solution used those two self loops. In one sub-graph, I used the red self-loop and didn’t have an edge between red and green. In the other, I used the green self-loop and didn’t have an edge between red and blue. Is that OK? Or did I really mess up?
I think you overcounted the number of (distinct) configurations of the cube stack by a factor of two. I'm guessing it's essentially the two that arises from the fact that flipping the entire stack upside down isn't really a new configuration.
I believe the puzzle has only one solution, which makes me wonder: How did they choose these specific cubes? Are there other sets of cubes with only 1 solution?
IQ'biki (android-puzzle) have more 1000 different puzzles. All cubes sets are unique and its can not be obtained from one another by repainting the faces. And there are 204 unique multy-graphs.
Solution to the Second Cube Problem if you are curious: . . . . . . . . . . In order of Front-Back-Left-Right 1st Cube: R-G-B-R 2nd Cube: G-R-R-B 3rd Cube: Y-B-Y-G 4th Cube: B-Y-G-Y
For me it is unclear why number of possible configurations should be 82944 as mentioned in video. For cubes №2 and №4 there are 24 possible positions, for №1 and №3 - there are 12 (two opposite sides of these have the same colour). Also in video I did't hear anything about the rule how we can stack cubes. It is appeared at 9:02 of video that №1 is on the bottom of the stack and №4 on the top - and all cubes in sequence. But is this order mandatory? If it is there are 24 * 12 * 24 * 12 / 4 = 20736 configurations (factor 4 because we can rotate stack around vertical axis) If this order is not mandatory there are 24 * 12 * 24 * 12 * 4! / 4 = 497 667 configurations of the stack So who is wrong?
But HOW do you find this sub-graph? It is not enough to say we can use this method to solve the problem - you should also show HOW this method solve this problem. it is so over complicated that I think there might be a simpler way to solve this - backtracking looks good for that.
I think there's something wrong with the puzzle. I tried to do both configurations by inspection and got them both right away. I thought maybe I just got lucky the first time, but the second was just as easy.
TL;DR I found the same solution a different and more tedious way but I'm happy about it!
I'm so proud of myself that I found my own solution using group theory! When you first posed the puzzle (before mentioning graph theory) I paused and tried it on my own.
Granted, it's not nearly as elegant as the graph theory solution and it's not really generalizable but it worked. I made a permutation group out of the rotational symmetries of the cube (on my paper I represented them like (GG),(RB),(YB) where each double is a front/back face pair. What I wrote as that example is cube 3 if you want to check that what I'm saying makes sense, and the permutations I used were (12),(34),(56) -> (34),(21),(56) to represent a quarter turn on the axis passing through (56) and variations of that).
The second insight was that the duplications of colors meant that the top/bottom faces needed and 2Y, 3R, 1B, 2G so that the sides would have exactly 4 of each color. I treated this as a linear system (well mostly I guess and checked but tried to be methodical in ticking off every possibility) and I found only 5 ways for this to happen (I believe I covered all branching possibilities but I might have missed some IDK).
Finally, I took these possibilities and my group structure and started checking off possible combinations like playing a Sudoku puzzle. I eventually came up with... well the same solution that they showed in this video. So not the most interesting result, but hey!
I know nobody out there probably cares, and this explanation if far from rigorous or even clear but I'm proud of finding this solution on my own and just wanted to share that.
Your next problem should be major one.
Some of us care. Kudos! :)
I just looked at cube three and rotated it around in my head, and realized that the answer is no
It's like... Little bit complex to understand for me.....
In the limit of infinite cubes and infinite colors, is this question NP complete?
it would have been better if you put the graph again on screen when asking to trying it at home...
Pause?
xiaoheidan
exactly my point, if they have put the graph again there, then one can pause it there and immediately go and try it out, but as they don't, then one have to no only pause but to go and search back in the video for the graph, which add a level of annoyance to it...
Agreed. It's nice, and typical in these kinds of videos. In fact, I'm so used to that approach in puzzle videos that I waited for the cut and paused on to work it out, only to realize it was the solution not the graph.
I've been told that people solve puzzles with graph theory but never saw how.
This is the best video ever at explaining it. Thank you.
here from peridiam !!!
Thank you Peridiam for bringing me here
I like how the conditions are motivated by trial and error, because, as far as i can tell, this is an important part of science, even in mathematics. People outside the field need to know that. Great vids. Keep it up.
I skipped the last few Infinite Series videos, but this lured me back. Great video!
Here's my solution for the set of cubes at the end. Notice that if we use any self-loop (edges from a color to itself), we cannot use that color again without violating Condition 3. In fact, subgraph A and B must each be composed of a set of disjoint cycles. So if we use a self-loop on, say, Yellow, we must have a disjoint set of cycles covering Red, Green, and Blue as well. But Green and Blue do not share any edges, and Blue does not have a self-loop, so we can't put {Red, Green, Blue} into a cycle. This means we can't ever use Yellow's self-loop.
This leaves Yellow with four available edges; hence, they must all be used in any solution. We can quickly find one legal solution just by trial and error at this point:
A: {Y -3-> G -4-> Y, R -1-> B -2-> R}
B: {Y -3-> B -4-> Y, R -1-> G -2-> R}
Here's another:
A: {Y -3-> B -2-> R -1-> G -4-> Y}
B: {Y -4-> B -1-> R -2-> G -3-> Y}
Paused the video to try myself. Would have been good at that point to see a diagram of the "combined + directed" graph (which wasn't displayed earlier). I know, 3 minutes with some pens and I could have put it together! Great video though. Thanks!
Lol, my teacher's class schedule had Instant Insanity as one of the topics covered near the end of the semester on the syllabus, and when I read through it, I was like "Oh boy, this is gonna be a fun semester"
Sadly, there is non-zero probability that a set of cubes exactly like those is in this house.
Non-zero, certainly. Did you mean near-zero?
That would have been a much less geeky admission inasmuch as it would allow for a value of zero. Do I exude geekiness? I suspect that most viewers of this video, by virtue of age or interests, could state with absolute certainty that there is not in some nook or cranny within their house a long forgotten copy of Instant Insanity. I am not one such.
kindlin Zero probability doesn't mean something will not happen. Probability that a continuous random variable equals some value is always zero. Yet it will have a value.
Bogdaniec Ze Zbyszka
That is just because people refuse to solve probabilities with non-standard calculus
The instructions for making them existing in a space, by my reckoning, count as them actually existing in that space. Sorta.
*blows dust off top of box containing cubes* I knew I’d need these specifically multi colored set of cubes one day
Cool problem and well-presented! I love it when problems like this can be reduced to mathematical analogies (from graph theory, group theory, combinatorics, etc). Bijections like these are one thing I love about math and that make it so interesting!
There are only 41,472 unique variations. I know because my code found 8 solutions with irrelevant variations (the stack rotated as a whole for 4 solutions and each of those solutions reversed for 4 more). It makes sense though:
There are 3 base sequences on a cube: Front, Left, Back, Right / Front, Top, Back, Bottom / Left, Top, Back, Right.
You can reverse the sequences by flipping a cube over, which doubles the permutations per cube.
You can also rotate each cube in the stack, which multiplies the permutations per cube by 4.
The order of the stack (cube 1 on top rather than on the bottom) doesn't matter, so we won't factor that in.
Thats 24 total permutations per cube and 4 cubes so 24⁴ = 331,776 permutations.
However...
The facing of the stack doesn't matter (we can rotate the whole stack as a unit), only the rotation of the cubes relative to each other matters. This means that one cube shouldn't rotate. You can get every unique stack by rotating the top 3 cubes. The video correctly factored out those variations to get the ~80k number.
Along the same lines, reversing the sequences only matters in relation to the other cubes, so you shouldn't reverse the order of the cube that you don't rotate. That reduces the permutations by another factor of two.
Therefore, one cube only needs the three base variations. So there are only 3 × 24³ = 41,472 unique solutions.
You are right. goole play promocode for iqbiki FJRRMF3PCT3RJDCRNDVV1NE
Got this puzzle in a cereal box in 1970, when I was eight years old. In 1980, I wrote a FORTRAN program to solve it with brute force (6X4)^4 = 331776 permutations. Handed my PUNCH CARDS to my college's mainframe computer operator, and picked up my form-feed printout later. It had timed out without a solution in 5 seconds of CPU time (the maximum allowed, LOL). A few years later I bugged my girlfriend in university to use her computer time. She entered the code on a terminal, and picked up the printout. It took 35 CPU seconds, and it was solved. She chewed me out because that was 1/3 of the total time allowed for her entire computer science semester! But I was was HAPPY.
Correct me if I am wrong, but the solution seems to be wrong as in 7:22 there is an edge from B->Y labelled 3, however, in the final solution there is an edge from Y->B labelled 3.
There were numbers, you promised there wouldn't.
Great video, very cool to learn about graph theory.
Regarding the 2 questions you asked, I found that :
1) no other configuration
2) there are 2 configurations
F/B : (R)>1>(G)>4>(Y)>3>(B)>2>(R) and L/R : (R)(R) and L/R : (R)
This was a great video that was really easy to follow but still rewarding for the simplicity of answering the _Instant Insanity Puzzle!!_ lol
It is an interesting use of graph. If you only hinted us to use graph theory on the cubes, I think my search space would be from {}->{Cube1(orientation1)}->{Cube1(1)Cube2(1)}...
That would be a very large tree. Look at the graph of your approach, it is genius!
I think the mixed reaction of the viewers are some of them couldn’t have get this appreciation. And the finale was a bit too plain. There could be an animation showing how you pick the edges from the curvy graph, and thus we could understand the conditions better.
An animation worths ten thousand words :)
As soon as the cubes were presented, with "can you find a solution," I whipped out Z3 and asked it to find a solution for me. SAT solvers are always the answer.
So once i learned the combinatorial trick behind this simple yet great puzzle,
I made my own one with 8 cubes the mission is to build the perfect 6 sided cube.
My little brother enjoyed it well (but of course he failed :) )
This puzzle is good case to see how our intuition sometimes could be best approach to problems without meta-level logic on our hands.
this is the first time graph theory made sense in a practical sort of way.
I paused before the title card and solved the first set in about 3 minutes. First I figured out which two opposite faces on each cube should be hidden by being the tops and bottoms. There were 7 red, 6 yellow, 6 green, and 5 blue faces, so we need to hide 3 red, 2 yellow, 2 green, and 1 blue. It was lucky that the answer is to hide the squares shown at the top and bottom of each diagram - none of the unwrapped cubes were permuted in a more complex way. Then starting by going left to right on the first cube, I found a starting point and direction of the rest that gave unique colors for each face of the stack. The answer is: 1. start at red going right, 2. start at blue going right, 3. start at yellow going right, and 4. start at the right side green, going left. That just means you will flip cube 4 upside down when stacking it.
This was surprisingly easy just using logic.
The cubes can be considered strips of 4 sides (because the top and bottom don't matter), which can be formed in three ways from each cube's colors.
You inevitably have to have the same total number of each color. I chose strips from each cube such that they compensated for any excess/lack of other cubes, wrote those in a text editor as RYGB etc. and used rotations and flips to find a permutation where it worked. Took about 5 minutes...perhaps I was lucky with my choice of strips, or perhaps most or all combinations which satisfy the color count matches work.
Haven't finished the video yet, so don't know if my answer is the same or if my method is partially isomorphic to what is presented.
That seems like a neat thing to code in Prolog
Goodbye Infinite Series.
I nearly didn't watch this. I don't know why because this is a great video
I paused right after you posed the question, figured it out, then unpaused and saw you made templates. That would have helped during the problem lol.
As for multiple solutions, I believe there is only one (besides the same tower rotated, or the blocks' orders changed). When I was solving the puzzle, I logically deduced things that had to be true of any solution to the problem, and I ended up with only one configuration which satisfied all of them.
what i find interesting and I don't know if this was done for the purpose of the demonstration but when all of the cubes are laid out - the four faces that are used are all the ones where the four are connected in the middle. The top and bottom of the cube, how it would sit, are the square on the top and bottom of the exploded cube. Obviously the cubes could be exploded in multiple manners this was just interesting to me that it ended up that way. My guess is the early shot of the exploded cubes was actually arrived at by working backwards.
It was incredibly well-presented, I loved how straightforward and engaging your explanation was, but How many subgraphs can be drawn that satisfy the conditions?
This was very cool, would love to see more in this style.
Correct me if I'm wrong, but (taking Cube 2 as our example), can't the undirected graphs for a cube represent _two_ different cubes? One is the chiral pair of the other, and they're distinct from each other! We need the arrows to capture this distinction: flipping a single arrow gives us the chiral sibling of the cube -- unless we happened to flip along an axis that the cube _does_ have mirror symmetry on, as you slyly did at 3:10.
Also, Condition 4 arises only because of the specific set of cubes we've picked. In your example at 8:28, technically there is no problem with having red appear twice -- we do have _three_ red sides available to us. If we had a cube with two pairs of red/green sides opposing each other, with (say) blue and yellow on the third opposing pair, Condition 4 would not necessarily hold. We actually need to prove Condition 4 for each cube individually: the graph of no cube has more than one edge between vertices.
It's definitely true that in the context of Instant Insanity, we don't care about the chirality of a solution -- finding a solution with one set of cubes gives us a solution where any cube is swapped for its chiral twin. But that wasn't how it was presented in the video.
I was being a bit too loose when I was talking about Condition 4 -- thanks for keeping me honest. I was more concerned with the example being given, which could give the impression that the problem is the duplicate colors, not the lack of another pair. To be fair, I probably just read too much into that line.
Just sat down to this with some T
Oh boy, instant insanity!
Brilliant way to show graph theory solving a problem. thanks! I think there are 3 solutions to the puzzle at the end of the video.
1. The Instant Insanity have only one GRAPHICAL solution, but for this solution exists 8 spatially different combinations of cubes positions.
2. Second set of cubes (9:22) have two graphical solutions and it is wrong puzzle.
And notes from me:
A. 1:09 - The first cube in the sequence is enough to be positioned in three ways, have placing it on one side of three opposite pairs of faces, accordingly: there are 3x24x24x24 = 41,472 possible arrangements of the four cubes, and 8 of these give a valid solution (alone graphical solution, but 8 spatially different combinations, see above). 82,944 is wrong number.
B. 9:05 - What does the phrase "Solution due to Robin Wilson, Emeritus Professor of Mathematics at Open University" mean? - The graphical solution of four cubes problem have first been published in 1947 by "F. de Carteblanche" (pseudonym for the team of four friends - Cambridge students: R.L. Brooks, C.A.B. Smith, A.H. Stone and W.T. Tutte) in Eureka No. 9, April 1947 (the undergraduate mathematics magazine of Cambridge University) - "The Coloured Cubes Problem", pp.9-11. And here is there a respected professor?
С. "Print off a template for the cubes shown in the video!" - Franz O. Armbruster completely copied the puzzle from genius Frederick A. Schossow, changing only two not visible faces from one cube. It's hard to believe that this man had an imagination, but it was he who came up with the name «Instant Insanity». How long will we replicate the same set? There are many other variations of the puzzle of the four cubes. In the android puzzle IQ'biki are over 1000.
To add to my previous comment, what happens when you replace the cubes with triangular prisms, or any regular prisms with an odd number of sides? What graph do you use? How do you define its edges?
Graph theory, the oldest nemesis from my rogues gallery.
This instalment moved deceptively quick! I'm going to need another round.
This was wonderful! I feel like you’re finding your feet on this channel. Was a great choice of topic as you were able to explain the whole thing with no "magic", while still tying in the larger mathematical ideas.
there are 6 solutions to the challenge at the end, the limited number of blues restricts the problem a lot as blue can't be on the inside of the column, solutions spoilers below, but without explicit construction of the graphs:
the insides colours must be 4 red, 2yellow and 2green and the options for insides colours for each cube are:
1 YY or GR
2 GG or GR
3 RR or GY
4 RR or GY
if 1 is YY then 3 and 4 must be RR as can't have more yellows on the inside which requires 2 to be GG, if 1 is GR 2 must be GR or can't get 4 reds (odd/even issue) then we have two green inside so 3 and 4 must be RR but then we have too many redh and no yellows so 1 can't be GR by contradiction. so middle is 1YY 2GG 3RR 4RR.
then 1 and 2 have two distinct possible arrangements that dons't put two of the same colour in the same column, same with 3 and 4, which pair up but one pair has 4 relative rotations that work and the other has 2:
RGBR RGBR or RGBR RGBR or RGBR RGBR
BRRG BRRG BRRG BRRG GRRB GRRB
YYGB GBYY GYYB GBYY BYYG YBGY
GBYY YYGB YBGY YYGB YBGY BYYG
snap, time to put a thinking cap on. the one with a propeller for extra cooling
Hello mom
Yes, there is only one solution, it was quite fun, and you could solve it like a Sudoku.
For the extra question, it was quite simple actually since the blue side only appeared four times and so it made it a bit simpler
Blue appeared 5 times.
Too good
I did not follow how graph theory was useful here but I solved both puzzles in about 2 minutes with just pen and paper. For the first puzzle I had the same answer as in the video. For the second puzzle I have:
1. RRGB
2. GBRR
3. YYBG
4. BGYY
each cube has at most 6 unique orientations. 1 for each of the 3 dimensions, and a mirrored copy by flipping each dimension.
in some cases flipping doesn't change the state, leaving that cube with less unique orientations.
The cubes 1,2,3,4 had 4,6,4,6 unique orientations. Single and double repeats of a color in an orientation were easy to eliminate, as they required being matched with at least one orientation from the other cubes not containing that color, and contradictions showed up quick.
Had a solution a lot quicker than using the graph method, but i can definitely see the graph method being ideal for bigger problems.
for the cubes at the end there are even less orientations and they're easier to eliminate, because there is zero yellow orientations for cube 2
Each cube has at most _24_ unique orientations: Fix the face on top (or in any other position, it doesn't matter) and rotate the cube keeping the top face fixed. For each of the six faces, there are four orientations. Of course, if a cube has a pair of opposite sides that are the same colour, that reduces the number of distinct orientations.
Nillie I didn't consider rotations to be unique orientations. As for this particular problem its clear when two orientations are incompatible e.g. [G,G,R,Y] AND [B,G,R,G] Rotations will fail to make these two cubes compatible because of the G's. And that's just one of many such incompatibilities
Kadmilos Somnium
When you combine cubes into stacks, the orientation of each individual cube _does_ matter, though the order of the cubes in the stack does not, nor does the orientation of the stack as a whole. As such, a stack of four cubes can have at most (24^4)/(4*2) distinct permutations, which is significantly more than the 6^4 you’re saying it can have. (Since the 24^4 only specifies the orientation of each cube, not their order, we don’t need to divide by 4!, though we do need to divide by 4 since the orientation of the cubes only matters relative to the other cubes, and we also need to divide by 2 since flipping every cube upside down doesn’t change the stack as a whole.)
When writing down the possible cycles of four sides on each cube, I noticed that there is one cycle which appears on both cube 1 and cube 4: RYGB (or YGBR or GBYR or YRBG or... you get the picture).
infiniTe is missing a T
Where?
No
Using Graph Theory this puzzle have exactly four equivalent solutions.... It's '4' because of rotational symmetry of the whole stack.
disappointed Infinite Series does not have Infinity War-related topic today. Opportunity missed
I admit, I solved both sets of cubes by inspection rather than by using graphs - for the second set, there are only 4 blue faces total, which drastically limits the possibilities, as does 3 and 4 being the same cube - if either of them has double red as their second pair of faces, then avoiding having a 5th red while keeping the 4 blues leaves you with 5 yellows and 3 greens, so 3 and 4 have to have their reds on top/bottom, meaning cubes 1 and 2 have to supply all 4 reds between them. The reds and yellows come in adjacent pairs, while the greens and blues are one per cube, so they can be arranged as required.
I do have two corrections/suggestions for the video:
Firstly, I think the 82944 is either an over- or an under-count - each cube can be oriented in 24 ways and still form a stack occupying the same space, and you can rotate the entire stack about its vertical axis to give 4-fold symmetry, which is presumably where the 82944 comes from, but you can also flip each cube about its front-back axis, effectively reflecting the stack (swapping left and right faces on every cube) since we're ignoring the top and bottom faces entirely, giving another factor of 2 (equivalently, you could flip the entire stack end for end and then reverse the order of the cubes, meaning each of the 8 rotational symmetries of the stack gives rise to a variation of the same solution), making only 41472 distinct arrangements.
Secondly, when displaying the tables of colours and positions associated with graphs A and B, it's confusing to have the columns go front, back, left, right, since it means that the arrows on graph A are pointing to the left of the table (to front, from back) while the arrows on B are pointing to the right of the table (from left, to right) - it would be more natural to have the columns in order back, front, left, right so that going from source to sink moves from left to right across the table in all cases.
Haven't fully watched the video, but this seems like an Einstein Problem.
6 × 24 × 24 × 24 = wee 82944 arrangements. Perfectly bruteforceable.
Only 41,472
Promo code for a similar puzzle (Google Play, free still 29 july) 5EV4EQUQ9UQAFBX5US49HWB
Now, I may well be wrong---I don't have a printer handy, so I can't really try it for myself---but it seems to me that if you hand a human these cubes and ask them to solve the problem, they probably would fairly quickly. That's not to say that the mathematical solution isn't interesting, just that I think the human intuition (read: fast subconscious pattern-matching algorithms) solution is pretty cool to think about as well.
One of the things I have always hated about graph theory, the little I know about it, is how hard it is to understand the subject at an introductory level, in large part due to the terminology used. For example, when two nodes (oddly referred to as “vertices”) of a graph are connected by a line (or curve), again oddly, such a line is referred to as an “edge.”
A problem with this odd use of terminology comes up in the graph theory solution to “Instant Insanity,” the puzzle sold in the sixties by Parker Brothers. In this case, if one thinks about Webster’s definition of edge as being “a line or line segment that is the intersection of two plane faces (as of a pyramid) or of two planes,” we can see that on a six-sided cube, there are twelve of such edges. Contrary to this common understanding, in the graph theory solution to Instant Insanity, an edge is defined as being between two opposite faces of the cube. In defiance of Webster’s definition of an edge, the opposite faces of a cube do not share or intersect at any actual edges at all.
Similarly, on a cube, the vertices of the cube are defined by the eight points where certain ones of the edges meet one another, and thus, there are eight of such vertices. However, in the graph theory solution to Instant Insanity, the vertices are defined by lines that extend between the opposite faces of the cube, and there are only three of such vertices, as opposed to the actual reality of there being eight of such vertices. In fact, in graph theory, as noted in this video, it is possible to have an isolated “vertex” with no “edge” connected to it at all, but how does an isolated vertex exist in any geometrical figure in real life? Again, Webster’s defines vertex as being “a point (as of an angle, polygon, polyhedron) that terminates a line or curve or comprises the intersection of two or more lines or curves,” so it’s impossible to have a vertex without having anything connected to it, whereas in graph theory, a lone vertex can just be out there all by itself with nothing connected to it at all.
Leave it to mathematicians to make things much more difficult than they need to be. If you are going to use a commonly used term with a given understanding in ordinary life or in another mathematical concept such as geometry, do not use a term which has another meaning that your use of the term contradicts. This should have been an easy one, for “vertex” you could have used the word “node,” and for “edge” you could have used the word “line” or “segment.”
Not sure if it will be seen but I just realized I have a math question I have no idea how to approach that seems up the alley of this channel (general relativity's finite but unbounded universe idea made me think of it). Could a space have properties such that traveling in a straight line can never either take you to some boundary or back to your starting point? Or does an unbounded space always mean you will reach your starting point eventually if you travel far enough in a geodesic?
Interesting video. The solution uses graphs. To me, the interesting part is the part that is left out. Of all the possible graphs you could use to describe the situation, how did you arrive at using colors for vertices, and opposite faces for edges? To me, that choice of graph was not at all obvious, and is only justified because it works. Could you please do another video on how to chhose which graph to use to solve a problem?
The choice of graph comes from thinking about what choices you have when you put a cube on the stack. If you put a particular face on the front side, then you have no control over what face ends up on the back side. You can still rotate the cube to change what is on the left side, but that will immediately fix the face on the right side. The top and bottom are "discarded" since they don't matter to the puzzle. So trying to encode the cubes with graphs focused on opposite faces, and then trying to make the correct choices based on those graphs, is a reasonable approach.
There's something here that you glossed over a bit that I had to stop and think about before realizing it's fine. I was confused where in your construction you guaranteed that just because (for example) red and green are opposite each other and blue and yellow are opposite each other, that you could arrange the cube such that red was left and blue was front. After a while, I realized such a configuration is guaranteed to be possible given my example, provided that you don't care which of the remaining two sides is up and which is down. If you had made a claim about the orientation of the last pair of opposite sides as well, then you wouldn't be able to guarantee such a configuration existed whilst still being an orientation-preserving symmetry of the cube.
Background: I'm used to group theoretical problems, so I was considering the groups of cube symmetries, orientation preserving or otherwise.
We want Kelsey back
-No math
-Cubes are labelled with numbers
*AAAAAAAAAAHHHHHH*
got a solution for 9:22 I think. But how to express it? SPOILERZZZ - I don't use any of the opposed pairs with matching colour.
spoilers, maybe.
#1 green at front; blue on left. Remaining 2 relevant sides red.
#2 blue at back; UNPAIRED green (ie the green-red) one on the right. Remaining 2 relevant sides red.
#3 blue at the front; green on the left- remaining two relevant sides yellow; and
#4 green at the back, and blue on the right; remaining two sides yellow.
Unused are the yellow-yellow pair of cube 1, the green-green pair of 2, and both red-red pairs in 3 and 4.
interestingly, Cubes 1 and 2 are interchangeable in this solution, as are cubes 3 and 4. I suspect this is intentional. ;)
Lastly, 9:16 - "Is this the only solution?"
Reasonably sure it's the only unique solution, yes. That diagonal of Cube 2's is unusable with the rules. The remaining two "2" lines only obey in the manner demonstrated.
But I say unique because you could reverse the arrows (turning the cubes upside down), or swap which mean front/back and left/right (rotating the stack 90°). But these don't add anything per se. they're variants on what's already shown.
amazing! thank you!!!
I don't see how the task of finding the two subgraphs is any easier than the original stated puzzle of manipulating the cubes.
the problem has no solution if one of the cubes has one color of two oppsite faces and that color does not appears again on another face. i.e. a cube C has two faces colored by color X (and no more faces colored by X), and those two faces are opposite.
Hi, thanks for the video.
Is it a mean to determine a set of cubes than can solve the problem?
In other words, who determine the set of cube conbinaison witch have a solution?
What an amazing host but an even better problem.
How did you arrive at the number of possible distinct arrangements of the four cubes is equal to 82,944?
How did you calculate 82,944 possible arrangements of the 4 cubes?
ok... without watching past the explanation here is my idea
there are 6 ways to orient the first cube (which face is up) rotation does not matter at this point as the rotation will be relative to the first cube
then there is 6*4=24 ways to place the second block
interate through the 6(first cube) * 24(second cube) = 144 possibilities
and remove any that has duplicate colors on the stack sides
then go through the N(remaining valid cube1+2) * 24(third cube) = ? posibilities
again removing any that have duplicate colors on a side
and repeat one more for the last cube
Not the most efficient idea but more efficiant than going through every possible combination
because in a stack of 4 cubes without duplicate colors on a side any combination of 2 also has no duplicates
so why even include the third or fourth block if the first 2 have the same color on the same side
82,944 is the total number of possible configuration, or called search space in graph theory. A “naive brute force” approach is to examine all of them. What you described a “smarter” approach is called pruning. It means exactly to not consider further in the search if a subproblem (2 cubes) already fails any condition.
Henry Miller just as Bryan says, the first cube’s rotation does not matter, only which face is up matters. So there is 6 * 24^3 = 82944
Henry Miller similar to what you said, but we rotate all blocks on top together with the first block instead of only the first block rotates. This reduces the # of configs by 4 because they are considered the same. Rotation along the up axis of the whole thing does not matter
Henry Miller 6*24*24*24. May be you count the number with only 2 blocks first. You shall see why there is 6*24 instead of 24*24.
even with the "cube with all different colored sides as a tool for counting"
how many orientations cannot be rotated along the vertical axis into another
6...
the answer is 6
Hmmm. I'm just going to look online for a straight jacket. What color do you think I should get it in? Red, blue, yellow or perhaps green :)
🐣 Is there a polynomial-time algorithm to find this subgraph? Or is it known to be NP-hard by reducing to what problem?
Is one supposed to use the non-directed graph, and then just randomly assign the direction (subject to one-in/one-out rule)? That was confusing - I was trying to solve using the directed graph but couldn't, because out of 6 connections, only 1 was in (or only 1 was out, if the convention was reversed). That led to a contradiction that once the edge was used, it couldn't be used again, but would have needed to be to complete both subgraphs. If that correct (that the solution comes from the undirected graph) then I'm curious if there is an application involving using the directed subgraph instead?
Nice. I'm stupid so i'm gonna have to watch every episode of Infinite Series like 10 times, but here I'm wondering if I could use graph theory to train a neural network.
Or maybe I could train a neural network to use graph theory to train a neural network...
I got 2 unique solutions for problem 1 and 12 unique solutions for problem 2 (4x if you count flipping all four cubes upside-down or front to back, x24 more if you mix up the cube order). If you number the faces 2 up, 3,4,1,5 , 0 down as shown and rotations 0 none, 1 L, 2 Upside-down, 3 R.
Cube:Front-face,rotation {space} next {space} next {space} next
1:1,1 2:3,3 3:4,0 4:4,2
1:4,0 2:5,2 3:3,3 4:1,3
set 2
1:1,1 2:0,0 3:0,3 4:2,3
1:1,1 2:0,0 3:4,1 4:4,3
1:1,1 2:3,2 3:0,1 4:5,1
1:1,1 2:3,2 3:0,3 4:5,3
1:1,1 2:3,2 3:2,1 4:4,3
1:1,1 2:3,2 3:2,3 4:4,1
1:4,0 2:0,2 3:4,1 4:0,1
1:4,0 2:0,2 3:4,3 4:0,3
1:4,0 2:0,2 3:5,1 4:2,3
1:4,0 2:0,2 3:5,3 4:2,1
1:4,0 2:3,0 3:2,3 4:0,3
1:4,0 2:3,0 3:5,3 4:5,1
I think there’s an error in the notation at the bottom of the graphic at 7:20. It should say BACK -> FRONT instead of LEFT -> RIGHT.
I thought the cubes you gave us was impossible because Red and blue are not on opposite sides on any of the cubes. But now I stand corrected.
And cube two has no yellow!
RGBR 1
GRRB 2
YBGY 3
BYYG 4
(And red and blue are opposite on both cube one and cube two.)
It doesn't necessarily have to have every color on every cube if you also double up colors on a different cube. It doesn't state that the order of each pattern must be unique. I had the same initial reaction to the first set, because cube 4 didn't have an obvious "different color on each side" arrangement, either.
Oh yeah, whoops
Michael Wade thanks I see my mistake lol.
Now I have realized that I have made several and that I might be color blind lol.
Exactly 41,472 possibilities (3*24*24*24)
*So you are wrong *
8:40 Conditions #4: The SUBgraphs [...]
thank g-d for @fleb
what about chirality ? The way you show the cubes they each could be folded in two different way. Surely that would affect the existence of solution(s)
Jimmy HUGUET Really..!!
I don't understand your reply ? Are you pointing out my comment is stupid ? did I miss something ? I'd be happy if you explained to me why it doesn't impact the result.
In this case chirality does not matter. When you flip let's say left and rigth you also have to flip top and bottom to keep front and back fixed. Top and bottom do not affect the solution so you can freely flip them. Thus chirality does not matter. (I think this should have been explained in the video...)
@Henry Miller, I thought about it a lot and I think he is right, even though you end up with different cube, it doesn't affect the solution or the puzzle. Here is why : in any solution, each cube only display 4 faces (relevant to the solution) 2 are hidden (top and bottom) if the cube is mirrored it actually only change thing for these two hidden faces, which doesn't affect the puzzle
I disagree, only 4 faces are relevant to the solution, the mirror image can always be put such that these 4 faces are the same, only the top and bottom would be swapped, which doesn't affect the solution
As always, your videos are the most challenging!
Gabe's are too, but not as yours
Anyone else come here from Peridiam/Survivor?
I don’t know if I did it right; my solution used those two self loops. In one sub-graph, I used the red self-loop and didn’t have an edge between red and green. In the other, I used the green self-loop and didn’t have an edge between red and blue. Is that OK? Or did I really mess up?
I think you overcounted the number of (distinct) configurations of the cube stack by a factor of two. I'm guessing it's essentially the two that arises from the fact that flipping the entire stack upside down isn't really a new configuration.
Yeah, I got that too
Or any permutations the cube order.
Infinie series?
I believe the puzzle has only one solution, which makes me wonder:
How did they choose these specific cubes?
Are there other sets of cubes with only 1 solution?
IQ'biki (android-puzzle) have more 1000 different puzzles. All cubes sets are unique and its can not be obtained from one another by repainting the faces. And there are 204 unique multy-graphs.
Of course it isn't the only solution you could just swap any of the cubes with the other... permutations i mean
Solution to the Second Cube Problem if you are curious:
.
.
.
.
.
.
.
.
.
.
In order of Front-Back-Left-Right
1st Cube: R-G-B-R
2nd Cube: G-R-R-B
3rd Cube: Y-B-Y-G
4th Cube: B-Y-G-Y
Peridiam
I'm still unclear as to why you chose to connect opposite instead of adjacent faces. That's not at all obvious to me.
For me it is unclear why number of possible configurations should be 82944 as mentioned in video. For cubes №2 and №4 there are 24 possible positions, for №1 and №3 - there are 12 (two opposite sides of these have the same colour). Also in video I did't hear anything about the rule how we can stack cubes. It is appeared at 9:02 of video that №1 is on the bottom of the stack and №4 on the top - and all cubes in sequence. But is this order mandatory? If it is there are
24 * 12 * 24 * 12 / 4 = 20736 configurations (factor 4 because we can rotate stack around vertical axis)
If this order is not mandatory there are
24 * 12 * 24 * 12 * 4! / 4 = 497 667 configurations of the stack
So who is wrong?
But HOW do you find this sub-graph?
It is not enough to say we can use this method to solve the problem - you should also show HOW this method solve this problem.
it is so over complicated that I think there might be a simpler way to solve this - backtracking looks good for that.
Anyone else think Gabe's videos are better?
Says "we'll be be using math with no numbers" then numbers the cubes and edges.
Gordon Charlton in fairness, she could have used letters. No math was done "with" the numbers. Though you’re probably making a joke lol.
made me chuckle too :)
I think there's something wrong with the puzzle. I tried to do both configurations by inspection and got them both right away. I thought maybe I just got lucky the first time, but the second was just as easy.
Same for me. So much for insanity.
These cubes violate ADA
The host is really great.
Infinite series?