# How to Solve Problem Similar to IMO(1995) Problem

Two years ago conjecture,Today I again remind of the problem

(conjecture) Let $$n$$ be an postive integer number. How many $$n$$-element subsets $$A$$ of $$\{1,2,\dots,2n\}$$ are there such that $$1+2+\cdots+2n$$ is divisible by the sum of the elements of $$A$$.

I have found this similar problem:IMO (1995) last problem:IMO

two year ago idea:

let $$A=\{x_{1},x_{2},\cdots,x_{n}\},1\le x_{1} and we have $$1+2+3+\cdots+2n\equiv 0\pmod{x_{1}+x_{2}+\cdots+x_{n}}$$

Today ADD it, By Now I have read Problem and from the book Chapter 7 example 4 (simaler problem):

(Solved ) Let $$f(n)$$ be the number of subsets of $$1,2,3,\cdots,n$$ whose elements sum to 0 $$\pmod n$$,the empty set is included,having the element sum equal to zero,Prove that $$f(n)=\dfrac{1}{n}\sum_{d|n,d~odd}\varphi(d)2^{\frac{n}{d}}$$ Solution: Let $$g(X)=\prod_{i=1}^{n}(1+X^i)=\sum_{k\ge 0}a_{k}X^k$$ if let $$\varepsilon =e^{\frac{2i\pi}{n} }$$,it is clear $$f(n)=\sum_{j\ge 0}a_{jn}$$ and other hand easily be computed $$\sum_{j=1}^{n}g(\varepsilon ^j)=n\sum_{j\ge 0}a_{jn}$$ if let $$d=\dfrac{n}{\gcd{(n,j)}}$$,and use well known $$x^d-1=(x-\varepsilon^j)(x-\varepsilon^{2j})\cdot (x-\varepsilon^{dj})$$ so we have $$(1+\varepsilon^j)(1+\varepsilon^{2j})\cdot (1+\varepsilon^{dj})=2$$ this shows that $$g(\varepsilon ^j)=2^{n/d},d ~~is odd$$ and $$0$$ otherwise. so $$\dfrac{1}{n}\sum_{j=1}^{n}g(\varepsilon ^j)=\dfrac{1}{n}\sum_{d|n,d~odd}\varphi(d)2^{\frac{n}{d}}$$

if $$n=p$$ be prime,then it's 1995 IMO problem.

But for conjecture Now I don't solve it by now!

• The English of the question is incomprehensible. I'll edit to says what I think is meant (notably in accord with the formulas that follow). – Marc van Leeuwen Nov 4 '14 at 7:59

Hint: Note that $$\sum_{i=1}^{2n}i = n(2n+1)$$ The sum of an $$n$$ element subset of $$A$$ is at least $$\frac 12n(n+1)$$, so the only sums that can divide $$n(2n+1)$$ are $$\frac 13n(2n+1)$$, $$\frac 12n(2n+1)$$ and $$n(2n+1)$$. You need to find how many $$n$$ element subsets sum to one of these. The first and third may not be a whole number, and should be ignored if so.

• nice!+1 but n and 2n+1maybe have common divisor ,then f ollow works it seems not easy, – math110 Nov 3 '14 at 15:58
• @math110 That doesn't matter (much). Suppose $a=n(2n+1)$ is the sum of the $2n$ elements and $b=\frac12n(n+1)$ is the minimum possible sum; then $a+n=n(2n+2)=4\cdot\left(\frac12n(n+1)\right)=4b$; in other words, $b\gt\frac14a$. Since $b$ is the minimum possible sum, the only divisors of $a$ that are at least $b$ are $\frac a2$ and $\frac a3$. – Steven Stadnicki Nov 3 '14 at 16:15
• oh,so this two possible case,so how many this subsets such condition？ – math110 Nov 3 '14 at 16:19
• For $n=3$ the sum $7$ of $\{1,2,4\}\subset\{1,2,3,4,5,6\}$ divides $21$, but is not equal to $\frac12n(2n+1)=\frac{21}2$. – Marc van Leeuwen Nov 4 '14 at 8:08
• If $S \geqslant \frac{1}{2}n(n+1)$, then $\dfrac{n(2n+1)}{\frac{1}{2}n(n+1)} = \dfrac{4n+2}{n+1} < 4$, so the candidates are $\frac{1}{3}n(2n+1)$, $\frac{1}{2}n(2n+1)$ and $\frac{1}{1}n(2n+1)$, with the last impossible since we need all $2n$ numbers to reach that sum. – Daniel Fischer Jan 31 '17 at 14:47

$\frac {n(2n+1)}{\frac {n(n+1)}{2}}<4$ ,so equation which a sum divided is 2 or 3.
(i)When sum of two elements is 2n+1, $$2n+1=(1,2n)(2,2n-1)\ldots(n,n+1)$$n pairs.By choosing $\frac n2$, $_nC_{\frac n2}$ pairs.This sum is just half of equation.

(ii)When sum of two elements is n or 3n$$(1,n-1)(2, n-2)\dots(\frac n2-1,\frac n2+1)$$ $$(n,2n)(n+1,2n-1)\ldots(\frac {3n}2-1,\frac {3n}2+1)$$This sum are $_\frac {n-2}2C_k$,$_\frac {n-2}2C_\frac {n-2k}2$ by choosing k,$\frac {n-2k}2$ . These sum is$$\tag{1}(n*k)(3n*(\frac n2-k))$$ By the way,there is no common diviser of $(n,2n+1)$ and (1) is not diviser of equation whatever k is.

(iii)When sum is 3, $(2n-2,1,2)(2n-6,3,4)\ldots(\frac {2n}3+1,\frac {2n}3-1,\frac {2n}3)$

$\frac {n}3+1$ pairs,$_{\frac n3+1}C_\frac n3=\frac n3+1$

So answers are,using $_{\frac n3}C_{\frac n3}=1$

if $n=6k-2,6k-4,$ $_nC_{\frac n2}+1$

if $n=6k-1,6k-5$, $_nC_{\frac {n-1}2}+1$

if $n=6k$, $_nC_{\frac n2}+{\frac n3}+1$

if $n=6k-3$,$_nC_{\frac {n-1}2}+{\frac n3}+1$

• How is the first inequality related to the question? – Michael Albanese Dec 22 '15 at 2:23
• sum of A is n(2n+1).This is max. sum of 1~n is 1/2 n(n+1).This is minimum subset. – Takahiro Waki Dec 26 '15 at 11:56