Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Question is :-

$n$ is a positive integer. Call a non-empty subset $S$ of $\{1,2,\dots,n\}$ "good" if the arithmetic mean of elements of $S$ is also an integer. Further Let $t_n$ denote the number of good subsets of $\{1,2,3,\ldots,n\}$. Prove that $t_n$ and $n$ are both odd or both even.

And my solution to this problem is :-

We deal with problem in 2 cases : n is even and other when n is odd. If n is odd , we first calculate n={1,2} by brute force. We get numbers of solutions for n=1 as 1 & n=3 as 5. Thus we conjecture that $t_n$=$t_{n-2}+2(n-1)$ for n as even. So by this recurrence we calculate $t_5$ which comes to be 15. A brute force manual calculation confirms this answer . Thus we prove our conjecture by induction. Now $t_1$ is odd (=1) so $t_2$ has to be odd since $t_2$=$t_1+2(3-1)$,here $t_1$ is odd & other term is even thus overall parity is odd. So $t_2$ is odd. Again $t_3$ has to be odd as $t_3$=$t_2$+2(3-1), $t_2$ is odd & other term even , so $t_3$ is odd. So , inductively we conclude that $t_n$ has to be odd . For the other case we conjecture same recurrence relation and prove in the same way.

share|improve this question
    
"subset $S$ of $S$"? And what is AM? –  Hagen von Eitzen Feb 3 '13 at 21:37
    
What does this mean? "if AM of elements of S is also an integer" Also, it is inadvisable to use idiosyncratic abbreviations for short words like "numbers". –  rschwieb Feb 3 '13 at 21:38
1  
I went ahead and edited in "arithmetic mean" since more than one reader seems to recognize that's what it should be. I think someone needs to think of a better title, though... –  rschwieb Feb 3 '13 at 21:41
1  
@rschwieb: It’s a very common abbreviation in contest circles, as is ‘AM-GM inequality’. –  Brian M. Scott Feb 3 '13 at 21:43
1  
oeis.org/A051293 –  Charles Feb 3 '13 at 22:33

2 Answers 2

up vote 2 down vote accepted

Let $[n]=\{1,\dots,n\}$. For $S\subseteq[n]$ let $\mu(S)$ be the arithmetic mean of $S$. For $m\in[n]$ let $$\mathscr{S}_m=\big\{S\subseteq[n]:\mu(S)=m\text{ and }S\ne\{m\}\big\}\;.$$ If $m\notin S\in\mathscr{S}_m$, then $S\cup\{m\}\in\mathscr{S}_m$. If $m\in S\in\mathscr{S}_m$, then $S\setminus\{m\}\in\mathscr{S}_m$. Let $$\mathscr{S}_m^*=\{S\in\mathscr{S}_m:m\in S\}\;.$$ Then the map

$$\mathscr{S}_m^*\to\mathscr{S}_m\setminus\mathscr{S}_m^*:S\mapsto S\setminus\{m\}$$

is a bijection, and $|\mathscr{S}_m|$ is even. The good subsets of $[n]$ that do not belong to $\bigcup_{m\in[n]}\mathscr{S}_m$ are precisely the singletons $\{1\},\dots,\{n\}$. If $\mathscr{S}$ is the set of all good subsets, we have

$$|\mathscr{S}|=\left|\bigcup_{m\in[n]}\mathscr{S}_m\right|+n\equiv n\pmod2\;.$$

(This was problem A3 on the 2002 Putnam.)

Added in response to comment: Here’s an example of what’s going on in this proof. Take $n=7$. Then the members of $\mathscr{S}_3$, the subsets of $[7]$ whose average is $3$ (other than the singleton $\{3\}$), are

$$\begin{align*} &\{1,5\},\{2,4\},\\ &\{1,2,6\},\{1,3,5\},\{2,3,4\},\\ &\{1,2,3,6\},\{1,2,4,5\},\text{ and}\\ &\{1,2,3,4,5\}\;. \end{align*}$$

They can be paired up:

$$\begin{align*} \{1,5\}&\leftrightarrow\{1,\underline{3},5\}\\ \{2,4\}&\leftrightarrow\{2,\underline{3},4\}\\ \{1,2,6\}&\leftrightarrow\{1,2,\underline{3},6\}\\ \{1,2,4,5\}&\leftrightarrow\{1,2,\underline{3},4,5\} \end{align*}$$

The argument shows that this happens with each collection of subsets all having the same average; that accounts for an even number of good subsets altogether. The only good subsets left are $\{1\},\{2\},\dots,\{7\}$, the same as the original $n$. Thus, we always have $n$ good singletons together with an even number of other good subsets of $[n]$.

share|improve this answer
    
Thanks proffessor (but i couldnt understand solution completly :P), and it was problem P4 in INMO held today today xD They just copied putnam contest problem and many had solved this question before , so unfair! –  Maggi Iggam Feb 3 '13 at 23:05
    
@Maggi: I added a bit to make the idea of the argument clearer. –  Brian M. Scott Feb 3 '13 at 23:18
    
Okay proffessor ^_^ –  Maggi Iggam Feb 4 '13 at 6:23

Let $A$ be the set of good subsets of $U=\{1,\ldots,n\}$. Then $$f\colon S=\{a_1,\ldots,a_k\}\mapsto n+1-S=\{n+1-a_k,\ldots,n+1-a_1\}$$ is a bijection $A\to A$ because the average $\overline{f(S)}$ of $f(S)$ is $n+1$ minus the average $\overline S$ of $S$, i.e. if one is integral so is the other. Since $f$ is an involution, $A$ can be partitioned into pairs $\{S, f(S)\}$ and the set $A^f$ of fixpoints of $f$. Thus $|A|\equiv |A^f|\pmod 2$. Buf if $S=f(S)$ is a fixpoint of $f$, then $\overline S=\frac{n+1}2$ because $\overline S=\overline{f(S)}=n+1-\overline S$. This is integral if and only if $n$ is odd. Hence for $n$ even we have immediately $|A|\equiv|A^f|\equiv 0\pmod 2$. On the other hand, if $n=2m-1$ is odd, then $$g\colon S\mapsto S\Delta\{m\}$$ (symmetric difference) is almost an involutory bijection $A^f\to A^f$: The exception is the one-element set $\{m\}$ that gets mapped to the empty set. In other words, $g$ defines an involution of $A^f\cup\emptyset$. Since $g$ clearly has no fixpoints, we see that $A^f\cup \emptyset$ has an even number of elements, i.e. $|A|\equiv|A^f|\equiv 1\pmod 2$.

share|improve this answer
    
Well it appears to be correct (votes up) but i couldnt understand most of it , it may be useful for other people viewing thread but can you tell me wether my solution is correct , i will be grateful :) –  Maggi Iggam Feb 3 '13 at 22:42
    
I simplified the argumentation by introducing another involution, hope that helps. Your original solution cannot be correct as the recursion is definitely wrong: From the symmetric sets (i.e. $A^f$) alone, necessarily $t_{2m+1}\ge 2^m$ and $t_{2m}\ge 2^m$. –  Hagen von Eitzen Feb 4 '13 at 7:17
    
Yeah Hagen , i think you are correct , i made a program to know that i was wrong , thanks for help :) –  Maggi Iggam Feb 4 '13 at 12:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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