Hacker News new | past | comments | ask | show | jobs | submit login
“The following surprisingly difficult problem was given to my son's Math Circle” (plus.google.com)
90 points by thepoet on Oct 21, 2014 | hide | past | favorite | 89 comments



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.


This solution got me thinking about something which I found interesting enough to feel the need to share.

I can imagine my Dad using this geometric method to solve the problem at hand. He's a very intelligent guy who has worked in the building industry doing manual labor all of his life.

I can guess that my sister, who is a medical doctor, would have solved it using the same process as the (current) top rated response here; stepping through the equations.

My immediate response would be to hack up a script and brute force the answer.

My Mother would tell me to go ask Dad.


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])


All of these solutions have the sale of chickens for $0, which makes the problem easy (eg, they each sold 7 chickens for $5 and gave the rest away), but is surely not in the spirit of the question.


Selling the chickens for $0 is not just "not in the spirit of the question", it's plain wrong! By definition, you can't "sell" something for $0, that's giving it away.

For example, one dictionary defines "sell" as "to exchange (something) for money". $0 is not money. It's literally nothing.

I don't know why people (not you) come up with "clever" solutions that violate the plain wording of the question.


I would have thought it obvious: it looks like a lateral thinking puzzle to some people, and it's painfully common to have the null case be a part of the solution (in a sort of perverted aha-gotcha! attempt).

After all, part of the linked article's point was how it struck him as potentially broken; if the problem seems broken, then many will heuristically start attacking the problem itself rather than the math. And once the problem's no longer trusted to be stated as exact and correct, well, a simple pedantic jump in meaning is a pretty small step. (I'll concede it's possible you've never come across a broken 'clever' math word problem before, but having found enough to be wary myself - both in school and college - I'm rarely surprised at people leaping for the lateral thinking solution.)


Clearly I was distracted by IBM selling its chip business yesterday for -$1.5bn.


Ha, yes. Reading the question, and indeed giving it any thought at all, were always the things that held me back in maths at school. Using cents and requiring > 0:

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

  Spoiler warning, scroll right:                                                    ([375 125 9 1 6 10 1 25])


The only odd thing about this answer is that farmer 1 apparently decided to lower prices after selling 9 of his 10 chickens in the morning...


n.b. Correct answer. Took me 20 minutes with paper and pen: 5 minutes of noodling and 15 of constructing a table and winnowing it quickly using an insight about relatively prime numbers.


And using computers instead of my head, that was another pitfall.


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.


I don't follow why you're subtracting `c`, or multiplying by the size of the decreased price. Can you elaborate on how you came to that?


Suppose x is the price before lunch, y - after. Then we get the following equations:

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

Which is equivalent to (assuming x = y + d):

ad + 10y = 3500; bd + 16y = 3500; cd + 26y = 3500


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 :)


There doesn't seem to be an integer solution though.

I did the following:

- starting from farmer with 10 chicken, I checked for i = 0..5 (number of chicken possibly sold in the worse part of the day) whether a = 4,5,6,7,8... were working prices for the first half of the day, by calculating 35 - a * (10 - i) and checking whether the result was divisible by an integer in the range 1 .. a-1 (can be done quickly by writing down a table)

- with possible solutions for the first merchant (e.g. a = 7, b = 2, sold 3 for a and 7 for b), repeat for 2nd and 3rd merchant and find solutions that work there also (can limit the choices of a to prior solutions from merchant 1)

- (also, the second price must be 1 if integer due to 26 chicken sold at $35)

I'd assume that I either did some calculations wrong (my old head) or the teacher would at least either expect the kids to also check non-integer solutions (perhaps try 1.5, 2.5 etc.) or actually solve this:

  a * x1 + b * (10-x1) = 35
  a * x2 + b * (16-x2) = 35
  a * x3 + b * (26-x3) = 35
  a > b
  x1 < 5 (unsure)
  x2 < 8 (unsure)
  x3 < 13 (unsure)

  (x1, x2, x3 positive integers; a, b at least rational numbers?)


You made an assumption that I originally did, which is that farmer $FOO was dissatisfied with his sales because he had half of his stock unsold at the midday mark. This assumption is unsupported by the text of the problem. Try relaxing it.

Also, chickens are integers but prices are not is a core insight. Life gets easier if you solve a related problem which forces prices to be integers as well, such as an alternate universe where chickens are priced in nickels.


Use cents as units to get an integer problem.


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


Think of whole chickens. The second guy sold a+6 chickens after lunch for the price of a chickens before lunch. Likewise #3 sold b+10 for the price of b. Since the price difference is constant, the common denominator is c+2 chickens for the price of c. The only solution (given the number of chickens) is 3 chickens for the price of 1. The chickens sold for one third the price after lunch. The rest is easy.


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)


An even sillier bruteforce lets you reproduce the problem almost verbatim: let a and b be the daytime and nighttime prices, let x, y, and z be the number of chickens sold during the day by each farmer.

  [(a, b, x, y, z) for a in xrange(1, 500) for b in xrange(1, a) for x in xrange(1, 11) for y in xrange(1, x) for z in xrange(1, y) if 3500 == a*x + b*(10 - x) == a*y + b*(16 - y) == a*z + b*(26 - z)]


Very nice, I need to practice my Python one liners :) It's significantly slower though as you are iterating over 2nd price as well (and I derive it from the fact that total profit is known so daytime price and amount of sold chickens sold implies nighttime price).


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."


I would have thought that the point of the post is "how effing ridiculous is it that we're giving kids severely broken problems?!"

I'm all for giving kids more open-ended problems so that they get a chance to think and explore, but this one is ridiculous. They each sell one chicken for $35 in the morning and give the rest away in the afternoon is a valid solution and yet utterly, utterly wrong since the odds of something like that happening in real life are basically nil.

If you're going to give kids an under-constrained problem like this at least make the solution a line rather than a surface so that way you're only screwing with their heads some instead of a lot.


This is clearly not intended to screw with their heads. It is likely the problem-poser didn't realize the issue with not constraining the afternoon price to be greater than zero. In fact, figuring out that little quirk is already a good intellectual exercise for the student, and it's easy for the teacher to say "great answer! what if you can't set the afternoon price to zero?".

Honestly, I think this kind of attitude about problems is what is "effing ridiculous". There is huge value in learning to question the constraints of a problem.


It's pretty clear from problem description that they are not giving away the chickens in the afternoon.

They lowered the price and came back selling. It's just doesn't happen in the real life that people call giving away selling. Also in natural language you would expect significantly different wording if they all made 35$ before lunch and then decide to just give remaining chickens for free. Another thing is usage of the word sell. You would have hard time selling anyone an idea that sell could mean give away in the context.

Understanding how natural language works and being able to write reasonable constraints based on this description is an important skill. Assuming the price could be 0 in the afternoon is just an error on solvers side.


Given the description, it sounds like this problem was given to a club of kids who do recreational/contest problems, which makes a pretty big difference. I think they probably get the spirit in which it is offered and understand the implicit constraints (e.g. no giving away chickens).


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).


I solved it in my head, using a bit of brute force, but mostly some informal reasoning. Basically (and a tad spoilingly):

Since we're dealing with whole chickens, there should an integral ratio between the two prices--that is, M expensive chickens should be the same price as N cheap ones. To go from, say, 10 to 16 chickens requires replacing X chickens with X+6 chickens sold later but costing the same in total. Same with 10 to 26 or 16 to 26. The GCD between these differences (6, 10, and 16) is 2, implying N<=M+2. We also know N/M>=2.6, meaning to trade from 10 chickens to 26 you need to get at least 2.6 cheap chickens for every expensive one you replace. So there's only one exchange rate that works: one expensive chicken costs as much as three cheap ones. Using this exchange rate, 8 of the 10 chickens would have to be traded to get 24 out of 26, leaving two chickens for each farmer that were sold for the same total, but at unknown prices. Three possibilities (0, 1, or 2 at the expensive rate) is a pretty easy brute force at that point.


How do you know that "M expensive chickens should be the same price as N cheap ones"? What assures us any two groups of chickens would sell for the same total price?


It's in the intersection of linear algebra and number theory, and knownm to be difficult. In effect it's a Diophantine equation, and most problems in that field have no generic techniques to solve them. I think Integer Programming is known to be NP-Hard, but I can't check that from here.

So no, there is no general technique apart from ingenuity, clever guesswork, and trial and error.


> apart from ingenuity, clever guesswork

That's what I'm asking though: what is the ingenuity or cleverness required to solve this problem? The only technique I can think of is guess and check.


In this particular case it's pretty easy because you know you'll be working with small numbers, so once you establish tighter bounds the work to 'guess and check' will be small.

This 'bound tightening' is the 'ingenuity' required for the problem. There's no general process to achieve that, which is why it requires ingenuity :)

SPOILERS BELOW

To do that you have to notice the common factor in the initial equations.

Let n1, n2, and n3 be number of chickens sold pre-lunch time by each farmer. The initial equations are:

  n1*x + (10-n1)*y = 35
  n2*x + (16-n2)*y = 35
  n3*x + (26-n3)*y = 35
Transforming them a little:

  n1 * (x - y) + 10y = 35 ;[1]
  n2 * (x - y) + 16y = 35 ;[2]
  n3 * (x - y) + 26y = 35 ;[3]
The common factor of (x-y) looks useful; you can establish relationships between n1, n2 and n3 with it:

  (n1 - n2) * (x - y) - 6y = 0  ;([1] - [2])
  (n1 - n3) * (x - y) - 16y = 0 ;([1] - [3])

  (n1 - n2) =  6 * (y / (x - y)) ;[4]
  (n1 - n3) = 16 * (y / (x - y)) ;[5]

  (n1 - n2) = 3/8 (n1 - n3) ;[6]
If you get there the puzzle is basically solved but for a bit of number crunching - you know n1, n2 and n3 are positive integers, n1 <= 10, so for [6] either n1=n2=n3 (trivial 0-post-lunch-price solution) or n1 - n2 = 3, n1 - n3 = 8. From there you substitute back into [4] and get 3 * (x-y) = 6y, so x = 3y.

You now have simple relations between n1, n2 and n3; as well as between x and y. The remaining step is to tie x or y to one of the n's by substituting into initial equations. For example from [1]:

  n1 * 2y + 10y = 35
  2y = 35 / (n1 + 5)
y must be integral in pennies; that part is tricker to derive and the simplest solution is to just notice that since n1 >= 0, and n3 >= 0, and n1 = n3 + 8, then 8 <= n1 <= 10, and try 8, 9 and 10 for n1. With n1 = 9, you get y = 1.25. That's the only 'guess and check' part of the problem.


Quite often swathes of the search space can be eliminated or winnowed by using modulo arguments. You can also sometimes fold these problems into smaller spaces by considering equivalence arguments. There are many ad hoc techniques that no one has yet classified or unified, they are scattered across many mathematical disciplines.


See: https://en.wikipedia.org/wiki/Diophantine_equation#System_of...

(Have the price be in cents so that it will be an integer.)


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.)


For this puzzle to work, you can't just assume their ages to be integers - their ages have to be integers. In other words, for this puzzle to be solvable, two people who are both X years old have to be considered to be exactly the same age, with neither elder than the other.


> How old are A's kids?

Much easier than the parent problem (at least now that we've seen how the parent problem unfolds).

Kids' ages: X, Y, and Z.

X * Y * Z = 36

CORRECTED: X + Y + Z ≥ 10 (the sum is two digits) [I had the ≥ backwards].

One triplet that works is 3, 3, and 4; also 1, 4, and 9.

EDIT: OK, I blew this one, I think --- see 'sunlr's correction below. (Note to 'sunlr: The problem as given is that the oldest kid has blue eyes, not the youngest. That fact doesn't eliminate twins --- all the kids could have blue eyes.)


3,3,4 isn't a valid solution because then B would not reply "that's not enough information." There's exactly one triplet that adds up to eleven, so if B's phone number ended in 11, she would have immediately deduced the solution instead of asking for more information. Same with 1,4,9: that's the only triplet adding to 14. The only valid triplets are ones that share a sum with another triplet. Only two triplets multiplying to 36 share a sum: 1,6,6 and 2,2,9 both add up to 13. Once B learns that A has an "oldest kid", B can rule out 1,6,6, because A would have said "one of my oldest kids has blue eyes" in that case. That leaves 2,2,9 as the only valid triplet.


> X + Y + Z ≤ 10 (the sum is two digits)

I don't understand this part. Surely every number between 10 and 99 (inclusive) has two digits? And numbers <10 have only one digit? Have I forgotten how to count to 2?

If we use your interpretation then the fact there is an oldest child is redundant; but if we don't then the fact that the sum is two digits is redundant, and there are multiple solutions.

The 'oldest child' thing rules out 6, 6, 1 as the answer, but afaict 18, 2, 1 and 12, 3, 1 and 9, 4, 1 and 9, 2, 2 and 6, 3, 2 are still valid solutions as well as 4, 3, 3.


> And numbers <10 have only one digit?

Not in a phone number.


I think the blue eye bit should be the "youngest has blue eyes" and the answer eliminates twins. Thus 2, 3, 6.

Also you have the sign reversed. Should be x + y + z >= 10.


> the answer eliminates twins

I don't believe so, because regardless of which child has blue eyes, it doesn't eliminate the possibility that either or both of the other children also have blue eyes. If the statement was qualified with an "only", then you could eliminate twins.


Thank you for this little riddle, I like how it sounds almost like a joke until you realise what the last piece of info actually means.


The ages can be:

    3 + 3 + 4 = 10
    1 + 4 + 9 = 14
    2 + 2 + 9 = 13
    1 + 6 + 6 = 13
If the sum is 10 or 14, B would have had enough information for the answer at once. So the sum should be 13.

And "oldest kid" is not "oldest kids", so 2, 2, 9 is the answer.


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.


It seems reasonable to require "real world" conditions. Non-zero prices, whole cent prices, integral chickens per sale, non-negative chickens per sale, etc. With those, the solution is unique, and in part, that's what makes this problem interesting, hard, surprising, and with its own elegance.


I don't think giving something away for $0 is ever called "selling", is it? I especially would not expect that usage in a problem like this.


30 years ago in Australia, only certain kinds of goods could be sold on a Sunday, books being one of them. An enterprising billiard-table seller, not wanting to lose one of his two prime days for selling that kind of entertainment device, exploited a loophole: on Sundays, he sold books. Really expensive books. But they came with a free billiard table!


http://www.astrabilliards.com.au/about/

> George Grech made himself known in the early years of trading when Astra Billiards began opening on a Sunday. Sunday trading was illegal and due to unpaid fines, George Grech was the first shopkeeper to be jailed for trading on a Sunday.

> George made front page headlines of the Herald Sun on a number of occasions.

> History shows at that time, booksellers were one of the few shops allowed to trade on a Sunday. “George & Helen Grech Booksellers” was born. Helen & George would sell a book for a price of a billiard table and give a billiard table for free with every purchase.

Fun story! I think English judges look at the intent of the law, not just narrow wording, so he would still have been in trouble if he'd tried it over here. (I am just guessing here though)


Victorian (state) law is very similar to British law, enough so that British lawyers can pretty much come directly here and start practicing, apparently. This was told to me by a British lawyer I met on a tour group, who was emigrating to Melbourne :)

If he had been taken to court, I imagine he would have lost, because by that time they have to apply the law. But I imagine the people who would apply the summons simply used discretion; it wasn't like this behaviour was rife.


"By the end of the day, they had sold all their chickens."


This is handled by the $0 post-lunch price.


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


Setting aside the trivial arithmetic error, I think a simpler attack approach comes from the first two farmers collectively having 26 chickens and making twice as much money as the third, giving you a simpler starting point.


Except that I get a different answer if you do a very simple bruteforce:

    def check(n,am,pm,total):
        for x in range(1,n):
            if (am * x + pm * (n-x)) == total:
                return "AM: %d @ %d / PM %d @ %d" % (x,am,n-x,pm)
        return None


    def solve(total,birds):
        for am in range(1,total):
            for pm in range(1,am):
                result = list(map(lambda n:check(n,am,pm,total),birds))
                if all(result):
                    return result

    print(solve(3500,[10,16,26]))


One small mistake at the end: x = $1.25 y = $3.75


o______o

oh my. this is why one shouldn't do math at 4am.

:s/4.25/3.75


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 am pretty sure he must have been short-selling in the chicken market. Good foresight.


Yeah, selling chickens in the morning promising afternoon delivery and then buying up all the surplus chickens after lunch at the reduced price.


Oh, it sounds much more realistic when you put it that way. I actually wasn't sure what a real-life application of "short selling" would look like.


It was more or less a thought experiment on whether it would be possible to sell negative chickens.


Pretty disappointed only one answer involved a time machine.


He rented a time machine so that he could buy the 36 chickens sold in the afternoon and then sell them in the morning at a $2.50 premium per chicken.


He arrived at the market, bought nine of Farmer 1's chickens, cooked them, and sold each cooked chicken for $10 more than he paid for it.


He preached about forth and was paid $90 to stop?


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.


A nickel is 5 cents, if like me you couldn't remember that.

A "dime" is 10 cents, which makes the famous bags seem very cheap.


A dimebag would be $10 -- stretching what "dime" means (I've never heard any other context where it means $10 instead of 10 cents!), but it must have been catchy enough to stick....



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.


If you assume that then I think you find the after-lunch price is 0, which is unrealistic. There are other solutions, and your task is to find one that's reasonable.


> If we assume

That'd be no fun in the puzzle then, wouldn't it? :)




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: