Instant Insanity Puzzle | Infinite Series

Поделиться
HTML-код
  • Опубликовано: 4 дек 2024

Комментарии • 204

  • @dayliss413
    @dayliss413 6 лет назад +115

    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.

    • @koohoo4500
      @koohoo4500 6 лет назад

      Your next problem should be major one.

    • @ArawnOfAnnwn
      @ArawnOfAnnwn 6 лет назад +6

      Some of us care. Kudos! :)

    • @ghostcontrollingameatsuit5119
      @ghostcontrollingameatsuit5119 6 лет назад +1

      I just looked at cube three and rotated it around in my head, and realized that the answer is no

    • @soumyadipchottopadhay9509
      @soumyadipchottopadhay9509 6 лет назад

      It's like... Little bit complex to understand for me.....

    • @pierrecurie
      @pierrecurie 6 лет назад

      In the limit of infinite cubes and infinite colors, is this question NP complete?

  • @copperfield42
    @copperfield42 6 лет назад +163

    it would have been better if you put the graph again on screen when asking to trying it at home...

    • @xiaoheidan
      @xiaoheidan 6 лет назад

      Pause?

    • @copperfield42
      @copperfield42 6 лет назад +12

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

    • @ardemus
      @ardemus 6 лет назад +2

      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.

  • @MarkAhlquist
    @MarkAhlquist 6 лет назад +15

    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.

  • @Quetzal00358
    @Quetzal00358 3 года назад +1

    Thank you Peridiam for bringing me here

  • @poverty9696
    @poverty9696 3 года назад +8

    here from peridiam !!!

  • @MrTheHazelnut
    @MrTheHazelnut 6 лет назад +5

    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.

  • @lmelior
    @lmelior 6 лет назад +3

    I skipped the last few Infinite Series videos, but this lured me back. Great video!

  • @stevethecatcouch6532
    @stevethecatcouch6532 6 лет назад +51

    Sadly, there is non-zero probability that a set of cubes exactly like those is in this house.

    • @kindlin
      @kindlin 6 лет назад

      Non-zero, certainly. Did you mean near-zero?

    • @stevethecatcouch6532
      @stevethecatcouch6532 6 лет назад +3

      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.

    • @bogdanieczezbyszka6538
      @bogdanieczezbyszka6538 6 лет назад +4

      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.

    • @Theraot
      @Theraot 6 лет назад

      Bogdaniec Ze Zbyszka
      That is just because people refuse to solve probabilities with non-standard calculus

    • @MarkAhlquist
      @MarkAhlquist 6 лет назад +1

      The instructions for making them existing in a space, by my reckoning, count as them actually existing in that space. Sorta.

  • @Twisol
    @Twisol 6 лет назад +8

    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}

  • @ChrisWalshZX
    @ChrisWalshZX 6 лет назад +13

    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!

  • @hikariwuff
    @hikariwuff 4 года назад +1

    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"

  • @anupaglawe5371
    @anupaglawe5371 5 лет назад +1

    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.

  • @Chris_Goulet
    @Chris_Goulet Год назад

    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.

  • @michaelmilson7538
    @michaelmilson7538 Год назад

    *blows dust off top of box containing cubes* I knew I’d need these specifically multi colored set of cubes one day

  • @alkankondo89
    @alkankondo89 6 лет назад +1

    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!

  • @Twisol
    @Twisol 6 лет назад +8

    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.

    • @Twisol
      @Twisol 6 лет назад +2

      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.

    • @Twisol
      @Twisol 6 лет назад +2

      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.

  • @stickfigure42
    @stickfigure42 6 лет назад

    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.

  • @kindlin
    @kindlin 6 лет назад +1

    This was a great video that was really easy to follow but still rewarding for the simplicity of answering the _Instant Insanity Puzzle!!_ lol

  • @retepaskab
    @retepaskab 6 лет назад +5

    There were numbers, you promised there wouldn't.

  • @ardemus
    @ardemus 6 лет назад +2

    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.

    • @nailer196
      @nailer196 6 лет назад

      You are right. goole play promocode for iqbiki FJRRMF3PCT3RJDCRNDVV1NE

  • @OnlyPenguian
    @OnlyPenguian 6 лет назад +1

    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?

  • @burthpinmc5489
    @burthpinmc5489 6 лет назад +1

    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.

  • @snowballeffect7812
    @snowballeffect7812 6 лет назад

    this is the first time graph theory made sense in a practical sort of way.

  • @ethancheung1676
    @ethancheung1676 6 лет назад +1

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

  • @alre9766
    @alre9766 6 лет назад

    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)

  • @nailer196
    @nailer196 6 лет назад

    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.

  • @KaylixYT
    @KaylixYT 6 лет назад +6

    Just sat down to this with some T

  • @rmsgrey
    @rmsgrey 6 лет назад +5

    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.

  • @paintingjo6842
    @paintingjo6842 6 лет назад +1

    That seems like a neat thing to code in Prolog

  • @cecilsmith24
    @cecilsmith24 2 года назад

    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.

  • @zebionic
    @zebionic 6 лет назад

    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.

  • @AgentMidnight
    @AgentMidnight 6 лет назад

    This was very cool, would love to see more in this style.

  • @Tesserex
    @Tesserex 6 лет назад

    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.

  • @zax1998LU
    @zax1998LU 6 лет назад

    I nearly didn't watch this. I don't know why because this is a great video

  • @kingkiller1451
    @kingkiller1451 6 лет назад

    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?

  • @steliostoulis1875
    @steliostoulis1875 6 лет назад +4

    What an amazing host but an even better problem.

  • @Topples7
    @Topples7 6 лет назад

    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.

  • @brendanlancaster8564
    @brendanlancaster8564 6 лет назад

    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.

  • @mheermance
    @mheermance 6 лет назад

    Graph theory, the oldest nemesis from my rogues gallery.

  • @ragnkja
    @ragnkja 6 лет назад

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

  • @LIQUIDSNAKEz28
    @LIQUIDSNAKEz28 6 лет назад +8

    infiniTe is missing a T

  • @braydenpreston7659
    @braydenpreston7659 6 лет назад

    disappointed Infinite Series does not have Infinity War-related topic today. Opportunity missed

  • @touisbetterthanpi
    @touisbetterthanpi 6 лет назад

    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.

  • @MrConverse
    @MrConverse 6 лет назад

    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.

  • @TheyCallMeNewb
    @TheyCallMeNewb 6 лет назад

    This instalment moved deceptively quick! I'm going to need another round.

  • @X-Gen-001
    @X-Gen-001 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 :)

  • @15october91
    @15october91 6 лет назад +2

    Goodbye Infinite Series.

  • @morkovija
    @morkovija 6 лет назад

    snap, time to put a thinking cap on. the one with a propeller for extra cooling

  • @soumyadipchottopadhay9509
    @soumyadipchottopadhay9509 6 лет назад

    Using Graph Theory this puzzle have exactly four equivalent solutions.... It's '4' because of rotational symmetry of the whole stack.

  • @robknight407
    @robknight407 7 месяцев назад

    How did you arrive at the number of possible distinct arrangements of the four cubes is equal to 82,944?

  • @endymionrhadamantha2799
    @endymionrhadamantha2799 6 лет назад

    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?

  • @flmbray
    @flmbray 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?

  • @jeshweedleon3960
    @jeshweedleon3960 6 лет назад

    Haven't fully watched the video, but this seems like an Einstein Problem.

  • @DaviddeKloet
    @DaviddeKloet 6 лет назад

    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

  • @Khazam1992
    @Khazam1992 6 лет назад

    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.

  • @StevieRZ
    @StevieRZ 6 лет назад

    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

  • @TheBenenene10
    @TheBenenene10 6 лет назад +8

    Hello mom

  • @OnlyPenguian
    @OnlyPenguian 6 лет назад +1

    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?

    • @zmaj12321
      @zmaj12321 Год назад

      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.

  • @JohnDlugosz
    @JohnDlugosz 3 года назад

    I don't see how the task of finding the two subgraphs is any easier than the original stated puzzle of manipulating the cubes.

  • @WJiam-k6n
    @WJiam-k6n Год назад

    🐣 Is there a polynomial-time algorithm to find this subgraph? Or is it known to be NP-hard by reducing to what problem?

  • @itisALWAYSR.A.
    @itisALWAYSR.A. 6 лет назад

    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.

    • @itisALWAYSR.A.
      @itisALWAYSR.A. 6 лет назад

      interestingly, Cubes 1 and 2 are interchangeable in this solution, as are cubes 3 and 4. I suspect this is intentional. ;)

    • @itisALWAYSR.A.
      @itisALWAYSR.A. 6 лет назад

      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.

  • @darylewalker6862
    @darylewalker6862 6 лет назад

    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?

  • @JorgetePanete
    @JorgetePanete 6 лет назад

    -No math
    -Cubes are labelled with numbers
    *AAAAAAAAAAHHHHHH*

  • @wataripg
    @wataripg 2 года назад

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

  • @manuelsalazar5257
    @manuelsalazar5257 6 лет назад

    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

    • @Topples7
      @Topples7 6 лет назад

      Blue appeared 5 times.

  • @stevenbanton5073
    @stevenbanton5073 6 лет назад

    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?

  • @paulbalog8614
    @paulbalog8614 3 года назад

    Oh boy, instant insanity!

  • @RobertKnight-em7gu
    @RobertKnight-em7gu 7 месяцев назад

    How did you calculate 82,944 possible arrangements of the 4 cubes?

  • @tildessmoo
    @tildessmoo 6 лет назад

    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.

  • @guiunit5908
    @guiunit5908 3 года назад

    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

  • @kadmilossomnium
    @kadmilossomnium 6 лет назад

    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.

    • @kadmilossomnium
      @kadmilossomnium 6 лет назад

      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

    • @ragnkja
      @ragnkja 6 лет назад

      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.

    • @kadmilossomnium
      @kadmilossomnium 6 лет назад

      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

    • @ragnkja
      @ragnkja 6 лет назад

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

  • @janApen
    @janApen 6 лет назад

    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.

    • @aelolul
      @aelolul 6 лет назад

      And cube two has no yellow!

    • @PvblivsAelivs
      @PvblivsAelivs 6 лет назад

      RGBR 1
      GRRB 2
      YBGY 3
      BYYG 4
      (And red and blue are opposite on both cube one and cube two.)

    • @NotHPotter
      @NotHPotter 6 лет назад +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.

    • @aelolul
      @aelolul 6 лет назад

      Oh yeah, whoops

    • @janApen
      @janApen 6 лет назад

      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.

  • @anteconfig5391
    @anteconfig5391 6 лет назад

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

  • @MrGone0608
    @MrGone0608 6 лет назад

    We want Kelsey back

  • @felip6180
    @felip6180 6 лет назад +2

    As always, your videos are the most challenging!
    Gabe's are too, but not as yours

  • @nodroGnotlrahC
    @nodroGnotlrahC 6 лет назад +17

    Says "we'll be be using math with no numbers" then numbers the cubes and edges.

    • @touisbetterthanpi
      @touisbetterthanpi 6 лет назад +8

      Gordon Charlton in fairness, she could have used letters. No math was done "with" the numbers. Though you’re probably making a joke lol.

    • @itisALWAYSR.A.
      @itisALWAYSR.A. 6 лет назад

      made me chuckle too :)

  • @bcaudell95
    @bcaudell95 6 лет назад

    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.

  • @MrDarkPage
    @MrDarkPage 6 лет назад +1

    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)

    • @soumyadipchottopadhay9509
      @soumyadipchottopadhay9509 6 лет назад

      Jimmy HUGUET Really..!!

    • @MrDarkPage
      @MrDarkPage 6 лет назад

      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.

    • @hirvonenjoonas7281
      @hirvonenjoonas7281 6 лет назад

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

    • @MrDarkPage
      @MrDarkPage 6 лет назад

      @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

    • @MrDarkPage
      @MrDarkPage 6 лет назад

      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

  • @Axacqk
    @Axacqk 6 лет назад

    6 × 24 × 24 × 24 = wee 82944 arrangements. Perfectly bruteforceable.

    • @nailer196
      @nailer196 6 лет назад +1

      Only 41,472

    • @nailer196
      @nailer196 6 лет назад

      Promo code for a similar puzzle (Google Play, free still 29 july) 5EV4EQUQ9UQAFBX5US49HWB

  • @supercat765
    @supercat765 6 лет назад +1

    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

    • @ethancheung1676
      @ethancheung1676 6 лет назад

      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.

    • @ethancheung1676
      @ethancheung1676 6 лет назад

      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

    • @ethancheung1676
      @ethancheung1676 6 лет назад

      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

    • @ethancheung1676
      @ethancheung1676 6 лет назад

      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.

    • @supercat765
      @supercat765 6 лет назад

      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

  • @victor666
    @victor666 6 лет назад

    8:40 Conditions #4: The SUBgraphs [...]

  • @JosiahWarren
    @JosiahWarren 2 года назад

    Too good

  • @shubhamupadhyay9308
    @shubhamupadhyay9308 3 года назад

    Exactly 41,472 possibilities (3*24*24*24)
    *So you are wrong *

  • @pablobragato7164
    @pablobragato7164 6 лет назад

    amazing! thank you!!!

  • @Topples7
    @Topples7 6 лет назад

    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?

    • @nailer196
      @nailer196 6 лет назад

      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.

  • @huh_wtf
    @huh_wtf 6 лет назад

    Of course it isn't the only solution you could just swap any of the cubes with the other... permutations i mean

  • @Delduwath0
    @Delduwath0 6 лет назад

    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

  • @elraviv
    @elraviv 6 лет назад +1

    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.

  • @kfjw
    @kfjw 3 года назад +1

    I'm still unclear as to why you chose to connect opposite instead of adjacent faces. That's not at all obvious to me.

  • @SSGranor
    @SSGranor 6 лет назад

    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.

    • @rmsgrey
      @rmsgrey 6 лет назад

      Yeah, I got that too

    • @nodroGnotlrahC
      @nodroGnotlrahC 6 лет назад

      Or any permutations the cube order.

  • @dalekemperorii5598
    @dalekemperorii5598 6 лет назад

    what do you think about learning mathematical facts as like the sinus (cos) from x° x € N, a I know twenty four and learning new everyday (to 8 decimals). I know some roots about 40 different values and some logarithms. What is the next step in mastering some field like goniometric functions or logarithms... memorize them so you can solve inverse functions of goniometrics or strenght of magnetic field with B to wire with current and some alfa degree or i dont know, something else...

  • @jonshonjohn4756
    @jonshonjohn4756 6 лет назад

    There aren't any good configurations because you would need to arrange each cube in suha way that each color apears only once on the sides but you can't do that with cube 3 and cube 4. on you 3 you need to get rid of one green and one blue face (aka put the on the top and on the bottom) but you cannot do that because there is no green face that has a blue face as its opposite and viceversa. The same can be said about cube four but the extra colors are green and yellow.

    • @jonshonjohn4756
      @jonshonjohn4756 6 лет назад

      I was wrong about cube 4 but i still dont get why there is a solution when cube 3 cant get 4 distinct colors on its sides.

    • @jonshonjohn4756
      @jonshonjohn4756 6 лет назад

      Nevermind, i got it, the condition of 4 distinct colors on the sides is not necesary at all. Although it is necesary for a similar scenario (when each side of the tower is a single color).

    • @StevieRZ
      @StevieRZ 6 лет назад

      i thought the same for a moment then i thought of 4 cubes, each only one colour all over :P

  • @cftmofficial176
    @cftmofficial176 3 года назад +1

    Peridiam

  • @TheBasileman
    @TheBasileman 3 года назад +1

    Anyone else come here from Peridiam/Survivor?

  • @quill444
    @quill444 5 лет назад

    if instead we examine just vertically, we can jump from one solution to 4! solutions by simply using four different solid-color cubes; what is the maximum number of solutions to the puzzle as given if we are allowed to color the cubes any way we please? - j q t -

  • @LeonidasSthlm
    @LeonidasSthlm 6 лет назад +6

    The host is really great.

  • @alexcwagner
    @alexcwagner 6 лет назад

    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.

    • @DaviddeKloet
      @DaviddeKloet 6 лет назад

      Same for me. So much for insanity.

  • @Melomathics
    @Melomathics 6 лет назад

    Colour saturation, and contrast, is a bit high in this. Great video otherwise. I'll be studying some Graph theory as of coming October, in my third year UG.

  • @ariel_haymarket
    @ariel_haymarket 6 лет назад

    thank g-d for @fleb

  • @IconOfCyn
    @IconOfCyn 3 года назад

    I actually solved this intuitively with some refined trial and error once the cube layouts were shown, without delving into the graph theory.
    My first observation was that each cube only has 3 "bands" that can be placed on each level, so only groups of four colors need to be considered at a time. Some of these bands are invertible, such that flipping the cube would reverse the order of the group, while some are not.
    The second observation was that certain configurations were more likely to be involved in a correct solution than others. Ones of particular interest were ones that contained all four colors.
    The last was that one can instantly rule out an entire band by finding that two colors match between an already set band.
    From there, I selected the cube 1 band RYGB and aligned it with the cube 2 band RYBG, rotated to BGRY, which was the only way it could fit, then I found that the only cube 3 band that could fit this setup was BBRY rotated to YBBR. And then you can just fill in the colors for the final cube to get GRYG, and check if that exists on the final cube, which it does.
    ~~I think in part I got lucky with picking the first two correctly on my first attempt, but I have a feeling this system could be used to vastly narrow down what is viable and what isn't.~~
    Edit: I've written some code to do this, minus the assumptions that certain bands are more likely to occur than others, and It was not luck. It finds all valid combinations of each stack height minus parity differences such as rotating the entire stack, flipping the entire stack, or reordering the cubes. There are 3 valid 1 cube stacks, 14 valid 2 cube stacks, 16 valid 3 cube stacks, and 1 valid 4 cube stack, with only a total of 296 different combinations being checked, a huge reduction from the 41,472 possibilities.