# Proving the existence of a given matrix

I found this problem in a programming forum Ohjelmointiputka, https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=ahdruu and https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=ahdruu2 Somebody said that there is a solution found by a computer, but I was unable to find a proof.

Prove that there is a 9×13 matrix containing the digits such that one can read the square of the numbers 1, 2, ..., 100.

Here read means that you fix the starting position and direction (8 possibilities) and then go in that direction, concatenating the numbers. For example, if you can find for example the digits 1,0,0,0,0,4 consecutively, you have found the integer 100004, which contains the square numbers of 1, 2, 10, 100 and 20, since you can read off 1, 4, 100, 10000, and 400 (reversed) from that sequence.

But there are so many numbers to be found (100 square numbers, to be precise, or 81 if you remove those that are contained in another square number with total 312 digits) and so few integers in a grid (9*13 = 117 digits, to be precise) that you have to put all those square numbers so densely that finding such a matrix is difficult, at least for me.

TL;DR  In other words, make a "number-search" puzzle (like a word-search, but with digits) where the numbers to be included are the squares of the numbers from 1 to 100.  The puzzle grid must be 9×13 digits.

• Thats not what that tag is for (was grid-deduction I edited).. this is better asked on either Stack Overflow or Math.SE – Beastly Gerbil Apr 19 '17 at 18:13
• @RosieF Definitely NOT metapuzzles! That's for puzzles whose solution is reliant on the answers to several other sub-puzzles, in one go (i.e. not a chain of puzzles). – boboquack Apr 19 '17 at 18:59
• Maybe I’m just the dumb kid here — I’m running low on caffeine — but I just don’t understand this. When you say “square”, do you mean it in the sense of $x^2$; e.g., in the sense that 49 is the square of 7?  I ask because, when you’re talking about an $n\times m$ grid, the term “square” could mean cell. And if you are talking about $x^2$, what does 10004 have to do with 1, 2, 10, 100 and 20?  I can see that “10004” contains the strings “1”, “4”, “100” and “400” (reading backwards) — but 100² = 10000, and “10004” doesn’t contain “10000” (unless you’re allowed to double back,  … (Cont’d) – Peregrine Rook Apr 19 '17 at 22:05
• Proving the existence of a matrix...hmmm... can the matrix think? No? ... Well so much for cogito ergo sum... I guess we will never know if the matrix really exists. – stack reader Apr 20 '17 at 7:32
• So we need to track 358 digits (for 100 numbers) in a 117 digit grid, meaning each square in the grid is on average part of 3,06 numbers. That's densily packed... – Tim Couwelier Apr 20 '17 at 8:53

The only way to prove is to make it, which is very tedious.

It is trivial to show it might possibly exist or not - we require at least N 1s, M 2s etc to build all numbers with that digit. If we consider every instance of a digit to be a part of max 4 numbers (lower bound as long as the digit is not on the edge or in the corner), we can easily show this might indeed be possible.

Now let's say we want to build it.

We need to focus mostly on 4 digit numbers - there are more of these and they are harder to obtain than 3 digit numbers (which are sometimes contained in 4 digit ones anyway). All 1 or 2 digit ones are trivially present as part of (5X)^2.

We have in total 358 digits

0: 40
1: 48
2: 44
3: 21
4: 50
5: 27
6: 48
7: 19
8: 24
9: 37

So, lets start looking at 3 and 7 as those two are the rarest. Numbers that are interesting with 3 or 7 are 3364, 3721, 7396, 8836 (double 8s, 8 is not that common either), 5776 and 7744. Out of these, 3721 and 7396 have 3 and 7 together (and are the only two with both). It would make sense to have number 127396 to have a single 3+7 junction. 5776 should be a part of something that has 57, say 965776. There is no 67 - there is no 76xx and a square never ends with 7. Now lets link these 2 and obtain a nice 10 digit number 1273965776, which contains 4 squares. No way to (relevantly) stuff it further with 3 or 7 in this direction. Let's move to the same number, other direction. There is a single 3, let's put double 3 on that number and make it along a diagonal to avoid making another 37 which would be irrelevant. Now we see we have obtained 36 by that new 3 and existing 6. It might be a part of 8836, fill that out. Out of 7s already here, we can use one to make the other double 7, in such a way there is no additional 77 generated, nor is there 37. Suppose it is the first 7 and also goes in the same half-space as 3364 (perpendicular to it).

Etc etc. I can't be bothered to continue further. You can if you wish.

There is no meaningful analysis and thinking to do, it is a programming exercise. Start with a number in top left corner, say we are starting from big to small and go with 10000. Put the next number (9801) to have highest overlap with current numbers. Then put the next one (9604) to maximize overlap again etc etc, until you reach 1 and end. On contradiction (no spaces left), remove last placed number and put it on the next best spot. Repeat until you find a solution. Keep going, and if you find 4 solutions in the end, it is unique, just mirrored (horizontally, vertically or both).

EDIT: This programming exercise did not work. Sure, it is increasing number of placed numbers, but far too slow to be worth waiting for an eventual solution. I might later try to make it work using better approaches, like first placing all numbers with 7 (minimizing number of 7s in the process), then with 3 etc - by rarity. Maybe. Who knows if it works. The thingy is incredibly dense and it isn't merely required to wiggle numbers a little bit and have it all fit.

• I once read the statement 'if brute force can't solve your problems, you're just not using enough of it'. However, randomly creating all possible grids (10^13 variations, and doing checks if all required numbers appear in there) would end up at somewhere in the 10^15-10^16 operations required. Unfortunately however, I do not have acces to one of them 500-terraflops-computers, so errr... I may resort to giving up due to lack of sufficient brute force. – Tim Couwelier Apr 20 '17 at 11:33
• @TimCouwelier Just 10^13 grids? Where did you find this number? Going by the dumbest brute force you would have 10^117 possible grids to search on :) 117 fields, 10 numbers per field. – Zizy Archer Apr 20 '17 at 12:14
• Went wrong twice - mistaken the 117 options for 113, and then somehow start typing and type 13 instead of 113. Either way, I'm lacking enough calculation power... – Tim Couwelier Apr 20 '17 at 13:03
• The most important statement in this answer is its first, that the "proof" is simply the solution found by computer. It's already sufficient as a proof of existence. – justhalf Apr 21 '17 at 3:46
• @justhalf Yeah, now we only need to find the solution by computer :) I tried with that pseudocode I wrote above and it doesn't work - it manages to only place 66 numbers in the first go (starting from top), and quickly reaches 65. 64 took a long time. Sure, if I let it run for a few days it might eventually reach 50-ish, but it is still a long way to go :) – Zizy Archer Apr 21 '17 at 7:13

Probably this should be a comment, but it's too long for that.
Here's a description of the complete list of numbers to be included in the matrix.

Squares of numbers for which $x\le10$ holds, are contained by the square of $10\times x$ (e.g. $7^2=49$, $70^2=4900$). Furthermore $20^2=400$ is contained by $80^2=6400$ and $30^2=900$ by $70^2=4900$.

$12^2=144$ and the reversal of $21^2=441$ are both contained by $38^2=1444$.

$13^2=169$ is a reversal of $31^2=961$.

$15^2=225$ and $25^2=625$ are contained by $35^2=1225$ and $75^2=5625$ respectively.

$18^2=324$ is contained by $57^2=3249$.

$33^2=1089$ is a reversal of $99^2=9801$.

So the numbers to be placed in the grid are the squares of integers in the range of $[11, 100]$, except $12$, $13$, $15$, $18$, $20$, $21$, $25$, $30$ and $33$.