Linked and Independent Sets

Problem

For M⊆N∗M \subseteq \mathbb{N}^* with ∣M∣=n≥5|M| = n \ge 5: if MM contains four distinct elements a,b,c,da, b, c, d with a+b=c+da + b = c + d, call MM linked and {a,b,c,d}\{a,b,c,d\} a linked subset; otherwise call MM independent.

1. Are {2,4,6,8,10}\{2,4,6,8,10\} and {1,2,3,5,8}\{1,2,3,5,8\} linked or independent? For linked ones, list all linked subsets. 2. Suppose M={a1<⋯<a5}M = \{a_1 < \cdots < a_5\} is linked, and every pair {ai,aj}\{a_i, a_j\} is contained in some linked subset of MM. Prove that a1,…,a5a_1, \dots, a_5 form an arithmetic progression. 3. If MM is independent, prove that some x∈Mx \in M satisfies x>n2−n+94x > \dfrac{n^2 - n + 9}{4}.

Answer

Solution

Difficulty9/10
Topicscombinatorics, Arithmetic Progression, number theory, Set Theory, Casework

Whiteboard

Your sketch is saved only in this browser. To share it, export your drawing as an image (whiteboard menu → Export as → PNG), then upload that image in the comments below.

Discussion

Ask questions, share alternate solutions, and use LaTeX freely.

0 comments
Log in to join the discussion.

No comments yet.