Find the largest n

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Find the largest n

G H J

Reveal topic tags

analytic geometry

pigeonhole principle

number theory unsolved

L

G H BBookmark kLocked kLocked NReply

Source: Baltic Way 2009

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mathgeniuse^ln(x)

5020 posts

mathgeniuse^ln(x)

#1 h Nov 30, 2009, 5:36 PM • 3 Y

Y by Adventure10, Mango247, and 1 other user

Find the largest integer $n$ for which there exist $n$ different integers such that none of them are divisible by either of $7,11$ or $13$ , but the sum of any two of them is divisible by at least one of $7,11$ and $13$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

867 posts

#2 h Dec 1, 2009, 3:08 AM • 3 Y

Y by Adventure10, Mango247, and 1 other user

the answer is actually 8.

we may represent each integer by a triple $(a, b, c)$ , where $a, b, c$ are the remainders upon division by 7, 11, 13, respectively. for each remainder $a$ , let $a'$ denote the complementary remainder; e.g., the complementary remainder modulo 7 of 3 is 4. for two $n$ -tuples $(a_1, ..., a_n)$ , $(b_1, ..., b_n)$ of remainders, we say that they "match" in the $i$ -th position if $a_i = b_i'$ . a set of $n$ -tuples will be called "matching" if any two of them match in at least one position; otherwise, we call them "mismatched." so the statement we want to prove is, that a set of matching triples must have size at most 8. first we prove the following lemma.

Lemma: a set of matching pairs can have size at most 4.

Proof: assume, for a contradiction, that we have a set of 5 matching pairs, and let $a, b, c, d, e$ denote these pairs. assume for the moment that $a$ matches 3 of the other pairs - WLOG we may assume they are $b, c, d$ - in the first position. then $b, c, d$ coincide in the first position, so any two of them must match each other in the second position - but this is impossible. so $a$ can match at most 2 of the other pairs in the first position, and similarly it can match at most 2 of the other pairs in the second position. since there are four other pairs, a must match *exactly* 2 in the first position and 2 in the second position. now let $a = (x,y)$ . by what we've just proved, the other pairs must be of the form $(x, a), (x, a'), (b, y), (b', y)$ . now, for $(x, a')$ to match $(b, y)$ , we must have either $x = b'$ or $y = a$ . in both cases, we have 3 pairs which coincide in one position, which as before, is impossible. this completes the proof of the lemma.

now to the result we want to prove. assume, for a contradiction, that we have a set of 9 matching triples. take the 9 numbers in the first coordinates of these triples and partition them into two sets so that no two numbers in the same set are complementary. (this is possible because every number has a unique complement and no number is its own complement because the moduli are odd.) by the pigeonhole principle, one of these sets contains 5 numbers, and these numbers are pairwise non-complementary. thus there are 5 triples which are mutually mismatched in their first coordinates. their second and third coordinates then give us 5 matching pairs, contrary to the lemma.

to see that 8 is indeed possible, take 8 triples of the form $(a, b, c), (a', b, d), (a, b', e), (a', b', f), (a', b', f'), (a, b, c'), (a', b, d'), (a, b', e')$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mathgeniuse^ln(x)

5020 posts

mathgeniuse^ln(x)

#3 h Dec 1, 2009, 11:23 PM • 2 Y

Y by Adventure10, Mango247

thank you.

I realized 120 was too high, as I thought that every pair added up to a multiple of 7, 11, 13 in my set of 120, but I was wrong.

Nice solution.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a