Art of Problem Solving
Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

1988 IMO Problems/Problem 2: Difference between revisions

← Older editNewer edit →
KRIS17 (talk | contribs)
editor
76 edits
No edit summary
KRIS17 (talk | contribs)
editor
76 edits
Line 42: Line 42:
Consider a regular polygon consisting of <math>n+1</math> vertices where each line joining two vertices <math>A_i, A_j</math> represents the element which <math>\in A_i, A_j</math>. Clearly there are a total of <math>n*(n-1)/2</math> such lines representing the total number of elements of the union where each vertex is connected to <math>n-1</math> vertices, meaning each element of <math>A_i</math> is part of <math>n-1</math> other subsets.
Consider a regular polygon consisting of <math>n+1</math> vertices where each line joining two vertices <math>A_i, A_j</math> represents the element which <math>\in A_i, A_j</math>. Clearly there are a total of <math>n*(n-1)/2</math> such lines representing the total number of elements of the union where each vertex is connected to <math>n-1</math> vertices, meaning each element of <math>A_i</math> is part of <math>n-1</math> other subsets.


Starting with <math>i = 1</math>, let us start coloring all lines joining vertices <math>A_i</math>, <math>A_i+1</math> with color Red, all lines joining <math>A_i</math>, <math>A_i+2</math> with color White, <math>A_i</math>, <math>A_i+3</math> with color Red, <math>A_i</math>, <math>A_i+4</math> with color White and so on ... <math>A_i</math>, <math>A_i+n/2</math> with color White.
Starting with <math>i = 1</math>, let us start coloring all lines joining vertices <math>A_i</math>, <math>A_{i+1}</math> with color Red, all lines joining <math>A_i</math>, <math>A_{i+2}</math> with color White, <math>A_i</math>, <math>A_{i+3}</math> with color Red, <math>A_i</math>, <math>A_{i+4}</math> with color White and so on ... <math>A_i</math>, <math>A_{i+n/2}</math> with color White.


Clearly each line from vertex <math>A_i</math> alternates Red, White for first <math>n/2</math> lines and then alternates White, Red for remaining <math>n/2</math> lines implying that we could have exactly <math>n/2</math> red lines emanating from each vertex <math>A_i</math>. But these <math>n/2</math> lines represent <math>n/2</math> elements of each subset <math>A_i</math> which could each be assigned a value of <math>0</math>.  This completes the proof.
Clearly each line from vertex <math>A_i</math> alternates Red, White for first <math>n/2</math> lines and then alternates White, Red for remaining <math>n/2</math> lines implying that we could have exactly <math>n/2</math> red lines emanating from each vertex <math>A_i</math>. But these <math>n/2</math> lines represent <math>n/2</math> elements of each subset <math>A_i</math> which could each be assigned a value of <math>0</math>.  This completes the proof.

Revision as of 00:28, 15 March 2020

Problem

Let $n$ be a positive integer and let $A_1, A_2, \cdots, A_{2n+1}$ be subsets of a set $B$.

Suppose that

(a) Each $A_i$ has exactly $2n$ elements,

(b) Each $A_i\cap A_j$ $(1\le i<j\le 2n+1)$ contains exactly one element, and

(c) Every element of $B$ belongs to at least two of the $A_i$.

For which values of $n$ can one assign to every element of $B$ one of the numbers $0$ and $1$ in such a way that $A_i$ has $0$ assigned to exactly $n$ of its elements?

Solution

Answer: All $n$ such that $4|n$

We first make the following $2$ claims:

Claim $1$: Each element of union belongs to exactly $2$ subsets.

Proof:

Consider a subset $A_i$. Assume that some element $x \in\ A_i$ also $\in A_k, A_l$. There are $n-1$ elements remaining in $A_i$ and there are $n-2$ subsets to choose from. By pigeon hole principle, at least $1$ of the remaining elements in $A_i$ must $\in A_k$ or $\in A_l$. This contradicts the assumption that any $2$ subsets have only $1$ element in common.

Claim $2$: $4|n$

Proof:

Now, since each element in $A_i \in$ exactly $1$ other subset, total number of elements present in the union = $n*(n-1)/2$. If each subset must have $n/2$ elements assigned a value of $1$, the total number of elements assigned value of $1$ = $n/2*(n-1)/2 = n*(n-1)/4$. Thus $4$ must divide $n$.


Now we make our final claim:

Claim $3$: $4|n$ is a sufficient condition to assign every element of the union one of the numbers 0 and 1 in such a manner that each of the sets has exactly $\frac {n}{2}$ zeros.

Proof:

Consider a regular polygon consisting of $n+1$ vertices where each line joining two vertices $A_i, A_j$ represents the element which $\in A_i, A_j$. Clearly there are a total of $n*(n-1)/2$ such lines representing the total number of elements of the union where each vertex is connected to $n-1$ vertices, meaning each element of $A_i$ is part of $n-1$ other subsets.

Starting with $i = 1$, let us start coloring all lines joining vertices $A_i$, $A_{i+1}$ with color Red, all lines joining $A_i$, $A_{i+2}$ with color White, $A_i$, $A_{i+3}$ with color Red, $A_i$, $A_{i+4}$ with color White and so on ... $A_i$, $A_{i+n/2}$ with color White.

Clearly each line from vertex $A_i$ alternates Red, White for first $n/2$ lines and then alternates White, Red for remaining $n/2$ lines implying that we could have exactly $n/2$ red lines emanating from each vertex $A_i$. But these $n/2$ lines represent $n/2$ elements of each subset $A_i$ which could each be assigned a value of $0$. This completes the proof.

- Kris17


Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

See Also

1988 IMO (Problems) • Resources
Preceded by
Problem 1 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 3
All IMO Problems and Solutions
Retrieved from "https://wiki.aopstest.com/wiki/index.php?title=1988_IMO_Problems/Problem_2&oldid=119429"