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.
Programming Praxis 
#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
#
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() #Inequality on line 4 should be reversed.
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 }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)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.
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)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.
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:
#!/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)