mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2022-08-07, 13:03   #1
Angel
 
Aug 2022

216 Posts
Default 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
Angel is offline   Reply With Quote
Reply

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

All times are UTC. The time now is 16:32.


Mon Sep 26 16:32:11 UTC 2022 up 39 days, 14 hrs, 1 user, load averages: 2.27, 2.36, 2.28

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔