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

Difference between revisions of "1988 IMO Problems/Problem 2"

(Created page with "== Problem == Let <math>n</math> be a positive integer and let <math>A_1, A_2, \cdots, A_{2n+1}</math> be subsets of a set <math>B</math>. Suppose that (a) Each <math>A_i</...")
 
 
(5 intermediate revisions by 2 users not shown)
Line 12: Line 12:
  
 
For which values of <math>n</math> can one assign to every element of <math>B</math> one of the numbers <math>0</math> and <math>1</math> in such a way that <math>A_i</math> has <math>0</math> assigned to exactly <math>n</math> of its elements?
 
For which values of <math>n</math> can one assign to every element of <math>B</math> one of the numbers <math>0</math> and <math>1</math> in such a way that <math>A_i</math> has <math>0</math> assigned to exactly <math>n</math> of its elements?
 +
 +
== Solution ==
 +
 +
Answer: All <math>n</math> such that <math>4|n</math>
 +
 +
We first make the following <math>2</math> claims:
 +
 +
Claim <math>1</math>: Each element of union belongs to exactly <math>2</math> subsets.
 +
 +
Proof:
 +
 +
Consider a subset <math>A_i</math>. Assume that some element <math>x \in\ A_i</math> also <math>\in A_k, A_l</math>. There are <math>n-1</math> elements remaining in <math>A_i</math> and there are <math>n-2</math> subsets to choose from. By pigeon hole principle, at least <math>1</math> of the remaining elements in <math>A_i</math> must <math>\in A_k</math> or <math>\in A_l</math>. This contradicts the assumption that any <math>2</math> subsets have only <math>1</math> element in common.
 +
 +
Claim <math>2</math>: <math>4|n</math>
 +
 +
Proof:
 +
 +
Now, since each element in <math>A_i \in</math> exactly <math>1</math> other subset, total number of elements present in the union = <math>n*(n+1)/2</math>.
 +
If each subset must have <math>n/2</math> elements assigned a value of <math>1</math>, the total number of elements assigned value of <math>1</math> = <math>n/2*(n+1)/2 = n*(n+1)/4</math>.
 +
Thus <math>4</math> must divide <math>n</math>.
 +
 +
 +
Now we make our final claim:
 +
 +
Claim <math>3</math>: <math>4|n</math> 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 <math> \frac {n}{2}</math> zeros.
 +
 +
Proof:
 +
 +
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</math> vertices, meaning each of the <math>n</math> elements of <math>A_i</math> is part of <math>1</math> other subset.
 +
 +
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.
 +
 +
- Kris17
 +
 +
 +
{{Alternate solutions}}
 +
 +
== See Also ==
 +
{{IMO box|year=1988|num-b=1|num-a=3}}
 +
 +
[[Category:Olympiad Combinatorics Problems]]

Latest revision as of 10:32, 30 January 2021

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$ vertices, meaning each of the $n$ elements of $A_i$ is part of $1$ other subset.

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://artofproblemsolving.com/wiki/index.php?title=1988_IMO_Problems/Problem_2&oldid=144055"