Hard problem this time

z-score

"Five men were stranded onan island. They went around picking up
coconuts for years. One day,they saw a ship coming. They had a radio
so they sent a message to comeand pick them up. The ship said "yes,
tomorrow morning!"


The five men went to sleep butthe first man woke up and thought "I
don't trust my buddies,"so he took 1/5 of the pile of coconuts.

Then a monkey came down andtook 1 coconut.


The second man woke up anddidn't trust his buddies either, so he took
1/5 of the remaining pile ofcoconuts.
The monkey came down again and
took 1 coconut.


During the rest of the night,the third, fourth, and fifth men did the
same and the monkey took 1coconut after each man.

In the morning, the five mentried to divide the remaining pile of
coconuts into five equalportions but had one left over, which they
gave to the monkey.
What is the least number of coconuts you could have in the original pile?

Please don't Google, otherwise there is no challenge!

leiz

是不是我没读懂题,还是这个是无解?
let n be the number of coconuts.
first man take 1/5, so n%5 == 0.
at the end, monkeys took 6 coconuts in total, so (n-6)%5 == 0.
we have (n = 0) %5 and (n = 1) %5.

编辑:没看清楚题,原来是分最后剩下的分成5份

江南之玥

dddddddddddddddddddddddddddddddd

celenachen

漂亮劲的--

不是排骨不熬汤

昨天阅兵空军的首批机群...

love_3_month

你的签名是今年的air show吗？

不是排骨不熬汤

不然12495就是最小值了..

不是排骨不熬汤

这个题目有点问题, 猴子先拿再除和先除猴子再拿 WILL MAKE THE DIFFERENCE.

如果猴子先拿再减1/5的话, 是3121?

(((((3121-1)X0.8-1)X0.8-1)X0.8-1)X0.8)-1)X0.8 = 1020

1020/5=204 可以最后平分.

不过这样猴子只拿了5个. 题目中猴子貌似拿了6个?

快乐的猴子

possible_value = ((((((X*5+2)*1.25+1)*1.25+1)*1.25+1)*1.25+1)*1.25) ;

output :
x=818   possible_value=12495
x=1842   possible_value=28120
x=2866   possible_value=43745
x=3890   possible_value=59370
x=4914   possible_value=74995
x=5938   possible_value=90620
x=6962   possible_value=106245
x=7986   possible_value=121870
x=9010   possible_value=137495
x=10034   possible_value=153120
x=11058   possible_value=168745
x=12082   possible_value=184370
x=13106   possible_value=199995
x=14130   possible_value=215620
x=15154   possible_value=231245
x=16178   possible_value=246870
x=17202   possible_value=262495
x=18226   possible_value=278120
x=19250   possible_value=293745
x=20274   possible_value=309370
x=21298   possible_value=324995
x=22322   possible_value=340620
x=23346   possible_value=356245
x=24370   possible_value=371870
x=25394   possible_value=387495
x=26418   possible_value=403120
x=27442   possible_value=418745
x=28466   possible_value=434370
x=29490   possible_value=449995
x=30514   possible_value=465620
x=31538   possible_value=481245
x=32562   possible_value=496870
x=33586   possible_value=512495
x=34610   possible_value=528120
x=35634   possible_value=543745
x=36658   possible_value=559370
x=37682   possible_value=574995
x=38706   possible_value=590620
x=39730   possible_value=606245
x=40754   possible_value=621870
x=41778   possible_value=637495
x=42802   possible_value=653120
x=43826   possible_value=668745
x=44850   possible_value=684370
x=45874   possible_value=699995
x=46898   possible_value=715620
x=47922   possible_value=731245
x=48946   possible_value=746870
x=49970   possible_value=762495
x=50994   possible_value=778120
x=52018   possible_value=793745
x=53042   possible_value=809370
x=54066   possible_value=824995
x=55090   possible_value=840620
x=56114   possible_value=856245
x=57138   possible_value=871870
x=58162   possible_value=887495
x=59186   possible_value=903120
x=60210   possible_value=918745
x=61234   possible_value=934370
x=62258   possible_value=949995
x=63282   possible_value=965620
x=64306   possible_value=981245
x=65330   possible_value=996870
x=66354   possible_value=1012495
x=67378   possible_value=1028120
x=68402   possible_value=1043745
x=69426   possible_value=1059370
x=70450   possible_value=1074995
x=71474   possible_value=1090620
x=72498   possible_value=1106245
x=73522   possible_value=1121870
x=74546   possible_value=1137495
x=75570   possible_value=1153120
x=76594   possible_value=1168745
x=77618   possible_value=1184370
x=78642   possible_value=1199995
x=79666   possible_value=1215620
x=80690   possible_value=1231245
x=81714   possible_value=1246870
x=82738   possible_value=1262495
x=83762   possible_value=1278120
x=84786   possible_value=1293745
x=85810   possible_value=1309370
x=86834   possible_value=1324995
x=87858   possible_value=1340620
x=88882   possible_value=1356245
x=89906   possible_value=1371870
x=90930   possible_value=1387495
x=91954   possible_value=1403120
x=92978   possible_value=1418745
x=94002   possible_value=1434370
x=95026   possible_value=1449995
x=96050   possible_value=1465620
x=97074   possible_value=1481245
x=98098   possible_value=1496870
x=99122   possible_value=1512495
x=100146   possible_value=1528120
x=101170   possible_value=1543745
x=102194   possible_value=1559370
x=103218   possible_value=1574995
x=104242   possible_value=1590620
x=105266   possible_value=1606245
x=106290   possible_value=1621870
x=107314   possible_value=1637495
x=108338   possible_value=1653120
x=109362   possible_value=1668745
x=110386   possible_value=1684370
x=111410   possible_value=1699995
x=112434   possible_value=1715620
x=113458   possible_value=1731245
x=114482   possible_value=1746870
x=115506   possible_value=1762495
x=116530   possible_value=1778120
x=117554   possible_value=1793745
x=118578   possible_value=1809370
x=119602   possible_value=1824995
x=120626   possible_value=1840620
x=121650   possible_value=1856245
x=122674   possible_value=1871870
x=123698   possible_value=1887495
x=124722   possible_value=1903120
x=125746   possible_value=1918745
x=126770   possible_value=1934370
x=127794   possible_value=1949995
x=128818   possible_value=1965620
x=129842   possible_value=1981245
x=130866   possible_value=1996870
x=131890   possible_value=2012495
x=132914   possible_value=2028120
x=133938   possible_value=2043745
x=134962   possible_value=2059370
x=135986   possible_value=2074995
x=137010   possible_value=2090620
x=138034   possible_value=2106245
x=139058   possible_value=2121870
x=140082   possible_value=2137495
x=141106   possible_value=2153120
x=142130   possible_value=2168745
x=143154   possible_value=2184370
x=144178   possible_value=2199995
x=145202   possible_value=2215620
x=146226   possible_value=2231245
x=147250   possible_value=2246870
x=148274   possible_value=2262495
x=149298   possible_value=2278120
x=150322   possible_value=2293745
x=151346   possible_value=2309370
x=152370   possible_value=2324995
x=153394   possible_value=2340620
x=154418   possible_value=2356245
x=155442   possible_value=2371870
x=156466   possible_value=2387495
x=157490   possible_value=2403120
x=158514   possible_value=2418745
x=159538   possible_value=2434370
x=160562   possible_value=2449995
x=161586   possible_value=2465620
x=162610   possible_value=2481245
x=163634   possible_value=2496870
x=164658   possible_value=2512495
x=165682   possible_value=2528120
x=166706   possible_value=2543745
x=167730   possible_value=2559370
x=168754   possible_value=2574995
x=169778   possible_value=2590620
x=170802   possible_value=2606245
x=171826   possible_value=2621870
x=172850   possible_value=2637495
x=173874   possible_value=2653120
x=174898   possible_value=2668745
x=175922   possible_value=2684370
x=176946   possible_value=2699995
x=177970   possible_value=2715620
x=178994   possible_value=2731245
x=180018   possible_value=2746870
x=181042   possible_value=2762495
x=182066   possible_value=2778120
x=183090   possible_value=2793745
x=184114   possible_value=2809370
x=185138   possible_value=2824995
x=186162   possible_value=2840620
x=187186   possible_value=2856245
x=188210   possible_value=2871870
x=189234   possible_value=2887495
x=190258   possible_value=2903120
x=191282   possible_value=2918745
x=192306   possible_value=2934370
x=193330   possible_value=2949995
x=194354   possible_value=2965620
x=195378   possible_value=2981245
x=196402   possible_value=2996870
x=197426   possible_value=3012495
x=198450   possible_value=3028120
x=199474   possible_value=3043745
x=200498   possible_value=3059370
x=201522   possible_value=3074995
x=202546   possible_value=3090620
x=203570   possible_value=3106245
x=204594   possible_value=3121870
x=205618   possible_value=3137495
x=206642   possible_value=3153120
x=207666   possible_value=3168745
x=208690   possible_value=3184370
x=209714   possible_value=3199995
x=210738   possible_value=3215620
x=211762   possible_value=3231245
x=212786   possible_value=3246870
x=213810   possible_value=3262495
x=214834   possible_value=3278120
x=215858   possible_value=3293745
x=216882   possible_value=3309370
x=217906   possible_value=3324995
x=218930   possible_value=3340620
x=219954   possible_value=3356245
x=220978   possible_value=3371870
x=222002   possible_value=3387495
x=223026   possible_value=3403120
x=224050   possible_value=3418745
x=225074   possible_value=3434370
x=226098   possible_value=3449995
x=227122   possible_value=3465620
x=228146   possible_value=3481245
x=229170   possible_value=3496870
x=230194   possible_value=3512495
x=231218   possible_value=3528120
x=232242   possible_value=3543745
x=233266   possible_value=3559370
x=234290   possible_value=3574995
x=235314   possible_value=3590620
x=236338   possible_value=3606245
x=237362   possible_value=3621870
x=238386   possible_value=3637495
x=239410   possible_value=3653120
x=240434   possible_value=3668745
x=241458   possible_value=3684370
x=242482   possible_value=3699995
x=243506   possible_value=3715620
x=244530   possible_value=3731245
x=245554   possible_value=3746870
x=246578   possible_value=3762495
x=247602   possible_value=3778120
x=248626   possible_value=3793745
x=249650   possible_value=3809370
x=250674   possible_value=3824995
x=251698   possible_value=3840620
x=252722   possible_value=3856245
x=253746   possible_value=3871870
x=254770   possible_value=3887495
x=255794   possible_value=3903120
x=256818   possible_value=3918745
x=257842   possible_value=3934370
x=258866   possible_value=3949995
x=259890   possible_value=3965620
x=260914   possible_value=3981245
x=261938   possible_value=3996870
x=262962   possible_value=4012495
x=263986   possible_value=4028120
x=265010   possible_value=4043745
x=266034   possible_value=4059370
x=267058   possible_value=4074995
x=268082   possible_value=4090620
x=269106   possible_value=4106245
x=270130   possible_value=4121870
x=271154   possible_value=4137495
x=272178   possible_value=4153120
x=273202   possible_value=4168745
x=274226   possible_value=4184370
x=275250   possible_value=4199995
x=276274   possible_value=4215620
x=277298   possible_value=4231245
x=278322   possible_value=4246870
x=279346   possible_value=4262495
x=280370   possible_value=4278120
x=281394   possible_value=4293745
x=282418   possible_value=4309370
x=283442   possible_value=4324995
x=284466   possible_value=4340620
x=285490   possible_value=4356245
x=286514   possible_value=4371870
x=287538   possible_value=4387495
x=288562   possible_value=4403120
x=289586   possible_value=4418745
x=290610   possible_value=4434370
x=291634   possible_value=4449995
x=292658   possible_value=4465620
x=293682   possible_value=4481245
x=294706   possible_value=4496870
x=295730   possible_value=4512495
x=296754   possible_value=4528120
x=297778   possible_value=4543745
x=298802   possible_value=4559370
x=299826   possible_value=4574995
x=300850   possible_value=4590620
x=301874   possible_value=4606245
x=302898   possible_value=4621870
x=303922   possible_value=4637495
x=304946   possible_value=4653120
x=305970   possible_value=4668745
x=306994   possible_value=4684370
x=308018   possible_value=4699995

走两步

12495, matlab 求证结果

hitye

lsd have empty

love_3_month

22# love_3_month I am now quite convinced that 12495 is the right (smallest) answer.  Because I think there should be some kind of characteristic for the answer, and 12495 seems the lowest possible n ...
夜.冥狼 发表于 2009-10-2 16:28

well i checked every number starting from 1. (yes i am cheating because i only know excel)

12495 is the first number meeting all criteria.

and from google i found the below thing, it got the same answer, but from another way. (seems much more professional than my Excel)

ATM does not think the below solution though. Anyone can read this through and check again?

but I am now more confident my answer is right kaka.......

http://mathforum.org/library/drmath/view/56769.html

This problem, or variants of it, have been around for a long time.  
This is how you solve it.

Let a be the number of coconuts to start with. After the first man and
the monkey took their coconuts, the number left was b = (4/5)*a - 1.
After the second man and the monkey took their coconuts, the number
left was c = (4/5)*b - 1. The third man left d = (4/5)*c - 1 coconuts.  
The fourth man left e = (4/5)*d - 1 coconuts.  The fifth man left
f = (4/5)*e - 1 coconuts.  At the end, f = 5*g + 1, where g is the
number of coconuts each man got in the morning.

Using the last equation, substitute in the previous one to get

           5*g + 1 = (4/5)*e - 1,
         5*(5*g+2) = 4*e,
         25*g + 10 = 4*e.

Now substitute that in the equation relating d and e:

         25*g + 10 = 4*[(4/5)*d - 1],
       5*(25*g+14) = 16*d,
        125*g + 70 = 16*d.

Now substitute that in the equation relating c and d:

        125*g + 70 = 16*[(4/5)*c - 1],
      5*(125*g+86) = 64*c,
       625*g + 430 = 64*c.

Now substitute that in the equation relating b and c:

       625*g + 430 = 64*[(4/5)*b - 1],
     5*(625*g+494) = 256*b,
     3125*g + 2470 = 256*b.

Now substitute that in the equation relating a and b:

     3125*g + 2470 = 256*[(4/5)*a - 1],
   5*(3125*g+2726) = 1024*a,
   15625*g + 13630 = 1024*a,
  1024*a - 15625*g = 13630.

Any positive whole numbers a and g which are a solution of this
equation will give you a solution to your original problem.  The
problem has been reduced to finding the value of a.

Notice that since 5 divides 15625 and 13630, but not 1024, that 5 must
divide a, so a = 5*h.  Then

   1024*5*h - 15625*g = 13630,

or, dividing by 5 througout,
  
      1024*h - 3125*g = 2726.

Similarly, since 2 divides 1024 and 2726, but not 3125, 2 must divide
g, so g = 2*i, and

    1024*h - 3125*2*i = 2726,
       512*h - 3125*i = 1363.

Now we can tell that i must be odd, so i = 2*j + 1, and

512*h - 3125*(2*j+1) = 1363,
     512*h - 3125*2*j = 1363 + 3125 = 4488,
       256*h - 3125*j = 2244.

Next, since 4 divides 256 and 2244, but 2 doesn't divide 3125, 4 must
divide j, so j = 4*k, and

     256*h - 3125*4*k = 2244,
        64*h - 3125*k = 561.

Similarly, k must be odd, so k = 2*m + 1, and

   32*h - 3125*m = 1843.

Similarly, m must be odd, so m = 2*n + 1, and

   16*h - 3125*n = 2484.

Now n must be divisible by 4, so n = 4*p, and

    4*h - 3125*p = 621.

Again, p must be odd, so p = 2*q + 1, and

    2*h - 3125*q = 1873.

Further, q must be odd, so q = 2*r+1, and

      h - 3125*r = 2499.

One solution to this is r = 0, h = 2499.  There are other, larger
ones, such as r = 1, h = 5624, and r = 100, h = 314999, but we will
stick with the smallest one.  The general solution is h = 2499 + 3125*
r, r any nonnegative whole number.

Backtracking, we get q = 1, p = 3, n = 12, m = 25, k = 51, j = 204,
i = 409, h = 2499, g = 818, f = 4091, e = 5115, d = 6395, c = 7995,
b = 9995, and a = 12495.  Sure enough,

   1024*12495 - 15625*818 = 13630.

Does this work?  Let's check.

Starting with 12495:
The first man took 2499 coconuts, and the monkey took 1.
  This left 12495 - 2500 = 9995 coconuts.
The second man took 1999 coconuts, and the monkey took 1.
  This left 9995 - 2000 = 7995 coconuts.
The third man took 1599 coconuts, and the monkey took 1.
  This left 7995 - 1600 = 6395 coconuts.
The fourth man took 1279 coconuts and the monkey took 1.
  This left 6395 - 1280 = 5115 coconuts.
The fifth man took 1023 coconuts and the monkey took 1
  This left 5115 - 1024 = 4091 coconuts.
In the morning, each man got 818 coconuts and the monkey 1 more.

It checks!  Hooray!

If we backtrack using h = 2499 + 3125*r, we will find that the general
answer is a = 12495 + 15625*r coconuts, for any nonnegative whole
number r.

The men must have done a whole lot of counting in the middle of the
night!

z-score

Exactly...

But 3120 is the closest in the 2500-3500 range....

(Yes, I test all these answer using excel.......)
夜.冥狼 发表于 2009-10-2 16:24

The answer has to end with either 1 or 6. Because when divide by 5, 1 is the remainder.

夜.冥狼

22# love_3_month I am now quite convinced that 12495 is the right (smallest) answer.  Because I think there should be some kind of characteristic for the answer, and 12495 seems the lowest possible number that fit the characteristics.........


Or maybe just like ATM said..... Our logic is on the wrong track to find the smallest number.........


LOL>>>>

夜.冥狼

if you use 3120, the last pile in the morning will be 1019, which cannot be didived by 5 and left 1.
love_3_month 发表于 2009-10-2 15:48

Exactly...

But 3120 is the closest in the 2500-3500 range....

(Yes, I test all these answer using excel.......)

夜.冥狼

21# saintjohn

I didn't ....

I got stuck exactly at where you get stuck... I.e. Know there are some other constraints besides the numbers, but could not put them into formula to solve them

3120 is an cheated answer from Excel.......

But even 3120 doesn't look right...

love_3_month

if you use 3120, the last pile in the morning will be 1019, which cannot be didived by 5 and left 1.

saintjohn

Well.......

3120 ??

total ??
夜.冥狼 发表于 2009-10-2 14:34

how did u work it out, bro?

夜.冥狼

Well.......

3120 ??

total ??

z-score

i think the formula should be

N original =+((((((X*5+2)*1.25+1)*1.25+1)*1.25+1)*1.25+1)*1.25) and make N integer

i still get the same result. x = 818 , N = 12495
love_3_month 发表于 2009-10-2 15:02

You have a solution, but not the solution with the least possible number of coconuts.

z-score

just work backwards:
for the original pile to have the least number of coconuts, the coconut at last day must be 6 (1 each and monkey gets one)
then before the 5th man took it, there were (6 + 1) x  ...
saintjohn 发表于 2009-10-2 14:18

The answer is around 3000.

love_3_month

i think the formula should be

N original =+((((((X*5+2)*1.25+1)*1.25+1)*1.25+1)*1.25+1)*1.25) and make N integer

i still get the same result. x = 818 , N = 12495

ceerose

15# saintjohn

you need a few more formulas than that

saintjohn

i guess in math term it is:

N original = ((((((5X +1)1.25 + 1)1.25 +1)1.25 + 1 )1.25 + 1)1.25 +1)1.25 +1

find smallest X to make N a positive integer.

is it?

saintjohn

13# love_3_month

oh true, stupid me

love_3_month

one man took 1/5, not left 1/5

your solution is like they took 4/5........

saintjohn

just work backwards:
for the original pile to have the least number of coconuts, the coconut at last day must be 6 (1 each and monkey gets one)
then before the 5th man took it, there were (6 + 1) x 5 = 35 coconuts
then before the 4th man took it, there were (35 +1) x 5 = 180 coconuts
then before the 3rd man took it, there were (180+1) x 5 = 905 coconuts
then before the 2nd man took it, there were (905+1) x 5 = 4530 coconuts
then originally (before the 1st man took it), there were (4530+1) x 5 = 22655 coconuts

love_3_month

here is my silly way (by excel, just put formula in A1, - F1, then copy down. )

the last pile should be 6, 11, 16, etc, (=x, put in A1 = 6, a2 = A1+5, copy down)
the previous one should be (x+1)*1.25 which is an integer, so x is 11/31/51/71/91 etc (B1 = (A1+1)*1.25)
the previous one should be ((x+1)*1.25+1)*1.25, which is an integer, so x is 11/91/171/251 etc (C1=(B1+1)*1.25)
the previous one should be (((x+1)*1.25+1)*1.25+1)*1.25, which is an integer, x is 251/571/891/1211 etc
the previous one should be ((((x+1)*1.25+1)*1.25+1)*1.25+1)*1.25, which is an integer, x is 251/1531/2811/4091 etc
the previous one should be (((((x+1)*1.25+1)*1.25+1)*1.25+1)*1.25+1)*1.25, which is an integer, x is 4091/9211/14331/19451 etc

when x = 4091, the original pile =12495

there must be something wrong, but i do know where.........

z-score

yeah still too big. keep trying though.

不是排骨不熬汤

关键在最后， 可以减一后，除5 得最小整数。

12495 可以得出整数818. -   有点大。。