KOMBINATORIK Opgave 1 Let n be a natural number and let S be a subset of {1, 2, ..., n} such that no pair of elements of S are relatively prime and no element in S is divisible by another element of S. Find the maximal number of S (as a function of n). _Besvarelse._ Enhver delmængde S, der opfylder kravene, må bestå af et antal elementer, da der altid kan være minimum et element, og for n = 1 er størrelsen af S 1. Herefter arbejder vi med n ≥ 2. Hvert element i S må nødvendigvis have en største ulige divisor der er mindre eller lig n. 2 elementer i S kan ikke have samme største ulige divisor, da der i så fald kun er en faktor af en 2’er potens til forskel mellem de 2 elementer, hvormed det ene af de to elementer må dele det andet af de to elementer. Dermed må antallet af elementer i S være mindre eller lig antallet af ulige tal mindre end n, dvs. det maksimalt mulige antal elementer i S er reduceret til $\lceil {2} \rceil$. Det vises nu at det kan lade sig gøre at udvælge en delmængde S på $\lfloor {4} \rfloor$ elementer, der opfylder de ønskede krav. Der udvælges nu alle ulige tal mindre eller lig ${2}$. Dem er der netop $\lfloor {4} \rfloor$ af: - Hvis $n\equiv 0 \ $ da er ${2}$ et lige tal, og da er der ${4}$ ulige tal mindre end eller lig ${2}$, og $\lfloor {4} \rfloor = {4} + \lfloor {4} \rfloor = {4}$ - Hvis $n\equiv 1 \ $ da er ${2}$ ikke et heltal, og da er ${2}$ et lige tal, og da er der ${4}$ ulige tal mindre end eller lig ${2}$, og $\lfloor {4} \rfloor = {4} + \lfloor {4} \rfloor = {4}$ - Hvis $n\equiv 2 \ $ da er ${2}$ et ulige tal, og da er der ${4}$ ulige tal mindre end eller lig ${2}$, og $\lfloor {4} \rfloor = {4} + \lfloor {4} \rfloor = {4}$ - Hvis $n\equiv 3 \ $ da er ${2}$ ikke et heltal, og da er ${2}$ et ulige tal, hvormed der ${4}$ ulige tal mindre end eller lig ${2}$, og $\lfloor {4} \rfloor = {4} + \lfloor {4} \rfloor = {4}$ Der gælder for en ulige faktor x, hvor $1\leq x \leq {2}$, at der kan ganges med en 2’er potens 2k, hvor k ∈ ℕ, så ${2}< 2^k x \le n $. Dette indses relativt nemt, idet: $1\leq x \leq {2}$, hvormed 2 ≤ 2x ≤ n. Hvis $2x>;{2}$ er vi færdige, ellers er $2\le 2x\le {2}$, hvormed vi igen kan gange igennem med 2. Dette gøres k gange, hvormed vi har et tal ${2}< 2^k x \le n $. Dette gøres for alle de $\lfloor {4} \rfloor$ ulige tal mindre end eller lig med ${2}$, og disse tal bliver netop elementerne i S. Det ses at disse $\lfloor {4} \rfloor$ tal netop opfylder kraverne: da de alle er lige er ingen par indbyrdes primiske, og da de alle har en forskellig største ulige divisor, kan ingen af tallene være ens, samt intet tal kan dele et andet, da der mellem det mindste og største tal er mindre end en faktor 2. Nu argumenteres der for at dette er den størst mulige mængde: Vælges en ulige divisor større end ${2}$ ses at ganges en 2’erpotens på denne eller et hvilket som helst heltal større end 1, er det resulterende tal nødvendigvis større end n og kan dermed ikke være del af S. Dermed skal en sådan ulige faktor, hvis den indgår i et element i S, indgå som tallet selv. Det ses for et ulige tal at: gcd(y, y ± 2)=gcd(y, 2)=1 og gcd(y, y ± 4)=gcd(y, 4)=1 Dvs. inddrages et ulige tal i mængden S udelukkes der minimum 2 andre ulige tal, som heller ikke kan indgå som den største ulige divisor i et tal, da de er indbyrdes primiske. Hvis der ikke er flere end 2 ulige tal mindre end eller lig n, så er der kun 1 og 3, og 1 kan ikke indgå sammen med nogle andre elementer i S, da 1 deler alle tal. I tilfælde af overlap mellem de to nye ulige tal der udelukkes, da er antallet af nye ulige tal der kan inddrages stadigvæk ikke flere end dem der udelukkes, og dermed er det umuligt at gøre mængden større. Dermed er det maksimale antal elementer i S er $\lfloor {4} \rfloor$, undtagen i tilfældet n = 1 hvor det maksimale antal elementer er 1. Opgave 2 A stack of boxes is stable if no box has a heavier box on top of it. If the stack above a box is stable, we can move that box to the top of the entire stack. This is called a move. We start with a stable stack which for every positive integer k ≤ n contains k boxes weighing k each, and place a box weighing n + 1 to the top of the stack. How many moves do we need to make in order to make the entire stack stable? _Besvarelse._ Lad an betegne antallet af træk det kræver at gøre hele stakken stabil for n = 1. For et givet n ≥ 2 betragter vi nu stakken. For at kunne foretage et træk med en af boksene med vægt n, skal hele stakken ovenfor være stabil, dvs. at alle bokse med vægt mindre end n skal flyttes oven over boksen med vægt n + 1, for ellers er der en boks med mindre vægt end n + 1 mellem boksene med vægt n og boksen ovenfor med vægt n + 1, og derfor kan der ikke udføres et træk med en boks med vægt n, da stakken ovenfor ikke er stabil. At flytte alle boksene med vægt mindre end n over boksen med vægt n + 1 så stakken fra boksen med vægt n + 1 og opefter er stabil, må netop kræve an − 1 antal træk, da det svarer til situationen for n − 1. Herefter er stakken ovenfor de n bokse med vægt n stabil. Dermed kan en af boksene med vægten n flyttes til toppen, hvorefter alle bokse med vægt mindre end n skal flyttes ovenfor boksen med vægt n på toppen, før der kan udføres et træk med den næste boks med vægt n. Dette skal gøres yderligere n − 1 gange, hvormed hele stakken er stabil. Dvs. at antallet af træk der kræves for at gøre hele stakken stabil må da være: $$a_n=a_{n-1}+n(a_{n-1}+1)=(n+1)\cdot a_{n-1}+n$$ Det ses at a₁ = 1. Det vises nu at an = (n + 1)! − 1 med induktion. Induktionsstarten: For n = 1 ses ganske rigtigt at: $$(n+1)!-1=2-1=1=a_1$$ Induktionsantagelsen: Det antages at an = (n + 1)! − 1. Induktionsskridtet: Det ses nu for n + 1 at: $$a_{n+1}=(n+2)\cdot a_n + n+1=(n+2)((n+1)!-1)+n+1=(n+2)!-n-2+n+1=(n+2)!-1$$ hvilket netop er det ønskede. Dermed er antallet af træk det kræver for at gøre hele stakken stabil an = n!−1. Opgave 3 Let n be a positive integer. Find the smallest integer k with the following property: Given any real numbers a₁, a₂, ..., ad such that a₁ + a₂ + ⋯ + ad = n and 0 ≤ ai ≤ 1 for i = 1, 2, ..., d, it is possible to partition these numbers into k groups (some of which may be empty) such that the sum of the numbers in each group is at most 1. (IMO shortlist 2013) _Besvarelse._ For et givet n og de reelle tal a₁, a₂, ..., ad, da må der gælde at for en fordeling ud i k grupper, at hvis der eksisterer to grupper, for hvilke summen af elementerne fra begge grupper er mindre end eller lig 1, da kan én gruppe indeholde alle elementerne fra begge grupper, og dermed er k ikke det mindste heltal med den beskrevne egenskab. For det mindst mulige k, vil det sige at summen af elementerne fra to vilkårlige grupper må være større end 1. Hvis man for alle mulige parringer af to grupper lægger elementerne sammen, får man ${k\choose 2}$ summer der alle skal være større end 1, idet der netop er ${k\choose 2}$ mulige parringer, og lægges alle disse summer sammen fås: $$(k-1)\cdot(a_1+a_2+ \cdots+a_d)$$ da hver gruppe tælles med netop (k-1) gange, da hver gruppe parres til alle de (k-1) andre grupper, og da alle tal a₁, a₂, ..., ad netop optræder i én gruppe, må alle elementer tælles med netop (k-1) gange. Da denne sum netop er ${k\choose 2}$ summer der alle skal være større end 1, og a₁ + a₂ + ⋯ + ad = n, da fås at for det mindste k må der gælde at: $$(k-1)\dot n=(k-1)\cdot(a_1+a_2+ \cdots+a_d)>{k\choose 2}\cdot 1={2}$$ og dermed fås at der skal gælde: $$2n>k$$ For et givet n, da ses at der for d = 2n − 1, findes elementer $a_1=a_2=\cdots=a_{2n-1}={2n-1}>{2}$, hvormed det ses at der ikke kan være 2 elementer i en gruppe. Dermed har vi at k ≥ 2n − 1. Dermed fås for det mindst mulige k at: $$2n>k\ge 2n-1$$ og dette medfører at det mindst mulige k, der opfylder betingelserne er k = 2n − 1, da k er et heltal.