All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
Wanted: gifted numbers (Posted on 2016-05-24) Difficulty: 3 of 5
How many positive integers are there, fitting the following description ("gifted" numbers):

a. The total number of digits is below 13.
b. The number of even digits is twice the number of odd digits .
c. The even digits within the number read from left to right form a non-decreasing sequence
d. The odd digits within the number may appear in any order.
e. The s.o.d. of the number is less than 69.
f. Clearly, no leading zeroes.

Few samples of qualifying numbers: 300, 254, 436111878, 653766668.

No Solution Yet Submitted by Ady TZIDON    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution computer assisted solution Comment 1 of 1
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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information