Opgave 457

Omdat er $5$ pizza's zijn voor $6$ aanwezigen, krijgt iedereen $5/6$ pizza. Iedere pizza moet dus minstens een keer doorsneden worden, aangezien anders iemand een hele pizza zou krijgen en dat is meer dan $5/6$. We kunnen dus net zo goed iedere pizza alvast een keer doorsnijden. Aangezien we de pizza's alleen over een rechte lijn door de oorsprong door mogen snijden, wordt iedere pizza precies in twee gelijke stukken gesneden van $1/2$ pizza. We hebben nu $10$ stukken van $1/2$ pizza. Niemand krijgt twee stukken van $1/2$ pizza, omdat deze persoon dan minstens $1/2 + 1/2 = 1$ pizza zou krijgen, meer dan $5/6$. Dus we moeten tenminste $4$ van deze halve pizza's nog een keer doorsnijden, en daarvoor moeten we nog minstens twee keer snijden. In totaal moeten we dus minstens $7$ keer snijden.

Met $7$ keer snijden lukt het ook: we snijden alle pizza's een keer doormidden, en dan twee pizza's nog een keer om ze te verdelen in twee stukken van $2/3$ en twee van $1/3$. Nu krijgen vier mensen een stuk van $1/2$ en een van $1/3$, en twee mensen een stuk van $1/2$ en twee van $1/6$. Zo krijgt iedereen $5/6$ pizza. 

Opgave 458

Noteer $[XYZ]$ voor de oppervlakte van driehoek $XYZ$, en analoog $[WXYZ]$ voor vierhoek $WXYZ$. We noemen het hoekpunt linksonder $A$ en de rest tegen de klok in $B, C, D$. Noem $E$ het snijpunt van lijnstuk $AB$ met de ingetekende lijnen, en $F$ het snijpunt op lijnstuk $AD$. Verder noemen we $x$ de oppervlakte van het gebied met het vraagteken, en $y$ de oppervlakte van de witte vierhoek in het midden van het figuur. De oppervlakte $[BCF]$ is uit te rekenen met $\tfrac{1}{2} \cdot {\rm zijde} \cdot {\rm hoogte}$ en dit is gelijk aan $\tfrac{1}{2}|BC||CD|$, oftewel de helft van $[ABCD]$. Op dezelfde manier is $[CDE] = \tfrac{1}{2}[ABCD]$. We hebben dus $[BCF] = [CDE]$. Door driehoek $BCF$ te splitsen krijgen we $[BCF] = 49 + x + y$ en met driehoek $CDE$ krijgen we $[CDE] = 53 + y + 9$. We hebben nu dus

$$49 + x + y = 53 + y + 9$$

en zo vinden we $x = 13$. 

Opgave 459

Het antwoord is: je kan in $7$ keer weten wat de drie zwaarste gewichtjes zijn. Een strategie hiervoor is als volgt. We delen de $25$ gewichtjes op in $5$ groepjes van $5$. Schrijf op alle gewichtjes van een groep de letter $A$, op een groep $B$, op een $C$, op een $D$ en op een $E$. We plaatsen steeds een van deze groepjes in de machine. Voor het gemak schrijven we '$1$' op de zwaarste, '$2$' op de volgende, en zo door tot '$5$' op de lichtste. Nadat we alle $5$ groepjes gehad hebben, nemen we de $5$ gewichtjes met '$1$' erop. Stel zonder verlies van algemeenheid dat gewicht $A1$ de zwaarste is, gevolgd door $B1, C1, D1$ en $E1$ als lichtste. Nu hebben we dus het volgende diagram, waarbij '$>$' betekent dat een gewicht zwaarder is.

$A1$	$\gt$	$B1$	$\gt$	$C1$	$\gt$	$D1$	$\gt$	$E1$
$\vee$		$\vee$		$\vee$		$\vee$		$\vee$
$A2$		$B2$		$C2$		$D2$		$E2$
$\vee$		$\vee$		$\vee$		$\vee$		$\vee$
$A3$		$B3$		$C3$		$D3$		$E3$
$\vee$		$\vee$		$\vee$		$\vee$		$\vee$
$A4$		$B4$		$C4$		$D4$		$E4$
$\vee$		$\vee$		$\vee$		$\vee$		$\vee$
$A5$		$B5$		$C5$		$D5$		$E5$

In de bovenste rij staat het resultaat van de laatste weging, en iedere kolom is een groep die we gewogen hebben. We weten nu bijvoorbeeld ook dat $B1$ zwaarder is dan $C2$. Merk op dat we niet weten of bijvoorbeeld $A2$ groter is dan $B2$.

We weten nu dat $A1$ het zwaarste gewicht is, dus het heeft niet echt zin meer om die mee te wegen. Ook weten we dat ieder gewicht waarvoor er drie zwaardere gewichten te vinden zijn niet in de top $3$ zwaarste gewichten zit. Er blijven dan nog $5$ gewichtjes over die mogelijk nummer $2$ of $3$ kunnen zijn, namelijk $B1, C1, A2, B2$ en $A3$. Als zevende stoppen we deze $7$ gewichtjes in de machine, en dan zijn de twee zwaarste gewichtjes die eruit komen nummer $2$ en $3$.

Bewijzen dat het niet nog beter kan is lastig, en wel om de volgende reden. Als we heel veel geluk hebben kunnen we ook in zes keer de drie zwaarste gewichtjes vinden. Of: als we van tevoren weten (of vermoeden) wat de drie zwaarste gewichtjes zijn, kunnen we met $6$ keer wegen dat bewijzen. Als voorbeeld: stel dat op de drie zwaarste gewichtjes $1, 2, 3$ staat en op de resterende $22$ $x$, dan kunnen we deze zes wegingen doen: 

$1$	>	$3$	=	$3$	=	$3$	=	$3$	=	$3$
$\vee$		$\vee$		$\vee$		$\vee$		$\vee$		$\vee$
$2$		$x$		$x$		$x$		$x$		$x$
$\vee$		$\vee$		$\vee$		$\vee$		$\vee$		$\vee$
$3$		$x$		$x$		$x$		$x$		$x$
$\vee$		$\vee$		$\vee$		$\vee$		$\vee$		$\vee$
$x$		$x$		$x$		$x$		$x$		$x$
$\vee$		$\vee$		$\vee$		$\vee$		$\vee$		$\vee$
$x$		$x$		$x$		$x$		$x$		$x$

en dit bewijst dat de $3$ gewichtjes $1,2,3$ inderdaad de $3$ zwaarste zijn. Merk op dat we technisch gezien niet eens de volgorde van $1,2,3$ hoeven te weten (alhoewel we dat in dit geval wel weten), er wordt alleen gevraagd om de drie zwaarste. Een algemene strategie waarmee het sowieso lukt kan echter niet in minder dan $7$ keer wegen. Dit gaan we bewijzen.

Stel dat we een strategie hebben die in $6$ keer altijd werkt. Dat betekent dan dat we ongeacht het resultaat van de zesde weging altijd weten wat de top $3$ is. We kijken naar de stand van zaken na afloop van de vijfde weging, en bewijzen dat dit niet mogelijk is.

Als we na afloop van de vijfde weging $22$ of minder gewichten gewogen hebben, dan zijn er tenminste $3$ gewichten die we nog niet gewogen hebben. Neem drie zulke gewichten $x, y, z$. In het gunstigste geval weten we nu ook precies wat de drie zwaarste gewichten zijn van de al wel gewogen gewichten. Stel dat dit $A > B > C$ zijn.

Stel dat we op de zesde weging de verzameling $Z$ van vijf gewichten wegen. Sowieso moeten $x, y, z$ erin zitten, want anders kunnen we nooit weten of deze in de top 3 zitten. Verder zitten maximaal 2 van $A, B, C$ erin: andere gewichten zijn sowieso geen top 3 en kunnen we dus zonder problemen niet kiezen.

• Stel dat we $A$ niet kiezen, en dat we dan als volgorde $x, y, z, B, C$ krijgen. Dan weten we niet of de top 3 zwaarste gewichten $x, y, z$ of $A, x, y$ is. 
• Stel dat we $B$ niet kiezen, en dat we dan als volgorde $A, x, y, z, C$ krijgen. Dan weten we dus niet of de top 3 zwaarste gewichten $A, x, B$ of $A, x, y$ is. 
• Stel dat we $C$ niet kiezen, en dat we dan als volgorde $A, B, x, y, z$ krijgen. Dan weten we dus niet of de top 3 zwaarste gewichten $A, B, C$ of $A, B, x$ is. 

In alle gevallen kunnen we niet weten wat de top 3 is, dus we kunnen niet altijd na $6$ keer wegen uitsluitsel geven, zelfs niet in het meest gunstige geval dat we $A, B, C$ weten.

Als we na de vijfde weging $23$ gewichten minstens een keer hebben gewogen (noem de twee overige gewichten $x$ en $y$), dan is wegens het laatjesprincipe een van de vijf groepjes die we hebben gewogen volledig verschillend (disjunct) van alle andere groepjes. Stel zonder verlies van algemeenheid dat dit groepje $A$ is. We gaan nu kijken welke elementen sowieso in het zesde groepje $Z$ moeten zitten dat we gaan wegen: 

• Van $x, y$ kunnen we nooit weten of ze in de top 3 zitten als we ze niet mee wegen, dus $x, y \in Z$. 
• Stel dat $A1$ niet in $Z$ zit. Dan kunnen we nooit weten of hij in de top 3 zit of niet, omdat we dan van geen enkel element weten dat het groter is dan $A1$ en ook niet voldoende elementen hebben kleiner dan $A1$. Dus moet $A1$ in $Z$ zitten. 
• Stel dat $A2$ niet in $Z$ zit en dat we als top 3 uit onze weging $A1, x, y$ krijgen. Dan is het mogelijk dat $A1, x, y$ de top 3 is, maar ook $A1, A2, x$. Om in dit geval uitsluitsel te bieden moet $A2$ dus ook in $Z$ zitten. 
• Stel dat $A3$ niet in $Z$ zit en dat we uit de weging $A1, A2, x$ krijgen. Dan kan de top 3 $A1, A2, x$ maar ook $A1, A2, A3$ zijn. Dus $A3$ moet ook in $Z$ zitten. 

We hebben nu dus dat $x, y, A1, A2, A3$ allemaal in $Z$ zitten, en aangezien $Z$ maar $5$ gewichten mag bevatten is dit zelfs $Z$. Dat betekent dus dat $B1$ nooit de zwaarste kan zijn, we moeten dus weten dat deze kleiner is dan $A1$ en $B1$ moet dus in $A$ zitten. Hetzelfde geldt voor $C1, D1, E1$. Maar dan hebben we maximaal 21 verschillende gewichten gewogen, tegenspraak.

Stel nu dat we na de vijfde weging $24$ gewichten minstens een keer hebben gewogen. Dan zijn er minstens $3$ groepjes die volledig verschillend (disjunct) zijn van alle andere groepjes gewichten. Stel zonder verlies van algemeenheid $A, B, C$. Dan moet met dezelfde redenering als net $A1, A2, A3, B1, B2, B3, C1, C2, C3$ allemaal in $Z$ zitten, terwijl deze maar $5$ elementen mag hebben: tegenspraak.

Als we na afloop van de vijfde weging alle $25$ gewichten minstens een keer hebben gewogen, hebben we ze allemaal exact een keer gewogen. Nu zijn alle groepjes dus disjunct en hebben we dat $A1, A2, A3, \ldots, E1, E2, E3$ allemaal in $Z$ moeten zitten, in totaal $15$ elementen, maar er mogen er maar $5$ inzitten: tegenspraak. 

Opgave 460

We noemen de straal van de grootste cirkel $r$, van de middelste cirkel $s$ en van de kleinste cirkel $t$.

Noem $C$ het hoekpunt van de driehoek met een rechte hoek, en de andere twee hoekpunten $A$ en $B$. Noem $D$ het punt waar de grootste cirkel lijnstuk $AB$ raakt. Merk op dat omdat driehoek $ABC$ gelijkbenig is geldt dat $D$ het midden van $AB$ is. Hieruit volgt ook dat $D$ het voetpunt van de hoogtelijn uit $C$ is. Noem $M$ het middelpunt van de grootste cirkel, dan ligt $M$ op $CD$ (als we spiegelen in lijn $CD$ verandert $\triangle ABC$ namelijk niet, dus $M$ ook niet, dus $M$ moet wel op $CD$ liggen).

De oppervlakte van $\triangle ABC$ is gelijk aan $\tfrac{1}{2}|AC||BC|$ maar ook aan $\tfrac{1}{2}|AB||CD|$, waaruit volgt dat

$$|CD| = \frac{|AC||BC|}{|AB|} = \frac{1}{\sqrt{2}}$$

Als we kijken naar de grootste cirkel is $|CD|$ gelijk aan $CM + MD = (1 + \sqrt{2})r$, waaruit volgt dat 

$$r = \frac{|CD|}{1 + \sqrt{2}} = \frac{1}{2 + \sqrt{2}} = \frac{2 - \sqrt{2}}{(2 + \sqrt{2})(2 - \sqrt{2})} = \frac{1}{2}(2 - \sqrt{2})$$

We kijken nu naar de middelste cirkel, met straal $s$. We kunnen $CM$ op twee manieren uitrekenen: we hadden al bedacht dat het gelijk is aan $r\sqrt{2}$, maar het is ook gelijk aan $r + (1 + \sqrt{2})s$. Hieruit volgt dat

$$r\sqrt{2} = r + (1 + \sqrt{2})s$$

oftewel 

$$\frac{s}{r} = \frac{\sqrt{2} - 1}{\sqrt{2} + 1} = \frac{(\sqrt{2} - 1)(\sqrt{2} - 1)}{(\sqrt{2} + 1)(\sqrt{2} - 1)} = 3 - 2\sqrt{2}$$

Op dezelfde manier kunnen we bewijzen dat

$$\frac{t}{s} = \frac{s}{r} = 3 - 2\sqrt{2}$$

We hebben nu dus
$$\begin{align*}
    t & = \frac{t}{s} \cdot \frac{s}{r} \cdot r \\
    & = (3 - 2\sqrt{2})^2 \cdot \frac{1}{2}(2 + \sqrt{2}) \\
    & = \frac{1}{2}(17 - 12\sqrt{2})(2 - \sqrt{2}) \\
    & = \frac{1}{2}(58 - 41\sqrt{2})
\end{align*}$$

als straal van de kleinste cirkel.