Partition set with equal sum and differnt cardinality

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

psi241

49 posts

psi241

#1 h Jul 17, 2019, 12:12 PM • 8 Y

Y by HWenslawski, jhu08, megarnie, ImSh95, Adventure10, Mango247, DroneChaudhary, Lhaj3

Let $n\geqslant 3$ be an integer. Prove that there exists a set $S$ of $2n$ positive integers satisfying the following property: For every $m=2,3,...,n$ the set $S$ can be partitioned into two subsets with equal sums of elements, with one of subsets of cardinality $m$ .

This post has been edited 1 time. Last edited by psi241, Jul 22, 2019, 6:00 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Neothehero

18 posts

Neothehero

#2 h Jul 17, 2019, 12:47 PM • 13 Y

Y by Tenee, Pluto04, HWenslawski, jhu08, guptaamitu1, ImSh95, jrsbr, Takeya.O, Adventure10, Mango247, Upwgs_2008, DroneChaudhary, BorivojeGuzic123

If $n=3$ use the set $\{1,2,3,4,5,7\}$ .
For $n>3$ construct $S = \{F_1,F_2,F_3,...,F_{2n-1}\}\cup\{F_{2n-2}-2\}$ and partition
$\begin{align*} A_m &= \{F_{2n-2m+3},F_{2n-2}-2\}\cup\{F_{2n-2m+4},F_{2n-2m+6},F_{2n-2m+8},...,F_{2n-2}\} \\ B_m &= S \setminus\ A_m. \end{align*}$ where $F_n$ denote $n^{th}$ Fibonacci number.
Seeing that $|A_m| = m$ then a straightforward calculation shows that this partition works.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

v_Enhance

6870 posts

v_Enhance

#3 h Jul 17, 2019, 12:51 PM • 16 Y

Y by Steff9, hsiangshen, v4913, Pluto04, jhu08, guptaamitu1, math31415926535, ImSh95, HamstPan38825, ljxlapin, Mathefishian, Adventure10, DroneChaudhary, Stuffybear, b_behruz, NicoN9

Here is a construction for $n = 5$ which generalizes readily: we write $\begin{align*} S &= \big\{ 1, 11, 111, 1111, 11111, \\ &\qquad 12, 123, 1234, a, b \big\} \end{align*}$ where $a$ and $b$ are integers chosen so that the first five elements have sum equal to the last five elements.

Observe that the two halves have equal sum. Then we have $\begin{align*} 1 + 11 + 111 + 1111 + 11111 &= 12 + 123 + 1234 + a + b \\ 12 + 111 + 1111 + 11111 &= 1 + 11 + 123 + 1234 + a + b \\ 123 + 1111 + 11111 &= 1 + 11 + 111 + 12 + 1234 + a + b \\ 1234 + 11111 &= 1 + 11 + 111 + 1111 + 12 + 123 + a + b \end{align*}$ which gives the desired equalities for $m = 2, 3, 4, 5$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

psi241

49 posts

psi241

#4 h Jul 17, 2019, 1:04 PM • 4 Y

Y by jhu08, ImSh95, Adventure10, DroneChaudhary

In my country's TST camp. There are many different solutions(at least 3).
My solution

This post has been edited 1 time. Last edited by psi241, Jul 17, 2019, 1:05 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

MarkBcc168

1594 posts

MarkBcc168

#5 h Jul 17, 2019, 2:06 PM • 7 Y

Y by Pluto04, AFSA, hakN, jhu08, ImSh95, Adventure10, Mango247

I guess I will share my construction as well.

If $n=3$ then just take $\{1,2,3,4,5,7\}$ .

If $n>3$ , take
$S = \{2^1,2^2,...,2^{n-1}\}\cup\{2^1-1,2^2-1,...,2^n-1\}\cup\{2^n-n-2\}.$ and partition
$\begin{align*} A_m &= \{2^n-n-2\}\cup\{2^{n-1},2^{n-2},2^{n-3},...,2^{n-m+2}\}\cup\{2^{n-m+2}-1\} \\ B_m &= \{2^1,2^2,2^3,...,2^{n-m+1}\}\cup \{2^1-1,2^2-1,...,2^n-1\}\setminus\{2^{n-m+2}-1\}. \end{align*}$ A straightforward calculation shows that this works.

This post has been edited 1 time. Last edited by MarkBcc168, Aug 1, 2019, 5:18 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Systematicworker

83 posts

Systematicworker

#7 h Jul 17, 2019, 4:45 PM • 6 Y

Y by 62861, test20, jhu08, ImSh95, Adventure10, Mango247

psi241 wrote:

Let $n\geqslant 3$ be an integer. Prove that there exists a set $S$ of $2n$ positive integers satisfying the following property: For every $m=2,3,...,n$ the set $S$ can be partitioned into two subsets with equal sums of elements, with one of subsets of cardinality $m$ .

https://artofproblemsolving.com/community/c6h455908p2561601
Not such good problem

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

sbealing

307 posts

sbealing

#8 h Jul 17, 2019, 5:44 PM • 4 Y

Y by jhu08, baby_shark, ImSh95, Adventure10

We do $n=3,4$ by giving examples:
$\begin{align*} n=3: & \quad \quad S=\{2,3,4,6,7,8\} \\ n=4: & \quad \quad S=\{1,2,3,4,7,8,10,15\} \end{align*}$ and the relevant sets are:
$\begin{align*} n=3: & \quad \quad \{7,8\} \, , \, \{3,4,8\} \\ n=4: & \quad \quad \{10,15\} \, , \, \{2,8,15\} \, , \, \{1,2,7,15\} \end{align*}$ We now go by induction on $n$ . Let $S_n$ be the working set for $n$ and let $2T$ be the total of all the elements in $S_n$ . Then define $A_k \subset S_n$ to be the subset of size $2 \leq k \leq n$ with total $T$ . We define:
$S_{n+2}=S_n \cup \{T,2T,3T,4T\}$
This has $2n+4$ elements as $S_n$ cannot contain an element $\geq T$ by considering $A_2$ and $S_n \setminus A_2$ which both have total of elements $T$ and neither can contain an element $\geq T$ .

Also the total of the elements in $S_{n+2}$ is $10T+2T=12T$ . Now we can define $B_k \subset S_{n+2}$ as follows:
$\begin{align*} k=2: & \quad \quad B_2=\{2T,4T\} \\ k=3: & \quad \quad B_3=\{T,2T,3T\} \\ k \geq 4: & \quad \quad B_k=\{3T,2T\} \cup A_{k-2} \end{align*}$ and all the $B_k$ have total $6T$ . As we've covered $n=3,4$ and shown we can go $n \rightarrow n+2$ by induction we're done for all $n \geq 3$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

JANMATH111

168 posts

JANMATH111

#9 h Jul 22, 2019, 1:48 PM • 4 Y

Y by e_plus_pi, jhu08, ImSh95, Adventure10

Do the integers in $S$ have to be distinct? It doesn't say in the problem, but if they don't have to be, then it is solvable by a simple induction. What am I missing?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

prtQ

10 posts

prtQ

#10 h Jul 22, 2019, 1:54 PM • 6 Y

Y by ike.chen, jhu08, ImSh95, Adventure10, sabkx, Jack_w

JANMATH111 wrote:

Do the integers in $S$ have to be distinct? It doesn't say in the problem, but if they don't have to be, then it is solvable by a simple induction. What am I missing?

The problem asks for a set of positive integers, which implicitly means that all $2n$ elements must be distinct.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

BOBTHEGR8

272 posts

BOBTHEGR8

#11 h Jul 31, 2019, 4:33 PM • 4 Y

Y by jhu08, ImSh95, Adventure10, Mango247

MarkBcc168 wrote:

I guess I will share my construction as well.

If $n=3$ then just take $\{1,2,3,4,5,7\}$ .

If $n>3$ , take
$S = \{2^1,2^2,...,2^n-1\}\cup\{2^1-1,2^2-1,...,2^n-1\}\cup\{2^n-n-2\}.$ and partition
$\begin{align*} A_m &= \{2^n-n-2\}\cup\{2^{n-1},2^{n-2},2^{n-3},...,2^{n-m+2}\}\cup\{2^{n-m+2}-1\} \\ B_m &= \{2^1,2^2,2^3,...,2^{n-m+1}\}\cup \{2^1-1,2^2-1,...,2^n-1\}\setminus\{2^{n-m+2}-1\}. \end{align*}$ A straightforward calculation shows that this works.

Your set has only $2n-1$ elements, it can easily be corrected by replacing $\{2^{n}-n-2\}$ by $\{2^{n}-n-3,1\}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

MarkBcc168

1594 posts

MarkBcc168

#12 h Aug 1, 2019, 5:18 AM • 3 Y

Y by jhu08, ImSh95, Adventure10

There was a typo in the original post. Thanks for noticing.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

RickyJin

256 posts

RickyJin

#14 h Aug 28, 2019, 8:26 AM • 4 Y

Y by jhu08, ImSh95, Adventure10, sabkx

I might be wrong, but there's actually no need for a construction...?

*Warning* The following is just a SKETCH and could be incorrect:

Let $S=\{ a_1,a_2,\cdots,a_n\}$ . WLOG let $a_1+a_2+\cdots+a_{2n}=1$ (because we can cancel out the denominator to turn rationals into integers) then we only need the following system of equations to hold:
$\begin{align*} a_{2n}+a_{2n-1}&=\frac12,\\ a_{2n}+a_{2n-2}+a_{2n-3}&=\frac12,\\ a_{2n}+a_{2n-3}+a_{2n-4}+a_{2n-5}&=\frac12,\\ \cdots\\ a_{2n}+a_{n}+a_{n-1}+\cdots+a_1&=\frac12. \end{align*}$ From this we can obtain $a_{2n-k}=a_{2n-2k}+a_{2n-2k-1}$ .

Note that there's only one constraint regarding $a_1,a_2,\cdots,a_n$ : Sum up $a_{2n-k}=a_{2n-2k}+a_{2n-2k-1}$ for $k=1,2,\cdots,n-1$ to get $a_1+a_2+\cdots+a_n=a_{2n}$ . Then the values of $a_1,a_2,\cdots,a_n$ can determine $a_1,a_2,\cdots,a_{n+\lceil \frac{n}{2}\rceil}$ . Repeat the above reasoning for multiple times, and you'll determine the value of $a_1,a_2,\cdots,a_{2n}$ . In the meanwhile we can allow $a_{2n}$ to be considerably small, so that $a_1+a_2+\cdots+a_{2n}=1$ still holds. $\square$

This post has been edited 1 time. Last edited by RickyJin, Oct 7, 2019, 12:58 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ACGNmath

327 posts

ACGNmath

#16 h Jan 25, 2020, 3:11 PM • 3 Y

Y by jhu08, ImSh95, Adventure10

I will present another construction.
Define sequence $(a_i)_{i=1}^{\infty}$ as follows:
$a_1=1$ , $a_2=2$ , $a_3=3$ .
$a_{4k}=a_{4k-2}+a_{4k-1}$ $a_{4k+1}=a_{4k-1}+a_{4k-2}+a_{4k-3}$ $a_{4k+2}=a_{4k+1}+1$ $a_{4k+3}=a_{4k+2}+1$ For example, our sequence starts $1, 2, 3, 5, 6, 7, 8, 15, 21, 22, 23, 45, 66, 67, 68, 135$ , etc.

Case I: $n=2x+1$ .
Then let
$S=\{a_1, a_2, \cdots, a_{4x}, a_{4x+1}, \sum_{i=1}^{4x} a_i - a_{4x+1}\}$ It is clear that $a_1 < a_2 < \cdots < a_{4x} < a_{4x+1} < \sum_{i=1}^{4x} a_i - a_{4x+1}$ .
Now let $A=\sum_{i=1}^{4x} a_i - a_{4x+1}$ .
$a_{4x+1}+A=\frac{1}{2}\sum_{s\in S} s$ Also, note that
$a_{4k+1}+a_{4k+2}+a_{4k+3}=a_{4k+1}+a_{4k+4}=a_{4k+5}$ Hence,
$\begin{align*} a_{4x+1}+A&=a_{4x-3}+a_{4x}+A\\ &= a_{4x-3}+a_{4x-2}+a_{4x-1}+A\\ &=a_{4x-7}+a_{4x-4}+a_{4x-2}+a_{4x-1}+A\\ &=a_{4x-7}+a_{4x-6}+a_{4x-5}+a_{4x-2}+a_{4x-1}+A\\ &=\cdots \end{align*}$ Hence we have provided a construction for $n$ odd.

Case II: $n=2x$
Then use a similar argument so that
$S=\{a_1,a_2,\cdots,a_{4x-2},a_{4x-3}+a_{4x-2},\sum_{i=1}^{4x-4}a_i\}$ It is clear that
$a_1 < a_2 < \cdots < a_{4x-3} < a_{4x-2} < a_{4x-3}+a_{4x-2} < \sum_{i=1}^{4x-4} a_i$ Using a similar argument to the odd case, the set $S$ also satisfies the condition.
Hence we have provided a construction for $n$ even.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

NJOY

495 posts

NJOY

#17 h Jan 25, 2020, 3:28 PM • 4 Y

Y by Pluto04, ImSh95, Adventure10, sabkx

Nice problem, but indeed very easy

Let $\mathcal{T}_m$ be the subset of cardinality $m$ satisfying the problem condition. Now, consider the sequence $t_k$ of positive integers such that $t_{2k+1}=t_{2k}+t_{2k-1},$ for all $k=2,3,\ldots,n-1$ . Take $t_{2n}=t_1+t_2+\cdots+t_{2(n-2)}$ . Now, choose the sets $\mathcal{T}_m$ to be $\mathcal{T}_m = \{t_{2n},t_{2n-2},\ldots,t_{2n-2m+4}\}.$ Now, the only condition to be checked of is that $t_{2n}\neq \{t_1,t_2,\ldots,t_{2n-1}\}$ which is a pretty easy task!

This post has been edited 4 times. Last edited by NJOY, Jan 25, 2020, 4:18 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

VulcanForge

626 posts

VulcanForge

#18 h Apr 1, 2020, 5:15 PM • 5 Y

Y by ImSh95, Mango247, Mango247, Mango247, NicoN9

Let the sequence $F_n$ be defined with $F_1=1, F_2=2,$ and $F_n = F_{n-1}+F_{n-2}$ for all $n \geq 3$ . Also let $a_n = F_1+F_2+ \dots +F_{2n-4}$ . I claim that the set $S = \{ F_1, F_2, \dots , F_{2n-1}, a_n \}$ works.

First we show that the elements of this set are distinct; it suffices to show that $F_{2n-3} < a_n < F_{2n-2}$ for all $n \geq 3$ . The lower bound is trivial; for the upper bound, we proceed by induction on $n$ . The base case is easy; assuming that the inequality is true for $n = k$ , then we note that $a_{k+1} = a_k+F_{2k-3}+F_{2k-2} < F_{2k}$ by the induction hypothesis, as desired.

Now we show that we can indeed create the desired partitions of $S$ . For every $m \in \{ 2, 3, \dots , n \}$ take the set $\{a_n, F_{2n-2}, F_{2n-4}, \dots , F_{2n-2m+4}, F_{2n-2m+3} \}$ . It is easy to see that this set has cardinality $m$ and the sum of its elements is $a_n+F_{2n-1}$ , which is half the sum of the elements of $S$ . Thus this construction works and we're done.

This post has been edited 3 times. Last edited by VulcanForge, Apr 1, 2020, 5:24 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Lasitha_Jayasinghe

257 posts

Lasitha_Jayasinghe

#70 h May 22, 2023, 3:04 PM

Y by

Simply consider the set $S={f_1,f_2,\dots,f_{2n}}$ where $f_i$ is the $i^{th}$ number in the recursion;
$f_1 =1 \ \ \ f_2 = 2\ \ \ f_{n+2}=f_{n+1}+f_n$ This is just the Fibonacci Sequence starting from 1 and 2. Now, notice that we can have
$\begin{align*} \{f_1,f_2,\dots,f_{2n-2}\} &\text{ and } \{f_{2n-1},f_{2n}\}\\ \{f_1,f_2,\dots,f_{2n-4},f_{2n-1}\} &\text{ and } \{f_{2n-3},f_{2n-2},f_{2n}\}\\ &\vdots\\ \{f_1,f_2,f_5\dots,f_{2n-1}\} &\text{ and } \{f_3,f_4,\dots,f_{2n}\} \end{align*}$ Thus, for all $n\geq 3$ , there exists a set $S$ of $2n$ distinct positive integers such that for any $m \in \{2,\dots,n\}$ the set $S$ can be partitioned into two sets with cardinalities $m$ and $2n-m$ with equal sums.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

axolotlx7

133 posts

axolotlx7

#72 h Jul 4, 2023, 10:44 AM

Y by

We can loosen the condition to allow positive rationals in $S$ (just scale everything up by LCM of denominators to recover the desired set of positive integers). Consider the set
$S = \left\{ \frac{9}{10}, \frac{9}{10^2}, \cdots, \frac{9}{10^{n-1}}, \frac{1}{10}, \frac{1}{10^2}, \cdots, \frac{1}{10^{n-1}}, x, y \right\}$ where $x$ and $y$ are arbitrary rationals such that the sum of all elements in $S$ is $2$ .
This is always possible as $\frac{9}{10} + \frac{9}{10^2} + \cdots + \frac{9}{10^{n-1}} + \frac{1}{10} + \frac{1}{10^2} + \cdots + \frac{1}{10^{n-1}} < 1 + \frac{1}{9}$ . Now for each $m$ we pick one of the subsets to be
$A = \left\{ \frac{9}{10}, \frac{9}{10^2}, ..., \frac{9}{10^{m-1}}, \frac{1}{10^{m-1}} \right\}$ It is easy to see that the sum of the elements in $A$ is $1$ , so the remaining elements in $S$ must sum to $2 - 1 = 1$ too.
(Just realized this is almost the same construction as #29)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Jndd

1417 posts

Jndd

#73 h Aug 9, 2023, 3:06 AM

Y by

Consider the sequence $f_1, f_2, f_3, \ldots$ where $f_1=1, f_2=2$ , and $f_n=f_{n-1}+f_{n-2}$ for all $n\geq 3$ . Now, we will prove that the set $S=\left\{f_1, f_2,\ldots, f_{2n-1}, c\right\} \text{with } c=\sum_{i=1}^{2n-4}f_i$ satisfies our desired property. We start with the sets $A=\{f_1, f_2,\ldots, f_{2n-2}\}$ and $B=\{f_{2n-1}, c\}$ . $\sum_{i=1}^{2n-2}f_i = f_{2n-2}+f_{2n-3}+\sum_{i=1}^{2n-4}f_i=f_{2n-1}+c$ so $m=2$ works. Now, we'll show that we can keep on replacing an element of $B$ with two elements of $A$ which have the same sum, to reach all desired values of $m$ . To do that, we'll use induction, showing that for every $m\in\{2,\ldots, n-1\}$ , $B$ contains $f_{2n-(2m-3)}$ and $A$ contains $f_{2n-(2m-2)}$ and $f_{2n-(2m-1)}$ . For $m=2$ , we see that this is true, because $f_{2n-1}\in B$ and $f_{2n-2}, f_{2n-3}\in A$ . Now, assume that it's true for $m=k$ . Then, since $f_{2n-(2k-3)}=f_{2n-(2k-2)}+f_{2n-(2k-1)}$ , we can swap $f_{2n-(2k-3)}$ with $f_{2n-(2k-2)}$ and $f_{2n-(2k-1)}$ to obtain the case where $m=k+1$ , and we see that $B$ now contains $f_{2n-(2k-1)} = f_{2n-(2(k+1)-3)}$ and $f_{2n-(2(k+1)-2)}=f_{2n-2k}$ and $f_{2n-(2(k+1)-1)}=f_{2n-(2k+1)}$ are still in $A$ as long as $2k+1\leq 2n-1$ , which simplifies to $k\leq n-1$ . Hence, our induction is complete, and we're done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AdventuringHobbit

164 posts

AdventuringHobbit

#74 h Sep 27, 2023, 8:30 PM

Y by

Let the set of the first $2n-1$ Fibonacci numbers be $S=\{F_1=1, F_2=2, F_3=3, F_4=5, \ldots F_{2n-1}\}$ . Let the sum of these be $F$ . Then consider the set $S'=S \cup \{F-2F_{2n-1}=F_{2n-2}-2\}$ . We can check this equality by a simple induction. Then $S'$ works. Basically the first set that works is ${F-2F_{2n-1},F_{2n-1}}$ . After this, we can repeatedly replace the Fibonacci number in our partition with the two previous Fibonacci numbers, so it still adds to the same thing. The only other thing I have to do is check $n=3$ , because in this case $F_{2n-2}-2$ is already a Fibonacci number and in our set. For this we can use the construction $\{1,4,5,11,16,6\}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

dkedu

180 posts

dkedu

#75 h Jan 27, 2024, 8:01 PM

Y by

We claim $S = \{F_1, F_2, \dots, F_{2n-1}, F_{2n-2} - 2\}$ , where $F_i$ is the $i+1$ th Fibonacci number works. Note that $\{F_{2n-1}, F_{2n-2} - 2\}, \{F_{2n-3},F_{2n-2}, F_{2n-2} - 2\}, \dots ,\{F_1, F_2, F_4, \dots, F_{2n-2}, F_{2n-2} -2\}$ work since $F_{2n-2} - 2 = F_1 + F_2 + \dots + F_{2n-4}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Scilyse

386 posts

Scilyse

#76 h Feb 8, 2024, 10:10 PM

Y by

If $n = 3$ , then we can let $S = \{1, 2, 3, 5, 6, 7\}$ whereupon we can choose the subsets $\{5, 7\}, \{1, 2, 3, 6\}$ and $\{1, 5, 6\}, \{2, 3, 7\}$ for $m = 2$ and $3$ respectively.

Else let $S$ be $\left\{3^{n - 1}, \frac{3^{n - 1} - 3}{2}\right\} \cup \bigcup_{0 \leq i \leq n - 2} \{3^i, 2 \cdot 3^i\}\text{.}$ This is a well-defined set since
$\begin{align*} \frac{3^{n - 1} - 3}{2} &= \frac{3(3^{n - 2} - 1)}{2} \\ &= 3(1 + 3 + \dots + 3^{n - 3}) \\ &= 3 + 3^2 + \dots + 3^{n - 2} \end{align*}$ and since $n - 2 \geq 2$ , this sum has at least two powers of $3$ and is thus not equal to any other element in $S$ by comparing their base- $3$ representations.

Now we show that this choice of $S$ actually works. This argument is clearer if we let $n$ be, say, $5$ :

We start with the two subsets $\left\{3^4, \frac{3^4 - 3}{2}\right\}, \{1, 2, 3, 2 \cdot 3, 3^2, 2 \cdot 3^2, 3^3, 2 \cdot 3^3\}$ which evidently work. Now we swap the $3^4$ on the left-hand side with the $3^3$ and $2 \cdot 3^3$ on the right-hand side:
$\left\{3^3, 2 \cdot 3^3, \frac{3^4 - 3}{2}\right\}, \{1, 2, 3, 2 \cdot 3, 3^2, 2 \cdot 3^2, 3^4\}\text{.}$ This still works since $3^4 = 3^3 + 2 \cdot 3^3$ . Now we swap the $3^3$ on the left-hand side with the $3^2$ and $2 \cdot 3^2$ on the right-hand side again. This argument can continue until we reach the sets
$\left\{3, 2 \cdot 3, 2 \cdot 3^2, 2 \cdot 3^3, \frac{3^4 - 3}{2}\right\}, \{1, 2, 3^2, 3^3, 3^4\}$ at which point we're done. (We can actually apply the argument again, but we don't need to.)

This post has been edited 1 time. Last edited by Scilyse, Sep 27, 2024, 5:46 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

eibc

597 posts

eibc

#77 h Feb 22, 2024, 5:18 PM

Y by

For $n \ge 3$ , consider the set $S = \{F_1, F_2, \ldots, F_{2n - 3}, x, y, z\}$ , where $F_i$ is the $i$ th Fibonacci number and $x$ , $y$ , and $z$ are integers such that $x + y + F_1 + F_2 + \cdots + F_{2n - 4} = F_{2n - 3} + z$ and none of $x$ , $y$ , and $z$ is equal to $F_i$ for $1 \le i \le 2n - 3$ (just make $x$ and $y$ super big). Then, if we let $\sigma$ be the sum of all elements in $S$ , observe that
$\frac{\sigma}{2} = z + F_{2n - 3} = z + F_{2n - 4} + F_{2n - 5} = z + F_{2n - 4} + F_{2n - 6} + F_{2n - 7} = \cdots = \underbrace{z + \sum_{i = 1}^{n - 2}F_{2i} + F_1}_{n\text{ elements}},$ which finishes.

This post has been edited 1 time. Last edited by eibc, Feb 22, 2024, 5:19 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Shreyasharma

667 posts

Shreyasharma

#78 h Feb 23, 2024, 1:54 AM

Y by

Consider the set $\{F_1, F_2, F_3, \dots, F_{2n-1}, \sigma - F_{2n-1}\}$ where we define $\sigma = F_1 + F_2 + \dots + F_{2n-2}$ . Then consider,
$\begin{align*} S_2 &= \{\sigma - F_{2n - 1}, F_{2n - 1}\}\\ S_3 &= \{\sigma - F_{2n - 1}, F_{2n - 2}, F_{2n - 3}\}\\ S_4 &= \{\sigma - F_{2n - 1}, F_{2n - 2}, F_{2n - 4}, F_{2n - 5}\}\\ &\vdots\\ S_n &= \{\sigma - F_{2n - 1}, F_{2n - 2}, F_{2n - 4}, F_{2n - 6}, \dots, F_{4}, F_3 \} \end{align*}$ Clearly each of these partitions work so we're done. $\square$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

kamatadu

465 posts

kamatadu

#80 h Apr 27, 2024, 7:19 PM

Y by

The above solutions are too easy to read? Well no worries, :yup:

I'm here

For $n=3$ take the set $\left\{1,2,3,5,7,8\right\}$ with the partitions $\left\{1,2,3,7\right\}$ and $\left\{5,8\right\}$ for $m = 2$ and $\left\{2,3,8\right\}$ and $\left\{1,5,7\right\}$ for $m=3$ . Now we work for $n\ge 4$ .

Consider the sets $S_i = \left\{2^{2n} - \sum_{k=i}^{n-1} 2^{2k}, 2^{2i} \right\}$ where $1 \le i \le n-1$ . We treat these sets as arrays due to my laziness and so, the notation $S[0]$ and $S[1]$ imply the first and the second element of the set $S$ .

First note that $S_i[0] + S_i[1] = S_{i+1}[0]$ . Now note that $\nu_{2}(S_i) = 2i$ . This implies that all the sets are disjoint. Now we show that the individual elements of each set are distinct. For this note that,
$S_i[0] = S_i[1] \iff 2^{2n} = 2^{2i} + \sum_{k=i}^{n-1} 2^{2k} \iff \nu_{2}(2^{2n}) = \nu_{2}\left(2^{2i+1} + \sum_{k=i+1}^{n-1} 2^{2k}\right) = \nu_{2}(2^{2i+1}) \iff 2n = 2i+1$ which is clearly false. So all the all the elements of set $S_i$ are distinct.

This gives us a total of $2(n-1)$ numbers. Now consider the quantity $\lambda = \sum_{i=1}^{n-1} S_i[0] + S_i[1]$ . Now,
$\nu_2(\lambda) = \nu_{2}\left(\sum_{i=1}^{n-1} S_i[0] + S_i[1]\right)= \nu_{2}\left(\left(\sum_{i=2}^{n-1} S_i[0]\right) + 2^{2n}\right) = \nu_2{2^{2\cdot 2}} = 4.$
Finally, we consider the final set $S_n = \left\{2^{2n}, \lambda - 2^{2n} \right\}$ . Now using another $\nu_2$ argument (the condition $n\ge 4$ is critically important here, I'm just tired to writeup the leftover details :stretcher:

), it is easy to note that $\lambda -2^{2n} \not= S_2[0]$ or $S_2[1]$ .

This means that each of our elements of $S_i$ for $1 \le i \le n$ are all unique.

Now to finish, we show that this construction works, that is $\displaystyle\bigcup_{i=1}^n S_i$ is our desired set.

Firstly, note that for $m=2$ , we can consider the sets $\displaystyle\bigcup_{i = 1}^{n-1} S_i$ and $S_n$ . It is easy to note that both their sums are $= \lambda$ . Now for higher values of $m$ , we can just swap $S_{n}[0]$ with $\left\{S_{n}[0], S_{n}[1]\right\}$ as they both have the same sum. This increases $m$ to $3$ . We can similarly keep doing this by swapping $S_{i+1}[0]$ with $\left\{S_i[0], S_i[1]\right\}$ till we reach $m=n$ . So done. :stretcher:

Remark: Bro what on Earth is this solution????? :wacko:

It literally took me $2$ hours to rigorize the idea and then type it. :stretcher:

. I admit that the solution looks very wordy, but the idea is pretty simple. Another thing to note that the condition $n\ge 4$ is pretty important in my solution since I keep jumping up and down the indices.

For an example of the case when $n=4$ , our individual sets are $S_1 = \left\{2^8 - 2^2 - 2^4 - 2^6, 2^2\right\}$ , $S_2 = \left\{2^8 - 2^4 - 2^6, 2^4\right\}$ , $S_3 = \left\{2^8 - 2^6, 2^6\right\}$ and $S_4 = \left\{2^8, (2^8 - 2^4 - 2^6) + (2^8 - 2^6) - 2^8\right\}$ . Then our working divisions are,

$\left\{(2^8 - 2^2 - 2^4 - 2^6), 2^2, (2^8 - 2^4 - 2^6), 2^4, (2^8 - 2^6), 2^6\right\} \text{ and } \left\{2^8, (2^8 - 2^4 - 2^6) + (2^8 - 2^6) - 2^8\right\}$
$\left\{(2^8 - 2^2 - 2^4 - 2^6), 2^2, (2^8 - 2^4 - 2^6), 2^4, (2^8)\right\} \text{ and } \left\{(2^8 - 2^6), 2^6, (2^8 - 2^4 - 2^6) + (2^8 - 2^6) - 2^8\right\}$
$\left\{(2^8 - 2^2 - 2^4 - 2^6), 2^2, (2^8 - 2^6), (2^8)\right\} \text{ and } \left\{(2^8 - 2^4 - 2^6), 2^4, 2^6, (2^8 - 2^4 - 2^6) + (2^8 - 2^6) - 2^8\right\}$
$\left\{(2^8 - 2^4 - 2^6), (2^8 - 2^6), (2^8)\right\} \text{ and } \left\{(2^8 - 2^2 - 2^4 - 2^6), 2^2, 2^4, 2^6, (2^8 - 2^4 - 2^6) + (2^8 - 2^6) - 2^8\right\}.$

This post has been edited 1 time. Last edited by kamatadu, Apr 27, 2024, 7:21 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

GrantStar

815 posts

GrantStar

#81 h May 3, 2024, 2:21 AM

Y by

I'm really confused.... does this work?

Take $a_i=N+i$ for $0 \leq i \leq n-2$ and some $i$ . Let $s_i=\sum_{k=0}^{i}a_i$ for $1 \leq i \leq n-2$ . I claim the set
$\{a_0,a_1,\dots, a_{n-2}, s_1, s_2, \dots, s_{n-2}, X_1, X_2, C\}$ for sufficiently large $N$ and $C$ such that $C+s_{n-2}$ is half the sum of the whole set works. Indeed, the subsets that are half the sum of the whole thing are
$\{C, s_{n-2}\}, \{C, s_{n-3}, a_{n-2}\}, \{C, s_{n-4}, a_{n-2}, a_{n-3}\}, \dots, \{C, s_{1}, a_{n-2}, a_{n-3}, \dots, a_2\}, \{C, a_{n-2}, a_{n-1}, \dots, a_{0}\}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ezpotd

1251 posts

ezpotd

#82 h Sep 23, 2024, 2:52 PM

Y by

We prove this over rationals, since we can just multiply common denominators to get an integer solution.

We use induction, we show that if we can find a set for $2n$ elements we can find one for $2n + 4$ .

Base Case: $1,3,5,7$ for $n = 2$ , and $1,1,2,2,2,4$ for $n = 3$ .

Inductive Step: Let the sum of all the elements be $s$ . We can let the first $2n$ elements sum to $\frac s8$ and be a scaled version of an already working set with $2n$ elements, then let the other $4$ elements be $\frac s8, \frac s4, \frac{s}{16}, \frac{7s}{16}$ . Then for $m = 2$ , we can take $\frac{s}{16}, \frac{7s}{16}$ with sum $\frac s2$ . For $2 < m < n + 2$ , we can take the set with $m - 1$ elements with sum $\frac{s}{16}$ from the first $2n$ elements and then add $\frac{7s}{16}$ . Lastly, for $m = n + 2$ , we can take the set with $n - 1$ elements with sum $\frac{s}{16}$ from the first $2n$ elements, then add $\frac{s}{16}, \frac s8, \frac s4$ , thus we can find all of the desired subsets. It just remains to show that this construction is actually a set. We show that none of the first $2n$ elements have value at least $\frac{s}{16}$ , this is obvious since we could not possibly have a number that large, since no set containing it could sum to half of $\frac s8$ and no set excluding it and at least one other element could sum to $\frac s8$ . Thus every element of the first $2n$ elements are less than the $4$ elements at the end, none of the $4$ elements at the end are equal, and none of the first $2n$ elements are equal by the inductive hypothesis, so we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

smileapple

1010 posts

smileapple

#83 h Dec 28, 2024, 7:06 AM

Y by

THIS TOOK ME 80 MINUTES :wallbash_red:

We use the Fibonacci sequence with the indexing $F_0=F_1=1$ . Specifically, we set $S=\{F_1,F_2,\dots,F_{2n-1}\}\cup\{F_{2n-2}-2\}$ . For any $m\in\{2,3,\dots,n\}$ , one valid partition is then given by $S=X\cup Y$ , where $U=\{F_{2n-2m+4},F_{2n-2m+6},\dots,F_{2n-2}\}\cup\{F_{2n-2m+3},F_{2n-2}-2\}$ and $Y=S\setminus X$ . It is easy to verify that this partition works by inducting on $m$ and also observing the identity $\sum_{i=1}^kF_i=F_{k+2}-2$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

g0USinsane777

44 posts

g0USinsane777

#84 h Dec 28, 2024, 9:59 AM

Y by

Consider the set $\{1, 2, 2^2, 2^3,... 2^{n-1}, 2^n-1, 2^{n-1}-1, ..., 2^2-1, k\}$ , where $k$ is any integer different from the ones already in the set.
It is easy to notice that the sum of the first $m$ (where $2 \le m \le n$ ) elements from the left is actually the $m^{th}$ element from right.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Saucepan_man02

1300 posts

Saucepan_man02

#85 h Jan 29, 2025, 7:52 AM

Y by

Construction:
Consider the set $S = \{F_1, \cdots, F_{2n-2}, F_{2n-1}, F_{2n-2}-1\}$ which clearly works.

Motivation

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mananaban

33 posts

mananaban

#86 h Mar 26, 2025, 9:32 PM

Y by

It is sufficient to find a set of $2n-1$ integers such that for each $m=2,\dots,n$ , there exists a subset with the same sufficiently small sum as the ones for other values of $m$ .
That is, we have that
$\sum \text{$1$ thing} = \sum \text{$2$ things} = \cdots = \sum \text{$n-1$ things} = x$ To show that this is true, assume that the sum of the $2n-1$ integers is $T$ . Simply let the $2n$ th integer be $T-2x$ , and add it to the $n-1$ different sets above. Note that this requires $T>2x$ .

For this set of $2n-1$ integers, consider the Fibonnaci sequence
$F_1, F_2, F_3, F_4, \dots, F_{2n-1} .$ Here, $F_1=1$ and $F_2=1$ .
With this construction, the common sum that we seek is $F_{2n-1} < \tfrac{1}{2} (F_1+\cdots+F_{2n-1})$ . The $n-1$ sets are
$\begin{align*} F_{2n-1} \\ F_{2n-2} \: F_{2n-3} \\ F_{2n-2} \: F_{2n-4} \: F_{2n-5} \\ F_{2n-2} \: F_{2n-4} \: F_{2n-6} \: F_{2n-7} \\ \vdots \\ F_{2n-2} \: F_{2n-4} \: F_{2n-6} \dots F_2 \: F_1 \end{align*}$ $\blacksquare$

Z K Y