A Combinatorics question whose solution I can't understand.

The question is

"For a natural number $n$, let $T(n)$ denote the number of ways we can place $n$ objects of weights $1,2,...,n$ on a balance such that the sum of the weights in each pan is the same. Prove that $T(100) > T(99)$."

Now while I have (one of the many possible) solutions thanks to the fact that the people conducting this test released it, though I do not understand one bit of it.

Could someone explain me how to do this question? It's very difficult (for students) as it's part of the Stage I of selection of students from India for the International Mathematics Olympiad.

I am so confused even looking at the question!!!

The solution which was posted was: (scroll down to the last question) http://olympiads.hbcse.tifr.res.in/uploads/crmo-2013-solutions-2

I apologize in advance if this is too simple to search on the Internet.

One way would be to find a $1$ to $1$ injection from balanced partitions with $99$ items to balanced partitions with $100$ items.

For example, replace item $50$ with item $100$ and put item $50$ in the other part: both parts have increased by $50$ so are still balanced

Then to show a strict inequality, find another balanced partition with $100$ items not already seen, i.e. with items $50$ and $100$ on the same side.

You said you now understand the first two sentences.

The third sentence is

We shall give a map $f : \mathcal S(99) \to \mathcal S(100)$ that is one-to one but not onto.

A map is a function. A function $f : A \to B$ takes an element from set $A$ and gives you back an element of set $B$. There is a theorem that says that if there is a function $f : A\to B$ that is one-to-one but not onto, then set $A$ has fewer elements than set $B$.

To see this, consider the range $f[A]$ of the function. This is a subset of $B$. Because $f[A]$ is in one-to-one correspondence with $A$, it is the same size as $A$. But because $f$ is not onto $B$ (that is, there are elements of $B$ that are not in the range of $f$) then $f[A]$ is a proper subset of $B$. So $A$ is the same size as a proper subset of $B$, so must have fewer elements than $B$.

If we could construct a function $f : \mathcal S(99) \to \mathcal S(100)$ that was one-to-one but not onto, we would have shown that $\mathcal S(99)$ was smaller than $\mathcal S(100)$, which , according to sentence 2 (which you say you understand) would solve the problem.

• GREAT! I understood this and why we did this. Now how to prove that $f : S(99) \to S(100)$ is one-to-one and not onto (I don't understand the steps given in the solution). Thanks a lot. Commented Nov 19, 2014 at 15:46
• The next three sentences (“Suppose that $A$ is … $f(A) = A\cup\{50\}$. ) define the function $f$ that the solution uses. Do you understand how the function $f$ works?
– MJD
Commented Nov 19, 2014 at 15:51
• Use A\setminus\{50\} to write $A\setminus\{50\}$. $A\setminus \{50\}$ is a set that has everything that $A$ has, except $50$.
– MJD
Commented Nov 19, 2014 at 16:08
• $A\setminus \{50\}$ is a set that has everything that $A$ has, except $50$.
– MJD
Commented Nov 19, 2014 at 16:10
• In particular, if you want $f$ to be a function from $\mathcal S(99)$ to $\mathcal S(100)$, it must take a set $x$ whose sum is 2475 and return a set whose sum is 2525. If the set doesn't already contain $50$, you can do that by returning $x\cup\{50\}$, and if $x$ already contains $50$, you can do that by returning $x\setminus\{50\}\cup\{100\}$.
– MJD
Commented Nov 19, 2014 at 16:33

The first sentence is

Let $\mathcal S(n)$ denote the collection of subsets $A$ of $X(n) = \{1, 2, \ldots n\}$ such that the sum of the elements of $A$ equals $n(n+1)/4$.

This means that $X(n)$ is the set that contains the numbers from 1 up to $n$, which you are trying to divide into two parts, so that the sum of the numbers in one part is equal to the sum of the numbers in the other part.

Since the sum of all the numbers $1+2+\cdots n$ is equal to $\frac12n(n+1)$, when the numbers are divided into two parts with equal sums, the two parts each have a sum of $\frac14n(n+1)$.

$S(n)$ is a family sets, each of which contains some of the numbers from $1$ to $n$. A set, say $A$, is a member of the family $S(n)$, if the sum of its elements is $\frac14n(n+1)$.

Do you understand the first sentence now? If not, what part don't you understand?

• So $S(n)$ is basically a power set of $X(n)$ including only those sets whose elements add up to $n(n+1)/4$? Commented Nov 19, 2014 at 14:36
• Yes, except that $\mathcal S(n)$ is a subset of the power set of $X(n)$. It doesn't contain every subset of $X(n)$; it contains only the subsets whose elements add up to $\frac14n(n+1)$.
– MJD
Commented Nov 19, 2014 at 14:37
• OK, got it. Thanks for the really quick replies. I don't understand the rest of the solution as well. Commented Nov 19, 2014 at 14:38
• Now you should re-read the second sentence and see if you understand it better.
– MJD
Commented Nov 19, 2014 at 14:38
• I don't understand what is giving a map $f : S(99) \to S(100)$ (a function? If yes, why do we do it, what does it really mean?) Commented Nov 19, 2014 at 14:42

We can show that we always need an even number of odd primes to satisfy this condition.So the number N has to be of the form 4k+3 for some positive integer k or 4q for some positive integer q.Now if we check for T(99) and t(100).99 falls into the category of 4k+3 and 100 of 4q.Now as we know that they are consecutive integers try to show that whenever 4k+3 and 4q are consecutive integers such that 4q-1=4k+3.Then the number of ways of arranging 4q are more.First you can take examples like t(7) and t(8). and when you solve you will find that the number of arrangements of subsets are more in t(8).and then by induction you can show this is true for all t(n).so we get t(99)

• Please edit and use MathJax to properly format math expressions. Commented Sep 1, 2019 at 3:36