## 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?

February 3rd, 2011 at 9:19 pm

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

February 3rd, 2011 at 9:32 pm

41 camels

2*3*7-1=41

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

February 3rd, 2011 at 9:40 pm

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?

February 3rd, 2011 at 10:42 pm

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.

February 4th, 2011 at 4:59 am

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).

February 4th, 2011 at 7:26 pm

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.

February 4th, 2011 at 7:31 pm

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.

February 4th, 2011 at 7:49 pm

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.

February 4th, 2011 at 8:01 pm

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.

February 4th, 2011 at 9:35 pm

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.

February 5th, 2011 at 12:06 pm

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.

February 5th, 2011 at 1:47 pm

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.

February 5th, 2011 at 1:55 pm

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.

February 6th, 2011 at 5:31 pm

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.

February 6th, 2011 at 5:40 pm

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.

February 6th, 2011 at 8:36 pm

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.

February 7th, 2011 at 2:29 am

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).

February 7th, 2011 at 10:56 am

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.

February 7th, 2011 at 5:19 pm

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

February 7th, 2011 at 5:57 pm

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.