Balls in Bins

Probability Level 3

You have 20 20 balls, numbered 1 − 20 1-20 .

Can you put them into 3 3 bins such that no bin contains 3 3 balls where 2 2 numbers add up to the third?

(For example 2 , 3 2, 3 and 5 5 couldn't go in the same bin since 2 + 3 = 5 2+3 = 5 )

Image credit : shutterstock

Yes No

Geoff Pilling by Geoff Pilling , 53, USA

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

3 solutions

Geoff Pilling
Nov 6, 2018

Yes.

One way to do it:

  • 1,2,4,8,19
  • 3,5,6,7,20
  • 9,10,11,12,13,14,15,16,17,18

Bonus question : What is the highest number of balls for which you can do this?

2 Helpful 0 Interesting 0 Brilliant 0 Confused

Using this solution you could put 21 and 22 in the second bin (but you would be stuck with 23), so the highest is at least 22. I'm not sure if you can go higher with another variation, though. A computer program would be handy here.

David Vreken - 2 years, 7 months ago

Log in to reply

Definitely!

Geoff Pilling - 2 years, 7 months ago

Log in to reply

I used a computer program and found 23 to be the highest number of balls. See my solution.

David Vreken - 2 years, 7 months ago
David Vreken
Nov 6, 2018

Here's another way to do it: (1, 2, 7, 17, 20), (3, 4, 5, 6, 18, 19), (8, 9, 10, 11, 12, 13, 14, 15, 16)

I wrote the computer program below to investigate some other questions on this thread. There are actually 357 possible (non-symmetrical) ways to place 20 balls in the 3 bins. The maximum number of balls is 23, for a total of 3 possible (non-symmetrical) ways:

Bin 1 : 1, 2, 4, 8, 11, 16, 22; Bin 2 : 3, 5, 6, 7, 19, 21, 23; Bin 3 : 9, 10, 12, 13, 14, 15, 17, 18, 20

Bin 1 : 1, 2, 4, 8, 11, 17, 22; Bin 2 : 3, 5, 6, 7, 19, 21, 23; Bin 3 : 9, 10, 12, 13, 14, 15, 16, 18, 20

Bin 1 : 1, 2, 4, 8, 11, 22; Bin 2 : 3, 5, 6, 7, 19, 21, 23; Bin 3 : 9, 10, 12, 13, 14, 15, 16, 17, 18, 20

(Switching the same set of numbers in two bins would count as a symmetrical solution.)

There are no possible ways to put 24 balls in the 3 bins.

By the way, the code below can also be altered to set bins = 2 to solve Blue and Red Balls (but multiply the answer by 2 to give the symmetrical answer of switching all the blue and red balls completely). 

 1
 2
 3
 4
 5
 6
 7
 8
 9
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
 
# Balls in Bins
# Python 2.7.3

bins = 3
print "There are", bins, "bins."

# p will be filled with possible sequences
# for example, sequence "1123" means ball 1 is in bin 1, ball 2 is in bin 1,
#   ball 3 is in bin 2, and ball 4 is in bin 3
p = []
p.append("1")

a = 1
while True:
    a += 1
    # fill newp with possible sequences that is one more than the first
    newp = []
    for b in range(0, len(p)):
        for c in range(1, bins + 1):
            # to give non-symmetrical results, a ball can't skip over
            #   an empty bin 
            if c < 3 or str(c - 1) in p[b]:
                # a ball can't be added if two balls in the same bin
                #   already add up to it
                oktoaddball = True
                for d in range(0, len(p[b]) / 2):
                    if p[b][d] == str(c) and p[b][d] == p[b][a - d - 2]:
                        oktoaddball = False
                if oktoaddball:
                    newp.append(p[b] + str(c))
    # post results
    print "  For", a, "balls, there are", len(newp), "possible (non-symmetrical) ways."
    # if there are still results, switch p to newp, and start over with the
    #   next ball.  If there are no results, stop the process.
    if len(newp) > 0:
        p = newp
    else:
        break

print ""
print "For", a - 1, "balls, the following (non-symmetrical) ways are possible:"
# post possible sequences for the last ball
for a in range(0, len(p)):
    for b in range(1, bins + 1):
        strbin = "  Bin " + str(b) + ": "    
        for c in range(0, len(p[a])):
            if p[a][c] == str(b):
                strbin += (str(c + 1) + " ")
        print strbin
    print ""


 1
 2
 3
 4
 5
 6
 7
 8
 9
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
 
There are 3 bins.
  For 2 balls, there are 2 possible (non-symmetrical) ways.
  For 3 balls, there are 4 possible (non-symmetrical) ways.
  For 4 balls, there are 11 possible (non-symmetrical) ways.
  For 5 balls, there are 27 possible (non-symmetrical) ways.
  For 6 balls, there are 63 possible (non-symmetrical) ways.
  For 7 balls, there are 136 possible (non-symmetrical) ways.
  For 8 balls, there are 290 possible (non-symmetrical) ways.
  For 9 balls, there are 525 possible (non-symmetrical) ways.
  For 10 balls, there are 920 possible (non-symmetrical) ways.
  For 11 balls, there are 1438 possible (non-symmetrical) ways.
  For 12 balls, there are 2009 possible (non-symmetrical) ways.
  For 13 balls, there are 2603 possible (non-symmetrical) ways.
  For 14 balls, there are 2856 possible (non-symmetrical) ways.
  For 15 balls, there are 2929 possible (non-symmetrical) ways.
  For 16 balls, there are 2452 possible (non-symmetrical) ways.
  For 17 balls, there are 2010 possible (non-symmetrical) ways.
  For 18 balls, there are 1176 possible (non-symmetrical) ways.
  For 19 balls, there are 710 possible (non-symmetrical) ways.
  For 20 balls, there are 357 possible (non-symmetrical) ways.
  For 21 balls, there are 151 possible (non-symmetrical) ways.
  For 22 balls, there are 32 possible (non-symmetrical) ways.
  For 23 balls, there are 3 possible (non-symmetrical) ways.
  For 24 balls, there are 0 possible (non-symmetrical) ways.

For 23 balls, the following (non-symmetrical) ways are possible:
  Bin 1: 1 2 4 8 11 16 22 
  Bin 2: 3 5 6 7 19 21 23 
  Bin 3: 9 10 12 13 14 15 17 18 20 

  Bin 1: 1 2 4 8 11 17 22 
  Bin 2: 3 5 6 7 19 21 23 
  Bin 3: 9 10 12 13 14 15 16 18 20 

  Bin 1: 1 2 4 8 11 22 
  Bin 2: 3 5 6 7 19 21 23 
  Bin 3: 9 10 12 13 14 15 16 17 18 20

1 Helpful 0 Interesting 0 Brilliant 0 Confused

Interesting... I wonder how much higher you can go beyond 20...

Geoff Pilling - 2 years, 7 months ago

Log in to reply

I edited my solution. I found 23 to be the max.

David Vreken - 2 years, 7 months ago

Whoa... Cool program, David!

(I guess this shows why, when I was trying to do it by hand, it was spiraling out of control)

So, we have,

  • N(1 bin) = 2
  • N(2 bins) = 8
  • N(3 bins) = 23

I wonder how N behaves in general as the number of bins increases...

I'm re-running your program for 4 bins ...

So far I have this... (I have a feeling this will take a while. 🤔 ) 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
  For 2 balls, there are 2 possible (non-symmetrical) ways.
  For 3 balls, there are 4 possible (non-symmetrical) ways.
  For 4 balls, there are 12 possible (non-symmetrical) ways.
  For 5 balls, there are 37 possible (non-symmetrical) ways.
  For 6 balls, there are 122 possible (non-symmetrical) ways.
  For 7 balls, there are 403 possible (non-symmetrical) ways.
  For 8 balls, there are 1346 possible (non-symmetrical) ways.
  For 9 balls, there are 4183 possible (non-symmetrical) ways.
  For 10 balls, there are 12995 possible (non-symmetrical) ways.
  For 11 balls, there are 38033 possible (non-symmetrical) ways.
  For 12 balls, there are 108640 possible (non-symmetrical) ways.
  For 13 balls, there are 295418 possible (non-symmetrical) ways.
  For 14 balls, there are 783400 possible (non-symmetrical) ways.
  For 15 balls, there are 1947501 possible (non-symmetrical) ways.
  For 16 balls, there are 4795291 possible (non-symmetrical) ways.
  For 17 balls, there are 11165863 possible (non-symmetrical) ways.
  For 18 balls, there are 24463007 possible (non-symmetrical) ways.
  For 19 balls, there are 52746172 possible (non-symmetrical) ways.
  For 20 balls, there are 108460620 possible (non-symmetrical) ways.
  For 21 balls, there are 214141658 possible (non-symmetrical) ways.
  For 22 balls, there are 397365315 possible (non-symmetrical) ways.
  For 23 balls, there are 736188820 possible (non-symmetrical) ways.

Geoff Pilling - 2 years, 7 months ago

Log in to reply

Unfortunately, there are too many possibilities for 4 bins for this method to work out well.

David Vreken - 2 years, 7 months ago
Ossama Ismail
Nov 8, 2018

Ans: Yes

  • 1-2-4-7-10-15-20
  • 8-9-11-12-13-14-16
  • 3-5-6-17-18-19
0 Helpful 0 Interesting 0 Brilliant 0 Confused

Wait... Where is 6?

Geoff Pilling - 2 years, 7 months ago

Log in to reply

number 6 has been added to the last group!

Ossama Ismail - 2 years, 7 months ago

Log in to reply

Looks good! Also 15 appears unnecessarily twice.

Geoff Pilling - 2 years, 7 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...