Problem 4

Let a and b be positive integers, and let A and B be finite sets of integers satisfying: (i) A and B are disjoint; (ii) if an integer i belongs either to A or to B, then i+a belongs to A or i-b belongs to B. Prove that a|A|=b|B|, where |X| denotes the number of elements of X.

Step 2 of 5: Force equality of the unions

Previous step Next step

A\cup B\subseteq A^*\cup B^*,\quad |A^*\cup B^*|\le|A^*|+|B^*|=|A|+|B|=|A\cup B|.

Detailed analysis

Condition (ii) puts every element of A∪B into A or B. Translation preserves cardinality, and A,B are disjoint, so the displayed cardinality chain has equal endpoints. Therefore every inequality is equality.