symmetric 2 variable function

Suppose $S = \{1,2,\dots,n\}$ and $f: S \times S \to R$ satisfies the following: $$f(i,j) + f(j,i) = 0 \forall i,j \in S$$ Now for any two number $i,j$, we say that $i$ is superior to $j$ if there exists a $k$ (not necessarily distinct from $i,j$) such that $f(i,k) + f(k,j) \geq 0$. Show that there exists a number $x \in S$ such that $x$ is superior to all elements of $S$.

Various double counting problems

These problems can all be solved by the double counting principle, that is, to count the same object two different ways and assert that those must match.

Suppose $n > 4$. Let $A_1, A_2, \dots ,A_k$ each be a set of $n$ integers, where $k \leq 4^{n-1} / 3^n$. Show that we can color each integer with one of the four colors so that each set contains integers of 4 different colors.

In a party attended by $n$ people, there were a number of handshakes. A group of 10 persons is called "tight" if each person shook hands with the other 9. It is known that we cannot add another handshake (two people who didn't shake hands now shaking hands) without increasing the number of tight groups. Prove that the number of handshakes is at least $8n-36$

In a class with many students, we choose 2016 committees among them. Each committee has 11 students, and each student may belong to multiple committees. Prove that there is a way to choose some of the students so that each committee has at least one chosen and one unchosen student.

Dancing partners

In a party with $n$ boys and $n$ girls, each boy dances with some girls and vice versa. (No pair of boy and girl dance more than once). There are $n^2-n+1$ dances that occurred throughout the night. Show that we can pair each boy with each girl so that everyone is paired with someone he/she danced with.

Solution

The key fact is because the number of dances is more than $n^2-n$. If it were exactly $n^2-n$, we could have a situation where $n-1$ boys danced with all the girls, and one boy never danced, and this effectively blocks that boy from being paired correctly.

Suppose that there is no way to pair them correctly. That is, for every given pairing, there's always a pair that did not dance. For each pairing, we define the score of said pairing to be the number of pairs that actually danced. This means a legal pairing is the one with score $n$.

Now let $S$ be the sum of all the scores of all possible pairings. Our contrapositive hypothesis is that all pairings have a score of at most $n-1$, so $S \leq (n-1)n!$ (because there are $n!$ possible pairings).

On the other hand, for each dance that happened throughout the night, we want to count how many points it contributes to $S$. Suppose the dance happens between boy $B$ and girl $G$. Then it contributes one point of score whenever the pairing pairs $B$ and $G$. In other words, there are $(n-1)!$ such pairings (because one pair is fixed and we have complete freedom to pair the other $n-1$ boys and $n-1$ girls. So the total number of score is: $$S = (n^2-n+1)(n-1)! > (n^2-n)(n-1)! = (n-1)n!$$ A contradiction.

Graph with degree 3

A graph where each vertex has degree 3 has all of its edges colored with red, green, or blue. How many colorings are there such that every 3 edges that meet in a vertex are either of the same color or have 3 different colors?

Triangular (and tetrahedral) lattice

An equilateral triangle $ABC$ with side $n$ a positive integer is divided into triangular lattice consisting of unit triangles.

Each point on the lattice is colored red, white, or blue such that:
1. No point on $AB$ is colored red
2. No point on $BC$ is colored blue
3. No point on $AC$ is colored white

Prove that there exists a unit triangle whose vertices are colored with 3 different colors.

Challenge problem: Same problem but for tetrahedron and four colors.

Solution

We first state the one-dimensional version of this problem:

Given a sequence of points on a line colored red or blue, and the first point must be colored red, and the last point must be colored blue, then we have an ODD number of segments that has two differently-colored end points.

This one-dimensional version is trivial to prove.

Now we turn to the 2-dimensional version as stated in the problem.
For each side that has both red and blue endpoints, we "mark" that side.
Then for each unit triangle, we give it a score based on how many marked sides it has. Now, if we consider the "outside" area as another "surrogate unit triangle", then we can also give it a score based on how many marked sides are facing the outside.

First, note that the total score of all areas must be even, since any marked side contribute one score to two areas.

Now, applying the 1-dimensional version of the problem, we know that side AC has an odd number of marked sides. Side AB and BC does not have any marked sides. So the outside area has an odd score. Thus, there is an odd number of unit triangles that has an odd score. In order for a unit triangle to have an odd score, it must have three differently-colored vertices.

Solution: Tennis Tournament

Original problem: http://dharmath.blogspot.com/2010/03/tennis-tournament.html

In a tennis tournament of 100 people, each player plays every other players exactly once. There is no draw in a tennis game, one side always wins.

Given that no player loses all of his games, prove that there is a cycle of exactly 3 players. That is, there are players A,B, and C such that A defeats B, B defeats C, and C defeats A.

First Solution

First we prove that there exists a cycle of any length in the tournament. Indeed, take player A, "mark" him, and take any player that A defeats, say B, and also mark that player.. And take any player that B defeats, say C, mark him, and so on. At each turn, we are guaranteed to find a player that loses to that player. If we ever find a player that we have marked before, we obtain a cycle. But the number of marked players increases steadily while there is only a finite number of players in the tournament. Sooner or later, we will run out of players and we are guaranteed to return to a previously marked player.

If this cycle that we found has length 3, then we are done. Now we establish the following statement via induction:

A cycle of length at least 3 contains a cycle of length 3.

The base case is trivial. Now suppose we have a cycle of length $k: A_1, A_2, \cdots, A_k$ where $A_i$ beats $A_{i+1}$ and $A_k$ beats $A_1$.

If $A_1$ beats $A_{k-1}$ then we have a cycle of length 3: $A_1$ beats $A_{k-1}$ beats $A_k$ beats $A_1$.

If $A_{k-1}$ beats $A_1$ then we have a cycle of length $k-1: A_1, \cdots, A_{k-1}$ which also contains a cycle of length 3 by induction hypothesis.

Students in a School

There are 3 schools, each of which has $n$ students. Each student knows altogether $n+1$ students from the other two schools. Prove that we can choose 3 students, each from a different school, such that they know each other.

OSN 2009 Problem 4

I proposed this problem to OSN (Indonesian Science Olympiad) 2009 committee and it was selected as problem #4.

There are 7 cities that are connected by a railroad network. Each railroad segment connects two cities, and each city is connected by at least 3 segments. Prove that there is a route that visits exactly 4 cities, visits them exactly once, and goes back to the city of origin.

(Example: A-B-C-D-A)