The item causing the most difficulty is rule e, making a simple combinatorics problem complex.
First, let's consider ways of choosing the 2, 4, 6 or 8 even digits. We need to consider separately those that have a zero (which is necessarily an initial zero due to rule c) and those that do not.
The sequence of numbers represent how many ways of making a given total using the given number of even digits. Only the even totals are shown, to save space, as odd totals will never occur; the counts start with zero. For example the sequence 0 0 1 1 2 2 2 1 1 at the beginning of the 2-digit possibilities without leading zeros represent the number of ways of producing totals of 0, 2, 4, etc. To be specific, no ways of getting zero or 2, as that would entail that at least one be a zero; there's only one way of getting 4 or 6 (22 or 24 respectively); two ways each of 8, 10 or 12 (26, 44; 28, 46; 48, 66); and one way each for 14 or 16 (68 or 88 respectively).
2 of even digits:
with leading zeros
1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5
without leading zeros
0 0 1 1 2 2 2 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10
4 of even digits:
with leading zeros
1 1 2 3 4 4 5 4 4 3 2 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 35
without leading zeros
0 0 0 0 1 1 2 3 4 4 5 4 4 3 2 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 35
6 of even digits:
with leading zeros
1 1 2 3 5 6 8 9 11 11 12 11 11 9 8 6 5 3 2 1 1 0 0 0 0 0 0 0 0 0 0 0 0 126
without leading zeros
0 0 0 0 0 0 1 1 2 3 4 5 7 7 8 8 8 7 7 5 4 3 2 1 1 0 0 0 0 0 0 0 0 84
8 of even digits:
with leading zeros
1 1 2 3 5 6 9 11 14 16 19 20 23 23 24 23 23 20 19 16 14 11 9 6 5 3 2 1 1 0 0 0 0 330
without leading zeros
0 0 0 0 0 0 0 0 1 1 2 3 4 5 7 8 10 11 12 12 13 12 12 11 10 8 7 5 4 3 2 1 1 165
Totals appear at the end of each row above
1 odd digits
1 1 5 30
2 0 0 0
3 1 5 30
4 0 0 0
5 1 5 30
6 0 0 0
7 1 5 30
8 0 0 0
9 1 5 30
10 0 0 0
11 0 0 0
12 0 0 0
13 0 0 0
14 0 0 0
15 0 0 0
16 0 0 0
17 0 0 0
18 0 0 0
19 0 0 0
20 0 0 0
21 0 0 0
22 0 0 0
23 0 0 0
24 0 0 0
25 0 0 0
26 0 0 0
27 0 0 0
28 0 0 0
29 0 0 0
30 0 0 0
31 0 0 0
32 0 0 0
33 0 0 0
34 0 0 0
35 0 0 0
36 0 0 0
2 odd digits
1 0 0 0
2 1 175 525
3 0 0 0
4 2 350 1050
5 0 0 0
6 3 525 1575
7 0 0 0
8 4 700 2100
9 0 0 0
10 5 875 2625
11 0 0 0
12 4 700 2100
13 0 0 0
14 3 525 1575
15 0 0 0
16 2 350 1050
17 0 0 0
18 1 175 525
19 0 0 0
20 0 0 0
21 0 0 0
22 0 0 0
23 0 0 0
24 0 0 0
25 0 0 0
26 0 0 0
27 0 0 0
28 0 0 0
29 0 0 0
30 0 0 0
31 0 0 0
32 0 0 0
33 0 0 0
34 0 0 0
35 0 0 0
36 0 0 0
3 odd digits
1 0 0 0
2 0 0 0
3 1 3528 7056
4 0 0 0
5 3 10584 21168
6 0 0 0
7 6 21168 42336
8 0 0 0
9 10 35280 70560
10 0 0 0
11 15 52920 105840
12 0 0 0
13 18 63504 127008
14 0 0 0
15 19 67032 134064
16 0 0 0
17 18 63504 127008
18 0 0 0
19 15 52920 105840
20 0 0 0
21 10 35280 69720
22 0 0 0
23 6 21168 41328
24 0 0 0
25 3 10584 20160
26 0 0 0
27 1 3528 6468
28 0 0 0
29 0 0 0
30 0 0 0
31 0 0 0
32 0 0 0
33 0 0 0
34 0 0 0
35 0 0 0
36 0 0 0
4 odd digits
1 0 0 0
2 0 0 0
3 0 0 0
4 1 54450 81675
5 0 0 0
6 4 217800 324720
7 0 0 0
8 10 544500 806850
9 0 0 0
10 20 1089000 1593900
11 0 0 0
12 35 1905750 2737350
13 0 0 0
14 52 2822820 3963960
15 0 0 0
16 68 3680160 5015340
17 0 0 0
18 80 4303200 5623200
19 0 0 0
20 85 4530075 5638050
21 0 0 0
22 80 4197600 4910400
23 0 0 0
24 68 3500640 3803580
25 0 0 0
26 52 2599740 2599740
27 0 0 0
28 35 1686300 1541925
29 0 0 0
30 20 917400 752400
31 0 0 0
32 10 432300 316800
33 0 0 0
34 4 160380 102960
35 0 0 0
36 1 36795 20295
In each case, the third and fourth columns indicate counts, when the total of odd numbers on that line is combined with the eligible totals of ways of sums of even digits so that the overall total is less than 69. It is in this stage that the separation of zero-containing even sequences from the rest is important.
Let's take the last line above to explain the entries in columns 3 and 4. That line shows how many ways 4 odd digits totalling 36 can be combined with 8 even digits, in accordance with the rules, to form such a 12-digit number.
(If there had been more than one way for the odd numbers to add to the given value, as in the case of a total of 34, we would have had to multiply by that number of ways--in the case of 34, that would be 4, as 9997, 9979, 9799 and 7999.)
As the digits must not total more than 68, the eight even digits must not total over 68 - 36 = 32.
The ways that a set of eight even digits that include at least one zero can add to zero through 32 are (increments of 2):
1 1 2 3 5 6 9 11 14 16 19 20 23 23 24 23 23
which add to 223.
The first digit must be odd, as the lowest (and therefore first) even digit is zero. Thereafter, any of the C(11,3) = 165 ways of arranging the remaining three odd digits together with the eight chosen even digits might be used. This multiplies out to the 36795 shown in column 3 for this entry.
The ways that a set of eight even digits that do not include at least one zero can add to zero through 32 are (increments of 2):
0 0 0 0 0 0 0 0 1 1 2 3 4 5 7 8 10
which add to 41.
This time any of the C(12,4) = 495 ways of arranging the four odd digits together with the eight chosen even digits might be used. This multiplies out to the 20295 shown in column 4 for this entry.
All the entries in all the columns 3 and 4 for 3-, 6-, 9- and 12-digit numbers add up to the answer:
73,849,286 numbers that fit the pattern asked for.
DefDbl A-Z
Dim crlf$, ct(64, 1, 8), oddct(36, 4), ctForLen(12), overtot
Private Sub Form_Load()
Form1.Visible = True
Text1.Text = ""
crlf = Chr$(13) + Chr$(10)
For a = 0 To 8 Step 2
For b = a To 8 Step 2
ab = a + b
If a = 0 Then
ct(ab, 0, 2) = ct(ab, 0, 2) + 1
Else
ct(ab, 1, 2) = ct(ab, 1, 2) + 1
End If
For c = b To 8 Step 2
For d = c To 8 Step 2
abcd = ab + c + d
If a = 0 Then
ct(abcd, 0, 4) = ct(abcd, 0, 4) + 1
Else
ct(abcd, 1, 4) = ct(abcd, 1, 4) + 1
End If
For e = d To 8 Step 2
For f = e To 8 Step 2
abcdef = abcd + e + f
If a = 0 Then
ct(abcdef, 0, 6) = ct(abcdef, 0, 6) + 1
Else
ct(abcdef, 1, 6) = ct(abcdef, 1, 6) + 1
End If
For g = f To 8 Step 2
For h = g To 8 Step 2
abcdefgh = abcdef + g + h
If a = 0 Then
ct(abcdefgh, 0, 8) = ct(abcdefgh, 0, 8) + 1
Else
ct(abcdefgh, 1, 8) = ct(abcdefgh, 1, 8) + 1
End If
Next
Next
Next
Next
Next
Next
Next
Next
For ndig = 2 To 8 Step 2
Text1.Text = Text1.Text & ndig & " of even digits:" & crlf
For z = 0 To 1
If z = 0 Then
Text1.Text = Text1.Text & "with leading zeros" & crlf
Else
Text1.Text = Text1.Text & "without leading zeros" & crlf
End If
tt = 0
For t = 0 To 64 Step 2
Text1.Text = Text1.Text & Str(ct(t, z, ndig))
tt = tt + ct(t, z, ndig)
Next
Text1.Text = Text1.Text & " " & tt & crlf
Next
Text1.Text = Text1.Text & crlf
Next
For a = 1 To 9 Step 2
oddct(a, 1) = oddct(a, 1) + 1
For b = 1 To 9 Step 2
ab = a + b
oddct(ab, 2) = oddct(ab, 2) + 1
For c = 1 To 9 Step 2
abc = ab + c
oddct(abc, 3) = oddct(abc, 3) + 1
For d = 1 To 9 Step 2
abcd = abc + d
oddct(abcd, 4) = oddct(abcd, 4) + 1
Next
Next
Next
Next
For nOdddig = 1 To 4
Text1.Text = Text1.Text & nOdddig & " odd digits" & crlf
For t = 1 To 36
Text1.Text = Text1.Text & mform(t, "#0") & mform(oddct(t, nOdddig), "####0")
toteven = 0
For i = 0 To 68 - t
If i <= 64 Then
toteven = toteven + ct(i, 0, 2 * nOdddig)
End If
Next
expCt = oddct(t, nOdddig) * toteven * combi(3 * nOdddig - 1, nOdddig - 1)
Text1.Text = Text1.Text & mform(expCt, "#########0")
overtot = overtot + expCt
toteven = 0
For i = 0 To 68 - t
If i <= 64 Then
toteven = toteven + ct(i, 1, 2 * nOdddig)
End If
Next
expCt = oddct(t, nOdddig) * toteven * combi(3 * nOdddig, nOdddig)
Text1.Text = Text1.Text & mform(expCt, "#########0")
Text1.Text = Text1.Text & crlf
overtot = overtot + expCt
Next
Text1.Text = Text1.Text & crlf
Next
Text1.Text = Text1.Text & crlf & overtot & " done"
End Sub
Function mform$(x, t$)
a$ = Format$(x, t$)
If Len(a$) < Len(t$) Then a$ = Space$(Len(t$) - Len(a$)) & a$
mform$ = a$
End Function
Function combi(n, r)
c = 1
For i = n To n - r + 1 Step -1
c = c * i
Next
For i = 2 To r
c = c / i
Next
combi = c
End Function
|
|
Posted by Charlie
on 2016-05-24 16:06:42 |
computer assisted solution
