Hacker News Reader

Comment by wfunction | Hacker News Reader

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

View on HN

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

Reply on news.ycombinator.com