## Cash cows

Posted by Chris on February 7, 2011 – 3:12 pm

Two men have equal shares in a herd of N cows. They sell all the cows for $N each. The money they get is in $10 bills plus less than ten $1 bills. One at a time they take a $10 bill. The man who takes the first $10 bill also takes the last one. The second man then takes all the $1 bills. How much does the first man owe the second?

February 7th, 2011 at 4:24 pm

$2

N cows for $N each means the total must be a square number

the number of 10’s must be odd to follow the rules.

It appears that all squares that fit end in 6 (36, 196 etc)

so the 1st man takes $4 more than the 2nd so needs to give him $2 to balance the takings.

February 7th, 2011 at 4:29 pm

Argh, Curtis beat be to it – yep I agree $2

February 7th, 2011 at 7:08 pm

Agreed. Used trial and error to find that 6 * $6 works for $36.

First man gets $10 + $10 = $20

Second man gets $10 + $6 = $16

Therefore the first man owes the second man $2, so that they will then each have $18.

February 8th, 2011 at 5:09 am

Too easy.

Let N = 10x+y where 0 ≤ y ≤ 9. The money received = N² = (10x+y)²

= 100x² + 20xy + y². The first 2 terms are an even multiple of $10, so we can disregard them. That leaves y² = 0,1,4,9,16,25,36,49,64,81. The only y² with an odd number of $10’s are 16 and 36. Either way the second man takes $4 less than the first man. So he’s owed $2.

February 8th, 2011 at 5:45 am

Basically the only argument needed is mod 4. Indeed, N is even, and since the number of 10-dollar bills is odd, its sum is 2 mod 4. Hence, the number x of 1-dollar bills must be 2 mod 4, as well (since N is even, N^2 is divisible by 4). But x is between 0 and 9, so it needs to be either 2 or 6. No perfect square ends in 2, so x=6.

February 8th, 2011 at 6:42 am

Hi slavy. I was hoping that you’d come up with a neater solution.

But (LOL, there’s nearly always a “but” from me), I don’t understand why, a priori, that N should be even. Also, I think it’s pushing things a bit by taking it is a given that no perfect square ends in 2 – I doubt that many people would immediately say that was so if you asked them – they’d have to work it out, as I have done. i.e. all perfect squares end with 0,1,4,5,6,9; but not 2,3,7,8.

However, I like the way you think, even if I haven’t (yet) fully understood it

February 8th, 2011 at 11:24 am

Ok. if we don’t know a priori that N is even, then we need a second case: N – odd. Then N^2=10+x (mod 4)= 1 (mod 4) and thus x= 3 mod 4. Hence x-3, or 7, but, again, no perfect square finishes at 3 or 7 (you made a mistake in the list, putting 3 in the wrong group)

February 8th, 2011 at 1:55 pm

Hi slavy. I’ve been out for most of the day. I hope that I can get a chance to examine your solution properly tonight.

I’ve fixed the mistake with 3, thanks for spotting it.

February 9th, 2011 at 8:56 pm

Hi slavy. I was about to say that I don’t understand your explanations, but I think I’ve just got there in the nick of time.

For the benefit of others (and to help me crystallise my understanding) here’s a long-winded version of what slavy did:

Let N = 10x + y. NB N can be any integer, and any number can be represented that way. NB in this post, all integers are positive

N² = 100x² +20x +y² => N² = y² (mod 4). Corresponding to y = 0 to 9, we

have y = 0,1,2,3,0,1,2,3,0,1 = 0,1,2,3 (mod 4) => y² = 0,1 (mod 4)

The last amazing fact is something that I believe that slavy has taken for granted. Also y² = 0 (mod 4) => y is even, and y² = 1 (mod 4) => y is odd.

But in turn this means that N is odd/even as y is odd/even.

Also N² = 100x² +20x +y² => N² = y² (mod 10). Corresponding to y = 0 to 9, we have y² = 0,1,4,9,16,25,36,49,64,81 => y² = 0,1,4,5,6,9 (mod 10). i.e. All perfect squares end with 0,1,4,5,6,9 and none end in 2,3,7,8 (in decimal notation).

In light of the facts in the posted problem, we must have N² = 20u + 10 + v, where the 20u accounts fo an even number of $10 bills, the 10 accounts for the fact that the number of $10 bills is odd, and 0 < v < 10. So N² = 2+v (mod 4) and N² = v (mod 10).

If N is odd, then 2+v = 1 (mod 4) => v = 3 or 7. As no perfect square ends in 3 or 7, this cannot be a solution to the problem.

If N is even, then 2+v = 0 (mod 4) => v = 2 or 6. As no square ends in 2, only v = 6 is possible and is therefore the solution. i.e. the second man took $6 and so is owed (10-6)/2 => $2.

That took me quite a lot of effort. But just to (re?)discover that all perfect squares = 0 or 1 (mod 4), and with the bonus that 0 => even and 1 => odd, made it very worthwhile for me.

February 10th, 2011 at 2:55 am

Hi Chris,

you got it I just want to point out that there is a much faster way to obtain the mod 4 argument, namely: if N=2n is even, then N^2=4n^2 = 0 mod 4, while if N=2n+1 is odd, then N^2=4n^2+4n+1=4n(n+1)+1= 1 mod 4 (the last equation even gives us 1 mod 8, but we don’t need it for this specific problem). Then we need the mod 10 argument and to link them both. And last remark – 8 is missing from the list of impossible last digits for a perfect square, but we don’t need this piece of information (just for the sake of completeness).

February 10th, 2011 at 5:44 am

Another trick that doesn’t save much work on the particular problem but might be crucial in other applications is that modulo 10 we don’t need to compute all the squares from 1 to 9, but only from 1 to 5, if we use the representation N=10x+y, with y between -4 and 5 (for example 17=2*10-3, rather than 17=10+7). We again have N^2=y^2 mod 10, and since the power is even the sign doesn’t matter. This approach gives us for free “coupling” of numbers with the same last digit of the squares (e.g., 11 and 19, 12 annd 18, 13 and 17, 14 and 16) and explains why only half of the digits are possible perfect square finishers…

February 10th, 2011 at 6:13 am

Hi slavy. Thanks for those extra comments, they are much appreciated.

I have a strong suspicion (based on this and another recent problem) that you are completely familiar with quadratic reciprocity. I also suspect that QR is important for image processing.

I’ve now added the missing 8. I seem to have a habit of missing one of the numbers in my lists

February 10th, 2011 at 6:38 am

Hi Chris,

I don’t actually use Number Theory in my research, but it together with Combinatorics were my strongest fields of interest while being a student and participating in all kinds of mathematical olympiads. So I “swim like fish” in these problems and still enjoy them. On the other hand, those well-known “tricks” that I’m using may not be familiar to the general audience and this is why I commented on the “Camel Inheritance” puzzle that such questions are more suitable for a mathematically oriented sites rather than here…

February 10th, 2011 at 8:41 am

Hi slavy. The camels problem is well within the scope of this site. I didn’t expect that a nice mathematical answer (such as yours) were likely to be offered by other posters. I certainly didn’t really give a nice answer; but I was satisfied that I had established the answer and that it was unique. But I had hoped (and was rewarded) that you’d take it the extra mile.

I had strugggled for about an hour with your solution to the problem on this page, and it was only while writing up how I couldn’t follow you argument that I realised what you had done. The problem with your answer is that you take e.g. the N² = 0,1 (mod 4) for granted. I would have expected that most visitors here would not know that and would have spelt it out and proved it (as I have now done).

I’m fairly sure that a lot of the visitors here aren’t even teenagers, and so are unlikely to know that sort of thing. I’m only surprised at how many people here even know about modulo arithmetic. I myself didn’t know it even had an algebra two years ago (I simply never had a reason to think about it at all). It’s only because of a particular “mind-reading” trick that a friend sent me a web link to (and wanted an explanation for) that I found out about modulo arithmetic. I’ll see if I can post that as a problem.

In solving that problem, I finally found out why you can tell if a number is divisible by 9 by seeing if the sum of the digits is divisible by 9 (and similarly for 3, and I also discovered the one for 11). And I could see the recursive extension, and I could see that the residue is the same – I loved finding that stuff out.

I also, about then, read up some (very) basics on Group Theory, but didn’t go further than being able to prove Lagrange’s Theorem. Sadly, I skipped a load of lectures on GT, but do vaguely remember stuff to do with “kernels”. Not sure if it was related to linear algebra though. That was nearly 40 years ago, so I’ve only got a hazy memory of something that I didn’t really learn in the first place.

Thank you for keeping me stimulated.

April 22nd, 2011 at 10:05 am

I agree with Curtis.