On a board, some cells on the top-right to bottom-left diagonal are marked. None of the marked cells is in a corner. Integers are written in each cell of this board in the following way. All the numbers in the cells along the upper and the left sides of the board are 1's. All the numbers in the marked cells are 0's. Each of the other cells contains a number that is equal to the sum of its upper neighbour and its left neighbour. Prove that the number in the bottom right corner is not divisible by 2011.
Solutions — 2
Solution 1
. Let a peg go on the board, stepping from a cell to the neighbor cell right or below. Then the number in the bottom right corner of the board is equal to the number of paths of the peg from the top left corner to the bottom right corner, which do not visit the marked cells.
The total number of paths (including those that pass through the marked cells) equals ; this number is not divisible by 2011, because 2011 is a prime number. The number of paths that pass through the -th cell of the diagonal equals , because in order to visit this cell starting from the corner the peg should make 2011 steps, of which are horizontal, and others are vertical; and after the visit it also should make 2011 steps, of which is vertical. Since (because the marked cells are not in the corner) this number is divisible by 2011.
So the number in the low right corner equals the difference of the number that is not divisible by 2011 and several numbers that are divisible by 2011.
Solution 2
1. Understanding the Problem:
We are given a board with some cells on the top-right to bottom-left diagonal marked. The cells in the corners are not marked. The numbers in the cells are defined as follows:
- All cells along the upper and left sides of the board contain the number 1.
- All marked cells contain the number 0.
- Each other cell contains a number equal to the sum of its upper neighbor and its left neighbor.
2. Initial Observation:
If no cells were marked, the number in each cell represents the number of ways to reach that cell from the top-left corner using only right and down movements. The number in the bottom-right corner would be the binomial coefficient .
3. Binomial Coefficient Modulo 2011:
We need to evaluate . Using properties of binomial coefficients and Fermat's Little Theorem, we know:
This is because for a prime .
4. Effect of Marked Cells:
Marking a cell (where moves to the right and moves down) decreases the number of ways to reach the bottom-right corner by . Since is prime, is divisible by for .
5. Conclusion:
Since each is divisible by , marking any cell on the diagonal does not change the fact that the number in the bottom-right corner remains congruent to . Therefore, the number in the bottom-right corner is not divisible by .