## 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 &approx; 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.

Pages: 1 2

### 10 Responses to “Three Farmers”

1. Meir said

#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

2. markhend said

Similar approach

#

```def solve(): # a = before price in cents, b = after price, f1a = farmer 1 before qty....
return next((a, b, f1a, f1b, f2a, f2b, f3a, f3b)
for a in range(1, 500) for b in range(1, 500)
if b > a

for f1a in range(11) for f1b in range(11)
if f1a + f1b == 10
if f1a*a + f1b*b == 3500

for f2a in range(17) for f2b in range(17)
if f2a + f2b == 16
if f2a*a + f2b*b == 3500

for f3a in range(27) for f3b in range(27)
if f3a + f3b == 26
if f3a*a + f3b*b == 3500)

print solve()
#```
3. markhend said

Inequality on line 4 should be reversed.

4. Andras Frey said

Scala:

```package eu.eyan.scala

object pp {
for (
x <- 0 to 10;
y <- 0 to x;
z <- 0 to y;
p1 <- 1 to 3500;
p2 <- 1 to p1
) {
def result(name: String, sum: Int, firstSell: Int): String =
name + " sells " + firstSell + " for " + p1 / 100.0 + " then " + (sum - firstSell) + " for " + p2 / 100.0
def check(x: Int, max: Int): Boolean = 3500 == x * p1 + (max - x) * p2
if (check(x, 10) && check(y, 16) && check(z, 26)) {
val price1 = p1 / 100.0
val price2 = p2 / 100.0
println(result("First", 10, x))
println(result("Second", 16, y))
println(result("Third", 26, z))
}
}                                               //> First sells 9 for 3.75 then 1 for 1.25
//| Second sells 6 for 3.75 then 10 for 1.25
//| Third sells 1 for 3.75 then 25 for 1.25
}
```
5. markhend said

Tweaked it a bit:

```print next((AM, PM, c, d, e, f, g, h) # AM/PM = morning/afternoon cents
for AM in range(1,500) for PM in range(1,500) if AM > PM
for c in range(11) for d in [10-c] if c*AM + d*PM == 3500
for e in range(17) for f in [16-e] if e*AM + f*PM == 3500
for g in range(27) for h in [26-g] if g*AM + h*PM == 3500)
```
6. Mike said

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.

7. Mike said

This time with formatting.

```def farmers4():
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

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

```
8. Mike said

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.

```def gcd(a, b):
while b:
a,b = b, a%b
return a

def farmers5():
for pm in range(1, 135):
n1 = 3500 - 10*pm
n2 = 3500 - 16*pm
n3 = 3500 - 26*pm

d = gcd(n1, n2)
if d <= 225: continue

d = gcd(n3, d)
if d <= 225: continue

print(pm + d, pm, n1//d, n2//d, n3//d)
```

Takes longer to print the answer than to calculate it.

9. Paul said

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.

10. matthew said

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:

```#!/usr/bin/python
# Price before lunch: x+y
# Price after lunch: y
# 26 chicken farmer sold a before lunch, 26-a after lunch
# 16 chicken farmer sold a+b before lunch, 16-a-b after lunch (so b >= 0)
# 10 chicken farmer sold a+c before lunch, 10-a-c (so c >= b)

# Have some obvious inequalities:
# 0 <= a <= 26
# 0 <= a+b <= 16
# 0 <= a+c <= 10

# and, since a,b,c all >= 0:
# 0 <= a <= 10
# 0 <= b <= 16
# 0 <= c <= 10

# Problem conditions are:
# a(x+y) + (26-a)y = 35
# (a+b)(x+y) + (16-a-b)y = 35
# (a+c)(x+y) + (10-a-c)y = 35

# Multiply out:
# ax + 26y = 35
# ax + ay + bx + by + 16y - ay - by = 35
# ax + ay + cx + cy + 10y - ay - cy = 35

# Simplify:
# A: ax + 26y = 35
# B: ax + bx + 16y = 35
# C: ax + cx + 10y = 35

# These give:
# D: bx = 10y (from B-A)
# E: cx = 16y (from C-A)

# Case i: y == 0:
# ax = 35 and b = c = 0
# Solutions for a = 1..10, with x = 35/x

# Case ii: y != 0, (so b,c and x != 0) so can divide D by E:
# b/c = 10/16 = 5/8 => b = 5, c = 8 (b = 10, c = 16 out of bounds)
# and from D:
# 5x = 10y => x = 2y

# Substituting and rearranging A:
# y = 35/(2a+26)
# and a+c <= 10 so have solutions for a = 0,1,2

from fractions import Fraction;

def check(x,y,a,b,c):
assert(a*(x+y) + ((26-a)*y) == 35)
assert((a+b)*(x+y) + ((16-a-b)*y) == 35)
assert((a+c)*(x+y) + ((10-a-c)*y) == 35)
print(x+y,y,a,a+b,a+c)

for a in range(1,11):
check(Fraction(35,a),0,a,0,0)

for a in range(0,3):
y = Fraction(35,2*a+26);
x = 2*y
b = 5
c = 8
check(x,y,a,b,c)
```