Brain Teaser

X-Act

X-Act

np: Biffy Clyro - Shock Shock
is a Site Content Manager Alumnusis a Top Programmer Alumnusis a Top Smogon Discord Contributor Alumnusis a Top Researcher Alumnusis a Top CAP Contributor Alumnusis a Top Tiering Contributor Alumnusis a Top Contributor Alumnusis a Smogon Media Contributor Alumnusis an Administrator Alumnus
You have exactly 127 identical balls. You also have 6 empty boxes numbered 1, 2, 3, 4, 5 and 6 (hence the boxes are distinguishable). Each of the 6 boxes can hold a maximum of 63 balls. You must put all the 127 balls into the boxes in any way you like. You could, for example, put 50 in box 1, 50 in box 2 and 27 and box 5. Or put 21 in box 1, 21 in box 2, 22 in box 3, 21 in box 4, 21 in box 5 and 21 in box 6. Or however you like.

In how many ways can you place all the 127 balls in the boxes?

EDIT: The answer can be found in subsequent posts. To continue the brain teaser, what exactly do you think I needed the answer to this brain teaser for? Hint: It is related to Pokemon!
 
127C6?

516 937 9427

works out to a phone number that i assume we are supposed to call for the prize

edit: no i am not sure >:(
 
This is not an easy problem. I'm still working it out, but I think I'm on the right track. If somebody works it out before me, I'd like to know how he or she did it.
 
The problem seems straightfoward enough; it's just going to be time consuming to find all of the combinations. I'll get back to when I eventually find it.
 
Well, after working it out a bit, I realised that this problem is quite difficult. The difficult bit is the fact that the boxes can hold only 63 balls at most.

Then, I found an online applet, which gave me the answer I needed by computation.

According to that applet, the answer is... I'm not gonna tell you. :)
 
Is the answer 246774528?

I used a greedy strategy where I assume that box 1 contains the most balls, followed by box 2 and so on, then for each ordering I calculate the number of ways I can shuffle it. I think it's right but maybe I made a mistake somewhere. I have nothing to check against :) Here's my python code:

Code: 
def shuffle(ns):
    streak = 1
    previous = -1
    res = 1
    i = 0
    for n in ns:
        i += 1
        res *= i
        if n == previous:
            streak += 1
            res /= streak
        else:
            streak = 1
        previous = n
    return res

def calc(n, boxmax, nboxes, list):
    if nboxes == 1 or n == 0:
        return shuffle(list + [n]*nboxes)
    floor = n / nboxes
    if n % nboxes:
        floor += 1
    ceil = min(boxmax, n)
    res = 0
    for x in xrange(floor, ceil + 1):
        res += calc(n - x, x, nboxes - 1, list + [x])
    return res

print calc(127, 63, 6, [])

As it stands, the algorithm is exponential time, but that's because it will compute the same things exponentially often. If I memoized the answers I think it's polynomial in n and asymptotically constant in nboxes.

Edit: well ok shuffle is linear in nboxes
 
i got 298080783 through a rather clunky excel spreadsheet

1 =SUM(A$1:A1) =SUM(B$1:B1)
2 =SUM(A$1:A2) =SUM(B$1:B2)
3 =SUM(A$1:A3) =SUM(B$1:B3)
4 =SUM(A$1:A4) =SUM(B$1:B4)
5 =SUM(A$1:A5) =SUM(B$1:B5)
6 =A6+B5 =B6+C5

(edit: excel formatting is lost when posting, not sure how to keep it in. Ah well)

pasted 127 cells along, and then evaluated DW6-BL6, to account for illegal numbers of balls (more than 63) in any one box

i'm not sure its right, but comparing answers is no bad thing

Edit the second:
Oops.
DW6-6*BK6 gives the right answer
 
246,774,528 is the correct answer. :)

I managed to do this with the help of an Excel sheet, although I had managed to calculate the number of possibilities using only 3 boxes (40320) and using only 4 boxes (2499840) using math only. Those for 5 boxes and for 6 boxes were too difficult though.

The way I did it was to notice that, if W_m,n is the number of ways to place m balls in exactly n boxes with a maximum limit of 63, then

W_m,n = Sum(W_{m-i-1},{n-1}) from i=0 to i=63. This assumes that W_0,0 = 1 and W_m,n = 0 for all m<0 and n<0.

Hence I constructed an Excel sheet to work out this summation for me. It turns out that

W_127,1 = 0
W_127,2 = 0
W_127,3 = 2016
W_127,4 = 166656
W_127,5 = 7030800
W_127,6 = 202049568

Hence the answer is 2016 x 6C3 + 166656 x 6C4 + 7040800 x 6C5 + 202049568 x 6C6 = 246774528.

Now, as an aside, and as to continue the brain teaser, what exactly do you think I needed the answer to this brain teaser for? Hint: It is related to Pokemon!
 
Seriously?

Hmm, it's stats-based, no doubt. Speaking of stats, each Pokemon has 6 stats: HP, Attack, Defense, Special Attack, Special Defense, and Speed.

63 happens to be the number of points that can be gained in a single stat through EVs. (252 / 4)

127 happens to be the the maximum number of stat points that can be gained in all of the stats through EVs. (508 / 4)

X-Act, you must have something in the works dealing with EVs, but that particular number of combinations doesn't seem to be useful... unless it's for, say, a stat-optimization applet?

I'm 99% sure I'm on the right track, but I need more time to ponder this...
 
Jumping off that idea, would the solution happen to be the number of ways a certain Pokemon can be EVed, assuming EVs are snapped to multiples of 4?
 
Yes, that's what I needed this answer for: I wanted to find the total number of EV combinations that a Pokemon can have. Good catch.

So now I know that there are 246,774,528 different EV combinations for every Pokemon... without considering its nature. Interesting how the vast majority of them are useless! I'd say there would be only around 20 EV combinations at the very most that would be viable on a particular Pokemon.
 
actually sir, can the same problem be solved by computing the coefficient of x^127 in the binomial expansion of (1-x)^64*(1-x)^(-1) ? that's the way we solved problems of such sorts where a box can hold none or more of a specified problem

i see how the topic title Brain teaser seems to be appropriate, however. :happybrain:
 
i predicted someone was going to whip up a quick algorithm in some sort of programming language and i was right!

Good work Brain :D
 
You must log in or register to reply here.
Back
Top