Opgave 557 ^[oOO]

Op het ogenblik dat Sjoerd $n$ evenwijdige lijnen tekent, heeft hij reeds

$$1 + 2 + \ldots + (n-1) = \frac{n(n-1)}{2}$$

lijnen op papier staan. Elk van de $n$ nieuwe lijnen kan elk van deze lijnen snijden, wat zorgt voor $n \cdot n(n-1)/2$ nieuwe snijpunten. De waarden van de functie $n^2(n-1)/2$ zijn voor $n = 1, \ldots, 10$ achtereenvolgend

$$0, 2, 9, 24, 50, 90, 147, 224, 324, 450.$$

De som van al deze getallen is $1320$.

Opgave 558 ^[oOO]

Een driehoek ligt vast door de keuze van drie verschillende hoekpunten. Hiervoor zijn

$$\binom{36}{3} = 7140$$

mogelijkheden. De enige situatie waarin een keuze van drie hoekpunten niet resulteert in een driehoek is als die drie punten op één lijn liggen, dus we moeten tellen voor hoeveel drietallen dit gebeurt.

Op elke horizontale lijn liggen $6$ punten, en op

$$\binom{6}{3} = 20$$

manieren kunnen we 3 punten op een lijn kiezen. Hetzelfde geldt voor de zes verticale lijnen, dus deze lijnen leveren $12 \cdot 20 = 240$ drietallen die op één lijn liggen. Het resteert nu de drietallen te tellen die op een zekere diagonaal liggen.

We beschouwen eerst de diagonalen die een hoek van $45^{\rm o}$ maken, zeg van linksboven naar rechtsonder. Er is 1 diagonaal van lengte $6$, en voor elke lengte van $$2 tot $5$ zijn er twee diagonalen. Dit levert in totaal

$$\binom{6}{3} + 2 \binom{5}{3} + 2 \binom{4}{3} + 2 \binom{3}{3} = 20 + 2 \cdot 10 + 2 \cdot 4 + 2 = 50$$

drietallen. De diagonalen van linksonder naar rechtsboven leveren een gelijk aantal drietallen, dus hier vinden we in totaal $100$ drietallen.

Nu resteren enkel de diagonalen die een andere helling hebben. Stel dat er twee punten zijn die slechts een vakje in hoogte verschillen. Dan moeten die twee punten wel precies $2$ vakjes in breedte verschillen, omdat er anders geen derde punt in het rooster past. Dit geeft lijnen met helling $\pm 1/2$, waarvan de drie punten die op 1 lijn liggen een rechthoek van $2 \times 4$ vakjes vastleggen. Omdat er precies $8$ van dat soort drietallen zijn, vinden we nu $2 \cdot 8 = 16$ drietallen die op 1 lijn liggen. Precies dezelfde redenering geeft dat er ook $16$ drietallen zijn als er twee punten zijn die precies $1$ vakje in de breedte verschilen. Dit zijn alle mogelijkheden; inderdaad, als alle punten minstens twee vakjes in de lengte en breedte verschillen, dan moeten ze wel op een diagonaal onder een hoek van $45^{\rm o}$ liggen om in het rooster te passen.

In totaal vinden we dus

$7140 - 240 - 100 - 32 = 6800 - 32 = 6768$  driehoeken.

Opgave 559 ^[ooO]

Omdat het vel A4 papier vier hoeken heeft en Merel het volledig wil bedekken met drie vierkanten, moet er wel een vierkant zijn dat twee hoeken bedekt. Om niet uit te steken moet dit vierkant dus wel volledig langs de korte zijde van het papier liggen, waarna een rechthoek van $9 \times 21$ centimeter overblijft om te bedekken met twee vierkanten. Deze vierkanten moeten opnieuw allebei een hoekpunt bedekken. Noem de lengte van de zijde van een van de vierkanten $x$ en van de andere $y$. Om de volledige zijde van lengte $21$ te bedekken moet gelden dat $x + y \geq 21$. Aan de andere kant zijn de korte zijdes van het vierkant volledig bedekt zodra $x, y \geq 9$. De totale oppervlakte van de twee vierkanten samen is $x^2 + y^2$. Merk nu op dat

$$2x^2 + 2y^2 = (x+y)^2 + (x-y)^2 \geq 21^2 + (x-y)^2 \geq 21^2.$$

We zien dat $x^2 + y^2 \geq 21^2/2$ met gelijkheid precies wanneer $x+y = 21$ en $x - y = 0$. We concluderen dat $x = y = 21/2$ de mimimale oppervlakte geeft, die dan gelijk is aan

$$21^2 + 21^2/2 = 3 \cdot 21^2 / 2 = 661\frac{1}{2}.$$

De oppervlakte van het overlappende deel is dan $661\frac{1}{2} - 21 \cdot 30 = 30\frac{1}{2}$.

Opgave 560 ^[ooO]

We bewijzen dat

$$(2^n-1)^2 < 4^n - (2n)^2 + 1 < (2^n)^2$$

voor alle $n \geq 7$. Omdat $(2^n)^2 = 4^n$, is tweede ongelijkheid altijd waar, dus we bewijzen de eerste door de haakjes uit te werken;

$$4^n - 2^{n+1} + 1 < 4^n - (2n)^2 + 1 \iff (2n)^2 < 2^{n+1} \iff n^2 < 2^{n-1}.$$

Merk nu op dat $7^2 = 49 < 64 = 2^6$, dus de ongelijkheid is waar voor $n = 7$. We bewijzen met inductie dat de ongelijkheid waar is voor alle $n \geq 7$. Inderdaad, als $n^2 < 2^{n-1}$, dan geldt

$$(n + 1)^2 = n^2 + 2n + 1 < 2n^2 < 2 \cdot 2^{n-1} = 2^n,$$

omdat $n^2 > 2n + 1$ voor $n \geq 3$, wat men kan inzien door dit te herschrijven tot $(n-1)^2 > 2$.

We concluderen dat voor $n \geq 7$, de uitdrukking $4^n - (2n)^2 + 1$ tussen de opeenvolgende kwadraten $(2^n-1)^2$ en $(2^n)^2$ in ligt, en dus zelf geen kwadraat kan zijn. Het resteert nu om te onderzoeken voor welke $n \in \{ 1, 2, 3, 4, 5, 6 \}$ de uitdrukking een kwadraat is. We berekenen achtereenvolgens de waarden $1, 1, 29, 193, 925, 3953$. Hiervan zijn de eerste twee waarden inderdaad kwadraten en $29$ is duidelijk priem en dus geen kwadraat. De waarde $925$ is gemakkelijk te ontbinden als $25 \cdot 37$ en is dus geen kwadraat. Ten slotte kunnen $193$ en $3953$ geen kwadraten zijn omdat een kwadraat nooit op het cijfer $3$ kan eindigen. Conclusie: $n = 0$ en $n = 1$ zijn de enige mogelijkheden.