A math brain teaser

[Random Variable]

If you know something about modular arithmetic, the following shouldn't be too difficult. If you don't, well, good luck.


Seven children are at a birthday party. A bowl full of jelly beans is distributed equally among the seven children with one jelly bean left over. The leftover jelly bean is fed to Mr. Fluffy. But before any of the children can eat his or her jelly beans, another child arrives at the party. All of the jelly beans are put back into the bowl and redistributed equally among the now eight children. This time there are six jelly beans left over which are consumed by a very happy Mr. Fluffy. Unfortunately a ninth child then arrives at the party, so the jelly beans have to be once again equally distributed among the children. There is again six jelly beans left over. What was the minimum number of jelly beans that could have been in the bowl at the start?

 

[Random Variable]

no guesses?

 

[Jesus the Porkyeti]

22

 

[Ika]

22 isn't it.

this isn't going to work with trial and error, will it...? I'm on 43 and the end is nowhere in sight....

 

[esun]

Let N be the number of beans.

N = 1 (mod 7)
N - 1 = 6 (mod 8)
N - 7 = 6 (mod 9)

N = 1 (mod 7)
N = 7 (mod 8)
N = 13 = 4 (mod 9)

Chinese Remainder Theorem time! This has a unique solution modulo lcm(7, 8, 9), which is 504. Hence, you can check all numbers 0 through 504 (it's probably easier to write a script for this than for me to go look up the CRT).

My script gives the solution as: 463

EDIT: Here's more info on the CRT in case anyone wants it:

http://en.wikipedia.org/wiki/Chinese_remainder_theorem

The brute force script (Perl)

#!/usr/bin/perl

for $i (0 .. 504) {
if ($i % 7 == 1 && $i % 8 == 7 && $i % 9 == 4) {
print "$i";
}
}


Oops, made a minor error. I only have to go to 503, not to 504. Duh. But since the answer wasn't zero anyway, doesn't matter.

 

[ShadowOfMyself]

Probably 22, unless when you say

Unfortunately a ninth child then arrives at the party, so the jelly beans have to be once again equally distributed among the children.

You mean the eight previous had already eaten theirs, and theres eight more, which would make it 30.. But im pretty sure its 22

 

[ShadowOfMyself]

Originally posted by: esun
Let N be the number of beans.

N = 1 (mod 7)
N - 1 = 6 (mod 8)
N - 7 = 6 (mod 9)

N = 1 (mod 7)
N = 7 (mod 8)
N = 13 = 4 (mod 9)

Chinese Remainder Theorem time! This has a unique solution modulo lcm(7, 8, 9), which is 504. Hence, you can check all numbers 0 through 504 (it's probably easier to write a script for this than for me to go look up the CRT).

My script gives the solution as: 463

EDIT: Here's more info on the CRT in case anyone wants it:

http://en.wikipedia.org/wiki/Chinese_remainder_theorem

The brute force script (Perl)

#!/usr/bin/perl

for $i (0 .. 504) {
if ($i % 7 == 1 && $i % 8 == 7 && $i % 9 == 4) {
print "$i";
}
}

 

[Ika]

463?

man took me 10 minutes of guessing but i did it by hand.

 

[Eeezee]

1+6+6 = 13 jelly beans eaten by the dog
Final number, after 7 are removed, is a 6 plus a multiple of 9, so the formula goes
7+6+9x = 13+9x where x > 0
13+9 = 22 (as a guess)

aaaand it looks like that's wrong
13+9 = 22
22/7 = 3r1 ---now subtract 1 from the total, it was given to the dog
21/8 = 2r5 so it's wrong

13+18 = 31
31/7 = 4r3 so that's wrong
13+27 = 40
40/7 = 5r5 so that's wrong
13+36 = 49
49/7 = 7r0 so that's wrong
58/7 = 8r2 so that's wrong
67/7 = 9r4 so that's wrong
74/7 = 10r4 so that's wrong
83/7 = 11r6 so that's wrong
92/7 = 13r1, 91/8 = 11r3, so that's wrong

Yeah that's enough

 

[imported_LoKe]

Who has a party with only 22 jelly beans? Obviously it's 463! :roll: :laugh:

Originally posted by: Aflac
463?

man took me 10 minutes of guessing but i did it by hand.

Shens.

 

[OdiN]

7,000 should be plenty of jellybeans for those little ******

 

[Eeezee]

Originally posted by: Aflac
463?

man took me 10 minutes of guessing but i did it by hand.

463/7 = 66r1
462/8 = 57r6
456/9 = 50r6

Nice :thumbsup:

 

[Ika]

Originally posted by: LoKe
Who has a party with only 22 jelly beans? Obviously it's 463! :roll: :laugh:

Originally posted by: Aflac
463?

man took me 10 minutes of guessing but i did it by hand.

Shens.

i actually went backwards. I figured out it had to be 9x [even number], then i figured out the even numbers incremented by 8. a little bit of notepad + calculator work and I got the answer.

here's how it went -

hmm, lets try 9x4. plus 6... nope not divisible by 8.

blah blah

lets try 9x18. plus 6... cool, divisible by 8! now lets add another 6... poo, not divisible by 7.

retry blah blah blah

9x50... plus 6... plus 6 again... hell yes divisible by 7! add one more, answer ding ding ding!

 

[Born2bwire]

Originally posted by: LoKe
Who has a party with only 22 jelly beans? Obviously it's 463! :roll: :laugh:

Originally posted by: Aflac
463?

man took me 10 minutes of guessing but i did it by hand.

Shens.

You could do it by brute force. That is notice you can solve for two of the conditions easily enough. For example, (x-7) = 8y and (x-13) = 9z OR (x-4) = 9m. So we can say that y = (9m-3)/8. So you can simply continuously add 9 to -3, and watch for multiples of 8 (that is, for a three digit number abc, it is divisible by 8 if ab*2+c is divisible by 8), which you can do in your head. Then when this condition is held, you find x and see if (x-1) is divisible by 7 (for three digit number abc is divisible by 7 if ab-2*c is divisible by 7) which again you can do in your head. This only requires around 50 iterations until you get up to the answer. So it is feasible to do it by hand in 10 minutes. Still, Chinese Remainder Theorem seems to me to be the textbook algorithm for solving this problem.

 

[sao123]

336

 

[thelanx]

Originally posted by: esun
Let N be the number of beans.

N = 1 (mod 7)
N - 1 = 6 (mod 8)
N - 7 = 6 (mod 9)

N = 1 (mod 7)
N = 7 (mod 8)
N = 13 = 4 (mod 9)

Chinese Remainder Theorem time! This has a unique solution modulo lcm(7, 8, 9), which is 504. Hence, you can check all numbers 0 through 504 (it's probably easier to write a script for this than for me to go look up the CRT).

My script gives the solution as: 463

EDIT: Here's more info on the CRT in case anyone wants it:

http://en.wikipedia.org/wiki/Chinese_remainder_theorem

The brute force script (Perl)

#!/usr/bin/perl

for $i (0 .. 504) {
if ($i % 7 == 1 && $i % 8 == 7 && $i % 9 == 4) {
print "$i";
}
}


Oops, made a minor error. I only have to go to 503, not to 504. Duh. But since the answer wasn't zero anyway, doesn't matter.

Man it has been a while since I really dug into math topics. I kinda miss it, maybe it is time to dig out my old Number Theory book. I really liked that class. Thanks for the reminder.

 

[iwantanewcomputer]

Got 463 in excel...took me about 10 min including reading the problem. would have been a little sooner, but i didn't remember how to make if-and statements right

i did one column = number jelly beans, next = mod(n,7) [remainder function], next =mod(n-1,8), next = mod(n-1-6,9) next=if statement where column 2 =1, 3=6, 4=6, and graphed that column

 

[nd]

I kind of cheated, but this was the fastest way I could come up with to solve it:

> #!/usr/bin/env python
>
> for n in range(8,999,7):
> if (n % 7 == 1) and ((n-1) % 8 == 6) and ((n-7) % 9 == 6):
> print "n = %d" % n

$ ./mod.py
n = 463
n = 967

 

[akubi]

you can do it by hand easy

a. x=1 mod 7
b. x=7 mod 8
c. x=4 mod 4

d. a => x=7y+1
e. d&b => 7y = 6(mod 8) => y=2(mod8)
f. e => y=8z+2
g. d&c => 7y = 3 (mod9) => y=3(mod9)
h. g&f => 8z=1(mod9) => z=8(mod9)

so let z=8, then y=66, and x=463

 

[Ika]

I rock, I'm the only one who did guess and check/trial and error.

time wasted ftw!

 

[ForumMaster]

Originally posted by: OdiN
7,000 should be plenty of jellybeans for those little ******

:laugh: Good one!
how about 42? never can go wrong with 42.

 

[Random Variable]

The answer is indeed 463. It's easier to use the substitution method than the Chinese Remainder Theorem. And if the modules had not been relatively prime, the CRT method would have failed.

 

[Oscar1613]

Originally posted by: Random Variable
The answer is indeed 463. It's easier to use the substitution method than the Chinese Remainder Theorem. And if the modules had not been relatively prime, the CRT method would have failed.

your sig makes baby jesus cry