mersenneforum.org Interesting meta variation on the Square-Sum Problem
 Register FAQ Search Today's Posts Mark Forums Read

 2022-08-07, 13:03 #1 Angel   Aug 2022 2 Posts Interesting meta variation on the Square-Sum Problem The problem I recently came across this video showing the Square-Sum problem and the solution proposed in this forum. I thought it might be interesting to solve other similar problems where the set of possible sums is different (for example, I came up with the Prime-Sum problem and spent some time working on it before finding it had already been studied before). Let's call this kind of problems 'S-sum problems', for each subset S of natural numbers (positive integers) containing the possible sums. The 'solutions' of some S-sum problem are the naturals n such that there's a permutation of (1, 2, 3, ..., n) where every pair of adjacent numbers adds up to a member of S. Then I came up with the following meta problem, which is the topic of this thread: A subset S of the naturals is 'cool' if the solutions for the S-sum problem are exactly the members of S, that is, if for all n, n is in S if and only if n is a solution to the S-sum problem. {1} and {1, 2, 3, 4, ...} are cool (note that the empty set is not cool because it has 1 as a solution but 1 is outside the empty set), I call those "trivial subsets". Can we find any non-trivial cool subsets? My progress For any cool subset S, I've proven the following facts: 1. 1 is in S. Proof: 1 is always a solution, no matter the possible sums, so 1 must be in every cool subset. 2. 2 is in S if and only if 3 is in S. Proof: For the 'if' part, suppose 2 is in S. Then 2 is a solution, so 1+2=3 must be in S. For the 'only if' part, suppose 3 is in S. Then 3 is a possible sum, so the permutation (1,2) (or (2,1)) makes 2 be in S. 3. If n>1 is in S, there exists a k1 in S, but by Fact 3 there's a k such that m+k is in S. We have found another element in S greater than m, a contradiction. 5. If S is not {1, 2, 3, 4, ...}, the set of naturals outside S is infinite. Proof: We proceed by contradiction, so we suppose S doesn't contain all naturals but there's a finite number of naturals outside S. Then let m be the minimum natural outside S, but then the permutation (1, m, 2, m-1, 3, m-2, ...) proves m is a solution, a contradiction. Apart from this I've tried several attempts of constructing a non-trivial cool subset, and I still haven't found any; maybe there aren't... What are your ideas? Last fiddled with by Angel on 2022-08-07 at 13:45 Reason: Mistyping in problem statement

 Similar Threads Thread Thread Starter Forum Replies Last Post henryzz Puzzles 35 2022-11-30 06:45 oreotheory Puzzles 8 2022-06-07 19:27 firejuggler Puzzles 1 2018-01-24 23:27 FDCmercs Math 0 2007-01-07 15:50 ThomRuley LMH > 100M 3 2004-02-08 15:57

All times are UTC. The time now is 07:51.

Mon Dec 5 07:51:34 UTC 2022 up 109 days, 5:20, 0 users, load averages: 1.44, 1.32, 1.17