{JF} - Mængde!

Lad mig minde om, at to mængder A og B er disjunkte, når A ∩ B = Ø. Disiunctus; adskilt på latin.

Ingen?

Det er endnu ikke lykkedes nogen at løse en MELLEM-opgave, så jeg falder ikke af stolen, når ingen kan løse en SVÆR opgave. :-)

Svaret er n = 41.

Vi kan antage at der findes 15 delmængder af X. Fællesmængden af alle 7 af disse 15 delmængder indeholder mindst 41 elementer, og der findes ingen 3 eller 15 delmængder, som ikke er disjunkte.

Da ethvert element af X kan tilhøre 2 eller 15 delmængder, kan vi antage at ethvert element i X tilhører nøjagtigt 2 af de 15 delmængder. Ellers kan vi tilføje flere elementer til nogle mængder af disse 15 delmængder, og betingelsen vil stadig holde.

Der er nu en mængde af de 15 delmængder, som vi lader være A, således at

|A| ≥ (2·56/15) + 1 = 8. (Tænk over dette.)

Lad de andre 14 mængder være A₁ , A₂ , ... , A₁₄.

Fællesmængden af hver 7. mængde af A₁ , A₂ , ... , A₁₄ indeholder mindst 41 elementer.

Så det totale antal er y≤41C₁₄⁷ .

Vi kan ydermere udtrykke y:

For a ∈ X, hvis a∉ A, da vil a tilhøre nøjagtigt 2 mængder af A₁, A₂ , ... , A₁₄ .

Dvs. a optræder C₁₄⁷ - C₁₂⁷ gange. 

Hvis a ∈ A. da vil a tilhøre én af disse mængder A₁ , A₂ , ... , A₁₄.

Dvs. a optræder C₁₄⁷ - C₁₃⁷ gange.

Absurdum ad reductio viser jeg, at der heraf følger

41C₁₄⁷ ≤ y ≤ (56 - |A|)(C₁₄⁷ - C₁₂⁷) + |A| (C₁₄⁷ - C₁₃⁷ )

= 56(C₁₄⁷ - C₁₂⁷) - |A| (C₁₃⁷ - C₁₂⁷)

≤ 56(C₁₄⁷ - C₁₂⁷) - 8(C₁₃⁷ - C₁₂⁷) .

196 ≤ 195. Modstrid!

Jeg vil nu vise, at n ≥ 41.

Hvis n ≤ 40 antager vi, at X = {1,2, ... ,56}

Lad nu A_i = {i, i + 7, i + 14, i + 21, i +28, i +35, i + 42, i + 49},

i = 1,2, ... ,7.

B_j = {j, j + 8, j + 16, j + 24, j + 32, j + 40, j + 48},

j = 1,2, ... ,8.

Heraf følger det, at

|A_i| = 8 (i = 1,2, ... ,7), |A_i ∩ A_j| = 0 (1 ≤ i ≤ j ≤ 7),

|B_j| = 7 (j = 1,2, ..., 8), |B_i ∩ B_j| = 0 (1 ≤ i ≤ j ≤ 8),

|A_i ∩ B_j| = 1 (1 ≤ i ≤ 7, 1≤ j ≤ 8).

For alle 3 af disse 15 delmængder, er der 2 mængder, som begge tilhører A_i eller begge tilhører B_j.

Så de 3 mængder er altså disjunkte.

Vi husker på, at alle 7 af disse 15 delmængder

fx A_i1 , A_i2 , ... , A_is

og B_j1 , B_j2 , ... , B_jt (s + t = 7).

Dermed har vi, at

|A_i1 ∪ A_i2 ∪ ... ∪A_is ∪ B_j1 ∪B_j2 ∪ ... ∪B_jt|

= |A_i1| + |A_i2| + ... + |A_is| + |B_j1| + |B_j2| + ... + |B_jt| - st

= 8s + 7t - st

= 8s + 7(7 - s) - s(7 - s)

= (s - 3)² + 40 ≥ 40.

Dermed er n ≥ 41, og vi har færdiggjort vores argument.

n = 41.

j skal være strengt mindre end i. Ellers giver det problemer. Der skal altså stå

|A_i| = 8 (i = 1,2, ... ,7), |A_i ∩ A_j| = 0 (1 ≤ i < j ≤ 7),

|B_j| = 7 (j = 1,2, ..., 8), |B_i ∩ B_j| = 0 (1 ≤ i < j ≤ 8).