## Three Farmers

### October 24, 2014

Instead of thinking about the problem, I immediately wrote a small program to make the calculation by brute force:

`> (list-of (list am pm first second third)`

(am range 1 3500)

(pm range 1 am)

(first range 11)

(second range 17)

(third range 27)

(= (+ (* first am) (* (- 10 first) pm)) 3500)

(= (+ (* second am) (* (- 16 second) pm)) 3500)

(= (+ (* third am) (* (- 26 third) pm)) 3500))

((375 125 9 6 1))

The first five clauses iterate over the range of possibilities, the last three check that the sales of each farmer are the correct total. That will take a while to run, as it does 3500 × 3500 × 11 × 17 × 27 ≈ 62 billion iterations. I started the calculation before I went to lunch, and it was complete when I returned.

A little bit of thought can greatly reduce the number of iterations. Here we say *a* is the am price and *p* is the pm price, and the three farmers sell *f*, *s* and *t* chickens before lunch. Total revenue is *f***a* + (10-*f*)**p* + *s***a* + (16-*s*)**p* + *t***a* + (26-*t*)**p* = 3*3500, which is (*f*+*s*+*t*)**a* + (52-(*f*+*s*+*t*))**p* = 10500. If we let *c* = *f*+*s*+*t* be the total number of chickens sold before lunch, then *a* = (10500 – (52-*c*)**p*) / *c*. We know that 0 < *c* < 52, and *p* < 202 because 10500 / 52 = 201.9, so we have only 52 * 202 = 10500 iterations to perform, which takes about zero time:

`> (list-of (list am pm first second third)`

(c range 1 52) (pm range 1 202)

(zero? (modulo (- 10500 (* (- 52 c) pm)) c))

(am is (quotient (- 10500 (* (- 52 c) pm)) c))

(zero? (modulo (- 3500 (* 10 pm)) (- am pm)))

(zero? (modulo (- 3500 (* 16 pm)) (- am pm)))

(zero? (modulo (- 3500 (* 26 pm)) (- am pm)))

(first is (quotient (- 3500 (* 10 pm)) (- am pm)))

(second is (quotient (- 3500 (* 16 pm)) (- am pm)))

(third is (quotient (- 3500 (* 26 pm)) (- am pm)))

(<= 0 first 10) (<= 0 second 16) (<= 0 third 26))

((375 125 9 6 1))

We used list comprehensions from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/EIpMomYE. In addition to discussion at Terence Tao’s G+ page, there is discussion at Hacker News.

#brute force

#a=number of chickens the first farmer sold before the price change

#b & c for the second two farmers

#must be a>b>c and p1 >p2

for a in range(11):

for b in range(a):

for c in range(b):

for p1 in range(0,500,1):

for p2 in range(0,p1,1):

if a*p1 + 10*p2 – a*p2 == b*p1 + 16*p2 – b*p2 == c*p1 + 26*p2 – c*p2 == 3500:

print(p1,p2,a,b,c)

$3.75 and then $1.25

Similar approach

#

Inequality on line 4 should be reversed.

Scala:

Tweaked it a bit:

From the problem, we know for each farmer that am_sales * am_price + (chickens – am_sales) * pm_price = 3500. Also, am_price > pm_[rice. From this we know that am_price has to be at least 350 or else the first farmer won’t make enough. We also know that pm_price is less than 135 or else the third farmer will make too much.

Solving for am_sales: am_sales = (3500 – chickens * pm_price) / (am_price – pm_price). We can iterate over the prices and solve for the sales directly (they have to be integers, no half-chickens for sale).

Lastly,because 26 does not divide 3500, farmer 3 mist have sold at least one chicken in the morning. Therefore,

3500 – chickens * pm_price >= am_price – pm_price, –> am_price <= 3500 – chickens * pm_price + pm_price, which is most limiting for the third farmer (chickens = 26).

Putting it all together:

[soucecode lang="python"]

def farmers():

for pm in range(1, 135):

n1 = 3500 – 10*pm

n2 = 3500 – 16*pm

n3 = 3500 – 26*pm

for am in range(350, n3 + pm + 1):

d = am – pm

if n3 % d or n2 % d or n1 % d: continue

farmer_1 = n1 // d

farmer_2 = n2 // d

farmer_3 = n3 // d

print(am, pm, n1 // d, n2 // d, n3 // d)

[/sourcecode]

Runs in a tenth of a second.

If you let the farmers give away chickens for free in the afternoon (pm can be zero), there are six more solutions.

This time with formatting.

While walking the dogs, it occurred to me that n1, n2, and n3 in my program above are all divisible by d = am – pm. Because am >= 350 and pm 225. So, a pm price is only possible if gcd(n1, n2, and n3) > 255.

Takes longer to print the answer than to calculate it.

There is another solution. Before lunch they all sell for 3.50 a chicken. The first farmer sells all his chckens (this is maybe not quite following the story). The second and third farmers sell 7 and 2 chickens. Then they set in the afternoon the price 3.50 for 3 chickens. The second farmer gets 7 * 3.50 + (9/3) * 3.50 and the third farmer 2 * 3.50 + (24/3) * 3.50.

Here’s an attempt at a complete solution (assuming whole non-negative chickens – I suppose they might be in the options market though). Lots of ideas taken from original thread: