Thursday 28 July 2011

cages for pigs

You have to build 4 cages to put 9 pigs in them such that
  • each cage can contain odd number of pigs and
  • no cage can be empty
\via{Harshada}

You may start with actually making some combinations of numbers in order to get sum as 9. But, as you can expect, it's not that trivial. Another important point to note here is that any two odd numbers will sum up to an even number thus it is not possible to split 9 into 4 additive factors each odd.

The solution is tricky but simple - Build cages such that 3 of them are put inside 4th one and those inner 3 contain pigs like 1,1,7 or 1,3,5 or 3,3,3.
Build cages such that one of those is inside another, i.e. say cage A, cage B and have a cage C inside cage D. Put pigs as follows - 1,1,1,6 (1,1,1-7) or 1,1,3,4 (1,1,1-7), 3,3,1,2(3,3,1-3) and so on. Meaning, here even if we put even number of pigs in D, still with C+D it has odd number of pigs.

(Thanks Hrushikesh for insights on odd+even = odd, that corrected the solution)

Another update-
But, looks like both solutions are half-correct. In first. i.e. cancelled one, we may say that we are violating condition that outermost box should also contain at least 1 pig on it's own. But, if we consider that, in second solution, we violate condition that D should have odd number of pigs on its own. So, basically we give up on one of the "on its own" constraints - either "odd on its own" or "at least one on its own"