Register to reply 
Minimum table size to contain combinations 000 to 999 in adjacent squares 
Share this thread: 
#1
Dec3112, 07:41 AM

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 30cell 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! 


#2
Dec3112, 10:33 AM

Mentor
P: 12,037

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. 


#3
Dec3112, 06:49 PM

P: 4

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


#4
Jan113, 07:20 AM

Mentor
P: 12,037

Minimum table size to contain combinations 000 to 999 in adjacent squares
If all 3 digits are in the same row, how many ways do we have to read that number? 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. 


#5
Jan113, 10:07 AM

P: 4

Three cells in a row with digits 1, 2 and 3 will only give us 123 and 321. 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 :) 


#6
Jan113, 01:09 PM

Mentor
P: 12,037

Oh sorry, I forgot the diagonals.
Here is a solution with 254 tiles: Consider a 2x2block 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 Lshaped 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 Lshaped 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 16x16square 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. 


#7
Jan313, 12:45 AM

P: 4

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! 


#8
Jan313, 11:01 AM

Mentor
P: 12,037

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. 


Register to reply 
Related Discussions  
Minimum Combinations problem, n detectives with unique clues. Min. no. of phonecalls?  Calculus & Beyond Homework  1  
Parallelogram: Sum of the squares of the sides = sum of the squares of the diagonals?  Precalculus Mathematics Homework  10  
Minimum Size in spin networks/foams.  Beyond the Standard Model  1  
Minimum feature size  Engineering, Comp Sci, & Technology Homework  0 