{JF} - Algebra vol. 2

Lad n ≥ 4 og betragt nu mængden

M = {m, m + 1, m + 2, ... , m + n + 1}.

Hvis 2 | m, da er m + 1, m + 2, m + 3 indbyrdes primiske.

Hvis 2 derimod ikke går op i m, er m, m + 1, m + 2 indbyrdes primiske.

Så, i enhver n - element delmængde af M, er der mindst 3 tal, som er indbyrdes primiske.

Vi har hermed, at

∃f(n) : f(n) ≤ n.

Lad §_n := {q : q ≤ n + 1 og 2 | q eller 3 | q }.

Da er §_n en delmængde af {2, 3, ... , n + 1}.

Men alle 3 elementer i §_n er ikke indbyrdes primiske, så f(n) ≥ |§_n| + 1.

Dermed har vi, at

|§_n| = (n+1) / 2 + (n+1) / 3 - (n+1) / 6. (Tænk over dette.)

Da er f(n) ≥ (n+1) / 2 + (n+1) / 3 - (n+1) / 6 + 1.

Heraf følger det klart, at

f(4) ≥ 4, f(5) ≥ 5, f(6) ≥ 5, f(7) ≥ 6, f(8) ≥ 7 og f(9) ≥ 8.

Lad os nu vise, at f(6) = 5.

Lad x₁ , x₂ , ... , x₅ ∈ {m, m + 1, ... , m + 5}.

Hvis der blandt disse fem tal er 3 ulige, så er de indbyrdes primiske.

Hvis der er 2 ulige blandt de 5 tal, så er der tre tal, der er lige.

Lad x₁, x₂, x₃ være de lige, og lad x₄, x₅ være de ulige.

Når 1 ≤ i < j ≤ 3, |x_i - x_j| ∈ {2,4}. Blandt de lige tal er der mindst et, som er deleligt med 3, og der er mindst et tal, der er deleligt med 5. Dermed er der et tal, som hverken er et multiplum af 3 eller 5. Lad x₃ være dette tal.

Da er x₃ , x₄ , x₅ indbyrdes primiske.

Så blandt de 5 tal er der 3 elementer, der er indbyrdes primiske.

Dvs. f(6) = 5.

Ydermere bemærker vi, at

{m, m + 1, ... , m + n} = {m, m + 1, ... , m + n - 1} ∪ {m + n}, som medfører

f(n + 1) ≤ f(n) + 1.

Da f(6) = 5, har vi, at

f(4) = 4, f(5) = 5, f(7) = 6, f(8) = 7 og f(9) = 8.

Da n∈[4,9] følger det, at

f(n) = (n+1) / 2 + (n+1) / 3 - (n+1) / 6 + 1.

Denne lighed gælder pr. induktion. Vi kan antage, at den gælder for ∀n≤k.

{m , m + 1, ... , m + k}

= {m, m + 1, ... , m + k - 6} ∪ {m + k - 5, m + k - 4, m + k - 3, m + k - 2, m + k - 1, m + k}

Ligheden holder for n = 6, n = k - 5. (Husk på k ≥ 9.)

Heraf følger det trivielt, at

f(k + 1) ≤ f(k - 5) + f(6) - 1

= (k+2)/2 + (k+2)/3 - (k+2)/6 + 1. Dermed holder ligningen for n = k + 1.

Heraf følger det, at vi for ∀n≥4 har

f(n) = (n+1)/2 + (n+1)/3 - (n+1)/6 + 1, og vi er færdige.

Man kan løse den på en mere elegant måde.

Vi kan starte med at vise identiteterne f(4) = 4, f(5) = 5 og f(6) = 6.

Lad n = 4 og betragt mængden {m, m + 1, m + 2, m + 3}.

Hvis m er ulige, da er m, m + 1, m + 2 indbyrdes primiske. Hvis m derimod er lige, da er m + 1, m + 2 og m + 3 indbyrdes primiske. Da er f(4) ≤ 4. Men fra mængden {m, m + 1, m + 2, m + 3} kan vi vælge en 3-element delmængde, der indeholder to lige og en ulige, hvor disse tre tal ikke er indbyrdes primiske, hvilket medfører at f(4) = 4.

Lad nu n = 5 og betragt mængden {m, m + 1, m + 2, m + 3, m + 4}.

Hvis m er lige, da er m, m + 2, m + 4 alle lige. Så alle 3 tal fra en 4-element delmængde {m, m + 1, m + 2, m + 4} er ikke indbyrdes primiske, så f(5) > 4.

Men fra en 5-element vilkårlig mængde kan vi finde 3 tal, der er indbyrdes primiske.

Så f(5) = 5.

Tilsvarende kan man vise, at f(6) = 6 ved at bruge samme idé.

Lad nu n > 6 og betragt mængden §_n := {q : q ≤ n + 1 og 2 | q eller 3 | q}.

Da er §_n en delmængde af {2, 3, ... , n + 1}, og alle 3-elementer i §_n er ikke indbyrdes primiske.

Dermed har vi, at

f(n) ≥ |§_n| +  1

= (n+1)/2 + (n+1)/3 - (n+1)/6 + 1

Uden tab af generalitet antager vi, at n = 6k + r, k≥1, r = 0, 1, ... , 5.

Da er

(n+1)/2 + (n+1)/3 - (n+1)/6 + 1 = 4k + (r+1)/2 + (r+1)/3 - (r+1)/6 + 1.

Det er klart, at

(r+1)/2 + (r+1)/3 - (r+1)/6 + 1 = r for r = 0,1,2,3 og r-1 for r= 4,5.

Hvis r = 0,1,2,3, kan vi dele n = 6k + r op i k grupper:

{m, m + 1, ... , m + 5} , {m + 6, m + 7 , ... , m + 11} , ... ,

{m + 6(k - 1), m + 6k - 5, ... , m + 6k - 1}, og tilbage med r tal

m + 6k, ... , m + 6k + r - 1.

Blandt 4k + r + 1 tal er der mindst 4k + 1 tal, der er indeholdt i de k grupper.

Der er mindst en gruppe, der indeholder 5 tal. Da f(6) = 5, må der være 3 tal, der er indbyrdes primiske.

Hvis r = 4, 5 kan vi tilsvarende vise, at der er 3 tal, der er indbyrdes primiske.

Summa summarum har vi

f(n) = (n+1)/2 + (n+1)/3 - (n+1)/6 + 1.