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

[islesv]

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!

 

[mfb]

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.

 

[islesv]

Thanks for the prompt reply 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).

 

[mfb]

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.

 

[islesv]

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 :-)

 

[mfb]

Oh sorry, I forgot the diagonals.

Here is a solution with 254 tiles:

Consider a 2x2-block
a b
c d
It contains every combination of those 4 digits without repetition, 24 numbers in total.

To get all 720 numbers with 3 different digits, we need at least 30 sets of those 4 numbers.

I started with all sets containing 1, and found a solution for 12 of those sets:
1234
1256
1278
1290
1357
1360
1389
1459
1468
1470
1580
1679

Obviously, they have some overlap: Groups which share two numbers. This allows a better packing into 3 blocks of 9 tiles each:

8 5 6
0 1 2
6 3 4

3 7 8
5 1 2
4 9 0

6 9 3
7 1 8
0 4 6

Every possible "L"-shaped set in those blocks gives 6 unique, different numbers, with a total of 12*24=288 numbers in those 27 tiles, including 216 with a 1 inside.

It gets tricky to find additional combination, but it still works. Here are all missing sets for 2 (without 1), again packed into blocks of 9. This gives additional 8*24=192 numbers in 18 tiles.

7 8 3
6 2 5
4 0 9

6 3 0
9 2 7
8 4 5

It is not possible to do the same for 3 - I think it is a fundamental problem. Here are groups which are quite good:
3456
3479
3480
3590 <- 590 was covered by 2590
3678 <- 678 was covered by 2678

As pattern:
4 0 7 9 0
8 3 4 3 5
7 6 5

This covers additional 18 groups of 3 numbers, so we have 108 more numbers with 13 tiles.

To summarize, I covered 588 numbers with 58 tiles.

There are 720 numbers with three different digits, so we are missing 132, or 22 groups of 3 numbers. As I am tired of finding blocks of 4, let's use L-shaped groups of 3 to cover those missing numbers: 66 additional tiles cover 132 numbers (see how bad the ratio gets ;)).

All those 720 numbers get covered with 124 tiles.

For numbers with repeating digits, consider the following pattern:
1 2 3 4
0 0 0 5 0
6 7 8 9
It contains all numbers with two or three times 0 (in total 28 combinations), and needs 13 tiles. We can use ten of those patterns to cover all missing numbers, this needs 130 tiles.

In total, we need 254 tiles to cover all numbers from 000 to 999.

This is a weak upper bound - those L-shaped elements have a bad ratio, and the pattern for doubled digits could be improved (and glued together), in addition some (most? all?) missing groups can be included there.
Geometry is an issue, but the possible size reductions should make it fit.

Edit: Improved design for 0, 4 and 5:
1 2 4 9
5 5 5 8 5
3 6 0 7 4 (see edit3)
4 4 4 5 4
1 2 9 8
0 0 0 7 0
3 4 5 6

This covers the triples (450,670,789,780,790,458,570,560,578,589) for a reduction by 30 tiles. In addition, it needs just 31 tiles instead of 39. This reduces the number of tiles by 38, for a new result of 216 tiles.

Edit2: Improved design for 6 and 7:
0 8 9 5
7 7 7 6 7
1 2 3 4
6 6 6 9 6
7 5 8 0 4 (see edit 3)
This covers the nine triples (469,567,568,689,680,690,467,569,579) for an additional reduction by 27 tiles. In addition, it just needs 22 tiles instead of 26. New result: 185 tiles.

Edit3: The two remaining triples can be added to the existing patterns, saving 4 tiles and removing all small parts. New result: 181 tiles.

Before you give that to your friend, you should let a computer check all combinations ;).Edit4: In any way, it fits in a 16x16-square without problems, see attachment. Even if there are some numbers missing, it is easy to add them.
You can combine 1/2/3/8/9 to save even more space without problems. This allows a reduction of at least 16 tiles. In addition, I would expect that many elements of the upper "3"-part are included in other elements, so this could shrink a bit, too.

 

[islesv]

Wow, amazing analysis, mfb. Thank you so much!

For now I just settled with a program to randomly populate a 16x16 table with the digits. The program also checks if all numbers from 000 to 999 exist in the table; if not, it generates another table.

Thanks again!

 

[mfb]

I would be interested in the fraction of tables with all numbers present.
We have ~10000 possible combinations, if they are all independent this leads to a probability of ~5% that at least one number is missing. Correlations increase this fraction a bit, but probably not more than a factor of 2. Hmm, ok, random tables are good.