For 1 ≤ i ≤ 2 0 1 8 with i ∈ Z , let A i be 2018 sets such that ∣ A i ∣ = 4 4 and for every integers 1 ≤ j < k ≤ 2 0 1 8 , ∣ A j ∩ A k ∣ = 1 . Find the smallest possible value of ∣ ∣ ∣ ∣ ∣ ∣ i = 1 ⋃ 2 0 1 8 A i ∣ ∣ ∣ ∣ ∣ ∣ .
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.
I think it would be a slightly harder problem if you asked for the smallest possible value of ∣ ∣ ∣ ⋃ i = 1 2 0 1 8 A i ∣ ∣ ∣ , as you'd have to convince yourself that every set intersected in the same point to be convinced that 8 6 7 7 5 was correct.
The second condition seems interesting. huh?? 1 ≤ j < k ≤ 2 0 1 8 and ∣ A j ∩ A k ∣ = 1 . ?? well. Let us imagine that there is an element say X such that every set contains 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 has 44 distinct elements. A 2 has 43 elements which are not in A_1. A 3 also has 43 elements which are not in A 1 or A 2 ........ and so on........ A 2 0 1 8 has 43 elements which are not in A 1 , A 2 , A 3 , . . . . . , A 2 0 1 7
thus the answer is 4 4 + 2 0 1 7 ∗ 4 3 = 8 6 7 7 5
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 for some integers i , j .
Problem Loading...
Note Loading...
Set Loading...
Since ∣ A 1 ∩ A i ∣ = 1 for all 1 ≤ i ≤ 2 0 1 8 and ∣ A 1 ∣ = 4 4 , by the Pigeonhole Principle , there exists an element a ∈ A 1 such that 46 other sets also contain a . Without loss of generality, let a ∈ A 1 , A 2 , . . . , A 4 7 .
Suppose there exists a set A q such that a ∈ / A q . Then A q ∩ A 1 = A q ∩ A 2 = . . . = A q ∩ A 4 7 , otherwise it would break the condition that ∣ A j ∩ A k ∣ = 1 for integers 1 ≤ j < k ≤ 2 0 1 8 . However, this also means that ∣ A q ∣ ≥ 4 7 , which is a contradiction. Hence no such A q exists.
This also means that i = 1 ⋂ 2 0 1 8 A i = a . Hence
∣ ∣ ∣ ∣ ∣ ∣ i = 1 ⋃ 2 0 1 8 A i ∣ ∣ ∣ ∣ ∣ ∣ = 2 0 1 8 × 4 3 + 1 = 8 6 7 7 5