If you generate all boards exhaustively with code it is very likely that your implementation generates the left one first because it starts with 2 "full" cells
@@Grimlock1979 Even when working out by hand, you figure that distance 1 is going to be one of the distances, so it's pretty natural to start with the adjacent pair. I wouldn't think to start with the D=2 and D=3 integer distances first, then get to the D=1 case later.
yeah, he's done that for all six of them, although to me it feels a little bit more like "is that what we're calling it?", which I think is also the reason why 'solutions' is just slapped on top of 'puzzles' in the thumbnail text thingy. Like it's a placeholder for until he comes up with something better to call it.
maybe we should all agree to send a helpful way to how our names out pronounced, along with our solutions, to matt, so he won't have as much trouble with it anymore!
I send along phonetic pronounciation of my name last week and he still messed it up :p I think they're just super swamped with submittions and so they miss stuff like that.
I'd love it if Matt could publish some Python solutions and spreadsheets for each puzzles. This is a fun way to understand other people's workflows and learn from them
"scrabble video will take longer" 2 months further already, very hyped up to see like a 5 hour video coming up or something xD Either way I'm sure you're very busy, so I'll be patient.
Regarding the exhaustive search, I've coded a multi-threaded c program which I've run on a 16-core machine, and managed to verify n=8-14 don't have solutions. n=15 is still running....
Brilliant! You can actually confirm that there are no solutions for n=15 using just pen and paper, by using the fact that every distance has to occur exactly once (because the number of possible distances is exactly equal to the number of pairs of points). So we've fully solved the problem!
I was wondering whether 10-15 had actually been checked! Not surprised that there aren't any, since the constraints seem to get tighter and tighter before becoming impossible at 16.
@@GalHorowitz It's not that hard to do: the biggest length is the distance between two diagonally opposite corners. But the only way to get distance 14 is to have both ends of a row/column (there is no Pythagorean triple with 14 as the hypotenuse), but whichever row/column you pick, one end will be the same distance from one corner as the other end is from the diagonally opposite corner - and you can't reuse either of those corners since their other end is a third corner, equidistant from both already used corners.
Hey, recently I've finished your book "Things To Make And Do In The Fourth Dimension", and I just wanted to say I really enjoyed it! Thank you Matt Parker
Pretty confident the bias in solutions is because of search techniques, like the one I used, where you start in one corner and gradually move counters along. For example, trying squares 0,1,2,3,4,5, then trying 0,1,2,3,4,6, then 0,1,2,3,4,7, etc. The left solution still used squares 0 and 1, rather than 0 and 2. It's not the clump at the end that matters, but the clump at the start.
Hey, Matt Parker. I think you can solve the "pronunciation problem" by putting a box in the submission form where one can put the pronunciation of their names if it would be chosen to feature in the video.
I know a few have said so, but I would guess that the “left” solution comes more naturally from pen and paper because an automatic tendency to start with a counter in the far most corner and work from there
Both solutions have a counter in a corner (which one doesn't matter, because this is just one of the rotations/reflections). I think it's because it has two adjacent counters in the corner, which would come first in most exhaustive searches.
Not only is there a pair in one corner, but it also uses the largest possible distance by having another in the diagonally opposite corner, which is intuitively appealing.
Noah Baker I did it using pencil on paper and found the “right hand” solution, but turned 180° because the 0,1;1,1;2,2 pattern was “intuitively obvious” as necessary, and I started with that at 0,0 and when that didn’t work moved it to 0,1 and low and behold a solution...
This is how I did it, to maybe shed some light on why the one solution was more popular. I began with all if the counters in the top row of the grid, and when it was obvious that that wasn’t a valid solution, I took the far right counter to the next row, and continued on in that fashion until that counter reached the end of the grid. I would then move the next to last counter one space along the grid, and return the final counter to the top. This is essentially this problem’s equivalent of trying every combination for a combo lock: 000, 001, 002, etc. the solution that was found more often would be reached first by this method, because the other solution involves moving the second counter from its starting position, which would be like a combo lock with 01xxxx, whereas the more common solution would equate to 00xxxx. I searched manually with a paper grid and dimes, but I’m sure people who coded it out checked in a similar manner, as this is a simple way to exhaustively check every possible combination.
I got the mathematical idea, but without any knowledge of programming at all, it was impossible to generate and verify the candidate solutions. Apparently, I will never get one of these correct, but I will never stop watching the videos (and trying for a few hours before giving up hopelessly)
For me, the first one was more intuitive because placing two tokens on the corners felt like a good place to start, since it's the largest distance between two points, which I hoped would give some leeway
4 года назад
Thanks for featuring my paper! Minor correction: I gave a solution for n=7 and verified that 8 through 12 doesn't have a solution. I've also found the maximum number of tokens you can place on different board sizes up to 12. Turns out you can do 10 on a 12x12 board. After that it probably gets even worse.
We have now hit a point where people are high on the leader board who haven't solved all problems correctly. Thanks to speed and weighted points place 4 didn't solve the first problem correctly and place 19 didn't even submit on the first problem. Hope this encourages more people to join in the fun (or continue after a missed problem)!
I am a little bit disappointed that you didn't include PowerShell in the list of tools people used to solve the puzzle. That was the whole reason why I did it with this language :D
I was in the minority as I found the second solution. In fact it was exactly as shown, not rotated or reflected. I was using coins on a hand drawn grid and decided to test different integer distances along the edge, then figuring out where to arrange the shorter distances near the opposite edge. A little trial and error and there it was!
Does anyone have a Python code that can check for the different permutations of a set of 6 points? In other words, the other orderings of [[0, 0], [1, 0], [3, 1], [5, 3], [2, 5], [5, 5]] ? I'm a brand-new coder and want to learn how to make my code more efficient. Need it to throw out the other 719 orderings once a solution is found. Thanks
I was a little disappointed there was no mention of triangular numbers and the role they play in this puzzle. Perhaps the connection was too obvious to be worth pointing out, but the number of distances to consider follows the triangular progression of 3 for 3 counters, 6 for 4 counters, 10 for 5 counters, etc. The number of unique possible distances available in the space also follows a triangular progression one step ahead, at least that is, until you hit that first Pythagorean triple (3,4,5). But for the purposes of this puzzle it's really the triangular numbers minus 1, because 0 is not a valid distance between two counters, so the number of distances available to use are 5 for 3x3, 9 for 4x4, and 14 for 5x5. As I said, you lose one for the 3,4,5 triangle, making it 19 for 6x6, and 26 for 7x7. After that the triangular progression continues to break down as more and more duplicate distances start to appear, such as 7,1 and 5,5 both resulting in a distance of √50, or 9,2 and 7,6 both resulting in √85. Then on top of that you continue to get more Pythagorean triples (6,8,10; 5,12,13; 9,12,15), until finally the number of unique distances needed outpaces the number of unique distances available on the 16x16 grid. I can't help but wonder though, if we were allowed to count these duplicate distances as unique because they follow a different path, such that the distances available continued their original triangular progression, would we have been able to find any solutions for grids higher than 7x7? Edit: I guess another way to put this would be: Puzzle Variant - If two distances are the same, but their Manhattan (taxicab) distances are different, they may be counted as unique distances for the purposes of this puzzle. How many more solutions can we now find on a 6x6 grid? Might there now be a solution for the 8x8 grid? And could there be other surprise solutions further up the chain now that we can't so easily rule out grids larger than 15x15, or are there other factors that would put a definitive limit on the largest possible grid with a viable solution?
I submitted the more common solution, because my brute force solution found it first. Before I decided to go with brute force, I figured using opposite corners was a good starting strategy.
I didn't find either (though now I see I was close... 😦), but I'm not surprised the one was more common. If you are just moving tiles around, it feels very common sense to start with the first two in opposite corners (max distance) and then one right next to one of those (min distance) and try to fit the remaining three.
I was hoping for a few published Python solutions. I'm learning as I go but couldn't solve it. These write ups could have helped me show a different solution or path to one.
I found the less common solution, but only because I wrote some code that randomly selected six points and checked them over and over again, and that's what it spat out.
I didn't submit in time because I was stuck on the 4x4 since I kept trying to find 3 counters rather than four. I'd like to see a general equation that could take an nxn grid and find the number of unique distances for m counters. Maybe one of the solutions papers have something I can work with. One of my initial thoughts was to treat it as trying to find an n-gon with all unique sides, but I didn't know where to go from there, so I ended up going through trees to figure out which solutions were valid or not.
Hey Matt, could you please link Rae's work showing that there are no possible solutions above 15? This claim although it seems to be true, but I found it was not trivial at all to prove!
4 года назад
It is also in my paper, linked above. Basically there aren't enough different distances on larger boards.
I imagine the more common solution appears more when doing searching algorithms because the adjacent pair in the top left corner seems more likely to be hit before the other arrangement.
I got the left solution because I saw this problem as “build an N-gon on an NxN grid with every distance being unique” So when I was playing around I got the shape on the left because that fit being a hexagon. The arrangement on the right is not immediately a shape, so it might have not been found as quickly.
Yeah! Me too. I tried looking it up to see if there was some kind of irregular n-gon problem out there, to no avail. There's also the matter of having more than two counters on a single line. I also messed up because I accidentally kept trying to solve a 4x4 grid, but with 3 counters.
I must have missed something with the right-side solutionat 3:00 I had something just like it with the three pegs stacked in one column/row spaced 2 and then 3. I knew it SHOULD have been a solution, but must have counted one wrong or twice. Would have been done much sooner if I got that one. Luckily, I still found the other one just fine.
It is obvious that if one does some kind of exhaustive search, then one starts with two adjacent tokens in the first two cells and tries to find a solution, one will naturally find the left one first. This is what I had done.
I don't think I actually find one of the solutions in the end (just submitted whatever I had on screen at 23:59 on deadline night and didn't even note it down to retrospectively check it, so no idea what my 'solution' was), but I worked out that a six by six grid had six different unique squares once all rotations and reflections were taken into account (e.g. in a 3x3 there are only corner, centre and the centre edge). I postulated that you either needed exactly one of each of the six, or that one of the types that had only four choices (one of the three layers of corners) would be doubled up at the expense of one the other three types. I even worked out that the type that I called 'E' (the 8 non-corners of the centred 4x4) was often where my 'solutions' screwed up. So if I had dropped an 'E', so to speak, and replace it with an second corner ('A') and persisted with my theory a bit longer I would eventually have arrived at the right hand solution, I think. Certainly the left hand solution is noticeably further removed from my postulations and theories for what a solution would look like, so I don't think I would ever have found it by my theories. All this is a long winded way of saying did the computer programmers who checked each combination in order usually find the left hand answer first (two consecutive cells in the top corner, as people have pointed out), and was it those who scribbled on paper and refined their theories of what was needed or likely in a solution, that tended to find the right hand answer? If so therte were either significantly more programming approachers than pen and paper ones, or significantly more pen and paper approachers failed.
Not surprising that code falls over - for a naive brute force, the number of possible arrangements of n counters on an nxn board grows exponentially with n (roughly n^(2n) ). Compared to which, the mere O(n^2) time to check each potential solution is an afterthought.
I got the left solution and i did use code to brute force it. I picked it as it was the first answer it spat out. But i did get all 16 of the ones if you count reflection. (I know its not the most math way to do things)
I tried finding a way to construct an nxn grid from an (n-1)x(n-1) grid and found (exhaustively on paper oof) that you can't get a 6x6 grid from a 5x5 and that's where I gave up. It is interesting that one of the solutions did not even have a 3x3 subgrid. The other solution has a 3x3 subgrid, and the 7x7 has a 4x4 subgrid. It makes me wonder if perhaps a 10x10 grid could be made from the 7x7.
I don't think it's at all surprising that the most popular solution is the most popular. Matt doesn't break down those two solutions by rotation and reflection, but I assume that if he did, the first solution with the two squares in the top left would still be the most popular. In my opinion the most likely-looking starting point for a systematic search is all the markers on the top row, then the first 5 markers on the top row, and the 6th marker in the 1st column of the 2nd row etc. At least in theory. In practice, it pays to discard any solution that has the first three boxes of the top row filled, without looking at the fourth marker at all.
mmh, I did it exhaustively using recursion but that's kind of cheap and easy. Was wondering if there is a way to do it non exhaustively, sadly didn't see a solution for that :(
There are ways you can reduce the search space. If you divide the grid up into black and white squares like a chessboard this helps. Paths from black to white use an odd number of steps. Staying on the same colour of square takes and even number of steps. A distance of 5 (0,5) or (3,4) will always use an odd number of steps. They cannot all on the same colour as that would exclude the 8 odd distances. Having 3 on black and 3 on white would have 3 x 3 = 9 odd distance and there are only 8. You can have one on black or two on black. If you have one token on black that uses all 11 even distances. That means two tokens must be at opposite corners (the only way to get the largest of these). There are only three valid black squares. That leaves three tokens to place. If you have two tokens on black squares that uses all 8 odd distances. I did not find that very useful. You can use the same trick again on the white squares. The white squares on odd rows make a 3 by 3 grid. If you stay in this subgrid the length of the path is always 4 or a multiple of 4. That restricts you again. It turns out you can have two in the odd grid and two in the even grid, or else you can have three in the odd grid and one in the even grid. I never checked the first case where there are two in each. You don't have to. Three tokens in a 3 by 3 grid is something we know we can solve. There are only 5 layouts. Put these out at double distance on the white cells. Leave space on all sides because the grid could be offset a bit and still be valid. That leaves three tokens to place. I did not do it exactly like this but this is how I would go about it now.
Not sure if it counts as code, but I made a spreadsheet that worked like the tool at 7:10 where you chose spots and it crossed out spaces that were invalid. Then I just played around until I got a solution; it was the second one. The initial coding took maybe an hour, finding the answer was about ten minutes, and then I spent another hour or so fixing it to be nice and pretty (e.g. crossing out equidistant points, whereas the first version just yelled at you for picking them).
I found the left solution first bc my code starting by placing tokens in the top left, and only advancing a token when all potential positions for the later tokens had been checked, so token 2 started next to token 1
I coded up an interactive solution checker just like Allison's (same features and all), but I thought it wouldn't be interesting enough to send to you. oh well
Not a fool at all! The point is just to have some fun with it in whatever way u want. This puzzle obviously lent itself well to programming, but good old pen and paper could work too
I also tried by hand but couldnt get anywhere. It feels a bit like you couldn't intuit this puzzle and it requires coding to check every possibility. Id like to see some pen and paper solves.
@@TheCrewdy I will see if I can put my notes in some sort of order. Cool fact. You will find a 3x3 solution in both of the 6x6 solutions. Divide the grid into nine sudoku-like. Look at the bottom right quarter of each square in the 72%. Then look the top left of each square in the 27%. That is not a coincidence.
Hasekell is a great language with a fan base. Personally I admire Haskell, but don't use it that often as I'm way more fluent in Python and my job pays me for C#. In recent years Haskell has huge influenced on a lot of very different language. E.g. the many languages that now have async/await (e.g. Python, C#, JavaScript) or LINQ on the .Net platform.
@@adaschma I know, I'm only mostly joking. Haskell does have quite the following and it is nice to look at when learning how programming languages are built. The syntax just confuses me.
Did anyone try 3D? I imagine you might be able to get more than n on and nxnxn board. I didn't get it right to start with so not sure I am the person to do it.
That's an interesting problem. I experimented a little and got 4 counters on a 3x3x3 board. Here is my solution: 100 000 000 100 000 001 010 000 000 The distances are 1, sqrt(2), sqrt(5), sqrt(6), sqrt(8), and 3 (sqrt(1^2+2^2+2^2))
So you have proved that 15 by 15 and larger is impossible, and that there is only one solution for 7 by 7. What does this mean for 8 by 8 up to 14 by 14, is brute forcing the only way to know if there are any solutions for these?
I'm very curious about the hilarious virtual award. I wonder if anyone has gotten it yet. If you have don't spoil me. I want to earn that many points and see for myself.
So did nobody discover any solution that didn't require exhaustive searches or trial-and-error? It's definitely not as interesting not gaining any new mathematical insight into the problem, other than discovering that it's harder than you'd think.
This didn't really explain how to understand it. I really tried, and spent hours with a couple of different approaches, but they were all totally useless. So I was looking forward to learning something, but this only confused me more.
I think the main takeaway for this puzzle is why there is such a huge disparity in the number of solutions when you jump to n = 6. There are dozens of solutions for n = 5, but n = 6 only has two unique solutions. Matt explains in the beginning of the video that this is tied to the smallest Pythagorean triple (3,4,5), which shows that 5 is the smallest possible diagonal distance. The reason why we jump all the way down to only two solutions when we reach n = 6 is because it is the smallest size for a grid in which you can have diagonal distances matching up with horizontal/vertical distances (ie: you can have a diagonal distance of 5 AND a horizontal/vertical distance of 5 in the same grid).
If you generate all boards exhaustively with code it is very likely that your implementation generates the left one first because it starts with 2 "full" cells
Exactly!
@@Grimlock1979 Even when working out by hand, you figure that distance 1 is going to be one of the distances, so it's pretty natural to start with the adjacent pair. I wouldn't think to start with the D=2 and D=3 integer distances first, then get to the D=1 case later.
I just realized Matt says " Matt Parker's Math *Solutions* " every time as if he's surprised that it's "Solutions", not "Puzzles".
yeah, he's done that for all six of them, although to me it feels a little bit more like "is that what we're calling it?", which I think is also the reason why 'solutions' is just slapped on top of 'puzzles' in the thumbnail text thingy.
Like it's a placeholder for until he comes up with something better to call it.
maybe we should all agree to send a helpful way to how our names out pronounced, along with our solutions, to matt, so he won't have as much trouble with it anymore!
I send along phonetic pronounciation of my name last week and he still messed it up :p
I think they're just super swamped with submittions and so they miss stuff like that.
I'd love it if Matt could publish some Python solutions and spreadsheets for each puzzles. This is a fun way to understand other people's workflows and learn from them
"scrabble video will take longer"
2 months further already, very hyped up to see like a 5 hour video coming up or something xD
Either way I'm sure you're very busy, so I'll be patient.
They are holding it to play enough games. Matt clarified in a reply on Twitter
The Haskell solution is beautifully succinct, as a Haskell developer for over 10 years, I wanted to say well done Mihai Maruseac!
Regarding the exhaustive search, I've coded a multi-threaded c program which I've run on a 16-core machine, and managed to verify n=8-14 don't have solutions. n=15 is still running....
Brilliant! You can actually confirm that there are no solutions for n=15 using just pen and paper, by using the fact that every distance has to occur exactly once (because the number of possible distances is exactly equal to the number of pairs of points). So we've fully solved the problem!
@@OscarCunningham I've actually tried to do that myself, but I am not a great Sudoku solver :) Could you post your working out please?
I was wondering whether 10-15 had actually been checked! Not surprised that there aren't any, since the constraints seem to get tighter and tighter before becoming impossible at 16.
@@GalHorowitz It's not that hard to do: the biggest length is the distance between two diagonally opposite corners. But the only way to get distance 14 is to have both ends of a row/column (there is no Pythagorean triple with 14 as the hypotenuse), but whichever row/column you pick, one end will be the same distance from one corner as the other end is from the diagonally opposite corner - and you can't reuse either of those corners since their other end is a third corner, equidistant from both already used corners.
@@GalHorowitz Proof that the n = 15 case has no solutions: oscarcunningham.com/670/unique-distancing-problem/
Hey, recently I've finished your book "Things To Make And Do In The Fourth Dimension", and I just wanted to say I really enjoyed it! Thank you Matt Parker
So cool to involve the community! Don't have the time, but it sounds amazing!
Pretty confident the bias in solutions is because of search techniques, like the one I used, where you start in one corner and gradually move counters along. For example, trying squares 0,1,2,3,4,5, then trying 0,1,2,3,4,6, then 0,1,2,3,4,7, etc. The left solution still used squares 0 and 1, rather than 0 and 2. It's not the clump at the end that matters, but the clump at the start.
Hey, Matt Parker. I think you can solve the "pronunciation problem" by putting a box in the submission form where one can put the pronunciation of their names if it would be chosen to feature in the video.
But then Matt would still need to replicate that pronunciation which can be difficult with sounds that don't exist in english.
@@fdagpigj It should ask for IPA pronunceation
I know a few have said so, but I would guess that the “left” solution comes more naturally from pen and paper because an automatic tendency to start with a counter in the far most corner and work from there
Both solutions have a counter in a corner (which one doesn't matter, because this is just one of the rotations/reflections). I think it's because it has two adjacent counters in the corner, which would come first in most exhaustive searches.
+
Not only is there a pair in one corner, but it also uses the largest possible distance by having another in the diagonally opposite corner, which is intuitively appealing.
If it were mirrored it'd reflect how I might have solved it, since I always started with the bottom left as a "zero" corner and went from there.
Noah Baker I did it using pencil on paper and found the “right hand” solution, but turned 180° because the 0,1;1,1;2,2 pattern was “intuitively obvious” as necessary, and I started with that at 0,0 and when that didn’t work moved it to 0,1 and low and behold a solution...
This is how I did it, to maybe shed some light on why the one solution was more popular. I began with all if the counters in the top row of the grid, and when it was obvious that that wasn’t a valid solution, I took the far right counter to the next row, and continued on in that fashion until that counter reached the end of the grid. I would then move the next to last counter one space along the grid, and return the final counter to the top. This is essentially this problem’s equivalent of trying every combination for a combo lock: 000, 001, 002, etc. the solution that was found more often would be reached first by this method, because the other solution involves moving the second counter from its starting position, which would be like a combo lock with 01xxxx, whereas the more common solution would equate to 00xxxx. I searched manually with a paper grid and dimes, but I’m sure people who coded it out checked in a similar manner, as this is a simple way to exhaustively check every possible combination.
I got the mathematical idea, but without any knowledge of programming at all, it was impossible to generate and verify the candidate solutions. Apparently, I will never get one of these correct, but I will never stop watching the videos (and trying for a few hours before giving up hopelessly)
512 views, 64 likes, 32 minutes ago
It’s binary madness
Share Shares
And now, 32 likes, so please forgive me for not increasing that number to 33!
Are there any solutions for triangular or hexagonal grids?
For me, the first one was more intuitive because placing two tokens on the corners felt like a good place to start, since it's the largest distance between two points, which I hoped would give some leeway
Thanks for featuring my paper!
Minor correction: I gave a solution for n=7 and verified that 8 through 12 doesn't have a solution. I've also found the maximum number of tokens you can place on different board sizes up to 12. Turns out you can do 10 on a 12x12 board. After that it probably gets even worse.
We have now hit a point where people are high on the leader board who haven't solved all problems correctly. Thanks to speed and weighted points place 4 didn't solve the first problem correctly and place 19 didn't even submit on the first problem. Hope this encourages more people to join in the fun (or continue after a missed problem)!
I found both solutions (exhaustively) but went with the most common one because I found it more aesthetically pleasing.
10:17 did someone noticed it says “Matthew Perry”? That’s the name of the actor who plays Chandler in the sitcom Friends.
I am a little bit disappointed that you didn't include PowerShell in the list of tools people used to solve the puzzle. That was the whole reason why I did it with this language :D
That's the straw breaking the camel's back - I finally have to subscribe to this channel.
I was in the minority as I found the second solution. In fact it was exactly as shown, not rotated or reflected. I was using coins on a hand drawn grid and decided to test different integer distances along the edge, then figuring out where to arrange the shorter distances near the opposite edge. A little trial and error and there it was!
Will you post a follow up video to the one with James Grime?
I struggled with this, but i was basically pen and paper since i cant code.
Well done to people who succeeded :)
So if there are none for 15 in 2 dimensions, what’s the smallest dimension (15x15x15), (15x15x15x15) etc that do have solutions?
This was a fun one, thanks!
Does anyone have a Python code that can check for the different permutations of a set of 6 points? In other words, the other orderings of [[0, 0], [1, 0], [3, 1], [5, 3], [2, 5], [5, 5]] ? I'm a brand-new coder and want to learn how to make my code more efficient. Need it to throw out the other 719 orderings once a solution is found. Thanks
I was a little disappointed there was no mention of triangular numbers and the role they play in this puzzle. Perhaps the connection was too obvious to be worth pointing out, but the number of distances to consider follows the triangular progression of 3 for 3 counters, 6 for 4 counters, 10 for 5 counters, etc. The number of unique possible distances available in the space also follows a triangular progression one step ahead, at least that is, until you hit that first Pythagorean triple (3,4,5). But for the purposes of this puzzle it's really the triangular numbers minus 1, because 0 is not a valid distance between two counters, so the number of distances available to use are 5 for 3x3, 9 for 4x4, and 14 for 5x5. As I said, you lose one for the 3,4,5 triangle, making it 19 for 6x6, and 26 for 7x7. After that the triangular progression continues to break down as more and more duplicate distances start to appear, such as 7,1 and 5,5 both resulting in a distance of √50, or 9,2 and 7,6 both resulting in √85. Then on top of that you continue to get more Pythagorean triples (6,8,10; 5,12,13; 9,12,15), until finally the number of unique distances needed outpaces the number of unique distances available on the 16x16 grid. I can't help but wonder though, if we were allowed to count these duplicate distances as unique because they follow a different path, such that the distances available continued their original triangular progression, would we have been able to find any solutions for grids higher than 7x7?
Edit: I guess another way to put this would be: Puzzle Variant - If two distances are the same, but their Manhattan (taxicab) distances are different, they may be counted as unique distances for the purposes of this puzzle. How many more solutions can we now find on a 6x6 grid? Might there now be a solution for the 8x8 grid? And could there be other surprise solutions further up the chain now that we can't so easily rule out grids larger than 15x15, or are there other factors that would put a definitive limit on the largest possible grid with a viable solution?
I included the bit about triangle numbers in my answer. I didn’t notice the correction involving the 3-4-5 right triangle though.
How would this puzzle work on a triangular grid?
I am part of a very very small, strict subset of people
I submitted the more common solution, because my brute force solution found it first.
Before I decided to go with brute force, I figured using opposite corners was a good starting strategy.
I didn't find either (though now I see I was close... 😦), but I'm not surprised the one was more common. If you are just moving tiles around, it feels very common sense to start with the first two in opposite corners (max distance) and then one right next to one of those (min distance) and try to fit the remaining three.
Interesting. I wonder if there are any solutions between 9 and 15.
Correction...?
This video is listed twice in the "Matt Parker's Maths Puzzles" playlist.
What if you change the definition of distance to only allow vertical or horizontal movement? Spot (1,1) and (2,2) are distance 2 apart.
This is known as Manhattan (or Taxicab) Distance, and was actually covered in this video @ 11:18.
_uploaded 10 seconds ago_
What great words to see
"Yves" is pronounced like "Eve".
Like an Eaves-dropper
I thought it was ives
@Richwell Chan Sim like many words, when they cross languages, their pronunciation can change. but in French, Yves = \iv\.
The left solution looked prettier. Makes a nice arc.( It's also the lexicographically first one)
What happens in higher dimensions of this puzzle
I was hoping for a few published Python solutions. I'm learning as I go but couldn't solve it.
These write ups could have helped me show a different solution or path to one.
Does anyone have their python code that worked? I was too stupid to get it to work and would love to see how to code it
I found the less common solution, but only because I wrote some code that randomly selected six points and checked them over and over again, and that's what it spat out.
I didn't submit in time because I was stuck on the 4x4 since I kept trying to find 3 counters rather than four. I'd like to see a general equation that could take an nxn grid and find the number of unique distances for m counters. Maybe one of the solutions papers have something I can work with.
One of my initial thoughts was to treat it as trying to find an n-gon with all unique sides, but I didn't know where to go from there, so I ended up going through trees to figure out which solutions were valid or not.
Hey Matt, could you please link Rae's work showing that there are no possible solutions above 15?
This claim although it seems to be true, but I found it was not trivial at all to prove!
It is also in my paper, linked above. Basically there aren't enough different distances on larger boards.
That Haskell is very nice, it's a great language. Has anyone done any code-golf type stuff for these puzzles?
I imagine the more common solution appears more when doing searching algorithms because the adjacent pair in the top left corner seems more likely to be hit before the other arrangement.
Can we see the roland spreadsheet?
I got the left solution because I saw this problem as “build an N-gon on an NxN grid with every distance being unique”
So when I was playing around I got the shape on the left because that fit being a hexagon. The arrangement on the right is not immediately a shape, so it might have not been found as quickly.
Yeah! Me too. I tried looking it up to see if there was some kind of irregular n-gon problem out there, to no avail. There's also the matter of having more than two counters on a single line. I also messed up because I accidentally kept trying to solve a 4x4 grid, but with 3 counters.
Hey, I coded mine in the R programming language!
I must have missed something with the right-side solutionat 3:00 I had something just like it with the three pegs stacked in one column/row spaced 2 and then 3. I knew it SHOULD have been a solution, but must have counted one wrong or twice. Would have been done much sooner if I got that one. Luckily, I still found the other one just fine.
It is obvious that if one does some kind of exhaustive search, then one starts with two adjacent tokens in the first two cells and tries to find a solution, one will naturally find the left one first. This is what I had done.
I don't think I actually find one of the solutions in the end (just submitted whatever I had on screen at 23:59 on deadline night and didn't even note it down to retrospectively check it, so no idea what my 'solution' was), but I worked out that a six by six grid had six different unique squares once all rotations and reflections were taken into account (e.g. in a 3x3 there are only corner, centre and the centre edge). I postulated that you either needed exactly one of each of the six, or that one of the types that had only four choices (one of the three layers of corners) would be doubled up at the expense of one the other three types. I even worked out that the type that I called 'E' (the 8 non-corners of the centred 4x4) was often where my 'solutions' screwed up. So if I had dropped an 'E', so to speak, and replace it with an second corner ('A') and persisted with my theory a bit longer I would eventually have arrived at the right hand solution, I think. Certainly the left hand solution is noticeably further removed from my postulations and theories for what a solution would look like, so I don't think I would ever have found it by my theories.
All this is a long winded way of saying did the computer programmers who checked each combination in order usually find the left hand answer first (two consecutive cells in the top corner, as people have pointed out), and was it those who scribbled on paper and refined their theories of what was needed or likely in a solution, that tended to find the right hand answer? If so therte were either significantly more programming approachers than pen and paper ones, or significantly more pen and paper approachers failed.
I found less likely solution rotated by 90 degree counterclockwise, that is one my code stumbled upon first.
What? There could be solutions for n between 10 and 14?
There could theoretically be solutions... but exhaustive search says there isn't :(
At 9:28 your pronunciation is on point
Not surprising that code falls over - for a naive brute force, the number of possible arrangements of n counters on an nxn board grows exponentially with n (roughly n^(2n) ). Compared to which, the mere O(n^2) time to check each potential solution is an afterthought.
Is Zoa their couple name? Should it be?
I got the left solution and i did use code to brute force it. I picked it as it was the first answer it spat out. But i did get all 16 of the ones if you count reflection. (I know its not the most math way to do things)
5:32 just wondering, isn't it pronounced like Yves Saint Laurent?
The first solution is found first programmatically
I tried finding a way to construct an nxn grid from an (n-1)x(n-1) grid and found (exhaustively on paper oof) that you can't get a 6x6 grid from a 5x5 and that's where I gave up. It is interesting that one of the solutions did not even have a 3x3 subgrid.
The other solution has a 3x3 subgrid, and the 7x7 has a 4x4 subgrid. It makes me wonder if perhaps a 10x10 grid could be made from the 7x7.
The most you can do on a 10x10 grid is 9 tokens.
I don't think it's at all surprising that the most popular solution is the most popular. Matt doesn't break down those two solutions by rotation and reflection, but I assume that if he did, the first solution with the two squares in the top left would still be the most popular. In my opinion the most likely-looking starting point for a systematic search is all the markers on the top row, then the first 5 markers on the top row, and the 6th marker in the 1st column of the 2nd row etc. At least in theory. In practice, it pays to discard any solution that has the first three boxes of the top row filled, without looking at the fourth marker at all.
mmh, I did it exhaustively using recursion but that's kind of cheap and easy. Was wondering if there is a way to do it non exhaustively, sadly didn't see a solution for that :(
So... how does one work out to the solution other than using the code?
Trial and error, note taking, and some balance of luck and perseverance. A lot of graph paper.
There are ways you can reduce the search space. If you divide the grid up into black and white squares like a chessboard this helps. Paths from black to white use an odd number of steps. Staying on the same colour of square takes and even number of steps. A distance of 5 (0,5) or (3,4) will always use an odd number of steps. They cannot all on the same colour as that would exclude the 8 odd distances. Having 3 on black and 3 on white would have 3 x 3 = 9 odd distance and there are only 8. You can have one on black or two on black.
If you have one token on black that uses all 11 even distances. That means two tokens must be at opposite corners (the only way to get the largest of these). There are only three valid black squares. That leaves three tokens to place.
If you have two tokens on black squares that uses all 8 odd distances. I did not find that very useful. You can use the same trick again on the white squares. The white squares on odd rows make a 3 by 3 grid. If you stay in this subgrid the length of the path is always 4 or a multiple of 4. That restricts you again. It turns out you can have two in the odd grid and two in the even grid, or else you can have three in the odd grid and one in the even grid. I never checked the first case where there are two in each. You don't have to.
Three tokens in a 3 by 3 grid is something we know we can solve. There are only 5 layouts. Put these out at double distance on the white cells. Leave space on all sides because the grid could be offset a bit and still be valid. That leaves three tokens to place.
I did not do it exactly like this but this is how I would go about it now.
Not sure if it counts as code, but I made a spreadsheet that worked like the tool at 7:10 where you chose spots and it crossed out spaces that were invalid. Then I just played around until I got a solution; it was the second one. The initial coding took maybe an hour, finding the answer was about ten minutes, and then I spent another hour or so fixing it to be nice and pretty (e.g. crossing out equidistant points, whereas the first version just yelled at you for picking them).
Can't speak for everyone, but I started by filling two squares in the corner and worked from there. Maybe that's why the first one is so popular
I found the left solution first bc my code starting by placing tokens in the top left, and only advancing a token when all potential positions for the later tokens had been checked, so token 2 started next to token 1
List to end to find out how to become a Matt Parker's Maths Puzzles Moderator Partner.
yes! plot!
7:10 Hey, I did that too! But with spreadsheets!
I coded up an interactive solution checker just like Allison's (same features and all), but I thought it wouldn't be interesting enough to send to you.
oh well
THE Matthew Perry? Haha
The left solution is first to find with naive backtracking, greedily placing counters as you go
Some of us did this the hard way damnit! You can tell I did by my scrawly mess and incorrect second solution. Was I a fool to even try?
I spent a bit of time on paper, then made an excel solution validator, then eventually caved and brute forced it. Definitely not a fool to try.
Not a fool at all! The point is just to have some fun with it in whatever way u want. This puzzle obviously lent itself well to programming, but good old pen and paper could work too
I also tried by hand but couldnt get anywhere. It feels a bit like you couldn't intuit this puzzle and it requires coding to check every possibility. Id like to see some pen and paper solves.
@@TheCrewdy I will see if I can put my notes in some sort of order.
Cool fact. You will find a 3x3 solution in both of the 6x6 solutions. Divide the grid into nine sudoku-like. Look at the bottom right quarter of each square in the 72%. Then look the top left of each square in the 27%. That is not a coincidence.
Wait, is THAT Matthew Perry?
I think you should add Tom Scott to your team.
He should be able to pronounce them {maybe}
10:01 a transpondster using spreadsheets
Am I bad for never sending in anything despite having had a go at every puzzle?
wow Mathew Perry did this? so whats what hes been doing since friends ended
This is the only comment I've found mentioning this. Thank you.
when i did this, i was using the vertices of each constituent tile to place the markers. disappointed i misunderstood!
I have 2 questions?
Who is the person who keeps submitting their solution in Haskell and who hurt you?
Hasekell is a great language with a fan base. Personally I admire Haskell, but don't use it that often as I'm way more fluent in Python and my job pays me for C#. In recent years Haskell has huge influenced on a lot of very different language. E.g. the many languages that now have async/await (e.g. Python, C#, JavaScript) or LINQ on the .Net platform.
@@adaschma I know, I'm only mostly joking. Haskell does have quite the following and it is nice to look at when learning how programming languages are built. The syntax just confuses me.
Sure we've got a Haskell submitter, but where's my FORTRAN bois at?
My program had a bug of assuming the top left corner must be empty, so I got the 27.3% answer...
Did anyone try 3D? I imagine you might be able to get more than n on and nxnxn board. I didn't get it right to start with so not sure I am the person to do it.
That's an interesting problem. I experimented a little and got 4 counters on a 3x3x3 board. Here is my solution:
100 000 000
100 000 001
010 000 000
The distances are 1, sqrt(2), sqrt(5), sqrt(6), sqrt(8), and 3 (sqrt(1^2+2^2+2^2))
There are also 9 unique distances in a 3x3x3 board, so 5 counters would be impossible since that would make 10 distinct pairs of counters.
So you have proved that 15 by 15 and larger is impossible, and that there is only one solution for 7 by 7. What does this mean for 8 by 8 up to 14 by 14, is brute forcing the only way to know if there are any solutions for these?
Pretty much yes.
I'm very curious about the hilarious virtual award. I wonder if anyone has gotten it yet. If you have don't spoil me. I want to earn that many points and see for myself.
If you use the discrete distance, there is no solution for n > 2.
Did no one manage to deal with the cases of sidelength 11, 12, 13 and 14?
I could, I think, but I didn’t test it
I did for 11, someone else in the comments (Gal Horowitz) did up to 14.
@@pepkin88 Thanks! Link: ruclips.net/video/G0i_YSFvMb0/видео.html&lc=Ugz-O1oGvrM1DBorDGB4AaABAg
I have it up to 12, but couldn't go beyond. I think 11 is the most you can get for 13 and 14.
I feel like an idiot, I accounted for the Pythagorean triple in my code but it snuck through both my code and my manual check. Dang it
I found them all with code and then picked one out of the middle of the list.
I used processing.
First solution was more because of brute force
So did nobody discover any solution that didn't require exhaustive searches or trial-and-error? It's definitely not as interesting not gaining any new mathematical insight into the problem, other than discovering that it's harder than you'd think.
Got a palindromic rank 313
Oh, NOOO
I got it wrong 😭
I didn't count the 3,4 and the 0,5 as the same
This didn't really explain how to understand it. I really tried, and spent hours with a couple of different approaches, but they were all totally useless. So I was looking forward to learning something, but this only confused me more.
I think the main takeaway for this puzzle is why there is such a huge disparity in the number of solutions when you jump to n = 6. There are dozens of solutions for n = 5, but n = 6 only has two unique solutions. Matt explains in the beginning of the video that this is tied to the smallest Pythagorean triple (3,4,5), which shows that 5 is the smallest possible diagonal distance. The reason why we jump all the way down to only two solutions when we reach n = 6 is because it is the smallest size for a grid in which you can have diagonal distances matching up with horizontal/vertical distances (ie: you can have a diagonal distance of 5 AND a horizontal/vertical distance of 5 in the same grid).
Here is my solver: github.com/nlitsme/mpmp7_solver
Both C++ and python code, solving this for higher dimensional cases
As a Pen and Paper guy, my take away from this puzzle is learn to code!!
No one tried using higher dimensional grids? Sigh...so disappointed ;)
My solution, though I can't remember exactly how it looked, was very similar to the first one, but I also quite sure it wasn't identical.
Second place :D