๐Ÿงฎ Brain Teaser

Three-Fold Closure Forces Two-Fold Closure

Field: Algebra (semigroups) ยท Putnam 1995 A1

Problem. Let SS be a set of real numbers that is closed under multiplication: if a,bโˆˆSa,b\in S, then abโˆˆSab\in S. Let TT and UU be disjoint subsets of SS whose union is SS. Suppose:

  • the product of any three elements of TT (not necessarily distinct) is in TT, and
  • the product of any three elements of UU (not necessarily distinct) is in UU.

Show that at least one of TT and UU is closed under multiplication of two elements.


Warm-up sanity check. Take S=Rโˆ–{0}S=\mathbb{R}\setminus\{0\}, T=(0,โˆž)T=(0,\infty) and U=(โˆ’โˆž,0)U=(-\infty,0).

  • The product of three negatives is negative, so UU satisfies the hypothesis.
  • The product of two negatives is positive, so UU is not closed under multiplication of two elements.
  • TT, however, is closed.

So the conclusion "at least one" cannot be strengthened to "both".


Why it's interesting: The statement sounds like it needs structure theory, such as sign characters or homomorphisms to Z/2\mathbb{Z}/2. In fact it falls to a single product of four elements that you are allowed to bracket in two different ways. It is a good example of using associativity as a weapon.

Estimated difficulty: 2 / 5

Reference: 56th Putnam (1995), Problem A1; solution following Kiran Kedlaya's writeup (materials: putnam/1995s.pdf).

semigroupsassociativityproof by contradictionalgebraPutnam 1995

Answer: Three-Fold Closure Forces Two-Fold Closure

Key Idea / Intuition

Suppose both TT and UU fail to be closed. Then some pair from TT "leaks" into UU, and some pair from UU leaks into TT. Multiply both leaky pairs together to get four numbers. The same product can be bracketed as "one element of UU times two elements of UU" or as "two elements of TT times one element of TT." The three-fold rule then forces this single number to lie in both UU and TT, which is impossible because they are disjoint.

The whole proof is: one product, two bracketings, two incompatible verdicts.


Formal Proof / Solution

Step 1: Assume both fail. Suppose, for contradiction, that neither TT nor UU is closed under multiplication. Then:

  • there exist t1,t2โˆˆTt_1,t_2\in T with t1t2โˆ‰Tt_1t_2\notin T;
  • there exist u1,u2โˆˆUu_1,u_2\in U with u1u2โˆ‰Uu_1u_2\notin U.

Step 2: Locate the leaked products. Since SS is closed under multiplication, t1t2โˆˆSt_1t_2\in S and u1u2โˆˆSu_1u_2\in S. Since S=TโŠ”US=T\sqcup U, it follows that t1t2โˆˆU,u1u2โˆˆT.t_1t_2\in U,\qquad u_1u_2\in T.

Step 3: Bracket the same product two ways. Consider P=t1t2u1u2.P = t_1t_2u_1u_2 .

  • First bracketing. Write P=(t1t2)โ‹…u1โ‹…u2P=(t_1t_2)\cdot u_1\cdot u_2. Each of the three factors t1t2,โ€…โ€Šu1,โ€…โ€Šu2t_1t_2,\;u_1,\;u_2 lies in UU. By the three-fold hypothesis for UU, we get PโˆˆUP\in U.
  • Second bracketing. Write P=t1โ‹…t2โ‹…(u1u2)P=t_1\cdot t_2\cdot(u_1u_2). Each of the three factors t1,โ€…โ€Št2,โ€…โ€Šu1u2t_1,\;t_2,\;u_1u_2 lies in TT. By the three-fold hypothesis for TT, we get PโˆˆTP\in T.

Both bracketings are legitimate because multiplication of real numbers is associative.

Step 4: Contradiction. We have found PโˆˆTโˆฉUP\in T\cap U, but TT and UU are disjoint. Hence our assumption was false, and at least one of TT, UU is closed under multiplication. โ– \blacksquare


Remarks

  • What was actually used. We used only that multiplication is associative. Commutativity was not needed, and neither was the fact that we are working with real numbers. The same argument works in any semigroup S=TโŠ”US=T\sqcup U.
  • The model example. Positives versus negatives is the prototype. There, UU behaves like the "odd" coset of a Z/2\mathbb{Z}/2-grading. Three-fold closure is exactly what an odd coset satisfies, since odd + odd + odd is odd. The theorem says that two such "odd-like" pieces cannot coexist.
  • The general lesson. When a hypothesis is about kk-fold products and the conclusion is about 22-fold products, try building a single product that can be read as a kk-fold product in two different ways.

Source: 56th William Lowell Putnam Competition (1995), Problem A1; solutions by Kiran Kedlaya (materials/putnam/1995s.pdf)

Type: PutnamSource: 56th William Lowell Putnam Competition (1995), Problem A1; solutions by Kiran Kedlaya (materials/putnam/1995s.pdf)Edit on GitHub โ†—