Tips til kule-problemet

Animasjoner - hva, hvorfor og hvordan? | Animasjoner og matematikk | Leke og oppdage | Tips til kule-problemet

 

Animasjon til kule-problemet

Animasjonen er tenkt å kunne brukes til konkretisering av det klassiske kule-problemet. Den skal kunne brukes til ulike varianter av problemstillingen. Det er lagt inn valgt for antall kuler, og om problemet er stilt med eller uten vektinformasjon om den spesielle kulen. Vi kan benytte oss av muligheten til å knytte merkelapper til hver kule med informasjon om den aktuelle kulens vekt etter hvert som vi finner det ut gjennom veiing og resonnering. Vis større.

Innhold av denne siden: Problemformuleringer . Kule-problemet - uten vektinformasjon . Kule-problemet - med vektinformasjon . Det generelle n-kule-problemet . Tips til det klassiske 12-kule-problemet

Problemformuleringer

Kule-problemet dukker opp som en hjernegymnastikk eller matematisk nøtt med jevne mellomrom og i ulike fora. Det finnes flere varianter av problemstillingen. Felles er:

En har en skålvekt og et gitt antall kuler.
Alle kulene er like store og ser like ut.
Alle bortsett fra 1 kule har samme vekt.

Med vekten kan vi utføre veiinger. Med en veiing menes at vi legger et utvalg kuler på venstre skål og et utvalg kuler på høyre skål slik at vi kan se om skålene er i likevekt eller om utvalget på den enkelte siden er lettest eller tyngst.

En veiing med skålvekt kan ha tre ulike utfall:

  1. Kulene på venstre siden er lettest.
  2. Kulene på venstre siden er tyngst.
  3. Kulene på hver side av vekten har samme vekt.
a.
b.
c.

Problemstillingen kan variere noe i de ulike nøttene. Til min animasjon har jeg valgt en åpen formulering:

Med færrest mulig veiinger skal vi finne kulen med avvikende vekt
og skal kunne si om den er lettere eller tyngre.

I animasjonen kan vi også velge mellom tre typer oppgaver avhengig av hvilken informasjon som er gitt:

En annen mulighet er å stille oppgaven veldig konkret. "Med færrest mulig veiinger skal vi finne kulen med avvikende vekt..." erstattes da med "Finn kulen med avvikende vekt med maskimalt x veiinger...". Eksempelvis:

Legg merke til at kule-problemene a) - c) er av typen ”uten vektinformasjon”, mens kule-problemet d) er av typen ”med vektinformasjon”. Det kan være lurt å først konsentrere se om én type problemstilling, enten uten vektinformasjon (**) eller med vektinformasjon (***), før en skifter over til den andre.

Alle disse problemstillingene er utfordrende og krever at en finner en systematisk måte å veie på.

Interessante diskusjoner

Store utfordringer

Kule-problemet - uten vektinformasjon

I kule-problemet uten vektinformasjon går vi ut fra at en kule har en annen vekt, men vi vet ikke om den er lettere eller tyngre enn de andre.

Det klassiske ”12-kuler-problemet”

Gitt er følgende:

Du har en skålvekt og 12 kuler. Den ene kulen har en annen vekt, men du vet ikke om den er lettere eller tyngre enn de andre.

Utfordringen:

Finn denne spesielle kulen og vektinformasjon, dvs. om den er tyngre eller lettere enn de andre, ved å veie 3 ganger. - Hvordan går du fram?

Til oppvarming er det lurt å løse ”3-kuler-problemet”: Du har en skålvekt og 3 kuler. Den ene kulen er lettere eller tyngre enn de 2 andre. Finn denne spesielle kulen ved å veie 2 ganger. - Hvordan går du fram?

Hjelp: Du bør ha prøvd selv en stund, før du henter tips fra "skjematisk forslag på løsning".

 

Kule-problemet - med vektinformasjon

I kule-problemet med vektinformasjon er det gitt at den spesielle kulen er lettere eller at den spesielle kulen er tyngre enn de andre kulene som har samme vekt.
a) En kule er lettere enn de andre
b) En kule er tyngre enn de andre.

”9-kuler-problemet”

Gitt er følgende:

Du har en skålvekt og 9 kuler. Den ene kulen er lettere (eller tyngre) enn de andre.

Utfordringen:

Finn denne spesielle kulen som er lettere ved å veie 2 ganger. - Hvordan går du fram?

Til oppvarming er det lurt å løse 3-kuler-problemet: Du har en skålvekt og 3 kuler. Den ene kulen er lettere (eller tyngre) enn de andre. Finn den spesielle kulen som er lettere (tyngre) ved å veie 1 gang.

Klar til større utfordring? Da anbefaler vi "27-kuler-problemet": Du har en skålvekt og 27 kuler. Den ene kulen er lettere (eller tyngre) enn de andre. Finn denne spesielle kulen som er lettere (tyngre) ved å veie 3 ganger. - Hvordan går du fram?

 

Det generelle n-kuler-problemet

Finner du et mønster? Problemet kan formuleres slik:

Finn maksimalt antall kuler n der følgende gjelder:
Den ene har en annen vekt.
Med v (>=2) veiinger kan vi finne den spesielle kulen
og kan entydig bestemme om den er lettere eller tyngre enn de andre.

Det er en meget krevende oppgave!

Det generelle n-kuler-problemet uten vektinformasjon Det generelle n-kuler-problemet med vektinformasjon

Hvis vi skal finne den spesielle kulen og om den er lettere eller tyngre, gjelder:

Hvis det allerede er gitt at den spesielle kulen er tyngre eller lettere, gjelder:


n - maks. antall kuler
v - antall veiinger


n - maks. antall kuler
v - antall veiinger
2 kuler
:
 meningsløst
3 kuler
:
 2 veiinger
4-12 kuler
:
 3 veiinger
13-39 kuler
:
 4 veiinger
40-120 kuler
:
 5 veiinger
osv.
 
 
v
n
antall
veiinger
maks
antall kuler
1
0
2
3
3
12
4
39
5
120
6
363
7
1092
8
3279
9
9840
10
29523
...
...
(2-) 3 kuler
:
 1 veiing
4-9 kuler
:
 2 veiinger
10-27 kuler
:
 3 veiinger
28-81 kuler
:
 4 veiinger
82-243 kuler
:
 5 veiinger
osv.
v
n
antall
veiinger
maks
antall kuler
1
3
2
9
3
27
4
81
5
243
6
729
7
2187
8
6561
9
19683
10
59049
...
...

Med v=2 kan vi finne den spesielle kulen blant 3 kuler. Vi veier først to kuler mot hverandre (1.veiing). Dersom kulene balanserer, har den tredje kulen en vekt som avviker. Om den er tyngre eller lettere, finner vi ut ved å veie den mot en av de to normale kulene. – Dersom de to kulene ikke balanserer, veier vi den letteste mot den tredje kulen som må være normal. Er den letteste også lettere enn den normale kulen, har vi funnet den spesielle kulen, og den er lettere. Balanserer den derimot med den normale kulen, er kulen som viste seg å være tyngre i 1. veiing den spesielle kulen, og den er tyngre.

Med v=3 kan vi finne den spesielle kulen blant 4 til 12 kuler. Det er tilstrekkelig at vi viser at dette stemmer for 12 kuler. Vi deler kulene i 3 hauger, der de to første har 4 kuler, og veier de to første haugene. Enten balanserer vekten (1) eller så tipper den (2).

(1) Dersom de balanserer, veier de alle likt og er normale, og den spesielle kulen er i den gjenværende haugen. Ved å veie 3 normale kuler på venstre vektskål mot 3 kuler fra den gjenværende haugen på høyre vektskål, kan vi i 2. veiing få tre mulige utfall.
(a) Balanserer vekten, er den siste gjenværende kulen spesiell. I en 3. veiing mot en normal kule kan vi finne ut, om den er lettere eller tyngre.
(b) Tipper høyre vektskål ned, vet vi at den har den tyngre kulen. Vi undersøker de tre kulene på høyre skål. Vi tar to av dem, veier dem mot hverandre og legger den tredje til sides. Veier de likt, så er den som er lagt til sides den spesielle kulen, og den er tyngre. Ellers er kulen på den synkende vektskålen den tunge.
(c) Tipper høyre vektskål opp, vet vi at den har den kulen som er lettere blant de tre kulene på høyre skål. Vi tar to av dem, veier dem mot hverandre og legger den andre til sides. Veier de likt, så er den som er lagt til sides den spesielle kulen, og den er lettere. Ellers er kulen på den stigende vektskålen den lette.

(2) Dersom de ikke veier det samme, er den spesielle kulen blant de åtte på vekten. Da kan vi merke kulene i den lette haugen med L? og kulene i den tunge haugen med T? og f.eks. veie to fra den lette haugen og en fra den tunge haugen (L?L?T?) på venstre skål mot en fra den lette, en fra den tunge og en normal (L?T?N) på høyre skål.
I 2. veiing kan du få to resultater: (a) De veier det samme. Da er den spesielle blant de tre kulene som ligger igjen og er merket L? eller T?. (b, c) De veier ikke det samme. Da er de som er markert T? i den lette skålen og de som er markert L? i den tunge skålen normale.
I 3. veiing veier du de to som fortsatt er markert likt (L?L? eller T?T?) mot hverandre. Hvis begge var merket L og du får forskjellig vekt, så er det den som er lettest som er spesiell. Hvis begge var merket T og du får forskjellig vekt, er det den tyngste som er spesiell. Hvis de to veier det samme, er det den som ligger igjen som er annerledes.

Se skjematisk forslag på løsning.

Med v=2 kan vi finne den tunge kulen blant kuler med ellers lik vekt, dersom vi har 4-9 kuler, og en av dem er tyngre en de andre. Vi deler kulene inn i 3 hauger, der de første to har like mange og inntil 3 kuler, og veier de to første haugene mot hverandre (1. veiing). Viser vekten likevekt, må den spesielle kulen være i haugen som ikke er veid, ellers er den i den synkende vektskålen. Vi tar så de maks. 3 aktuelle kulene og legger to av dem på de to vektskålene. Viser 2.veiing at de er like tunge, så er den spesielle kulen den som er igjen, ellers er kulen på den synkende vektskålen den tunge.

Med v=3 kan vi finne den tunge kulen blant 10 til 27 kuler. Vi deler kulene inn i 3 hauger med inntil 9 kuler og veier de to første haugene mot hverandre (1. veiing). Er de to haugene like tunge, må den spesielle kulen være i haugen som ikke er veid, ellers er den i den synkende vektskålen. Vi fortsetter veiingen med de aktuelle kulene. Det er mellom 4 og 9 aktuelle kuler, og vi vil kunne finne den spesielle kulen med ytterlige 2 veiinger, slik som skissert i forrige avsnitt.

Formelen stemmer dermed for v=3, når vi vet at den spesielle kulen er tyngre enn de andre. Hvis vi vet at den er lettere enn de andre, går vi tilsvarende fram.

Det henvises til matematiske avhandlinger fra Brodowski og Abbuehl som belyser n-kuler-problemet og beviser formelen ved induksjon.

Setningen kan bevises ved induksjon. En deler kulene inn i 3 hauger med inntil kuler.

 

Tips til 12-kuler-problemet uten vektinformasjon

Hvordan kan en gå fram, for å finne ut med 3 veiinger på en skålvekt, hvilken kule som har en annen vekt, og om den er lettere eller tyngre?

Tilbake til oppgavestillingen

Her kommer et forslag til framgangsmåte. I skjemaet under er veiingene oppført rødt, mens mulige konklusjoner om den enkelte kulens vekt er oppført blått. Vi tenker oss kulene nummeret fra 1 til 12, og angir konklusjonen for kulene i denne rekkefølgen.

V: 1-2-3-4 mot H: 5-6-7-8
<
 >
 =
L?L?L?L? T?T?T?T? N!N!N!N! T?T?T?T? L?L?L?L? N!N!N!N! N!N!N!N! N!N!N!N! TL?TL?TL?TL?

V: 1-2-5 mot H: 3-6-9

V: 1-2-5 mot H: 3-6-9

V: 1-2-3 mot H: 9-10-11
< > = < > = < > =

L?L?N!N!
N!T?N!N!
N!N!N!N!

 N!N!L?N!
T?N!N!N!
N!N!N!N!		 N!N!N!L?
N!N!T?T?
N!N!N!N!		 N!N!T?T?
L?N!N!N!
N!N!N!N!		 T?T?N!N!
N!L?N!N!
N!N!N!N!		 N!N!N!T?
N!N!L?L?
N!N!N!N!		 N!N!N!N!
N!N!N!N!
T?T?T?N!		 N!N!N!N!
N!N!N!N!
L?L?L?N!		 N!N!N!N!
N!N!N!N!
N!N!N!tl?

V:1 mot H:2

V:5 mot H:9

V:7 mot H:8

V:3 mot H:4

V:1 mot H:2

V:7 mot V:8

V:9 mot H:10

V:9 mot H:10

V:1 mot 12
< > = > = < > = < > = < > = < > = < > = < > = < >
L=1 L=2 T=6 T=5 L=3 T=8 T=7 L=4 T=4 T=3 L=5 T=2 T=1 L=6 L=7 L=8 T=4 T=10 T=9 T=11 L=9 L=10 L=11 T=12 L=12

V: Venstre vektskål H: Høyre vektskål
< Kulene på den høyre vektskålen er tyngre. = Det er likevekt mellom vektskålene.
> Kulene på den venstre vektskålen er tyngre.   
L? Den aktuelle kulen kan tenkes å være lettere enn de andre. Hvis alle andre kuler viser seg å være normale, er denne kulen lettere. T? Den aktuelle kulen kan tenkes å være tyngre enn de andre. Hvis alle andre kuler viser seg å være normale, er denne kulen tyngre.
tl? Den aktuelle kulen kan tenkes å ikke være normal. Hvis alle andre kuler viser seg å være normale, har denne kulen en annen vekt, men en vekt ikke om den er lettere eller tyngre. N! Resultat: Den aktuelle kulen er normal.
L= Resultat: Den aktuelle kulen er lettere. T= Resultat: Den aktuelle kulen er tyngre.

 

Referanser/Fotnoter

(1) 12 kuler, uten vektinformasjon.
Se f.eks. på LAMIS matematikk diskusjon, Kuleproblemet, gjenoppstått til påske?, Annie Selle, 20.03.2005, http://www.lamis.no/forum/reply.asp?ID=433&Reply=433,
på Oraklet http://www.erfaring.com/orakel/show.php?id=5355,
og på http://www.root.no/forum/lofiversion/index.php/t4037.html.
(2) 8 kuler, uten vektinformasjon.
Se f.eks. http://www.hannes-becker.de/raetsel/balkenwaageL.html
(3) 3 kuler, uten vektinformasjon.
Se f.eks. http://www.nysgjerrigper.no/pdf-filer/matte0205.pdf
(4) 8 eller 9 kuler med vektinformasjon.
Se f.eks. http://www.eiker.vgs.no/matematikk/dagensnott/dagensnott.htm (9 kuler, med vektinformasjon) og http://www.matematikk.net/ressurser/matteprat/viewtopic.php?t=504 (8 kuler, med vektinformasjon)
(5) 13, 14 kuler, uten vektinformasjon.
Se f.eks. http://www.mathehotline.de/cgi-bin/mathe4u/hausaufgaben/show.cgi?tpc=4373&post=12755
6) Dominik Brodowski, 2001: Allgemeine Lösung des 12-Kugel-Problems
http://www.brodo.de/pub/kugelproblem.pdf
7) Abbuehl, 21.08.00: Das Rätsel mit der Balkenwaage
http://homepage.hispeed.ch/Abbuehl.net/mathematik/balkenwaage/Balkenwaage.pdf