We call a set $S$ a good set if $S=\{x,2x,3x\}(x\neq 0).$ For a given integer $n(n\geq 3),$ determine the largest possible number of the good subsets of a set containing $n$ positive integers.
Problem
Source: China Western Mathematical Olympiad 2019 Day 2 P4
Tags: combinatorics, Sets
15.08.2019 02:23
Answer is $n-\lceil\frac{\sqrt{8n+1}-1}{2}\rceil$.
15.08.2019 04:27
Can you kindly share your proof ? If it is possible.
15.08.2019 11:54
I introduce my student's proof: Let $a_i=2^{a_i}3^{b_i}A_i$, where $gcd(6, A_i)=1$, $1\leq i \leq n$. $X=\{(a_i, b_i): 1\leq i \leq n \}$. The number of $x+y=k$ 's solutions in $X$ is $x_k$, now we try to find the number of $((x,y),(x+1,y),(x,y+1))$ is less than or equal to $\max \{0, \min\{x_k, x_{k+1}-1\} \}$, where $x+y=k$, $1 \leq k \leq T$, $x_{T+1}=0$, $x_1+\cdots+x_T=n$, we try to find the Maximum of $$f=\sum_{k=1}^T \max \{0, \min\{x_k, x_{k+1}-1\} \}.$$We notice: if $f$ takes the Maximum value, we must have $x_1 \leq \cdots \leq x_T$, we can proof it by Induction on $T$, and use $T-1$ for $\sum_{k=2}^T$. We assume the number of $x_a=x_{a+1}$ is $b$, then $$\sum_{k=1}^T \max \{0, \min\{x_k, x_{k+1}-1\} \} \leq x_1+\cdots+x_T-b-x_T.$$Clearly, $x_T$ can't be too small because $1+2+\cdots+x_T \geq n$, we can get $x_T \geq \frac{\sqrt{8n+1}-1}{2}$, then the answer is $n-\lceil\frac{\sqrt{8n+1}-1}{2}\rceil$.
15.08.2019 16:41
Select this set: $$\left( \bigcup\limits_{k=0}^{m-1} \{2^i \cdot 3^{k-i} : 0 \leq i \leq k \} \right)\cup \{2^m 3^0, 2^{m-1}3^1, \cdots, 2^{m-(n-\frac{m(m+1)}{2})+1}3^{n-\frac{m(m+1)}{2}-1}\},$$where $\frac{m(m+1)}{2} <n \leq \frac{(m+1)(m+2)}{2}$.