“The following surprisingly difficult problem was given to my son's Math Circle”

There is a geometric way to solve this, requiring only graph paper and a straight edge.

If x is the number of chickens sold in the morning, and y is the number sold after lunch, then the straight line x+y=10 represents all possible values of x and y for the first farmer. Of course, this allows fractional chickens, so the true set of possible values is the set of points where x and y have integer values.

Now you can draw parallel lines to this first line for x+y=16 and x+y=26, representing valid x and y values for the second and third farmer.

Now, if you take any other line that intersects these 3 lines, then that line can be represented by the equation ax+by=35, for some value of a and b. The key observation then is that if we interpret a and b as the morning and afternoon prices respectively, then the points where this line intersects each of the 3 parallel lines represents the x and y values for each farmer such that that farmer's net earnings are $35.

So now the problem reduces to placing a straight edge on your paper and finding a line that passes through integer points on each of the 3 parallels.

This is pretty easy - start with the edge at (0,26) for farmer 3 and (1,15) for farmer 2 and see if it intersects the first line at an integer point - it doesn't. Keep going and you'll find a nice intersection at (0,26), (5,11) and (8,2). Unfortunately the corresponding prices don't round nicely to cents, but you can shift the entire line to the right to get the right answer: (1,25), (6,10) and (9,1), corresponding to prices of $3.75 and $1.25.

With clojure.core.logic:

  user> (run* [q]
          (fresh [morning afternoon a b c d e f]
            (fd/in morning afternoon a b c d e f
                   (fd/interval 0 35))
            (fd/eq
              (< afternoon morning)
              (= (+ a b) 10)
              (= (+ c d) 16)
              (= (+ e f) 26)
              (= (+ (* morning a) (* afternoon b)) 35)
              (= (+ (* morning c) (* afternoon d)) 35)
              (= (+ (* morning e) (* afternoon f)) 35))
            (== q [morning afternoon a b c d e f])))

  Spoiler warning, scroll right:                                                         ([5 0 7 3 7 9 7 19] [7 0 5 5 5 11 5 21] [35 0 1 9 1 15 1 25])

If the farmers sold a, b and c chickens before lunch, and the price decreased by d then it's easy to write down the equations and arrive at the following equivalency:

(a + b - c) * d = 3500 cents

Since those are all integers, (a + b - c) must be a divisor of 3500. It must also be positive and <= 26. So it can possibly be 1, 2, 4, 5, 7, 10, 14, 20, 25. For each of these choices just solve a system of 2 linear equations to get the solution.

For example if a + b - c = 1 then d = 3500 and the price after lunchtime has to be 0. So they each sold exactly 1 chicken before lunchtime for $35 and gave away all the other chickens for free. It adds up!

Checking of the other solutions is left as an excercise to the reader.

Since this puzzle has a definitive answer, it is solvable by simply iterating from 1 to 10 for the number of chickens sold by the 1st farmer and then seeing which quantity can yield integer quantities for other farmers. And since it's for kids and the number is 10 and I would guess it's the way this puzzle was meant to be solved (in the Math Circle).

How to solve it or to even determine it's uniquely solvable for arbitrary set of 10, 16, 26 and 35 - I don't know, but I'm pretty sure it's doable and has to do with the groups :)

I want to know how the kid in the maths circle solved it. Presumably not with Clojure.

Assuming the prices are in whole cents, here is a very silly bruteforce:

    #ap, bp - prices before/after lunch
    sell_distrib = [(a,b,c) for a in range(10) for b in range(16) for c in range(26) if a > b > c]
    for bp in range(0, 3501):
      for x in sell_distrib:
          ap = (3500-x[0]*bp) // (10-x[0])
          if x[0]*bp + (10-x[0])*ap == 3500 and \
             x[1]*bp + (16-x[1])*ap == 3500 and \
             x[2]*bp + (26-x[2])*ap == 3500:
              print("Prices: {0} {1}".format(bp, ap))
              print("Before lunch sales: {}, {}, {}".format(x[0], x[1], x[2]))

Note: it's Python 3 (the division!) and first line in the conditional eliminates cases where after lunch price wouldn't be a whole number because then it wouldn't add up to 3500.

It doesn't consider cases where one farmer sold everything before lunch (supposedly sales didn't go so well). It's two lines of code more if we want to check those cases. Eliminating of 0 price and requirement that after lunch price is lower than before lunch one is covered by noticing that the solution then must have farmer A selling more than farmer B who in turn sell more than farmer C before lunch.

There is a unique solution in whole cents which is nice (no spoilers, you can copy-paste the code to Python interpreter to see it)

I'll assume we're selling fractional chickens. The problem has 5 free parameters and 2 equality constraints, and several inequality constraints, so it's underconstrained, and its solution space is a (5-3) = 2-dimensional surface (manifold with edges). If you parameterize it by the two price parameters, x > y, it's simply a half-rectangle:

       x >= 7/2    ($3.50)
   0 < y <= 35/26  ($1.35 approx.)

There's a solution for any (x,y) in this region.

Using the notation that the j_th farmer has an inventory of I_j, and sells a_j fractional chickens before lunch with revenue R_j ($35), the problem is a triple of linear equations:

    { a_j*x + (I_j - a_j)*y = R_j }_{j=1..3}

with solution

    a_j = (R_j - y*I_j)/(x - y)

Mathematica simplifies the set of inequalities (I count 8?)

    With[{r=35, is={10,16,26}},
      Simplify[(0<y<x) &&
        And @@ Table[0 <= (r - i*y)/(x-y) <= i, {i,is}]]]

returns

    0 < y <= 35/26 && 2x >= 7 && x > y

(the last one's redundant)

The problem didn't say the price must be > 0. So they may all lowered the price to 0 after lunch time, so the price before lunch time can be $5, $7, or $35 in this case...

If the price must be > 0, assume the it is `a` cents before lunch, `b` cents after lunch, and farmers sold `x`, `y`, and `z` chickens before lunch, where `a`, `b`, `x`, `y`, `z` are all unsigned integers satisfying:

    ax + b(10-x) = 3500
    ay + b(16-y) = 3500
    az + b(26-z) = 3500

Note 10 + 16 - 26 = 0, we can sum the above equations into:

    (a-b)(x + y - z) = 3500

let c = a - b, we know that c is positive integer (price before lunch is higher than after lunch). There are two obvious facts:

1) c is a factor of 3500

2) since x + y - z <= 26, c must be >= 3500/26 = 134

We also know that 3500/c is integer, with the equations we know 10(b/c), 16(b/c), 26(b/c) are all unsigned integers, so 2b/c is unsigned integer, assume d = 2b/c, we have:

    x = 3500/c - 5d
    y = 3500/c - 8d
    z = 3500/c - 13d

Remember that we are investigating the cases of b > 0, so d > 0, so 3500/c >= 13, then we have the fact:

3) c <= 3500/13 = 269

with 1), 2), 3), c = 140, 175 or 250

when c = 140, 3500/c = 25, so d = 1, x = 25 - 5 * 1 = 20 > 10, not valid

when c = 175, 3500/c = 20, so d = 1, x = 20 - 5 * 1 = 15 > 10, not valid

when c = 250, 3500/c = 14, so d = 1, x, y, z are all valid, we get b = 125, a = 375

Answer: the price before lunch is $3.75, after lunch is $1.25

I get interested in the response to these sorts of problems. Both in the comments here and over at Tao's post, there are a lot of examples of brute force solutions. This seems like a common response to recreational mathematical problems, and it has always seemed to me like it's missing the point. These questions aren't generally posed because people care about the answer, but because there are interesting or surprising ideas involved in working it out. In this problem, I guess the surprising thing would be that you are actually given sufficient information to find the answer. The simplest brute force approaches can tell you this, but don't tell you anything about why that may be. I'm reminded of Hamming's motto: "the purpose of computing is insight, not numbers."

Is there an actual technique for solving this that you can reasonably expect to work? Seems like you basically have to code it, needs a lot of patience but not much ingenuity on the math side (maybe on the CS side for coding it practically efficiently though).

If you want a problem in similar spirit:

Two mathematicians are meeting again after not having seen each other for a long time. They are discussing their lives, and mathematician A reveals to have three children. Mathematician B ask how old they are.

A: If you multiply their ages, you get 36. And if you sum up their ages, the result is actually the last two digits of your phone number.

She thinks for a moment, but then...

B: That's not enough information, can you tell me more?

A: Yes, you're right. Well, my oldest kid has blue eyes.

How old are A's kids?

(Yes, you can assume their ages to be integers.)

Seems to be missing some information.

Otherwise you could say the price before lunch was $35 and each sold one chicken, and the price after lunch was $0 and each sold all the rest of their chickens.

Here's a fairly deterministic proof that doesn't involve much guess-and-checking:

Let p be the prices after lunch, let d be the difference in the prices, and let a, b, c be the number of chickens each farmer sold before and after lunch. Then

3500 = ad + 10p = bd + 16p = cd + 26p. This gives us the following equation:

3500 = d * (a + b - c). Thus d and (a + b - c) must divide 3500.

Now, note that (a - b)d = 6p. Thus 3 divides (a - b)d. But d is a divisor of 3500, so 3 cannot divide d, thus 3 must divide a - b. Since 10 >= a > b > c >= 0, this means a = b + 3 or a = b + 6. Similarly 4 must divide a - c, so a = c + 4 or a = c + 8. Finally, (b - c)d = 10p = (5/3)* 6p = (5/3) * (a - b)d.

Dividing by d we get b - c = (5/3) * (a - b). Since a - b is 3 or 6, that means b - c is 5 or 10.

The only set of possibilities that satisfies (a = c + 4 or c + 8, a = b + 3 or b + 6, b = c + 5 or c + 10, a <= 10) is (a, b, c) = (a, a - 3, a - 8).

Since a <= 10, c must be 0, 1, or 2. If c = 0, then we get 3500 = cd + 26p = 26p, which is impossible since 3500 is not divisible by 13. If c = 2, then 3500 = d * (a + b - c) = d * 15, which is impossible since 3500 is not divisible by 3. Thus c = 1, b = 6, a = 9 is the only possibility.

Though this is more a recognition rather than an optimization problem, it can be modeled with optimization modeling languages. Here's an example in Mosel (disclaimer: I work for the company that develops Mosel). Here, a and b are the am/pm price, while (x,y), (u,v), and (t,z) are the am/pm chickens sold by each farmer.

  model "chicken"
    uses "mmxnlp"

    declarations
      a,b: mpvar;
      x,y,u,v,t,z: mpvar;
    end-declarations

    x is_integer
    y is_integer
    u is_integer
    v is_integer
    t is_integer
    z is_integer

    a*x+b*y=35
    a*u+b*v=35
    a*t+b*z=35

    x+y=10
    u+v=16
    t+z=26

    a>=b

  end-model

The solution can be found by a non-convex optimization solver in a fraction of a second.

  Spoiler: scroll right for the answer.                                                   a = 3.75, b = 1.25, x = 9, y = 1, u = 6, v = 10, t = 1, z = 25

[edit: clarification]

Here's how I solved it mathematically:

  Farmer 1 has 10 chickens.
  Farmer 2 has 16 chickens.
  Farmer 3 has 26 chickens.

  Price before lunch: x
  Price after lunch: y

  # of chickens sold before lunch by farmers 1, 2, 3: a, b, c

  Total earned by each farmer: $35

We're told that,

  x > y

and can logically deduce that,

  a > b > c

because otherwise, the farmers with less chickens would have no chance of making the same amount as the other farmer.*

From this information, we know that:

  ax + (10 - a)y = bx + (16 - b)y = cx + (26 - c)y = 35

Let's isolate the first and second farmers here:

  ax + (10 - a)y = bx + (16 - b)y
  ax - ay + 10y + bx - by + 16y = 0
  (a - b)(x - y) = 6y

We can do the same between farmers 1 and 3:

  (a - c)(x - y) = 16y

These two formulas yield,

  (a - b) = (3 / 8)(a - c)

Since a > b > c,

  (a - b) > 0
  (a - c) > 0

Since farmer 1 only has 10 chickens,

  a ≤ 10

Since you can't sell negative chickens,

  b ≥ 0
  c ≥ 0

And since the problem isn't very interesting if the farmers are allowed to sell half-chickens, a, b, and c (and the difference between them) are integers.

Given all of this, 0 ≤ (a - b), (a - c) ≤ 10. The only numbers that satisfy this and,

  (a - b) = (3 / 8)(a - c)

are,

  (a - b) = 3
  (a - c) = 8

Since c ≥ 0 and a ≤ 10, we have three triplets to consider:

  a = 10: {10, 7, 1}
  a = 9:  {9, 6, 1}
  a = 8:  {8, 5, 0}

We can find the relationship between x and y from an earlier equation:

  (a - b)(x - y) = 6y
  3(x - y) = 6y
  3x = 9y
  x = 3y

So the farmers reduced their price to a third of the original price during the afternoon. What a deal!

We've got a few equations that look like,

  ax + (10 - a)y = 35

Which we can now simplify to,

  2ay + 10y = 35

By plugging [10, 9, 8] into the above formula, the only value that gives us a proper dollar amount for y is a = 9.

So...

  y = $1.25
  x = $4.25

Reading through the G+ comments it looks like someone beat me to it, but I figured I'd share my solution anyway.

*This is assuming that they didn't decide to "sell" their chickens for $0 in the afternoon, which is probably a safe bet.

Edit: add intermediate steps for clarity

Many of the comments here talk about "selling" the chickens in the afternoon for $0. These solutions are all in error.

Selling something involves receiving money for it. You can't "sell" something for no money at all, because that's not what the word means! Zero dollars is not money, it is literally nothing.

Check any dictionary, or test this with any of your friends: "Here, take this chicken. Don't give me any money for it. It's free. Now, did I sell it to you or give it to you?"

Beware of overly clever solutions to a problem. The cleverness of the solution may blind you to the fact that you've simply misread the question or misunderstood the plain wording of the words.

And then the farmers were arrested for price collusion and artificially keeping prices high.

Using Mathematica's solve: sols=Solve[Subscript[c, A] x+(10-Subscript[c, A])y==Subscript[c, B] x+(16-Subscript[c, B])y==Subscript[c, C] x+(26-Subscript[c, C])y==35&&Element[Subscript[c, A],Integers]&&Element[Subscript[c, B],Integers]&&Element[Subscript[c, C],Integers]&&0<=Subscript[c, A]<=10&&0<=Subscript[c, B]<=16&&0<=Subscript[c, C]<=26&&x>0&&y>0&&x>y,Reals] Select[sols,Divisible[x,1/100]&&Divisible[y,1/100]/.#&]

Took me about 20 minutes to solve using a bruteforce solution scaling linearly over the total revenue (in cents, so in this case 10500 iterations).

Writing down equations:

    x*a + (10 - x)*b = 3500
    y*a + (16 - y)*b = 3500
    z*a + (26 - z)*b = 3500

    x*a + (10 - x)*b + y*a + (16 - y)*b + z*a + (26 - z)*b = 3 * 3500
    (x + y + z)*a + (10 - x + 16 - y + 26 - z)*b = 10500
    (x + y + z)*a + (52 - (x + y + z))*b = 10500
    p = x + y + z
    p*a + (52 - p)*b = 10500
    a = (10500 - (52 - p)*b) / p

p is the total number of chickens sold before the break. Obviously this can't be negative nor more than 52. At least 1 chicken must be sold both before and after the break, because 52 is not a factor of 10500. So 0 < p < 52.

We know that b < a so b < (10500 - (52 - p) * b) / p.

    b < (10500 - (52 - p)*b) / p
    b*p < 10500 - (52 - p)*b
    b*p + (52 - p)*b < 10500
    b*52 < 10500
    b < 202

This is easy to bruteforce:

    for p in range(1, 52):
        for b in range(1, 202):
            if (10500 - (52 - p)*b) % p == 0:
                a = (10500 - (52 - p)*b) // p

                if ((3500 - 10*b) % (a - b) == 0
                and (3500 - 16*b) % (a - b) == 0
                and (3500 - 26*b) % (a - b) == 0):
                    x = (3500 - 10*b) // (a - b)
                    y = (3500 - 16*b) // (a - b)
                    z = (3500 - 26*b) // (a - b)
                    
                    if 0 <= x <= 10 and 0 <= y <= 16 and 0 <= z <= 26:
                        print("Before the break one chicken cost ${:.2f} and the farmers sold ({}, {}, {}).".format(a / 100, x, y, z))
                        print("After the break one chicken cost ${:.2f} and the farmers sold ({}, {}, {}).".format(b / 100, 10-x, 16-y, 26-z))

Spoiler:

                                                                                                      Before the break one chicken cost $3.75 and the farmers sold (9, 6, 1).
                                                                                                      After the break one chicken cost $1.25 and the farmers sold (1, 10, 25).

For extra credit, a forth chicken trader came to the market that day with no chickens and came home with $90 in profits. How did he do it?

I tried random search, trying random prices and calculating the number of chickens that each buyer would need to sell to meet $35. The result that is closest to an integer for every seller and meets the other constraints:

before: $3.75, after: 1.25

code: http://pastebin.com/gLtg2P9d

My math skills are not good enough solve this, I realized after trying for 30 min. I was happy I managed to solve it with good at least! Here is a JavaScript brute-force solution: http://jsfiddle.net/e88xy75f/15/

If you want to solve by hand, the problem gets MUCH easier if you redenominate the problem in nickels.

With Python/Numpy: https://gist.github.com/anonymous/e760473080c3743451ef

Bonus: The linked Google Plus post is by Terence Tao.

I can see why he thought it was ill-posed -- it doesn't have a single solution if you think in fractions rather than dollars and cents.

Math teacher:

* Step 1: Disguise unsolved problem as homework assignment and give it Terry's son to solve.

* Step 2: Muhahahaha

Is it possible to use WolframAlpha or SymPy to solve this?

Price before lunch = x

Price after lunch = y

Chickens sold before lunch for each farmer respectively (ace)

Chickens sold after lunch for each farmer respectively (bdf)

Solve these six equations:

Farmer 1:

  35 = x*a + y*b

  a + b = 10

Farmer 2:

  35 = x*c + y*d

  c + d = 16

Farmer 3:

  35 = x*e + x*f

  e + f = 26

If we assume they sold the same amount of chickens before lunch as the price was the same, then a = c = e. This reduces it to 6 equations for 6 variables.