Kalender 2000

Antwoorden week 34 (21 t/m 27 augustus)

Weegpuzzels.

Maandag 21 augustus:

Bepaal van twee objecten het lichtste. In de volgende wegingen wordt steeds het lichtste object dat tot dan toe gevonden is, vergeleken met een nog niet gewogen object. Herhaal dit tot alle objecten gewogen zijn. Het lichtste object bij de (N-1)ste weging is het lichtst van alle N.

Dinsdag 22 augustus:

Aan het begin zijn er N objecten waarvan geen enkel tweetal vergeleken is. Na 1 weging zijn er als het ware N-1 groepen die onderling "onvergeleken" zijn. Na 2 wegingen zijn er N-2 groepen, na k wegingen zijn er N-k groepen. Zolang er meer dan 1 groep is, kan er geen harde uitspraak over het lichtste object worden gedaan. Met minder dan N-1 wegingen kan het dus niet.

Woensdag 23 augustus:

Je kunt de objecten paarsgewijs vergelijken en van ieder paar het lichtste object onthouden. Met die N/2 (of (N+1)/2) lichtste objecten ga je dan op de een of andere manier verder.

Donderdag 24 augustus:

Bepaal in N-1 wegingen het lichtste object, en dan in N-2 wegingen het zwaarste van de overige N-1 objecten.

Vrijdag 25 augustus:

Noem de objecten A, B, C, D. Weeg eerst A en B. Stel, zonder beperking, dat A lichter is, korter opgeschreven: A<B. Weeg dan C en D en neem aan dat C<D. Weeg vervolgens A en C. De lichtste van deze 2 is de lichtste van het hele stel. En de zwaarste van B en D is de zwaarste van de vier objecten.

Zaterdag 26 augustus:

Neem eerst even aan dat N even is. Stel dat je van 2k objecten het lichtste (L) en het zewaarste (Z) kent. Pak nu 2 nog niet gewogen objecten X en Y, en bepaal het lichtste. Stel X<Y. Dan zijn de lichtste van L en X en de zwaarste van Z en Y de nieuwe "recordhouders". Met 3 extra wegingen hebben we weer 2 objecten verwerkt. Omdat we voor 4 objecten in 4 wegingen klaar zijn (zie vrijdag), kunnen we van N objecten het lichtste en het zwaarste bepalen in 3N/2 - 2 wegingen, als N even is. Als N oneven is, sorteren we eerst 3 objecten in 3 wegingen, en de overige N-3 behandelen we op de manier die hierboven is beschreven. Het aantal wegingen wordt dan (3N-3)/2. Deze aantallen kloppen met de formule in de opgave.

Zondag 27 augustus:

Bepaal eerst het lichtste object (L) op de manier waarop in een tennistoernooi de winnaar wordt bepaald. Bepaal vervolgens van de objecten die rechtstreeks met L zijn vergeleken, het lichtste. Dat moet het op één na lichtste zijn. Bij N objecten zijn op deze manier minder dan N + log2N wegingen voldoende.