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

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.

@@ Line 14: / Line 14: @@
 == 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}}
@@ Line 19: / Line 53: @@
 == See Also ==
 {{IMO box|year=1988|num-b=1|num-a=3}}
+[[Category:Olympiad Combinatorics Problems]]

1988 IMO (Problems) • Resources
Preceded by Problem 1	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 3
All IMO Problems and Solutions

Page

Toolbox

Search

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

Latest revision as of 10:32, 30 January 2021

Problem

Solution

See Also