Some time ago, I was asked to look at a simple to formulate puzzle. Consider the list of numbers {1,2, ..., 33}. Try to split this list in 11 triples, such that in every triple the third number is the sum of the two others. Obviously, this puzzle can be generalized: let nn be a multiple of 3, then try to split the list {1,2, ..., nn} into triples, such that in every triple the largest number is the sum of the two others.
Since it is not immediately clear, at least to me, how to do that with pen and paper, I wrote a Mathematica program for solving this problem with backtracking, see my answer below. To my surprise, when there is not a bug in my program, the results suggest that such a splitting is impossible. Of course I did this testing only for small multiples of 3, up to 48. Otherwise, the backtracking takes far too much time. Maybe there are better techniques. Anyway, I could prove that for odd multiples of 3 the splitting indeed is impossible. Would that be true for even multiples as well?
EDIT
Clearly, the answer of @ubpdqn shows that I must have been terrible incorrect, both in my "proof" that for odd multiples of 3 the splitting is impossible, and in my backtracking program, that did not find any partition at all. I updated my answer.
Comments
Post a Comment