Anecdotes in Problem Solving--The Tale of the Lights Puzzle

Поділитися
Вставка
  • Опубліковано 12 лис 2024

КОМЕНТАРІ • 98

  • @ZedaZ80
    @ZedaZ80 3 роки тому +82

    I love how you tell this like a story, and walk through the process of discovery. Lovely animation and presentation!

  • @zakthayer9315
    @zakthayer9315 3 роки тому +92

    I literally had a cs class where we had to code a this "lights out" game last Friday and I said to my teacher there must be some way to use linear algebra to solve this and he was like ahh, I doubt it, maybe ¯\_(ツ)_/¯, I'ma send him this lmfao

  • @sebastianjost
    @sebastianjost 3 роки тому +28

    I did not expect that solving lights out is equivalent to solving a linear equation in Z/2Z.
    That's very cool!

  • @williamrutherford553
    @williamrutherford553 3 роки тому +40

    Speaking of finding the linear combination being easier for a computer, this problem is suited to addition of binary numbers, rather than linear algebra. Adding the vectors mod 2 is equivalent to addition without carrying. 0 + 0 = 0, 0 + 1 = 1, 1 + 1 = 0 So we're using an XOR operation, meaning we return 1 when the two numbers are different.

    • @r75shell
      @r75shell 3 роки тому +10

      Everything here works just because remainders of 2 is Field. So, this is *in fact* linear algebra. Just vector space is over this tricky field.

    • @Radi0actvChickn
      @Radi0actvChickn 3 роки тому +8

      Yup, as a CS major, xor was the first thing that came to mind. Both ways are completely valid though

  • @matthewritchie7011
    @matthewritchie7011 2 роки тому +1

    I'm not big on subscribing but I made an exception for you. I had to pause the video 2 minutes in because I want my wife to watch this with me because of how well done the storytelling is. Thank you for all your effort with this.

    • @throwmathatit4961
      @throwmathatit4961  2 роки тому

      Thank you so much! I'm glad that you were able to enjoy it. :)

  • @lawrencewhitfield8155
    @lawrencewhitfield8155 3 роки тому +14

    Very clever - great application of Gauss-Jordan elimination method - great presentation - very engaging.

  • @MACIEJ454545
    @MACIEJ454545 3 роки тому +16

    This video reminded me how much I loved Linear Algebra at university before I dropped out and that at some point I knew the method that loved this problem. I need to revisit that and remind myself how to do it because on top of being a powerful tool seeing matrices of that size and knowing i could methodically crunch them just excited that mathematics part of my brain

  • @hiteshpandharkar4631
    @hiteshpandharkar4631 3 роки тому

    Never watched something like this. I paused at times to figure out what's to come. So good!

  • @alarak5474
    @alarak5474 3 роки тому

    Refreshing video format, absolutely adored it. Superlative first video! One of my quickest subscriptions in a very long time.

  • @Maric18
    @Maric18 3 роки тому +8

    i did this by "accident" during one of my first programming projects (zanzarah's box locks work this way and i always found them fascinating): a lock generator for a pen and paper rpg project
    you could play it by typing in the coordinates (linear cell number or coordinates separated by space), or you could type in "hack" and it would start figuring out the difference from current state to optimal state and then build a catalogue (could have been hardcoded but eh, technically it could have supported any size field and any solvable ruleset that way :D) of moves to flip a tile exactly. it then added all the moves together (just arrays, not matrices) and then randomly pulled a coordintate which in the array was bigger than 0 every 100ms, automatically entered it and decremented it by 1. There also was "fasthack" that took every number in the array mod 2 first :D
    looked cool as hell and i felt so fucking good about it in 7th grade

  • @artemshlyakhtov9375
    @artemshlyakhtov9375 2 роки тому

    This is pretty relatable. I was playing a game (hammerwatch) that had the occasional 3x3 lights out puzzle. I would do the puzzles by trial and error until I learned that the fewer moves you took for the puzzle the greater your reward was. I tried several different approaches before realizing we were working with 9 entry vectors in Z2. I ended up with a general solution for any 3x3 lights out puzzle. What you need to do is know how to flip a single corner piece, a single side piece and a single middle piece hence by symmetry you can know how to flip any individual piece. And then for example to solve (1,0,0,0,1,1,0,0,0) you add mod2 the solutions of (1,0,0,0,0,0,0,0,0), (0,0,0,0,1,0,0,0,0) and (0,0,0,0,0,1,0,0,0).

  • @Robert-jy9jm
    @Robert-jy9jm 3 роки тому +9

    Loved the bunnyhat (you probably already have a name for the cute animation) and the explanation too!
    Great name for your channel!

  • @aviberezovskiy7633
    @aviberezovskiy7633 2 роки тому

    This is one of the most entertaining videos I have ever seen done on math, and believe I watched some! Wow!

  • @maxgeopiano
    @maxgeopiano 8 місяців тому

    This video kinda felt like one of these interactive childrens shows to me, but in a really good way.
    Like I was actively trying to solve it with you and I actually progressed with you

  • @purplenanite
    @purplenanite 3 роки тому +16

    Reminds me of a puzzle in Myst i encountered a few years ago, but I don't remember if I solved it or not.
    Also, the mod 2 would mean that you never have to flip a number more than once, meaning the upper bound on the number of moves is the number of vectors.
    Fun stuff!

    • @sebastianjost
      @sebastianjost 3 роки тому +1

      It would be interesting to see if there is a tighter upper bound or if n moves for n lamps is the best upper bound.

    • @aaronwelther3536
      @aaronwelther3536 3 роки тому +1

      @@sebastianjost i would guess that n moves is an upper bound for n lamps (but prove still needed)
      What i am interested in, how are the "states" connected? Like what would the graph look like representimg the states and their connection

    • @HeavyMetalMouse
      @HeavyMetalMouse 3 роки тому +1

      @@sebastianjost I imagine that the only way you could have a tighter upper bound is if the set of moves were overpopulated - that is if, for one of the moves, there were some linear combination of the rest of the moves that could perform the same result. In that case, since no final state requires more than 1 use of any specific move, any move combination that included the 'redundant' move could be made smaller by replacing it with its equivalent combination and 'cancelling out' the duplicated moves to leave a combination of at most one of each remaining move; while any combination that doesn't include the redundant move already naturally contains less than the previous upper bound.
      This would show up in your linear algebra as one of those rows 'zeroing out' [0, 0, 0, ..., 0 | 0] in the reduction I believe.
      Likewise, if the available moves can't make the solution at all, then we'd likely see a 'half zeroed out' row show up [0, 0, 0, ..., 0 | 1] in the reduction

    • @hughcaldwell1034
      @hughcaldwell1034 Рік тому

      @@sebastianjost Depends on your lamp array. Short answer is yes, there are light configurations on arrays of n lamps that require n moves to solve. Apart from the most trivial case (1 lamp by itself, turned on to start), a 2-by-2 grid with all lamps on at the start will require 4 moves to turn off.

  • @kodirovsshik
    @kodirovsshik 3 роки тому +1

    Man, even tho I've only seen this single video, I already love this channel
    That's like super cool how the video goes

  • @themathematicstutor4092
    @themathematicstutor4092 4 місяці тому

    Subscribed! This is an underrated channel.

  • @shambosaha9727
    @shambosaha9727 3 роки тому +2

    I keep coming back to this one SoME1 video, it's too good! 🤗

  • @snekz6714
    @snekz6714 3 роки тому +4

    I really like the story you have here as a kind of motivation and the process you went through, rather than just jumping directly to "matrix with elements of ring Z2."

  • @La4geas
    @La4geas 3 роки тому +1

    I had this same problem in a game called Bean Stalker. Except instead it only flipped adjacent lights, and I just had to make them all the same, so 2 solutions per puzzle. One of the puzzles I messed up thinking it was a 5x5 grid, and when I thought of solving it like that, I gave up when I saw the number of vectors I was dealing with.
    Also tried working with the ammount of lights each button could switch at a time, but I currently wanna test a more "individual" way of solving. See which ones are lit up to know if around them there is an odd or even number of buttons pressed, and then trying to figure out which buttons are pressed to give me the pattern at hand.
    ...Though turns out the grid is 4x4, and after solving 3 different patterns, it would seem the game just takes a solved position, and randomly clicks 4~5 buttons...

  • @leefisher6366
    @leefisher6366 3 роки тому +1

    15:46 - Behind puzzle three... puzzle four (a ten by ten grid of lights).

  • @element118_5
    @element118_5 3 роки тому +3

    Nice video!
    I was thinking of a slightly more efficient way to solve it, where you find a general rule to clear a single row by using moves that are in the next row (which is linear algebra but on a smaller matrix), then, using those rules to solve everything but the last row, then for each move in the first row, we can use that general rule to "solve" it to the last row to make a "last row move", then we only need to do the linear algebra on the last row using "last row moves".
    However, for boards which are 2 mod 3 in length or width, there may be no solution for clearing a row, and this technique fails.
    Though, we can generalise this technique for boards that do have a solution. For each light, (from left to right, from top to down), not in the last row or column, click the button in the next row and column from the light. This ensures we end up with only the last row and column lights possibly lit up. For the buttons not part of this procedure, we can "solve" them to make a "last row and column" move, then do linear algebra using those "last row and column" moves.

  • @coaster1235
    @coaster1235 3 роки тому +1

    Aw, I hoped that in the end you would explain what the process of row reduction would look on the puzzle itself so that you don't have to switch between the m-by-n board of lights and mn-by-mn augmented matrix, and instead solve the puzzle by direct inspection.

  • @jasonpatterson9821
    @jasonpatterson9821 3 роки тому +5

    Excellent video, though I have to admit that I was hoping that there would be a 10x10 lights puzzle instead of the sword next and you'd just break down from the matrix.

  • @andohiroshige6569
    @andohiroshige6569 3 роки тому

    I want more videos. Thank you for this one.

  • @_spartan11796
    @_spartan11796 3 роки тому +1

    Great stuff!

  • @814200
    @814200 3 роки тому +1

    I have developed light out games for android some time back. You can find a casual game approach with items on the play store called "Skull Flip" or a more minimalistic puzzle only version called "The Puzzle and You". Both have a tipp function, which show the next best step for a minimum solution. The first game has ads in it, the second does not, both are free.
    The approach in the video finds a solution, as in one of many, but it is not the best solution, as in minimum required steps. You will need quiet patterns for that, maybe you show that in the next video? :)
    Nice animation and story telling, really easy to understand things.

  • @PrometheusMMIV
    @PrometheusMMIV 3 роки тому +1

    This feels like Blue's Clues for adults

  • @jakoolaboo
    @jakoolaboo 3 роки тому

    Keep up the good work
    WE NEED MORE (COMBINATORIAL) PROBLEMS

  • @jonathannissim2774
    @jonathannissim2774 3 роки тому

    awesome puzzle and video thanks!

  • @sharpfang
    @sharpfang 2 роки тому +1

    My reactions. "Ah, I got this far myself." "Ah, cool, I'm following this." "Good, and now what?" 13:18 numbers change magically at random. **Yes, that's what I was trying to achieve!** Me: (╯°□°)╯︵ ┻━┻

    • @throwmathatit4961
      @throwmathatit4961  2 роки тому

      Ha ha, whoops. Sorry for that leap of logic. I didn't want the video to get bogged down by the long and boring row reduction process, so I sort of skipped through it. If you'd like to know how I changed the matrix to get the final answer, I recommend looking up row reduction or Gauss-Jordan elimination. There are lots of good resources, and the technique is pretty straightforward once you learn it.

  • @nemderogatorius
    @nemderogatorius 3 роки тому +1

    As I know, the first electronic version of this game, called "Lights Out" was invented by the mathematician and game theorist László Mérő around 1983.

  • @chadgregory9037
    @chadgregory9037 3 роки тому

    3:34 that "oh fuck" moment when am like "oh oh, 0 and 1 matrix with ordered transformations to arrive at the solution, boom" lol

  • @gameygeemer4142
    @gameygeemer4142 3 роки тому

    Oh shit, I don't know much about Linear Algebra, but I was super excited when I recognized the xOR gate in this.

  • @FinetalPies
    @FinetalPies 3 роки тому

    This was excellent, I love throwing math at things

  • @juanroldan529
    @juanroldan529 3 роки тому +2

    I loved working in this problem when learning how to use Mathematica. It's a neat problem, a shame you are not taught things like this in university.

  • @DarkLightning96
    @DarkLightning96 3 роки тому

    Loved this video! Hope you upload more soon :D

  • @Fabelaz
    @Fabelaz 3 роки тому

    that was nice. Especially considering linear algebra isn't something I remember really.

  • @aaronwelther3536
    @aaronwelther3536 3 роки тому

    Please more of this good stuff

  • @miniwizard
    @miniwizard 3 роки тому +2

    Great channel name and hoping for more content and more anecdotes in the future! I know there have been several occasions where I have also thrown some math at various puzzles in the past (with varying success) - though can't immediately recall a specific example.

  • @yura7906
    @yura7906 3 роки тому +1

    I really like your style ! And i hope to see more of the adventures of that little rabbit weaponizing math tools to solve funny problems 😁

  • @junelle9080
    @junelle9080 3 роки тому +1

    omg this is so fun and engaging, but i also did feel like i learned a lot from it!!! i can feel how sincere the whole thing is 🥺 keep producing math stuff ♡♡♡

  • @joeimjoe
    @joeimjoe 3 роки тому

    "The following is based"
    Indeed. Indeed.

  • @kumozenya
    @kumozenya 3 роки тому +2

    This is amazing! I never thought these puzzles would have a systematic way of solving!

  • @ProofofConceptMath
    @ProofofConceptMath 3 роки тому

    A super charming video. I'll send my students to this!

  • @luizquevedo6580
    @luizquevedo6580 3 роки тому +1

    Watching this was... hehe... worth it.

  • @MrGranddy
    @MrGranddy 3 роки тому

    This was actually super fun, I hope there will be more videos :) subscribed. ("How to Solve It" by Polya, such a nice detail.)

  • @agargamer6759
    @agargamer6759 3 роки тому

    Loved the video!

  • @bolivarbelenosantos5967
    @bolivarbelenosantos5967 3 роки тому

    Loved this

  • @coolcat23
    @coolcat23 3 роки тому +5

    Very nice video but I find it more straightforward to think of the numbers as binary numbers and using the XOR operation. Also, instead of using Gauss-Jordan elimination, you can just work out the combinations needed to flip a single dot and then simplify the combination of all dot flips steps required to flip all dots that need flipping.

  • @ShadowSliph
    @ShadowSliph 2 роки тому +1

    How do you solve this if you have more than two states per position?
    There's one of these Lights Out style puzzles in Destiny 2 for example, where each position of the 3x3 grid can be one of three symbols.

    • @throwmathatit4961
      @throwmathatit4961  2 роки тому +1

      Interesting. I haven't tried a puzzle like that before. If the symbols always cycle through the same order as you click on them, then it's possible that this could be modeled in the exact same way but modulo three instead of two. So you would have a matrix filled with 0's, 1's, and 2's, and you'd need to reduce it mod 3. I'd be curious to know if a method like that worked.

  • @t6hp
    @t6hp 3 роки тому

    OMG please make more videoes!

  • @bunshine
    @bunshine 3 роки тому +1

    this video was so cute! love the vibe of this

  • @ghislains3020
    @ghislains3020 3 роки тому +4

    Great job !
    i would like to know wich operations are done since 13:18 for the row reduction, can someone explain or give me a link to a video that explain that ?

    • @throwmathatit4961
      @throwmathatit4961  3 роки тому +3

      There are lots of really great examples of doing row reductions on UA-cam. I suggest searching "Gauss-Jordan elimination" or "matrix row reduction" on UA-cam and picking a video that seems to fit for you. :)

  • @TRex-fu7bt
    @TRex-fu7bt 3 роки тому

    nice video

  • @andy02q
    @andy02q 3 роки тому

    For every configuration of this lights off/on problem that is humanly possible you can code (a simplified version of) the puzzle instead of the algebra needed to solve it and throw brute force at it, mod2 all steps and get the solution much faster.

  • @78Mathius
    @78Mathius 3 роки тому

    This was great!

  • @zachrodan7543
    @zachrodan7543 3 роки тому

    14:59 why not? seems like a hell of a lot of fun!

  • @diophantine1598
    @diophantine1598 3 роки тому +3

    The time complexity here is way better than what I came up with. The best I could get is O(2^n). N being the shortest side. I need to look up Gauss-Jordan elimination... can you get multiple answers from this? If so, how?

    • @Boringpenguin
      @Boringpenguin 2 роки тому

      Yes you can indeed get multiple answers in some cases. One of those cases is in fact puzzle 3 (14:36) !!
      If my quick and dirty code is right, the matrix at 14:47 is actually singular. And if you do the Gauss-Jordan elimination, you will find that the rank of the matrix is only 16, so we have 4 degrees of freedom. In particular, the last column of puzzle 3 can all be treated as free variables, and we should get 2^4 = 16 solutions in total.
      Btw I'm also guessing that only square puzzles will have unique solution, but I don't really know how to proof it.

  • @mikefochtman7164
    @mikefochtman7164 3 роки тому +3

    Nice way to solve these types of problems. But throughout the video, I was wondering..."Is there some pattern that cannot be changed into another pattern?" Like with the sliding '15' puzzle, or Rubic's cube, do these have some sort of 'parity' where some combinations are just not possible? Is there a proof one way or the other?

    • @throwmathatit4961
      @throwmathatit4961  3 роки тому +4

      That's a good question! If my memory of linear algebra serves me, the fact that we can row reduce the matrices in the 3x3 and 5x5 puzzles to row echelon form means that both matrices are invertible, which would imply they can reach any vector in their codomain space, so any arrangement of the lights could be turned into any other arrangement of the lights. I'm not entirely sure whether that theorem changes in mod 2 space, but my instinct is that it doesn't.
      Additionally, some other comments on this video have mentioned that there are other ways of solving the problem, such as using a XOR process to change each of the lights one at a time. If you can do that, then you can change any light you like without altering the rest of the lights, and that would again show that any pattern can be changed into any other pattern.

    • @teraflonik
      @teraflonik 3 роки тому

      All you have to do is look at the augmented matrix. If it has a determinant not equal to 0, the system has only one solution mod 2, otherwise the system might have no solution, or infinitely many, though i'm not sure what infinitely many solutions would mean mod 2. I took the matrix from the possible moves from 12:50 and saw that its determinant is 1. What this means is that, for this particular arrangement, with a 3x3 grid and switching neighbours and the point itself, any configuration is achievable from any other configuration. However, this can change by varying grid size or the way the switches are made.

    • @murmol444
      @murmol444 3 роки тому +1

      It is easy to observe that if grid is 2x3, then some combinations cannot be obtained from some others. It depends on determinant of the matrix. But it is possible to word it in simple terms. There are unattainable combinations if (and only if) action of several basic operations is equivalent to single basic operation. On 2x3 grid top-left corner and bottom-left corner give the same result.
      For larger grids, I think, it is a rather hard question, because this switch operation doesn't work so well with matrices.

  • @DaSquyd
    @DaSquyd 3 роки тому +1

    So… who’s gonna tell him about XOR?

  • @NE0KRATOS
    @NE0KRATOS 3 роки тому +1

    Does anyone know if there is a website that does the reduction / a way to code it in Python? Even for bigger matrices?

  • @ro-ce8vg
    @ro-ce8vg 3 роки тому

    great video

  • @Bl00drav3nz
    @Bl00drav3nz 3 роки тому

    Oh god this was great, thank you :)

  • @hacker2ish
    @hacker2ish 3 роки тому

    Feels like more can be done because this a very particular kind of matrix

  • @kitastro
    @kitastro 3 роки тому

    if the problem space is small enogh then just keep clicking randomly very fast... Don't overthink

  • @jpt13913
    @jpt13913 3 роки тому

    Fun my wife aside it did not make her want to look up how do the math . but I did way cool! Thanks

  • @seneca983
    @seneca983 2 роки тому

    0:00 "The following is based"

  • @djfalcon2368
    @djfalcon2368 3 роки тому

    is there anywhere i can play this version of the puzzle?

  • @danmimis4576
    @danmimis4576 3 роки тому

    I was searching for "life of friedrich gauss" and came over your vid. Nice presentation. Who's Jordan?

    • @throwmathatit4961
      @throwmathatit4961  3 роки тому +1

      Wilhelm Jordan, who was a professor of geodesy in the 19th century. He made some alterations to the Gaussian elimination method, so his name got tagged on as well. Confusingly, there's another mathematician named Jordan as well who's famous for different things.

  • @Kazzit_Chang
    @Kazzit_Chang 3 роки тому

    Which leads u to the group theory.

  • @vanderkarl3927
    @vanderkarl3927 3 роки тому +1

    The following is *based*

  • @lora6938
    @lora6938 7 місяців тому

    Hi! Why do you have a diagonal? Did you do this yourself?

  • @astroceleste292
    @astroceleste292 3 роки тому +1

    can you put subtitles? the automatic captions are crap for mathematical terms.

    • @throwmathatit4961
      @throwmathatit4961  3 роки тому

      Thanks for the suggestion. I've gone ahead and done better subtitles now.

  • @ksdr5412
    @ksdr5412 3 роки тому

    love you bunny man :D

  • @nif4345
    @nif4345 3 роки тому

    13:20 may I ask how you did that?

  • @MichaelDarrow-tr1mn
    @MichaelDarrow-tr1mn Рік тому

    So what was puzzle 2

  • @KiyotakaAyanokoji1
    @KiyotakaAyanokoji1 2 роки тому

    does the order in clicking matters?no ig correct me if i am wrong

  • @Graverman
    @Graverman 3 роки тому

    lmao this is so cool

  • @deleted_handle
    @deleted_handle 3 роки тому

    I hated watching this video.

  • @Manigo1743
    @Manigo1743 10 місяців тому

    I have no idea how you did this, because I blocked your channel when the music began. Bye.