Olympiad Question [ Russia 2005, Indian TST 2012, France 2006]: 

In a 2 x n array, we have positive reals such that the sum of the numbers in each of the n columns is 1. Show that we can select one number in each column such that the sum of the selected numbers in each row is at most (n+1)/4 

In this problem each column consists of a pair of numbers that total to 1.0   The sum (n+1)/4 can be violated easily when  we pick the higher fractions in each column. Therefore, one strategy could be to pick the smallest numbers in each column. Unfortunately that also breaks the limit of (n+1)/4 in some cases such as for instance when the smaller fractions are all 0.4 and appear in the top row. Let the numbers in the top row be sorted in non-decreasing order as a1,a2, … an with their bottom counterparts as b1, b2, .. bn. The sum of the top row is assumed to be smaller or equal to that of the bottom row. 

One algorithm suggested by the book Olympiad Combinatorics is as follows: Starting from a1, keep choosing the smallest remaining element in the top row as long as possible. In other words, select a1, a2, …ak,  such that a1 + a2 + … + ak  <= (n+1)/4 but a1 + a2 + … + ak  + ak+1 > (n+1)/4. Now we cannot select any more from the top row. And so from the bottom row we choose the remaining elements.  All that is left to prove at this point is that the sum of the chosen elements in the bottom row is at most (n+1) /4 . 

The k+1 th element in the top row in the top row is at least the average of the k+1 elements including itself which is  more than (n+1)/4(k+1) . 

Therefore the bottom element for k+1th column has to be 1- ak+1  = 1 – (n+1)/4(k+1) but bk+1 is the largest of the chosen elements  in the bottom row (because we sorted the upper row in ascending order, the bottom row is in decreasing order and the first element we  picked is this one. So the sum of the chosen elements in the bottom row cannot exceed  b at k+1 times (n-k).  which if we simplify and substitute from the value above we get : 

                (1 – (n+1)/4(k+1)  ) (n-k)  

        =   (n – k – (n+1)(n-k)/4(k+1)) 

        =  ((n+1)/4) (4(n-k)/(n+1) – (n+1)(n-k)/4(k+1)) 

          <= (n+1)/4  

In a graph G with V vertices and E edges, show that there exists an induced subgraph H with each vertex having degree at least E/V. In other words, a graph with average degree d has an induced subgraph with minimum degree at least d/2. 

The degree of a graph is the number of edges incident to the vertex with loops being counted twice. The total degree for all the vertex therefore adds up to twice the number of edges because the same undirected edge counts twice for both the vertices. Therefore the average degree of a vertex is 2.E/V 

To get a subgraph with degree at least E/V, we start with the graph G and start deleting vertices with degree < E/V. In other words, we try to get rid of bad vertices. However in the process of doing so, we are also eliminating edges and vertices that were once good on the basis of their degree might now become bad. This is quite ok as long as there is at least one vertex left. In this case we satisfy the problem’s condition. However what happens if there are no vertex left. Fortunately such a possibility does not exist because the ratio of edges to vertices is strictly increasing on every delete. It starts at E/V and each time we deleted a vertex, less that E/V edges were deleted by the condition of our algorithm. Hence it is impossible to reach a stage when only 1 vertex is remaining, since in this case the edges to vertices ratio is 0. Since there will at least be more than one vertex, where each of them have a degree at lease E/V, we are guaranteed that the number of deletes is bounded and a valid solution will remain at that point. 

A set of three non-negative integers {x,y,z}  with x < y < z satisfying {z-y, y-x} = {1776, 2001} is called a historic set. Show that the set of all non-negative integers can be written as a disjoint union of historic sets.

We can rewrite the historic set of the form {x, x+a, x+a+b} where a and b are interchangeable and therefore lead to 'small' and 'big' sets. We use the integers from the number line because it is sorted.
Every number must be covered but no number must be covered twice. We use the following guidelines:
1: The smallest number not yet covered is the most "unsafe". We should choose x as the smallest "unsafe" number
2: Since we prefer small numbers, we should prefer "small" sets to "big" sets.
Now we can prove by contradiction where we suppose it fails and show that it doesn't.

Let us suppose the algorithm to pick the smallest number not yet covered and the subsequent step to pick the ‘small’ set first or the big set fails when we are in iteration n+1. At this time, the value of (Xn+1) + a + b will not be covered because it is greater than all the covered numbers. So Xn+1 + a or Xn+1 +b must have been covered which is why the process is failing. Further Xn+1 + a  is smaller than Xn+1 +b so the latter must be the largest number in the set and the smallest number in the set would be Xn+1+b-(a+b) = Xn+1-a  but at this stage the small set should have been used and xn+1 should have been in that set which is  a contradiction.