Subscribe via feed.

Camel Inheritance

Posted by luv2fap on February 3, 2011 – 9:11 pm

An old man willed that upon his death, his three sons would
receive the uth, vth and wth parts of his herd of camels (i.e.,
1/u, 1/v and 1/w of the herd). He had uvw-1 camels in his
herd when he died. Since they could not divide uvw-1 into u,v
and w parts, they approached a distinguished mathematician
for help. He rode over and added his camel to the herd, and
then fulfilled the old man’s wishes. One camel remained, which
was of course his own.
How many camels were there in the herd?

Tags:
This post is under “Tom” and has 20 respond so far.
If you enjoy this article, make sure you subscribe to my RSS Feed.

20 Responds so far- Add one»

  1. 1. John Said:

    wow, this is tricky…I’m pretty sure I’ll be spending the next few hours trying to solve this.

  2. 2. Nathan Said:

    41 camels

    2*3*7-1=41
    2*3+2*7+3*7=6+14+21=20+21=41

  3. 3. luv2fap Said:

    Good work Nathan. Why did you say 2, 3 and 7 though? Did you make any assumptions? 11 also works, if we say u=3, how come you didn’t say that?

  4. 4. Nathan Said:

    some trial and error used, numbers given to show that the given number of camels is actually a solution and not just a guess as far as the number of camels is concerned.

  5. 5. slavy Said:

    I know what you mean luv2fap, but actually 11 doesn’t work for u=3 – it is just the only possibility that MIGHT work there. 41 is the unique solution of the problem and I will not give out my arguments so far, although I think that the problems you presented are too mathematical for the taste of the people here (of course, I personaly don’t complain about that).

  6. 6. Chris Said:

    Hi luv2fap. You’ve put up ome good problems, thank you.

    I don’t have a nice answer for this. But here are might thoughts so far.

    I’m assuming that u, v and w are integers.

    We must have uvw = vw + wu + uv + 1 (that’s the sons shares plus the borrowed camel). So vw = -1 (mod u), wu = -1 (mod v) and uv = -1 (mod w).

    Clearly u,v,w > 1, otherwise one son would get the whole herd.

    Also u,v and w must be co-prime and hence distinct.
    Proof: e.g. if v was not co-prime to u, then v = nu for some n and then vw = nuw = 0 (mod u) and not -1 as required.

    In general I find it difficult solving modular arithmetic equations, so I’ll use some common sense instead. Dividing the first equation by uvw and rearranging =>
    1/u + 1/v + 1/w = 1 – 1/(uvw).

    Using the uniqueness and co-primality of u,v,w => that uvw ≥ 2*3*5 = 30. So 29/30 ≤ 1/u + 1/v + 1/w < 1. If any of u,v,w are larger than that, the lower bound of that approximation becomes closer to 1.

    I'll probably be half an hour before posting more.

  7. 7. Chris Said:

    Ooops. I just realised that u,v,w need not be co-prime. I really meant that that one cannot be a multiple of another. My arguments still hold, I simply used the wrong terminology.

  8. 8. Chris Said:

    LOL. I’ve definitlely got a touch of brain-fart.
    u,v and w must be co-prime after all.
    Proof: let e.g. u and v have a common prime factor p, so u = pm and v = pn, for some n and m, then using
    uvw = vw + wu + uv + 1, we have uvw = p²mnw = 0 (mod p).
    But vw + wu + uv + 1 = pnw + wpm + p²mn + 1 = 1 (mod p).
    That => 0 = 1, and that’s not allowed.

    Back soon.

  9. 9. Chris Said:

    Trying u,v,w = 2,3,5 => 30 camels, so the son’s would get 15+10+6 = 31 camels, so that’s no good. We need them to get 29, so that’s no good. The next possible choice is 2,3,7 => 42 camels => 21+14+6 = 41 and that does the job.

    I’m going to have a think about this, especially as slavy says that’s the only possible answer. But it’s 3 am here and I’m gagging to play Resident Evil 4 for an hour.

    Other possible herd sizes would be 2*5*7, 3*5*7, 2*3*11 etc.

  10. 10. Chris Said:

    I’m a nit. I had forgotten where I was going with the inequality at the end of my first post. The point was that as the herd size increases (uvw-1), then 1/u + 1/v + 1/w must become closer to 1. Therefore we need each of u, v and w to be approcimately 3. But the next possible herd size after 42 is u,v,w = 2,3,11 => 66. But then 1/2 + 1/3 + 1/11 = 61/66, and is woefully short of 1 – 1/66 = 65/66. As we increase the herd size further, we get further away from satisfying the inequality.

    So the only possible (original) herd size is 41 and then
    u,v,w = 2,3,7.

  11. 11. Chris Said:

    This post is just me waffling away ;)

    I don’t like my solution, although it is “correct”.
    I’ve been examining: vw = -1 (mod u), wu = -1 (mod v) and uv = -1 (mod w)

    Using the third we have uv = mw -1 for some m > 0.
    Partially substituting into uvw = uv + vw + uw + 1 =>
    uvw = (mw-1) + w(u+v) + 1 = w(m + u + v)
    As w ≠ 0, we can divide throughout by w => uv = m + u + v, from which we immediately have m+v = 0 (mod u) and m+u = 0 (mod v).
    m+v = 0 (mod u) => m = -v (mod u) => m = nu – v for some n > 0.
    Substituting that into uv = mw – 1 => uv = nu – v + u + v
    => uv = (n+1)u => v = n+1 => m = nu -n-1 = n(u-1) -1

    At this point I have completely lost the plot.

    Considering uv = -1 (mod w), I was nearly tempted to conclude that meant
    that either u = 1 and v = -1 (mod w) or u = -1 and v = 1 (mod w). But that conclusion cannot be drawn (as easily seen using the 2,3,7 known solution shows). So be warned, you must be very careful when manipulating residues.

  12. 12. slavy Said:

    Let me give an alternative/more mathematical solutions for the problem. From uv+uw+wv=uvw-1 we immediately conclude that each pair of variables are co-prime. Indeed, assuming that the greatest common divisor of u and v is bigger than 1, i.e., (u,v)=p>1, then p divides the left-hand-side, p divides uvw, so p should divide 1 as well – contradiction. Since the numbers are co-prime – they are different. Let, without loss of generality, assume u<v0 (w should be a positive integer!) But, since v<w, we have v(uv-u-v)<uv+1, which is equivalent to v(uv-2u-v)<1 and since the right-hand-side is always an integer we conclude v(uv-2u-v) less or equal to 0. Hence, u-1-2u/v < =0. Since u/v<1, we have u0 we have u>1 (the last thing we have by other more obvious reasons, but let’s not go into trivialities). Therefore u=2 and w=(2v+1)/(v-2)=2+5/(v-2). In order w to be an integer, v-2 should divide 5, so v-2=1 or v-2=5, and since we assumed v<w, only v-2=1, v=3 and w=2+5=7 is a solution.

  13. 13. slavy Said:

    OK – I got the usual problem with the mathematical notation and half of my post didn’t appear, so let me try to rewrite the missing moments. After establishing that the three numbers are different, we can assume that u is smaller than v, which is smaller than w and solve our equation with respect to w. We get w=(uv+1)/(uv-u-v) and, since v<w we get v(uv-u-v)<uv+1, which is equivalent to v^2(u-1-2u/v)<1. Since the left-hand-side is an integer, we conclude that u-1-2u/v is less or equal to 0 and since u/v is smaller than 1 (remember u<v!) we conclude u<3. Hence u=2 and w=(2v+1)/(v-2)=2+5/(v-2). In order w to be an integer, v-2 should divide 5, so v-2=1 or v-2=5, and since we assumed v<w, only v-2=1, v=3 and w=2+5=7 is a solution.

  14. 14. luv2fap Said:

    Solution: The answer is 41. We may assume that u <= v = 2, otherwise one son would get all the
    camels. Then the condition of the will is that vw + uw + uv =
    uvw – 1.
    (a) If u = 2 then the equation becomes (v – 2)(w – 2) = 5
    which has the unique integral solution v = 3, w = 7 and
    uvw – 1 = 41.
    (b) If u = 3, the equation becomes (2v – 3)(2w – 3) = 11,
    which has unique solution v = 2, w = 7. But his violates
    the condition u = 4 then we have 1-1/(uvw) = 1/u+1/v+1/w <= 3/4,
    so uvw <= 4 which is impossible.

  15. 15. luv2fap Said:

    correction to above*

    b) If u = 3, the equation becomes (2v-3)(2w-3) = 11, which has a unique solution v=2, w=7. But this violates the condition u=4, then we have 1-1/uvw = 1/u + 1/v + 1/w <= 3/4, so uvw <= 4 which is impossible.

  16. 16. Chris Said:

    Hi slavy. I shall re-read your solution. It is pretty terse, and I feel that it will leave most people breathing your dust – including me (after only one read of it).

    Hi luv2fap. That was nearly a pretty good solution. But I don’t understand where the condition u = 4 came from. Is it a typo, possibly caused by this website sporadically taking exception to ? Nor do I understand where the 3/4 in
    1-1/(uvw) = 1/u+1/v+1/w ≤ 3/4 came from.

    But it does also seem to suffer in that trial and error were used. I don’t really see that u,v,w = 3,2,7 is a real difficulty. You also don’t say why you only tried u = 2 and u = 3.

    THe only condition that you can (initially) make, is that u,v,w > 1. By showing that u,v,w are co-prime, then it is fair (and useful) to assert that you will assume w > v > u without lossof generality.

    Nevertheless, it was a good problem and your use of
    e.g. (v – 2)(w – 2) = 5 was very slick.

    In turn, I didn’t say why 3,4,5 shouldn’t have been considered. There again, slavy is the one who explicitly brought attention to the fact that the solution is unique.

  17. 17. slavy Said:

    Hi Chris,

    luv2fap’s solution is correct: He/She assumes that u<v<w and, thus, if u is greater or equal to 4, then so are the others and 1/u<=1/4, while 1/uvw<=1/64. Hence 1/u+1/v+1/w<=1/4+1/4+1/4+1/64=49/64<1, which is a contradiction. Technically, it is the same idea as mine, but executed in a slightly clumsier way (with more cases to consider).

  18. 18. Chris Said:

    Hi slavy. Your solution was easier to follow than my first quick read had suggested. I think your solution is the best. I especially like the fact that it forces u = 2.

    I didn’t say that luv2fap’s solution was wrong. I was complaining that it skipped crucial steps and observations, and so put too much onus on the reader.

  19. 19. luv2fap Said:

    I agree with you Chris, Slavy definitely has the best solution. Good work Slavy!

  20. 20. Chris Said:

    Hi luv2fap. Thanks for not being miffed at my response to your solution.

    My raison d’être is to find/understand and then fully explain the solutions. If it can be done with at least a reasonable amount of rigour and appropriate elegence, then I’m in heaven. Some problems have solutions that are so elegant, that they are beautiful – then I’m in seventh heaven. I don’t like solutions that have been obtained by trial and error – unless that really is the only way to do it.

Post a reply




PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_mssql.dll' - The specified module could not be found. in Unknown on line 0 PHP Warning: PHP Startup: Unable to load dynamic library 'C:\Program Files (x86)\Parallels\Plesk\Additional\PleskPHP5\ext\php_pdo_mssql.dll' - The specified module could not be found. in Unknown on line 0