BrainDen.com - Brain Teasers
• 0

# check digit problem

Go to solution Solved by DejMar,

## Question

Find the maximum number of distinct ways you can create combination of six digit number
(from 0 through 9). with following rules :

1. Each number can be used more than one.
2. Any two combinations can have at most 1 digit in same place.

example :
a. 075922 and 166433 is accepted.
b. 075922 and 166432 is accepted, both put 2 in 6th place).

c. 075922 and 066432 cannot both be used,
because both put 0 in first place, and 2 in 6th place).

Edited by jasen

## Recommended Posts

• 0
• Solution
Spoiler

As each 6-decimal-digit string can have at most one digit shared positionally between any two strings of digits, there is at most ten 6-decimal-digit strings that can occur for any given position. The answer to the problem is then the same for any decimal-digit string of length n, such that n > 1, which is 102 = 100 strings of n-decimal-digits. The number of different sets of one hundred 6-decimal-digit strings that can be formed is much greater finite number, but does not change the answer to the total number of different ways one can create a combination of six digit numbers, using the decimal digits within the given constraints.

##### Share on other sites
• 1

I think DejMar was right, though I have not yet proven it. Here is my solution for N=3 (100):

Spoiler

000 101 202 303 404 505 606 707 808 909
011 112 213 314 415 516 617 718 819 910
022 123 224 325 426 527 628 729 820 921
033 134 235 336 437 538 639 730 831 932
044 145 246 347 448 549 640 741 842 943
055 156 257 358 459 550 651 752 853 954
066 167 268 369 460 561 662 763 864 965
077 178 279 370 471 572 673 774 875 976
088 189 280 381 482 583 684 785 886 987
099 190 291 392 493 594 695 796 897 998

##### Share on other sites
• 0

Unless I'm counting wrong, it's

Spoiler

digits accepted permutations
2      100
3       76
4       70
5       46
6       62

##### Share on other sites
• 0

@bonanova. How do you get the numbers?

If I search the numbers by computer start from 000000 to 999999 the result is exactly same with your calculation. (although maybe it is not the best answer)

["000000","011111","022222","033333","044444","055555","066666","077777","088888","099999","101234","110325","123016", "132107","145670","154761","167452","176543","202318","213209","220153","231042","246735","257624","264580","275491","303145","312054", "321360","330271","347506","356417","365723","374632","404826","415937","428405","439514","480649","491758","506951","517840","529687","538796", "581473","590562","608579","619468","626894","637985","684257","695346","724978","735869","748021","759130","786302","797213","842963", "853872","962831","973920"]
Edited by jasen
##### Share on other sites
• 0

Same approach.
May not be sophisticated, likely not optimally efficient, but took only about 15 minutes.

We're both "very close" and "exactly the same"?
I guess we haven't proved the answers are unique.
Starting with a different seed might yield different results.

Anyway, here are my numbers:

Spoiler

N=2 (all 100, obviously)
00
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

N=3 (76)
000
011
022
033
044
055
066
077
088
099
101
110
123
132
145
154
167
176
189
198
202
213
220
231
246
257
264
275
303
312
321
330
347
356
365
374
404
415
426
437
440
451
462
473
505
514
527
536
541
550
563
572
606
617
624
635
642
653
660
671
707
716
725
734
743
752
761
770
808
819
880
891
909
918
981
990

N=4 (70)
0000
0111
0222
0333
0444
0555
0666
0777
0888
0999
1012
1103
1230
1321
1456
1547
1674
1765
2023
2132
2201
2310
2467
2576
2645
2754
3031
3120
3213
3302
3475
3564
3657
3746
4048
4159
4284
4395
4806
4917
5069
5178
5296
5387
5814
5905
6085
6194
6249
6358
6827
6936
7097
7186
7268
7379
7835
7924
8408
8519
8680
8791
8842
8953
9429
9538
9692
9783
9850
9941

N=5
(46)
00000
01111
02222
03333
04444
05555
06666
07777
08888
09999
10123
11032
12301
13210
14567
15476
16745
17654
20231
21320
22013
23102
24675
25764
26457
27546
30312
31203
32130
33021
34756
35647
36574
37465
40489
41598
48904
49815
50894
51985
58049
59158
60948
61859
68195
69084

N=6
(62)
000000
011111
022222
033333
044444
055555
066666
077777
088888
099999
101234
110325
123016
132107
145670
154761
167452
176543
202318
213209
220153
231042
246735
257624
264580
275491
303145
312054
321360
330271
347506
356417
365723
374632
404826
415937
428405
439514
480649
491758
506951
517840
529687
538796
581473
590562
608579
619468
626894
637985
684257
695346
724978
735869
748021
759130
786302
797213
842963
853872
962831
973920

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.