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

Home > Algorithms
Marbles in boxes (Posted on 2017-08-16) Difficulty: 4 of 5
How many distinct distributions (x,y,z,w) of n identical marbles in 4 boxes labeled A,B,C and D are there, such that
x,y,z,w are positive integers in strictly increasing order?

Verify the validity of your formula (or set of formulas) by manual listing of all such distributions for n=18.

No Solution Yet Submitted by Ady TZIDON    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution solution | Comment 2 of 5 |
In mathematical notation:

Sigma{x=1 to floor((n-1)/4)} 
  Sigma{y=x+1 to floor((n-1-x)/3)}
    Sigma{z=y+1 to floor((n-1-x-y)/2)}
                                       1

The algorithm produces

 n distributions
10       1
11       1
12       2
13       3
14       5
15       6
16       9
17       11
18       15
19       18
20       23
21       27
22       34
23       39
24       47
25       54
26       64
27       72
28       84
29       94
30       108
31       120
32       136
33       150
34       169
35       185
36       206
37       225
38       249
39       270
40       297
41       321
42       351
43       378
44       411
45       441
46       478
47       511
48       551
49       588
50       632
51       672
52       720
53       764
54       816
55       864
56       920
57       972
58       1033
59       1089
60       1154
61       1215
62       1285
63       1350
64       1425
65       1495
66       1575
67       1650
68       1735
69       1815
70       1906

For n=18 the fifteen distributions are:

1 2 3 12
1 2 4 11
1 2 5 10
1 2 6 9
1 2 7 8
1 3 4 10
1 3 5 9
1 3 6 8
1 4 5 8
1 4 6 7
2 3 4 9
2 3 5 8
2 3 6 7
2 4 5 7
3 4 5 6

The program below uses a, b, c and d instead of x, y, z and w. The same idea. The for statement increments by 1 each time, so it will indeed stop with the floor of the terminal value given.


DefDbl A-Z
Dim crlf$


Private Sub Form_Load()
 Form1.Visible = True
 
 
 Text1.Text = ""
 crlf = Chr$(13) + Chr$(10)
 
 For n = 10 To 70
   ct = 0
   For a = 1 To (n - 1) / 4
   For b = a + 1 To (n - a - 1) / 3
   For c = b + 1 To (n - a - b - 1) / 2
       d = n - a - b - c
       ct = ct + 1
   Next
   Next
   Next
   Text1.Text = Text1.Text & n & Str(ct) & crlf
 Next
 
 
 Text1.Text = Text1.Text & crlf & " done"
  
End Sub

                                       1

  Posted by Charlie on 2017-08-16 11:41:37
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 (7)
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