# Minimum table size to contain combinations 000 to 999 in adjacent squares

 P: 4 Consider an m x n table containing single digits 0 to 9. So each cell contain the digits 0 to 9. My goal is to make sure that all combinations from 000 to 999 can be found in the table in adjacent cells. A cell is adjacent to the cells around it (i.e. above, below, to the left, to the right, upper right, upper left, lower right, lower left). What is the minimum size (lowest m and n) of a table which will satisfy the condition? Obviously it must be at least 6 x 5 or 5 x 6 since we need a 30-cell table since each of the digits must appear thrice in order to form the triples (000, 111, etc.). If anybody can nudge me to the right direction, I'll be very grateful. Thank you very much!
 Mentor P: 11,925 Question: Does this table include "123", "415" and "463"? 1 4 5 2 3 6 Each cell can be a part of at most 18 sets of 3 numbers. Assuming order does not matter, this gives a maximum of 18*6/3=36 numbers per cells, neglecting things like 333 (which is just a single number and not 6 different numbers). This gives 28 numbers as lower bound - worse than yours, but it will increase if you restrict the ways to build numbers.
P: 4
Thanks for the prompt reply mfb!

 Quote by mfb Question: Does this table include "123", "415" and "463"? 1 4 5 2 3 6
123 yes, 415 no, 463 yes.

I realize I should have been more explicit in the restriction. I'm not actually referring to a combination, but a permutation, although this is only relevant if we are talking about numbers all in the same row or in the same column (since if the numbers are not in the same row or the same column, we could produce all permutations, as in the case of 1, 2 and 3 in your example where 123, 132, 213, 231, 312 and 321 could be produced).

 Each cell can be a part of at most 18 sets of 3 numbers.
I don't see how to arrive at this number. Per my analysis, a cell which is at least three rows and three columns away from the border of the table would be the first digit of 42 sets. For example, in the table below, there will be 42 numbers starting with 0:

abcde
fghij
kl0pq
rstuv
wxyz*
Of course, some of these numbers would be identical. But our cell 0 in my example could also be the second or third digit.

BTW, for the real-world relevance: I saw someone looking at a 'tip sheet' for the pick 3 digit lotto game in our country and he was very confident that the three digits for the next draw is somewhere in the 16 x 16 (I think) table of single digits. He had the drawn combinations for the previous days indicated in the previous days' tipsheets, and indeed they are 'adjacent' to each other.

I immediately realized that with enough cells, it should be possible to include in the table all the combinations (as they are popularly called, but mathematically they are permutations) from 000 to 999, so a tipsheet will never be wrong (it's just that the gambler did not know where to look for the combination).

Mentor
P: 11,925
Minimum table size to contain combinations 000 to 999 in adjacent squares

 I realize I should have been more explicit in the restriction. I'm not actually referring to a combination, but a permutation, although this is only relevant if we are talking about numbers all in the same row or in the same column (since if the numbers are not in the same row or the same column, we could produce all permutations, as in the case of 1, 2 and 3 in your example where 123, 132, 213, 231, 312 and 321 could be produced).
I don't understand the logic behind that.
If all 3 digits are in the same row, how many ways do we have to read that number?

 I don't see how to arrive at this number.
Including 0:
0hc
0hg
0hi
(9 more with 0l, 0p, 0t)
0hl
(5 more with other combinations)
12+6=18

I would expect that 16x16=256 fields are sufficient to list all numbers - most numbers (720) have 3 different digits, so you can cover them with just 120 different groups of 3 numbers each, and they can overlap significantly.
P: 4
 Quote by mfb I don't understand the logic behind that. If all 3 digits are in the same row, how many ways do we have to read that number?
In the Pick 3 Lotto, the order of the digits would matter. So 123 is not the same thing as 132, and you cannot get the jackpot.

Three cells in a row with digits 1, 2 and 3 will only give us 123 and 321.

 Including 0: 0hc 0hg 0hi (9 more with 0l, 0p, 0t) 0hl (5 more with other combinations) 12+6=18
But a diagonal will also satisfy the condition, so 0ga in my example will be counted. That's why I counted 42. If we go the other way (0 in my example as the last digit instead of the first) we will also get another 42. You also add the case where cell 0 is the middle, and you get another 8. So for a cell at least three rows and columns away from the border, the cell could be part of 92 sets.

 I would expect that 16x16=256 fields are sufficient to list all numbers - most numbers (720) have 3 different digits, so you can cover them with just 120 different groups of 3 numbers each, and they can overlap significantly.
Since the holidays are over, I would have to leave this interesting problem for now. My quick and dirty solution for my friend is a program which randomly populates a 16x16 table with digits 0 to 9, and checks if each number from 000 to 999 is in the table. Surprisingly, some 16x16 tables would fail, but then again, the assignment of digits is random, and not through some algorithm, so that is expected. It would be interesting to produce an algorithm to make sure that a 16x16 table contains each of the numbers from 000 to 999.

Once I find a table which satisfies the condition, I copy it to another document, which I then email to my friend, telling him that tomorrow's combination is in that 16x16 table. I'll leave it up to him to discover this post on physicsforums.com :-)