Competition problem — Combinatorics

Library / /295 of 520

Combinatorics Difficulty 5.3 AIME, harder Prove it

Question 11 Let the set of integers $A$ have $n$ elements. Prove: there exists a subset $B$ of set $A$ such that the number of elements in $B$ is greater than $\frac{n}{3}$ , and for any $x, y \in B$ , we have $x+y \notin B$ .

---

The translation maintains the original text's line breaks and formatting.

Solution

Prove that for a prime $p$ satisfying
$p>\max _{x \in A}|x|, p \equiv 2(\bmod 3) \text {. }$

Define the set
$H_{k}=\{a \in A \mid a k$ is the smallest non-negative residue of $p$ modulo 3 and is congruent to 1 $\}$ , where $0\frac{|A|}{3}$ is the desired result.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.