Interesting Sets

For 1 i 2018 1 \le i \le 2018 with i Z , i \in \mathbb{Z}, let A i A_i be 2018 sets such that A i = 44 |A_i| = 44 and for every integers 1 j < k 2018 , 1 \le j < k \le 2018, A j A k = 1. |A_j \cap A_k| = 1. Find the smallest possible value of i = 1 2018 A i . \displaystyle \large \left| \bigcup _{ i=1 }^{ 2018 }{ A_{ i } } \right|.


The answer is 86775.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Julian Poon
Jun 3, 2018

Since A 1 A i = 1 |A_1 \cap A_i| = 1 for all 1 i 2018 1 \le i \le 2018 and A 1 = 44 |A_1| = 44 , by the Pigeonhole Principle , there exists an element a A 1 a \in A_1 such that 46 other sets also contain a a . Without loss of generality, let a A 1 , A 2 , . . . , A 47 a \in A_1, A_2, ..., A_{47} .

Suppose there exists a set A q A_q such that a A q a \notin A_q . Then A q A 1 A q A 2 . . . A q A 47 A_q \cap A_1 \ne A_q \cap A_2 \ne ... \ne A_q \cap A_{47} , otherwise it would break the condition that A j A k = 1 |A_j \cap A_k| = 1 for integers 1 j < k 2018 1 \le j < k \le 2018 . However, this also means that A q 47 |A_q| \ge 47 , which is a contradiction. Hence no such A q A_q exists.

This also means that i = 1 2018 A i = a \displaystyle \bigcap _{ i=1 }^{ 2018 }{ A_{ i } } =a . Hence

i = 1 2018 A i = 2018 × 43 + 1 = 86775 \displaystyle \large \left| \bigcup _{ i=1 }^{ 2018 }{ A_{ i } } \right| = 2018 \times 43 + 1 = 86775

I think it would be a slightly harder problem if you asked for the smallest possible value of i = 1 2018 A i , \left| \bigcup _{ i=1 }^{ 2018 }{ A_{ i } } \right|, as you'd have to convince yourself that every set intersected in the same point to be convinced that 86775 86775 was correct.

Patrick Corn - 3 years ago

Log in to reply

Nice! I've modified the question to that

Julian Poon - 3 years ago
Ankon Dey
Jun 3, 2018

The second condition seems interesting. huh?? 1 j < k 2018 1\le j<k\le 2018 and A j A k = 1. |A_j\cap A_k|=1. ?? well. Let us imagine that there is an element say X X such that every set contains X X . And all other elements are distinct. So the second condition is ensured and the first condition helps us to count the answer.

A 1 A_1 has 44 distinct elements. A 2 A_2 has 43 elements which are not in A_1. A 3 A_3 also has 43 elements which are not in A 1 A_1 or A 2 A_2 ........ and so on........ A 2018 A_{2018} has 43 elements which are not in A 1 , A 2 , A 3 , . . . . . , A 2017 A_1,A_2,A_3,.....,A_{2017}

thus the answer is 44 + 2017 43 44+2017*43 = 86775 86775

You need to prove that this is the only way. You have not disproved the case where A 1 A 2 A i A j A_1 \cap A_2 \ne A_i \cap A_j for some integers i , j i, j .

Julian Poon - 3 years ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...