7
$\begingroup$

Is it possible to construct a 5x5 matrix of decimal digits, such that each of the numbers 0-99 are present as individual or adjacent digits. Adjacent can mean horizontal, vertical or diagonal and reversed in all three cases. For example, the matrix below contains 18 as the top left digits are 1 and 8, and 60 is diagonal at the bottom left.

\begin{array}{ccc} 1&8&7&9&4\\ 5&1&8&3&5\\ 3&0&6&2&5\\ 9&9&2&6&7\\ 3&1&4&4&0 \end{array}

The above matrix isn't a solution as 33,48,77 and 84 are missing. I would be interested to see a successful solution, or a proof that none exists.

$\endgroup$
  • 1
    $\begingroup$ The example does not seem to match the description. Neither $6$ nor $2$ is in the top line and the only $45$ I find is in the top right. Do the numbers need to be two digits, so we need $00$? We need $01$ because we need $10$ and so on. $\endgroup$ – Ross Millikan Nov 27 '18 at 14:48
  • $\begingroup$ Well spotted thanks @RossMillikan $\endgroup$ – user2882061 Nov 27 '18 at 14:59
6
$\begingroup$

I don't know if it is possible, but it is very restrictive.

There are $72$ adjacent pairs of digits in the grid ($20$ horizontal, $20$ vertical, $16$ in each diagonal direction).

We want every two-digit number to occur. That means that we will have $10*9/2=45$ pairs with distinct digits, plus a further $9$ pairs with identical digits (we're excluding $00$). So our numbers use up $45+9=54$ adjacent pairs in the grid.

Consider any adjacent pair of identical digits. If there is a cell adjacent to both, then you waste one of the grids pairs because you will have a duplicate 2-digit number pairing. Wherever you place an identical digit pair, there will always be at least two neighbouring cells adjacent to both digits. If you place them horizontally or vertically and not at the outside edge of the grid, you even get four. In any case, every identical pair wastes two of the grid's pairings, so $9*2=18$ pairings get wasted in this manner.

Since $54+18=72$, you cannot waste any further grid pairings. In particular, you cannot put identical digits horizontally or vertically adjacent, unless they are both on the edge of the grid. In your example, the two horizontally adjacent $9$s show that it cannot be a solution.

Edit:
@TodorMarkov pointed out in the comments that it is possible to arrange two identical pairs so they diagonally cross each other. This uses up $6$ grid pairings, but contains three of the two-digit numbers. So this arrangement wastes only $3$ grid pairings on duplicates instead of the $4$ that the two identical pairs would otherwise waste.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ You can squeeze some more leeway by arranging digit pairs on the diagonals of a a 2x2 square, which would make you double count some. On the other hand, you're guaranteed to have at least one digit three times, which will cause waste. $\endgroup$ – Todor Markov Nov 27 '18 at 15:39
  • 1
    $\begingroup$ There are 144 pairs, (20 + 20 + 16 + 16)*2. Five numbers will appear three times and five twice. Those that are twice must be adjacent to get 11, 22 etc. $\endgroup$ – user2882061 Nov 27 '18 at 16:03
  • 1
    $\begingroup$ @user2882061 I am considering adjacent pairs regardless of their order, and so considering for example $16$ and $61$ to be the same number. If the zero digit appears only twice they do not have to be adjacent. It is possible (but unlikely) that some digit occurs more than 3 times, though you then have at least 6 other digit values that occur only twice. $\endgroup$ – Jaap Scherphuis Nov 27 '18 at 16:27
  • 1
    $\begingroup$ Let's consider those 5 numbers that only appear twice. At least 4 of them are not zero and they going to be adjacent to each other, so they need to form a compact island $$\begin{pmatrix}1&1&2&2\\3&3&4&4\end{pmatrix}$$ $\endgroup$ – Vasily Mitch Nov 27 '18 at 16:34
  • 2
    $\begingroup$ Update 2 $$ \begin{array}{ccccc}0&1&8&5&6\\ 9&5&1&6&5\\ 6&2&3&4&7\\ 2&0&4&3&7\\ 7&8& 8&9&9\end{array}$$ lacks only one pair 17. If I haven't made a mistake in my bruteforce, that is the best you can do. $\endgroup$ – Vasily Mitch Nov 28 '18 at 14:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.