Three Farmers
October 24, 2014
Today’s exercise is a math puzzle from Terence Tao:
Three farmers were selling chickens at the local market. One farmer had 10 chickens to sell, another had 16 chickens to sell, and the last had 26 chickens to sell. In order not to compete with each other, they agreed to all sell their chickens at the same price. But by lunchtime, they decided that sales were not going so well, and they all decided to lower their prices to the same lower price point. By the end of the day, they had sold all their chickens. It turned out that they all collected the same amount of money, $35, from the day’s chicken sales. What was the price of the chickens before lunchtime and after lunchtime?
Your task is to calculate the price of chickens before and after lunch. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
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)