A Combinatorics question whose solution I can't understand.

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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?

Answer 4

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)