IMO 1974 LL ROM28

Origin: ROM

Problem

Let M be a finite set and P = {M1, M2, . . . , Mk} a partition of M (i.e., %k i=1 Mi = M, Mi ̸= \emptyset, Mi \capMj = \emptysetfor all i, j \in{1, 2, . . ., k}, i ̸= j). We define the following elementary operation on P: Choose i, j \in{1, 2, . . ., k}, such that i ̸= j and Mi has a elements and Mj has b elements such that a \geqb. Then take b elements from Mi and place them into Mj, i.e., Mj becomes the union of itself unifies and a b-element subset of Mi, while the same subset is subtracted from Mi (if a = b, Mi is thus removed from the partition). Let a finite set M be given. Prove that the property “for every partition P of M there exists a sequence P = P1, P2, . . . , Pr such that Pi+1 is obtained from Pi by an elementary operation and Pr = {M}” is equivalent to “the number of elements of M is a power of 2.”