• Non ci sono risultati.

# Let m be a positive integer, and let A and B be nonempty subsets of {0, 1}m

N/A
N/A
Protected

Condividi "Let m be a positive integer, and let A and B be nonempty subsets of {0, 1}m"

Copied!
1
0
0

Testo completo

(1)

Problem 11666

(American Mathematical Monthly, Vol.119, October 2012)

Proposed by Dmitry G. Fon-Der-Flaass (Russia) and Max. A. Alekseyev (USA).

Let m be a positive integer, and let A and B be nonempty subsets of {0, 1}m. Let n be the greatest integer such that |A|+|B| > 2n. Prove that |A+B| ≥ 2n. (Here, |X| denotes the number of elements in X, and A + B denotes {a + b : a ∈ A, b ∈ B}, where addition of vectors is componentwise modulo 2.)

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.

We will prove a more general statement.

Let p be a prime and let A and B be nonempty subsets of the abelian group Zmp. If |A| + |B| > pn then |A + B| ≥ pn.

We divide the proof in several claims:

i) If |A| = 1 then |A| + |B| > pn implies that |B| ≥ pn and

|A + B| = |a + B| = |B| ≥ pn. ii) Assume that |A| > 1. If B intersects A properly that is if

A ∩ B 6= ∅ and A \ B 6= ∅

then let A0= A ∩ B and let B0= A ∪ B so that |A0| < |A|, and |A0|+|B0| = |A|+|B|. Moreover if a0+ b0∈ A0+ B0 then

a0+ b0∈ A + B for b0 ∈ A and a0+ b0∈ B + A for b0∈ B

which imply that A0+ B0 ⊂ A + B and |A0+ B0| ≤ |A + B|. Hence it suffices to prove the required property for A0 and B0 with 1 ≤ |A0| < |A|.

iii) If B does not intersect A properly, take A0 = A + (p − 1)a + b with a ∈ A and b ∈ B then b = a + (p − 1)a + b ∈ A0∩ B 6= ∅. If there is b ∈ B such that A0\ B 6= ∅ then B intersects A0 properly and we can apply i) with A replaced by A0.

iv) If at each step it is possible to apply iii) and ii), we are able to reduce the size of the set A until we can use i) and the proof is complete. Thus it suffices to consider the case when at some step we can not apply iii): A0\ B = ∅ for all b ∈ B, that is (A + (p − 1)a) + B ⊂ B.

Since 0 ∈ (A+(p−1)a) it follows that B ⊂ (A+(p−1)a)+B and therefore (A+(p−1)a)+B = B.

Consider the set S(B) = {x ∈ Zmp : x + B = B}. It is easy to verify that S(B) is a subgroup of Zmp, and (A + (p − 1)a) + B = B implies that (A + (p − 1)a) ⊂ S(B) and B is the union of cosets of S(B). Hence |A| = |(A + (p − 1)a)| ≤ |S(B)| = pd, |B| = r|S(B)| = rpd for some integers d ≥ 0 and r ≥ 1 and

|A + B| = |(A + (p − 1)a) + B| = |B| = rpd , |A| + |B| = |(A + (p − 1)a)| + |B| ≤ (r + 1)pd. Now rpd = |A + B| < pn< |A| + |B| ≤ (r + 1)pd yields the contradiction 1 ≤ r < pn−d< r + 1 (pn−d is an integer!). Therefore |A + B| ≥ pn.



Riferimenti

Documenti correlati

We can now conclude with a brief summary on how the previous Lemmas provide the proof of the various cases stated in Theorem 4.1 (for each case we point out an example as

[r]

We denote with A, B, and C the position vectors of the vertices of the given

[r]

[r]

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit` a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.. If M is finite then the

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit` a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy. Let N b (k) be the set of

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.. For k