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.

Advertisements

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

%d bloggers like this: