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.

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)
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: