12

You are given an empty 4x4 grid. You can place some diagonal mirrors into the cells of the grid. You then fire a laser from some location outside of the grid. The laser travels in a straight line. When it hits a mirror it bounces off at a right angle and spins the mirror by 90 degrees. The same mirror can be hit and spun multiple times.

Consider the following example. We place 4 mirrors in the centre of the grid and fire the laser below the second column. It hits the mirrors like so:

enter image description here

The mirrors spin around and the laser continues hitting another 2 mirrors before exiting the grid. In total it had 6 mirror hits:

enter image description here

What is the most number of mirror hits you can obtain on a 4x4 grid?

Dmitry Kamenetsky
  • 35,897
  • 5
  • 66
  • 276

2 Answers2

12

Proving a solution to be optimal will require programmatically checking all possible mirror placements, let's go ahead and do that.

The results are in, and the winner is:

This layout, which scores 49 hits!
Mirror grid

This optimal solution is essentially unique. Aside from reflections and rotations, the only other optimal solution is the inverse, which follows the same path in reverse and has as it's initial position the final position of the above solution with all mirrors rotated.

Daniel Mathias
  • 14,926
  • 2
  • 30
  • 62
  • That's very cool, thank you! Interesting that not all cells are used. Also I was hoping we can get an infinite loop, but perhaps there is no space for that. That might be my next puzzle. – Dmitry Kamenetsky Nov 30 '21 at 04:10
  • 7
    @DmitryKamenetsky An infinite loop is impossible on any finite grid. Every mirror involved in the loop will be hit an infinite number of times. Consider the left-most column containing such mirrors, and then the top-most mirror in that column. That mirror will deflect the laser to the top or left in one of its orientations, sending the laser out into space and breaking the loop. – Jaap Scherphuis Nov 30 '21 at 10:09
  • That's a nice proof. Thanks! – Dmitry Kamenetsky Nov 30 '21 at 13:03
  • What if we add one fixed (nonspinning) mirror to the grid, can we get infinite loop then? If not, how many fixed mirrors do we need? – Ross Presser Nov 30 '21 at 14:31
  • 1
    @RossPresser My argument holds for all four corners, so you need at least four. You could of course have them arranged on the corners of a rectangle, with the laser going looping around in that rectangle. There is however no way to set it up without the laser gun being in the way, even with additional spinning mirrors. The reason is that everything is time-reversible. If you film it going through one of the loops, you could play that backwards repeatedly and it would still be a valid looped path. That path loops, so could never go back to the laser gun that supposedly started it. – Jaap Scherphuis Nov 30 '21 at 15:53
  • @RossPresser Another way to think of it is this: You can setup a 4-mirror infinite loop but there's no way to get the laser into that loop. – Engineer Toast Nov 30 '21 at 15:55
  • I don't suppose your computer program also generates a gif animated figure of the laser moving through the grid and flipping the mirrors? :( – Stef Nov 30 '21 at 16:22
  • 1
    @Stef No, that will take a bit more effort. I could probably create an animation in Blender, but that may take a while as I have no prior experience with the software. – Daniel Mathias Nov 30 '21 at 16:47
  • Since you have a computer program, what winner amounts do you get for other $n$? Maybe there is a formula for, and/or an oeis sequence correlating to, the answer to this nice question? – FirstName LastName Nov 30 '21 at 21:04
  • 2
    @FirstName 4x4 has just over 43 million possible grids. 5x5 has nearly 20 thousand times as many. Run time for 4x4 is under a minute. For 5x5, could be over a week. – Daniel Mathias Nov 30 '21 at 21:44
  • tag optimization was not a bad choice then :-) just curious, did you try 3x3? – FirstName LastName Nov 30 '21 at 22:15
  • 2
    @FirstName Easy enough. Optimal solution for 3x3 has 18 hits. With the added condition that all cells must contain a mirror, optimal solutions have 17, 46, and 85 hits. Allowing exactly one vacant cell limits the search space enough that 5x5 is still feasible (~450 million grids). In that case optimal solutions have 18, 49, and 102 hits. – Daniel Mathias Dec 01 '21 at 00:03
  • perfect, I was curious if, perhaps unexpectedly, some existing pattern would be revealed – FirstName LastName Dec 01 '21 at 00:48
  • I found another optimal solution where the laser starts on a non-edge column. – Dmitry Kamenetsky Dec 03 '21 at 03:01
  • @DmitryKamenetsky It is the inverse of the solution I posted. – Daniel Mathias Dec 03 '21 at 03:08
  • oh I see what you mean by inverse now (I thought it's inverse of the mirrors). – Dmitry Kamenetsky Dec 03 '21 at 03:12
  • For 5x5 I found a solution that scores 120, where laser starts in top left. I believe this could be optimal. https://pastebin.com/sAxkCUXF – Dmitry Kamenetsky Dec 03 '21 at 03:14
  • 1
    @DmitryKamenetsky You beat me to it. I was going to expand my 5x5 search to three, maybe four vacant cells. I estimate the run-time for three to be less than an hour; for four, about two and a half hours. Full search not more than 72 hours. – Daniel Mathias Dec 03 '21 at 03:29
  • Well it would be nice if you can confirm that it is indeed optimal. I can then make an OEIS sequence out of it. Meanwhile I will search for 6x6. – Dmitry Kamenetsky Dec 03 '21 at 04:35
  • I wonder what the growth rate for n*n/hits is? – Dmitry Kamenetsky Dec 03 '21 at 04:42
  • 1
    @DmitryKamenetsky For 5x5, I checked all arrangements with up to 5 vacant cells. Your solution, with 120 hits, is optimal. Not only that, but it is its own inverse. For 6x6, a limited search on grids with one vacant cell finds \//|\/\|\/\|////|.\///|\/// with 185 hits. – Daniel Mathias Dec 05 '21 at 14:19
  • @DanielMathias thank you for verifying the 5x5! For 6x6 I can get 219: https://pastebin.com/J0NgPvvf – Dmitry Kamenetsky Dec 06 '21 at 09:31
  • @DmitryKamenetsky New approach, faster results. Complete search on 5x5 in 30 seconds. A bit longer (60+ hours total CPU time) on 6x6: https://pastebin.com/90cKNvNc – Daniel Mathias Dec 08 '21 at 03:20
  • 1
    @DmitryKamenetsky 23 hours, 37 minutes into the first of three processes (the others completed in under 20 hours) and we have a new high score: https://pastebin.com/iHZqqMjS – Daniel Mathias Dec 08 '21 at 04:34
  • @DanielMathias nice work. I ran 5 instances of my program and 4 of them found the same solution, so it could be optimal: https://pastebin.com/xBh5CBZ5 – Dmitry Kamenetsky Dec 08 '21 at 12:51
  • 1
    @DmitryKamenetsky My search was exhaustive, 233 is the maximum. Optimization of the new code reduced the 5x5 run time from 30 seconds to just 7 seconds. – Daniel Mathias Dec 09 '21 at 01:02
  • 1
    @FirstNameLastName In case you're still interested, we now have optimal solutions for 5x5 (120 hits) and 6x6 (233 hits) – Daniel Mathias Dec 09 '21 at 01:15
  • @Daniel Mathias : sounds good! – FirstName LastName Dec 09 '21 at 13:21
  • Perhaps it is time to look at 7x7? Here is my best: https://pastebin.com/D2VGDVPi – Dmitry Kamenetsky Dec 17 '21 at 23:27
  • @DmitryKamenetsky Yeah, I've been optimizing my code for that. Exhaustive search on 5x5 now completes in about four seconds, with the search on 6x6 estimated at ten hours. I'm going to try to get an estimate on 7x7 runtime this weekend, but I don't really expect it to be reasonable. – Daniel Mathias Dec 18 '21 at 02:41
  • 1
    @DmitryKamenetsky Now this is interesting: https://pastebin.com/nCa3m9ZJ – Daniel Mathias Dec 18 '21 at 12:22
  • @DanielMathias wow that is fascinating! A simple pattern with so many gaps works so well. I am going to try looking for more such patterns. – Dmitry Kamenetsky Dec 19 '21 at 02:32
  • 1
    @DmitryKamenetsky Estimated total CPU time for exhaustive search on 7x7 grid: 50 years. (Single-thread, 3.2 GHz) That is not unreasonable for distributed computing; I was expecting at least double. For comparison: 5x5, 1.9 seconds; 6x6, about 5 hours. – Daniel Mathias Dec 21 '21 at 00:24
  • 1
    @DmitryKamenetsky https://pastebin.com/fpY491aT (still at the extreme tip of a very large iceberg) and some data in a spreadsheet with chart. – Daniel Mathias Dec 25 '21 at 17:34
4

This is not an answer but here is an animation showing Daniel Mathias's answer.

enter image description here

caPNCApn
  • 19,113
  • 1
  • 63
  • 96