Nötter (1 poäng).
I tre högar finns 22, 14 respektive 12 nötter. Du får göra tre förflyttningar, så att högarna får lika många nötter. Under en förflyttning får du flytta ett antal nötter från en hög till en annan, men antalet nötter man flyttar måste vara lika med antalet nötter i högen man flyttar till. Vilka förflyttningar ska du göra?
Äpplen (3 poäng). Några lådor innehåller sammanlagt 2000 äpplen. Du får antingen ta bort lådor eller ta bort äpplen från lådor. Visa att du kan med hjälp av sådana operationer få kvar lådor med samma antal äpplen i varje, så att det sammanlagt finns minst 100 äpplen kvar.
Visa lösningar
Nötter (Axels lösning):
Start:
22 14 12
flyttar från 22 till 14
8 28 12
flyttar från 28 till 12
8 16 24
flyttar från 24 till 8
16 16 16
Äpplen (Skäggets lösning):
Låt oss försöka hitta ett motexempel, alltså någon fördelning av äpplen i lådor så att det inte går.
Ifall vi har hundra lådor som inte är tomma, då tar vi bort alla andra lådor och sedan alla äpplen utom 1 i varje av dessa lådor. Då får vi 100 lådor med 1 äpple i varje och är klara.
Om någon låda har 100 eller fler äpplen, då tar vi bort alla andra lådor, och alla äpplen i denna låda utöver 100, och är då klara.
Ett eventuellt motexempel måste alltså vara en fördelning där ingen av fallen ovan inträffar. Antag att vi har en sådan fördelning. Betrakta då den låda som innehåller flest äpplen (eller en av dem, ifall det är fler). Den innehåller färre än 100 stycken, ty annars har vi ett av fallen ovan. Den låda som innehåller näst mest måste innehålla färre än 50 äpplen, ty annars har vi två lådor som båda har minst 50 äpplen, och då kan vi ta bort alla andra lådor och sedan ta bort tillräckligt många äpplen i den låda som har flest äpplen för att lådorna ska vara lika, och då är vi klara.
På samma sätt, den låda som innehåller tredje mest måste ha mindre än en tredjedel av 100 stycken äpplen, eftersom annars har vi tre lådor med minst 100/3 äpplen var. I allmänhet måste den n:te lådan i ordningen (sorterat efter antalet äpplen) innehålla mindre än 100/n äpplen (avrundat nedåt till närmaste heltal).
Efter 49 lådor måste vi alltså ha högst 1 äpple i varje kvarvarande låda, annars har vi 50 lådor med minst 2 äpple i varje.
Låt oss nu vara generösa och säga att de första 10 lådorna alla innehåller högst 100 äpplen snarare än 99, 40, 32, 24, …, 10. Låt sedan de nästa 40 lådorna vara uppåt begränsade av 10. Då har vi i de första 50 lådorna högst 10*100 + 40*10 = 1400 äpplen (egentligen väldigt mycket färre). Bland de kvarvarande lådorna, som alla innehåller ett äpple var ska vi ha sammanlagt 600 äpplen. Alltså har vi 600 lådor med ett äpple var, och således även 100 lådor med ett äpple var, och för det fallet har vi redan konstaterat att det finns en lösning.
Alltså, om vi försöker fördela våra äpplen på ett sådant sätt att inga n lådor innehåller 100/n äpplen vardera, då kommer vi garanterat ha 100 lådor som har minst 1 äpple var, och därför kan vi vara säkra på att vi har något av dessa fall, och för båda fallen kan vi uppnå önskat resultat med våra givna operationer, så inga motexempel finns.
Relaterade
