Q28 Matemática (IMO Longlists 1974)

28 | IMO Longlists | 1974 | Matemática

Seja $M$ um conjunto finito e $P = {M_{1}, M_{2}, \dots, M_{l}}$ uma partição de $M$ (ou seja, $⋃_{i = 1}^{k} M_{i}, M_{i} \neq = \emptyset, M_{i} \cap M_{j} = \emptyset$ para todos os $i, j \in {1, 2, \dots, k}, i \neq = j)$ . Definimos a seguinte operação elementar em $P$ : Escolha $i, j \in {1, 2, \dots, k}$ , tal que $i = j$ e $M_{i}$ tenham elementos a e $M_{j}$ tem elementos $b$ tais que $a \geq b$ . Em seguida, pegue os elementos $b$ de $M_{i}$ e coloque-os em $M_{j}$ , ou seja, $M_{j}$ se torna a união de si mesmo e um subconjunto de elementos $b$ de $M_{i}$ , enquanto o mesmo subconjunto é subtraído de $M_{i}$ (se $a = b$ , $M_{i}$ é removido da partição). Seja dado um conjunto finito $M$ . Prove que a propriedade “para cada partição $P$ de $M$ existe uma sequência $P = P_{1}, P_{2}, \dots, P_{r}$ tal que $P_{i + 1}$ é obtido de $P_{i}$ por um elemento elementar operação e $P_{r} = {M}$ ” é equivalente a “o número de elementos de $M$ é uma potência de $2$ .”