I searched for the official solution on the net, but I only found the solutions in Italian
Can anybody be kind enough to translate the solution to problem 6 please? At least the example...
Thanks.
Andrei.
A translation?
A translation?
Hey guys. I am a romanian who participated at your National Olimpiad at Cesenatico this year. After the contest, I wanted to read the solution to problem 6. During the contest, I found the right bound, but I could not find the example.
I searched for the official solution on the net, but I only found the solutions in Italian
Can anybody be kind enough to translate the solution to problem 6 please? At least the example...
Thanks.
Andrei.
I searched for the official solution on the net, but I only found the solutions in Italian
Can anybody be kind enough to translate the solution to problem 6 please? At least the example...
Thanks.
Andrei.
You have $ n $ colours $ c_1 $, ... , $ c_n $, and a $ \binom{2n}{2}\times 2n $ array, and you want to color the array so that there is no rectangle with all the four vertices of the same colour.
You can divide the array in $ n $ smaller arrays $ 2n-1 \times 2n $; take the first of these arrays. Suppose there is a way to divide each column (which has $ 2n $ boxes) in $ n $ couplets so that there are not two similar couplets in different columns. It means that if you take any two columns $ a $ and $ b $, there's not a couplet in $ a $ whose boxes are at the same height of a couplet in $ b $. If there is a way to divide thus the first array's columns, then you will colour each of the $ n $ couplets of each column of the first array with a different colour, and you won't get monochromatic rectangles in the first array. You have $ n $ arrays with $ 2n-1 $ columns all divided in couplets as in the first array. Choose a couplet from a column of the first array; you will find that couplet also in the other arrays, in the same column and in the same position. In each array there is one and only one couplet with the boxes at that height, so you have a group of $ n $ similar couplets, and you can color each of them with a different color; so for each couplet you choose in the first array, there are exactly $ n $ couplets of that type, one in the first array and $ n-1 $ in the others. You can color each of these couplets with a different colour and you won't get monochromatic rectangles, because in order to get a monochromatic rectangle you need two couplet of the same type (of course in different columns) of the same colour.
Now you have to find a way to divide each column of the first array in $ n $ couplets so that there are no similar couplets in different columns. First of all, write a number 1 in the first box of each column; the remaining part of the array is a$ 2n-1\times2n-1 $ square. Write a number 1 also in the main diagonal of this square (of course you will get a different couplet of 1 in each column). Now think of the square: it has a main diagonal, but also other diagonals parallel to it: for example, if you get all the boxes at the right of a box of the main diagonal, you will get another diagonal, but the main one has $ 2n-1 $ boxes, the new one we are considering has $ 2n-2 $ boxes, because the last box of the main column is at the right side of the square, so there are no other righter boxes; we say that the second diagonal continues by the left side, so (as in the popular videogame snake) if you go beyond the right side, you will arrive in the box of the first column at the same height. In this way we can find another box on the first column for the secon diagonal, and thus the second diagonal has $ 2n-1 $ boxes, one for each column and one for each row. You can divide the square in $ 2n-1 $ diagonals, which start from each box of the first row.
Now, in the first row you have $ 2n-1 $ boxes. The lefter one has a number 1, the other $ 2n-2 $ are still empty. Divide these $ 2n-2 $ boxes of the first row in two groups: the first $ n-1 $ on the left and the second $ n-1 $ on the right. In the first you write, in this order, the numbers 2, 3, ... , $ n $; in the second group you write the numbers $ n $, $ n-1 $, ... , 3, 2. Now write in each diagonal the number written in its box of the first row. For $ n=5 $ you get this array $ 9\times 10 $:
1 1 1 1 1 1 1 1 1
1 2 3 4 5 5 4 3 2
2 1 2 3 4 5 5 4 3
3 2 1 2 3 4 5 5 4
4 3 2 1 2 3 4 5 5
5 4 3 2 1 2 3 4 5
5 5 4 3 2 1 2 3 4
4 5 5 4 3 2 1 2 3
3 4 5 5 4 3 2 1 2
2 3 4 5 5 4 3 2 1
Now, for each column, you consider the couplets with the same number. A couplet with number 1 is different by the other couplets with number 1 because it has a box in the main diagonal at a different height, and is also different by any other couplet with another number because it has a box in the highest row.
Now we can forget the couplets with number 1 and therefore the highest row, so we are considering again only the square.
If there were two couplets at the same height and with the same number, the vertices would form a rectangle and would lie on at least 3 diagonals, but we know that all the boxes with a number $ i $ lie on two diagonals.
So we need only to demonstrate that there are no similar couplets with different numbers. The distance between two boxes of a couplet with number $ i $ is $ 2i-2 $ or $ 2n+1-2i $, so for each number $ i $ we can associate an even number$ 2i-2 $ between 2 and $ 2n-2 $, and an odd number $ 2n+1-2i $ between 1 and $ 2n-3 $. So the distance between the two boxes of a couplet depends on the number of the couplet and is different for each number.
You can divide the array in $ n $ smaller arrays $ 2n-1 \times 2n $; take the first of these arrays. Suppose there is a way to divide each column (which has $ 2n $ boxes) in $ n $ couplets so that there are not two similar couplets in different columns. It means that if you take any two columns $ a $ and $ b $, there's not a couplet in $ a $ whose boxes are at the same height of a couplet in $ b $. If there is a way to divide thus the first array's columns, then you will colour each of the $ n $ couplets of each column of the first array with a different colour, and you won't get monochromatic rectangles in the first array. You have $ n $ arrays with $ 2n-1 $ columns all divided in couplets as in the first array. Choose a couplet from a column of the first array; you will find that couplet also in the other arrays, in the same column and in the same position. In each array there is one and only one couplet with the boxes at that height, so you have a group of $ n $ similar couplets, and you can color each of them with a different color; so for each couplet you choose in the first array, there are exactly $ n $ couplets of that type, one in the first array and $ n-1 $ in the others. You can color each of these couplets with a different colour and you won't get monochromatic rectangles, because in order to get a monochromatic rectangle you need two couplet of the same type (of course in different columns) of the same colour.
Now you have to find a way to divide each column of the first array in $ n $ couplets so that there are no similar couplets in different columns. First of all, write a number 1 in the first box of each column; the remaining part of the array is a$ 2n-1\times2n-1 $ square. Write a number 1 also in the main diagonal of this square (of course you will get a different couplet of 1 in each column). Now think of the square: it has a main diagonal, but also other diagonals parallel to it: for example, if you get all the boxes at the right of a box of the main diagonal, you will get another diagonal, but the main one has $ 2n-1 $ boxes, the new one we are considering has $ 2n-2 $ boxes, because the last box of the main column is at the right side of the square, so there are no other righter boxes; we say that the second diagonal continues by the left side, so (as in the popular videogame snake) if you go beyond the right side, you will arrive in the box of the first column at the same height. In this way we can find another box on the first column for the secon diagonal, and thus the second diagonal has $ 2n-1 $ boxes, one for each column and one for each row. You can divide the square in $ 2n-1 $ diagonals, which start from each box of the first row.
Now, in the first row you have $ 2n-1 $ boxes. The lefter one has a number 1, the other $ 2n-2 $ are still empty. Divide these $ 2n-2 $ boxes of the first row in two groups: the first $ n-1 $ on the left and the second $ n-1 $ on the right. In the first you write, in this order, the numbers 2, 3, ... , $ n $; in the second group you write the numbers $ n $, $ n-1 $, ... , 3, 2. Now write in each diagonal the number written in its box of the first row. For $ n=5 $ you get this array $ 9\times 10 $:
1 1 1 1 1 1 1 1 1
1 2 3 4 5 5 4 3 2
2 1 2 3 4 5 5 4 3
3 2 1 2 3 4 5 5 4
4 3 2 1 2 3 4 5 5
5 4 3 2 1 2 3 4 5
5 5 4 3 2 1 2 3 4
4 5 5 4 3 2 1 2 3
3 4 5 5 4 3 2 1 2
2 3 4 5 5 4 3 2 1
Now, for each column, you consider the couplets with the same number. A couplet with number 1 is different by the other couplets with number 1 because it has a box in the main diagonal at a different height, and is also different by any other couplet with another number because it has a box in the highest row.
Now we can forget the couplets with number 1 and therefore the highest row, so we are considering again only the square.
If there were two couplets at the same height and with the same number, the vertices would form a rectangle and would lie on at least 3 diagonals, but we know that all the boxes with a number $ i $ lie on two diagonals.
So we need only to demonstrate that there are no similar couplets with different numbers. The distance between two boxes of a couplet with number $ i $ is $ 2i-2 $ or $ 2n+1-2i $, so for each number $ i $ we can associate an even number$ 2i-2 $ between 2 and $ 2n-2 $, and an odd number $ 2n+1-2i $ between 1 and $ 2n-3 $. So the distance between the two boxes of a couplet depends on the number of the couplet and is different for each number.
Sono il cuoco della nazionale!