Ken's Puzzle of the Week

Non-Sum-able Sets

Divide the non-negative integers (1..N) into 'k' sets, such that no sum of any two elements in a set (including sums of the same element) sum to another element in the same set. (For example, '1' and '2' cannot be placed in the same set, because 1+1=2.  All odd numbers could be placed in a single set, since no pair will sum to another element of the set.)  Maximize N, solving for k=3 and k=4.

For k=2 sets, the maximum N=4, and the two sets are {1,4} and {2,3}.  '5' cannot be placed in either set without creating a complete sum.

Extension: Repeat, with the requirement that the sums may only be of distinct elements.

Source: Based upon a problem from the Turkish PuzzleUp.

Original problem (I'm also interested in original solutions for this.  My solution moved toward the math problem proposed above.  Perhaps there are simpler explanations.): N points are all connected to each other with lines.  Each line is one of three colors.  What is the maximum N, such that no triangle can be formed of a single color?  [And I'd extend this one to ask the same question if four colors were available.]


Solution
Mail to Ken