MathDB

2

Part of 2013 Iran MO (2nd Round)

Problems(2)

Complete set of weights

Source: Iran second round- 2013- P2

5/4/2013
Let nn be a natural number and suppose that w1,w2,…,wn w_1, w_2, \ldots , w_n are nn weights . We call the set of {w1,w2,…,wn}\{ w_1, w_2, \ldots , w_n\} to be a Perfect Set if we can achieve all of the 1,2,…,W1,2, \ldots, W weights with sums of w1,w2,…,wn w_1, w_2, \ldots , w_n, where W=∑i=1nwiW=\sum_{i=1}^n w_i . Prove that if we delete the maximum weight of a Perfect Set, the other weights make again a Perfect Set.
inductioncombinatorics proposedcombinatorics
Amazing Table

Source:

5/19/2013
Suppose a m×nm \times n table. We write an integer in each cell of the table. In each move, we chose a column, a row, or a diagonal (diagonal is the set of cells which the difference between their row number and their column number is constant) and add either +1+1 or −1-1 to all of its cells. Prove that if for all arbitrary 3×33 \times 3 table we can change all numbers to zero, then we can change all numbers of m×nm \times n table to zero.
(Hint: First of all think about it how we can change number of 3×3 3 \times 3 table to zero.)
inductioninvariantgeometrygeometric transformationcombinatorics proposedcombinatorics