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}<x_{2}<\cdots<x_{n}\le 2n$$ 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!

  • $\begingroup$ 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). $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ nice!+1 but n and 2n+1maybe have common divisor ,then f ollow works it seems not easy, $\endgroup$ – math110 Nov 3 '14 at 15:58
  • $\begingroup$ @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$. $\endgroup$ – Steven Stadnicki Nov 3 '14 at 16:15
  • $\begingroup$ oh,so this two possible case,so how many this subsets such condition? $\endgroup$ – math110 Nov 3 '14 at 16:19
  • 2
    $\begingroup$ 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$. $\endgroup$ – Marc van Leeuwen Nov 4 '14 at 8:08
  • 1
    $\begingroup$ 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. $\endgroup$ – 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$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.