Browse · MathNet
PrintTeam Selection Test for JBMO 2024
Turkey 2024 counting and probability
Problem
A real number is written on each square of a board such that sum of all real numbers on the board is equal to . The board is also entirely covered by or dominoes each consisting unit squares of the board such that no square is covered by two different dominoes. For each domino, Asli erases the two numbers it covers, writes on one of the squares and writes the sum of the two numbers on the other square. Find the maximal possible number such that regardless of how the real numbers were written and the dominos were placed initially Asli can guarantee that after her moves there exists a column or row such that the sum of all numbers on it is at least .
Solution
Answer: .
First, we will give an example showing that the answer is at most . Suppose that initially the number is written on each unit square. Let us divide the whole board to equal pieces each of sizes and cover the top-left and bottom-right pieces with horizontal dominoes and the remaining ones with vertical dominoes. Then, initially the sum of numbers on each row or column is equal to and for any given row or column Asli can increase this sum by at most .
Now, let us prove that in any initial case Asli can get a row or column with sum at least . We use the method of double counting. Consider the maximal possible sum of entries for any given row or column. Let be the sum of all these sums. Each number written on any unit square contributes to since it contributes to either two rows and one column or two columns and one row. Hence, . Therefore, by pigeonhole principle, there exists at least one row or column that can achieve the sum . We are done.
First, we will give an example showing that the answer is at most . Suppose that initially the number is written on each unit square. Let us divide the whole board to equal pieces each of sizes and cover the top-left and bottom-right pieces with horizontal dominoes and the remaining ones with vertical dominoes. Then, initially the sum of numbers on each row or column is equal to and for any given row or column Asli can increase this sum by at most .
Now, let us prove that in any initial case Asli can get a row or column with sum at least . We use the method of double counting. Consider the maximal possible sum of entries for any given row or column. Let be the sum of all these sums. Each number written on any unit square contributes to since it contributes to either two rows and one column or two columns and one row. Hence, . Therefore, by pigeonhole principle, there exists at least one row or column that can achieve the sum . We are done.
Final answer
3/2
Techniques
Counting two waysPigeonhole principle