Suppose that we have $2n$ non-empty subset of $ \big\{0,1,2,...,2n-1\big\} $ that sum of the elements of these subsets is $ \binom{2n+1}{2}$ . Prove that we can choose one element from every subset that some of them is $ \binom{2n}{2}$ Proposed by Morteza Saghafian and Afrouz Jabalameli
Problem
Source: Iran TST 2023 ; Exam 2 Problem 6
Tags: Subsets, combinatorics
17.03.2023 12:42
Are you sure the statement is correct?
27.03.2023 14:26
This statement is not correct. Consider the following counterexample for $n=3$: Subsets: {0}, {1}, {2}, {3}, {1,2,3}, {2,3,4}
27.03.2023 15:06
M.Shahverdi wrote: This statement is not correct. Consider the following counterexample for $n=3$: Subsets: {0}, {1}, {2}, {3}, {1,2,3}, {2,3,4} Actually this problem says sum of the number of elements of subsets is $\binom{2n+1}{2}$ , not sum of the elements !
02.04.2023 18:57
AHZOLFAGHARI wrote: Suppose that we have $2n$ non-empty subset of $ \big\{0,1,2,...,2n-1\big\} $ that sum of the elements of these subsets is $ \binom{2n+1}{2}$ . Prove that we can choose one element from every subset that some of them is $ \binom{2n}{2}$ Proposed by Morteza Saghafian and Afrouz Jabalameli Bump this one !
04.04.2023 17:58
Shayan-TayefehIR wrote: AHZOLFAGHARI wrote: Suppose that we have $2n$ non-empty subset of $ \big\{0,1,2,...,2n-1\big\} $ that sum of the elements of these subsets is $ \binom{2n+1}{2}$ . Prove that we can choose one element from every subset that some of them is $ \binom{2n}{2}$ Proposed by Morteza Saghafian and Afrouz Jabalameli Bump this one ! Not sure whether this works for all of the cases or not , but consider a special case where $|A_i|=i$.(where $A_1,...,A_{2n}$ are thise subsets) Then consider a bipartite graph where one of the groups of vertices is $A_i$'s and the other is $0,...,2n-1$ and connect $A_i , j$ iff $j \in A_i$. Now by hall's maridge theorem , we can pick a matching ; consider $A_{i_1},...,A_{i_k}|$ to be some of the subsets. Then the union of these sets contain at least $max{i_j} \geq k$ so the statement of hall's holds. So we can just pick $0,...,2n-1$ in this case. I'm not sure it's possible or not but I guess we can change $0,...,2n-1$ in a way that the sum of them is invariant and in that graph , it's possible to apply hall's.
05.04.2023 00:04
01.07.2023 19:32
As I finished all problems which had proposed by Mr. Safaei in this year. My second choice is immediately the problems which had proposed by Mr. Saghafian. I think it's a good start!
06.05.2024 20:34
Very Beautiful Problem: First we recall the following result, Quote: Consider the sets of integers $X_1, X_2, \dots, X_m$. Then let $$X=\{x_1+x_2+\dots+x_m |x_1\in X_1,x_2\in X_2,\dots ,x_m\in X_m\} $$The following inequality holds $$|X|\geq |X_1|+|X_2|+\dots+|X_m|-(m-1)$$ Now label the sets $A_1,A_2,\dots,A_n,B_1,B_2,\dots,B_n$. Consider two sets of possible sums, $$A=\{a_1+a_2+\dots+a_n |a_1\in A_1,a_2\in A_2,\dots, a_n\in A_n\}$$$$B=\{b_1+b_2+\dots+b_n |b_1\in B_1,b_2\in B_2,\dots ,b_n\in B_n\}$$Using the result we get that $|A|+|B|\geq \binom{2n+1}{2}-2(n-1)=2n^2-n+2$. Notice $A$ and $B$ contain integers from $0$ to $2n^2-n$ and notice that $\binom{2n}{2}$ is also equal to $2n^2-n$. Thus by PhP there exists a element from $A$ and an element from $B$ which sum to $\binom{2n}{2}$.