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

90 pointsby thepoetover 10 years ago

29 comments

e271828over 10 years ago

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.

评论 #8490322 未加载

thomover 10 years ago

With clojure.core.logic:<pre><code> 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])</code></pre>

评论 #8486664 未加载

Grue3over 10 years ago

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

评论 #8488253 未加载

epsover 10 years ago

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

评论 #8486662 未加载

jimmytideyover 10 years ago

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

评论 #8487240 未加载

bluecalmover 10 years ago

Assuming the prices are in whole cents, here is a very silly bruteforce:<pre><code> #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])) </code></pre> 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)

评论 #8488193 未加载

throwaway_yy2Diover 10 years ago

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:<pre><code> x >= 7/2 ($3.50) 0 < y <= 35/26 ($1.35 approx.) </code></pre> 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:<pre><code> { a_j*x + (I_j - a_j)*y = R_j }_{j=1..3} </code></pre> with solution<pre><code> a_j = (R_j - y*I_j)/(x - y) </code></pre> Mathematica simplifies the set of inequalities (I count 8?)<pre><code> With[{r=35, is={10,16,26}}, Simplify[(0<y<x) && And @@ Table[0 <= (r - i*y)/(x-y) <= i, {i,is}]]] </code></pre> returns<pre><code> 0 < y <= 35/26 && 2x >= 7 && x > y </code></pre> (the last one's redundant)

luikoreover 10 years ago

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:<pre><code> ax + b(10-x) = 3500 ay + b(16-y) = 3500 az + b(26-z) = 3500 </code></pre> Note 10 + 16 - 26 = 0, we can sum the above equations into:<pre><code> (a-b)(x + y - z) = 3500 </code></pre> 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 35002) since x + y - z <= 26, c must be >= 3500/26 = 134We 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:<pre><code> x = 3500/c - 5d y = 3500/c - 8d z = 3500/c - 13d </code></pre> 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 = 269with 1), 2), 3), c = 140, 175 or 250when c = 140, 3500/c = 25, so d = 1, x = 25 - 5 * 1 = 20 > 10, not validwhen c = 175, 3500/c = 20, so d = 1, x = 20 - 5 * 1 = 15 > 10, not validwhen c = 250, 3500/c = 14, so d = 1, x, y, z are all valid, we get b = 125, a = 375Answer: the price before lunch is $3.75, after lunch is $1.25

评论 #8487832 未加载

bkcooperover 10 years ago

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

评论 #8487633 未加载

wfunctionover 10 years ago

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

评论 #8486703 未加载

评论 #8486593 未加载

评论 #8486698 未加载

cstuderover 10 years ago

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

评论 #8487068 未加载

评论 #8486980 未加载

评论 #8488185 未加载

评论 #8491285 未加载

评论 #8487013 未加载

arsover 10 years ago

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.

评论 #8486471 未加载

评论 #8486455 未加载

评论 #8486412 未加载

评论 #8487918 未加载

SatvikBeriover 10 years ago

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. Then3500 = 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.

merrakshover 10 years ago

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.<pre><code> 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 </code></pre> The solution can be found by a non-convex optimization solver in a fraction of a second.<pre><code> Spoiler: scroll right for the answer. a = 3.75, b = 1.25, x = 9, y = 1, u = 6, v = 10, t = 1, z = 25 </code></pre> [edit: clarification]

rileyjshawover 10 years ago

Here's how I solved it mathematically:<pre><code> 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 </code></pre> We're told that,<pre><code> x > y </code></pre> and can logically deduce that,<pre><code> a > b > c </code></pre> 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:<pre><code> ax + (10 - a)y = bx + (16 - b)y = cx + (26 - c)y = 35 </code></pre> Let's isolate the first and second farmers here:<pre><code> ax + (10 - a)y = bx + (16 - b)y ax - ay + 10y + bx - by + 16y = 0 (a - b)(x - y) = 6y </code></pre> We can do the same between farmers 1 and 3:<pre><code> (a - c)(x - y) = 16y </code></pre> These two formulas yield,<pre><code> (a - b) = (3 / 8)(a - c) </code></pre> Since a > b > c,<pre><code> (a - b) > 0 (a - c) > 0 </code></pre> Since farmer 1 only has 10 chickens,<pre><code> a ≤ 10 </code></pre> Since you can't sell negative chickens,<pre><code> b ≥ 0 c ≥ 0 </code></pre> 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,<pre><code> (a - b) = (3 / 8)(a - c) </code></pre> are,<pre><code> (a - b) = 3 (a - c) = 8 </code></pre> Since c ≥ 0 and a ≤ 10, we have three triplets to consider:<pre><code> a = 10: {10, 7, 1} a = 9: {9, 6, 1} a = 8: {8, 5, 0} </code></pre> We can find the relationship between x and y from an earlier equation:<pre><code> (a - b)(x - y) = 6y 3(x - y) = 6y 3x = 9y x = 3y </code></pre> 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,<pre><code> ax + (10 - a)y = 35 </code></pre> Which we can now simplify to,<pre><code> 2ay + 10y = 35 </code></pre> 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...<pre><code> y = $1.25 x = $4.25 </code></pre> 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

评论 #8487229 未加载

评论 #8486840 未加载

评论 #8486822 未加载

评论 #8487072 未加载

评论 #8486823 未加载

评论 #8489232 未加载

Stratoscopeover 10 years ago

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.

daloreover 10 years ago

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

tyiloover 10 years ago

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]/.#&]

nightcrackerover 10 years ago

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:<pre><code> 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 </code></pre> 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 We know that b < a so b < (10500 - (52 - p) * b) / p.<pre><code> b < (10500 - (52 - p)*b) / p b*p < 10500 - (52 - p)*b b*p + (52 - p)*b < 10500 b*52 < 10500 b < 202 </code></pre> This is easy to bruteforce:<pre><code> 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)) </code></pre> Spoiler:<pre><code> 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).</code></pre>

bakingover 10 years ago

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?

评论 #8487565 未加载

评论 #8487529 未加载

评论 #8487796 未加载

评论 #8487674 未加载

Houshalterover 10 years ago

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.25code: <a href="http://pastebin.com/gLtg2P9d" rel="nofollow">http://pastebin.com/gLtg2P9d</a>

Luffover 10 years ago

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: <a href="http://jsfiddle.net/e88xy75f/15/" rel="nofollow">http://jsfiddle.net/e88xy75f/15/</a>

patio11over 10 years ago

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

评论 #8486659 未加载

ghgrover 10 years ago

With Python/Numpy: <a href="https://gist.github.com/anonymous/e760473080c3743451ef" rel="nofollow">https://gist.github.com/anonymous/e760473080c3743451ef</a>

dctoedtover 10 years ago

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

m-photonicover 10 years ago

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.

pathikritover 10 years ago

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

estover 10 years ago

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

kabousengover 10 years ago

Price before lunch = xPrice after lunch = yChickens sold before lunch for each farmer respectively (ace)Chickens sold after lunch for each farmer respectively (bdf)Solve these six equations:Farmer 1:<pre><code> 35 = x*a + y*b a + b = 10 </code></pre> Farmer 2:<pre><code> 35 = x*c + y*d c + d = 16 </code></pre> Farmer 3:<pre><code> 35 = x*e + x*f e + f = 26 </code></pre> 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.

评论 #8486572 未加载

评论 #8486567 未加载