Let $n,k$ be positive integers such that $n\geq2k>3$ and $A= \{1,2,...,n\}.$ Find all $n$ and $k$ such that the number of $k$-element subsets of $A$ is $2n-k$ times bigger than the number of $2$-element subsets of $A.$
Problem
Source: Bulgarian TST 2007 for Balkan MO and ARO, II day Problem 2
Tags: inequalities, number theory proposed, number theory
09.04.2007 12:33
We need solve $\binom{n}{k}=(2n-k)\cdot \binom{n}{2}$? Can you post all problem in National Olympiad box ,too?
09.04.2007 13:18
Only $k=4,n=27$.
09.04.2007 13:29
Rust wrote: Only $k=4,n=27$. This is the answer but post a solution.
10.04.2007 01:19
As N.T.TUAN said we need to solve $\binom{n}{k}=(2n-k)\cdot \binom{n}{2}$ Assume $k \geq 6,$ then we have $2\cdot n! = k! (n-k)! (2n-k) n (n-1)$ $2 (n-2)\cdot ...\cdot (k+1) = (n-k)! (2n-k)$ $\binom{n-2}{k-2}= \frac{(2n-k)\cdot k \cdot (k-1)}{2}$ But $\binom{n-2}{k-2}\geq \binom{n-2}{4}$, thus $\frac{(n-5)(n-4)(n-3)(n-2)}{24}\leq \frac{(2n-k) k (k-1)}{2}\leq \frac{(2n-6)k(k-1)}{2}$ or $24k(k-1)\geq (n-5)(n-4)(n-2)\geq (2k-5)(2k-4)(2k-2)$ $6k\geq (2k-5)(k-2)$ iff $2k^{2}-15k+10\leq 0$ As we can see for $k\geq 7$ the inequality does not hold. Thus it is remained to check for $2 \leq k \leq 6$ For $k=2$ we have $\binom{n}{2}=(2n-2)\cdot \binom{n}{2}$, $2n-2=1$, contradiction. For $k=3$ we have $\binom{n}{3}=(2n-3)\cdot \binom{n}{2}$, $(n-2)=3(2n-3)$ or $7=5n$, contradiction. For $k=4$ we have $\binom{n}{4}=(2n-4)\cdot \binom{n}{2}$, $\frac{(n-2)(n-3)}{12}=2(n-2)$, $n=27$ - solution. For $k=5$ we have $\binom{n}{5}=(2n-5)\cdot \binom{n}{2}$, $\frac{(n-2)(n-3)(n-4)}{60}=(2n-5)$. Observe that $(2n-5)> (n-4)$ and is coprime with $(n-2),(n-3)$ For $k=6$ we have $\binom{n}{6}=(2n-6)\cdot \binom{n}{2}$, $\frac{(n-2)(n-3)(n-4)(n-5)}{60\cdot 6}=2(n-3)$ or $(n-2)(n-4)(n-5)=12\cdot 60$ $(n-4) < \sqrt[3]{12\cdot 60}< (n-2)$. It follows that $n-4 \leq 8$ and $n-2\geq 9$, therefore $11\leq n \leq 12$ and you can check that they do not satisfy the condition, because left part is divisible by $7$.