2022-08-07, 13:03 | #1 |
Aug 2022
2_{16} 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 k<n such that n+k is in S. Proof: n is a solution, so there's a permutation of (1, 2, ..., n) where adjacent terms add up to members in S. Picking k to be an/the adjacent term to n in such permutation, we see n+k must be in S. 4. If S is not {1}, S is infinite. Proof: We proceed by contradiction, so we suppose S is not {1} but is finite. Then there exists a maximum element m>1 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 |
Thread Tools | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
The Square-Sum problem | henryzz | Puzzles | 34 | 2022-08-08 19:30 |
Variation on Locker Student Problem | oreotheory | Puzzles | 8 | 2022-06-07 19:27 |
The Square-Diff problem | firejuggler | Puzzles | 1 | 2018-01-24 23:27 |
Interesting Encryption problem | FDCmercs | Math | 0 | 2007-01-07 15:50 |
Interesting problem | ThomRuley | LMH > 100M | 3 | 2004-02-08 15:57 |