We continue discussing Olympiad problems and their solutions.
A natural number is written in each square of an m x n chessboard. The allowed move is to add an integer k to each of the two adjacent numbers in such a way that non-negative numbers are obtained (two squares are adjacent if they share a common side). Find a necessary and sufficient condition for it to be possible for all numbers to be zero after finitely many operations.
The chessboard happens to be black and white alternatively with equal numbers of black and white. If we pick adjacent numbers one will be on a black square and another will be on a white square. Since we add equally at each step, the sum of the numbers on the black square must be the same as the sum of the numbers on white square at any point of time! - at the beginning, at the end and every step of the progressive conversion to zero in between the beginning and the end.
But how do we pick these adjacent squares ? For the progression, the choice of squares don't matter because any two adjacent squares we pick we should be able to make them both zero and if we don't revisit the squares we have made zero, we can progress towards the end. If we can make two adjacent squares in a row zero in each step, then we can repeat this for all the rows while leaving only the last two in each row. Then we can descend down the last two columns a row at a time, thus sweeping the chessboard without revisiting the squares. By symmetry of a chessboard, the same can be done by sweeping columns at a time until the last two rows and then sweeping the last two rows.
Having discussed the way to progress without revisiting the squares converted to zero, let us now look at how to convert each pair of adjacent squares. Let us call the two adjacent squares in a row a and b. If a < b then we can add -a to both and make one zero. if a > b and b is adjacent to c, then we can add a-b to both b and c . b becomes a at this point and both a and b can become zero by adding -a. Thus we convert one square or both squares to zero. Since a-b is a positive number and the numbers on the chess board were natural numbers to begin with, we don't diminish the squares we have not covered and we progress towards the goal.
#codingexercise
Node GetSecondLargestInBST ( node root){
Node largest = GetRightmost (root);
Return GetPredecessor(largest);
}
A natural number is written in each square of an m x n chessboard. The allowed move is to add an integer k to each of the two adjacent numbers in such a way that non-negative numbers are obtained (two squares are adjacent if they share a common side). Find a necessary and sufficient condition for it to be possible for all numbers to be zero after finitely many operations.
The chessboard happens to be black and white alternatively with equal numbers of black and white. If we pick adjacent numbers one will be on a black square and another will be on a white square. Since we add equally at each step, the sum of the numbers on the black square must be the same as the sum of the numbers on white square at any point of time! - at the beginning, at the end and every step of the progressive conversion to zero in between the beginning and the end.
But how do we pick these adjacent squares ? For the progression, the choice of squares don't matter because any two adjacent squares we pick we should be able to make them both zero and if we don't revisit the squares we have made zero, we can progress towards the end. If we can make two adjacent squares in a row zero in each step, then we can repeat this for all the rows while leaving only the last two in each row. Then we can descend down the last two columns a row at a time, thus sweeping the chessboard without revisiting the squares. By symmetry of a chessboard, the same can be done by sweeping columns at a time until the last two rows and then sweeping the last two rows.
Having discussed the way to progress without revisiting the squares converted to zero, let us now look at how to convert each pair of adjacent squares. Let us call the two adjacent squares in a row a and b. If a < b then we can add -a to both and make one zero. if a > b and b is adjacent to c, then we can add a-b to both b and c . b becomes a at this point and both a and b can become zero by adding -a. Thus we convert one square or both squares to zero. Since a-b is a positive number and the numbers on the chess board were natural numbers to begin with, we don't diminish the squares we have not covered and we progress towards the goal.
#codingexercise
Node GetSecondLargestInBST ( node root){
Node largest = GetRightmost (root);
Return GetPredecessor(largest);
}
No comments:
Post a Comment