MathDB
Operation on the set P of partitions of M [ILL 1974]

Source:

January 2, 2011
combinatorics proposedcombinatorics

Problem Statement

Let MM be a finite set and P={M1,M2,…,Ml}P=\{ M_1,M_2,\ldots ,M_l\} a partition of MM (i.e., ⋃i=1kMi,Mi≠∅,Mi∩Mj=∅\bigcup_{i=1}^k M_i, M_i\not=\emptyset, M_i\cap M_j =\emptyset for all i,j∈{1,2,…,k},i≠j)i,j\in\{1,2, \ldots ,k\} ,i\not= j). We define the following elementary operation on PP: Choose i,j∈{1,2,…,k}i,j\in\{1,2,\ldots ,k\}, such that i=ji=j and MiM_i has a elements and MjM_j has bb elements such that a≥ba\ge b. Then take bb elements from MiM_i and place them into MjM_j, i.e., MjM_j becomes the union of itself and a bb-element subset of MiM_i, while the same subset is subtracted from MiM_i (if a=ba=b, MiM_i is thus removed from the partition). Let a finite set MM be given. Prove that the property “for every partition PP of MM there exists a sequence P=P1,P2,…,PrP=P_1,P_2,\ldots ,P_r such that Pi+1P_{i+1} is obtained from PiP_i by an elementary operation and Pr={M}P_r=\{M\}” is equivalent to “the number of elements of MM is a power of 22.”
Back to ProblemsView on AoPS