Hur många drag kan man som mest göra?
En svart och en vit pjäs står i två intilliggande hörn av en 12-hörning. På ett drag får man flytta en valfri pjäs till ett ledigt grannhörn. Man får inte gör drag som leder till att pjäserna står på ett sätt som de stått på förut. Hur många drag kan man som mest göra?
-
Jag har försökt förenkla problemet litegrann genom att se hur det är om det istället är en 6-hörning. Dock inte hundra på att jag tolkat frågan rätt och förstår hur jag ska lösa den här uppgiften.
.
Får att om vit står kvar vid där den börjar och den andra flyttas runt görs 6 drag (i en 6 hörning). Om vit flyttas 1 steg och svart flyttas runt görs 8 drag. Om vit flyttas 2 steg och svart flyttas runt görs 9 drag.
-
Detta är hur jag börjat, men känns inte som tanken är att man ska göra så.
Tacksam för hjälp!
Den svarta får inte flyttas till där den vita står, för det står "ledigt hörn".
Men i stället för att titta på hur de rör sig drag för drag kan man först räkna ut hur många olika sätt det finns för dem att stå som är tillåtna. Dvs. om man började med en tom tolvhörning och de två pjäserna, på hur många sätt kan man placera dem på tolvhörningen (utan att flytta omkring dem).
Att förenkla som du gjorde är förresten en utmärkt idé i många sammanhang. Det kanske ger något om du gör figuren ännu mindre, t.ex. fyra hörn.
Laguna skrev:Den svarta får inte flyttas till där den vita står, för det står "ledigt hörn".
Men i stället för att titta på hur de rör sig drag för drag kan man först räkna ut hur många olika sätt det finns för dem att stå som är tillåtna. Dvs. om man började med en tom tolvhörning och de två pjäserna, på hur många sätt kan man placera dem på tolvhörningen (utan att flytta omkring dem).
120 tillåtna? Hur kan det bli samma som att räkna ut hur många drag man som mest kan göra?
Det återstår ju att bevisa, förstås. Hur kom du fram till 120?
Laguna skrev:Det återstår ju att bevisa, förstås. Hur kom du fram till 120?
Jag ritade upp en 12-hörning. Flyttade fram den vita 1 steg i taget. Sedan såg jag vilka ställen den svarta då kunde stå på. Det blev att den svarta kunde stå på 10 ställen varje gång den vita flyttades 1 steg.
lamayo skrev:Laguna skrev:Den svarta får inte flyttas till där den vita står, för det står "ledigt hörn".
Men i stället för att titta på hur de rör sig drag för drag kan man först räkna ut hur många olika sätt det finns för dem att stå som är tillåtna. Dvs. om man började med en tom tolvhörning och de två pjäserna, på hur många sätt kan man placera dem på tolvhörningen (utan att flytta omkring dem).
120 tillåtna? Hur kan det bli samma som att räkna ut hur många drag man som mest kan göra?
Det här är enklare än man kan tro.
Ledtråd 1: Antal tillåtna drag kan inte vara lika många som antal tillåtna positioner. I så fall kommer man ju att göra ett drag som placerar pjäserna på samma sätt som ursprungspositionen.
Ledtråd 2: Är det möjligt att komma till alla tillåtna positioner med hjälp av enbart tillåtna drag?
Jag tänkte fel, det var inte riktigt den uppgift jag trodde.
Yngve skrev:lamayo skrev:Laguna skrev:Den svarta får inte flyttas till där den vita står, för det står "ledigt hörn".
Men i stället för att titta på hur de rör sig drag för drag kan man först räkna ut hur många olika sätt det finns för dem att stå som är tillåtna. Dvs. om man började med en tom tolvhörning och de två pjäserna, på hur många sätt kan man placera dem på tolvhörningen (utan att flytta omkring dem).
120 tillåtna? Hur kan det bli samma som att räkna ut hur många drag man som mest kan göra?
Det här är enklare än man kan tro.
Ledtråd 1: Antal tillåtna drag kan inte vara lika många som antal tillåtna positioner. I så fall kommer man ju att göra ett drag som placerar pjäserna på samma sätt som ursprungspositionen.
Ledtråd 2: Är det möjligt att komma till alla tillåtna positioner med hjälp av enbart tillåtna drag?
På 4-hörningen fick jag: Drag=8 och Positioner=6, på 3-hörningen: Drag=2 och Positioner=3.
Sedan är väll det inte möjligt att komma till alla positioner på 1 drag?
lamayo skrev:På 4-hörningen fick jag: Drag=8 och Positioner=6, på 3-hörningen: Drag=2 och Positioner=3.
Sedan är väll det inte möjligt att komma till alla positioner på 1 drag?
Vi börjar med 3-hörningen. Den har 6 tillåtna positioner och 5 tillåtna drag, se bild.
Och nej, det är inte möjligt att komma till alla ppsitioner på endast 1 drag.
Knepet här är att inse att alla möjliga positioner är nåbara.
Yngve skrev:lamayo skrev:På 4-hörningen fick jag: Drag=8 och Positioner=6, på 3-hörningen: Drag=2 och Positioner=3.
Sedan är väll det inte möjligt att komma till alla positioner på 1 drag?
Vi börjar med 3-hörningen. Den har 6 tillåtna positioner och 5 tillåtna drag, se bild.
Och nej, det är inte möjligt att komma till alla ppsitioner på endast 1 drag.
Knepet här är att inse att alla möjliga positioner är nåbara.
Är det då i en fyrhörning 12 tillåtna positioner och 11 tillåtna drag?
lamayo skrev:Yngve skrev:lamayo skrev:På 4-hörningen fick jag: Drag=8 och Positioner=6, på 3-hörningen: Drag=2 och Positioner=3.
Sedan är väll det inte möjligt att komma till alla positioner på 1 drag?
Vi börjar med 3-hörningen. Den har 6 tillåtna positioner och 5 tillåtna drag, se bild.
Och nej, det är inte möjligt att komma till alla ppsitioner på endast 1 drag.
Knepet här är att inse att alla möjliga positioner är nåbara.
Är det då i en fyrhörning 12 tillåtna positioner och 11 tillåtna drag?
Ja det stämmer.
För varje möjligt hörn den svarta pjäsen kan stå i (dvs 4 st) så kan den vita pjäsen stå i 3 andra hörn. Antalet möjliga placeringar är alltså 4*3.
Yngve skrev:lamayo skrev:Yngve skrev:lamayo skrev:På 4-hörningen fick jag: Drag=8 och Positioner=6, på 3-hörningen: Drag=2 och Positioner=3.
Sedan är väll det inte möjligt att komma till alla positioner på 1 drag?
Vi börjar med 3-hörningen. Den har 6 tillåtna positioner och 5 tillåtna drag, se bild.
Och nej, det är inte möjligt att komma till alla ppsitioner på endast 1 drag.
Knepet här är att inse att alla möjliga positioner är nåbara.
Är det då i en fyrhörning 12 tillåtna positioner och 11 tillåtna drag?
Ja det stämmer.
För varje möjligt hörn den svarta pjäsen kan stå i (dvs 4 st) så kan den vita pjäsen stå i 3 andra hörn. Antalet möjliga placeringar är alltså 4*3.
Betyder det att antal tillåtna drag är 1 mindre än antal tillåtna positioner?
lamayo skrev:Yngve skrev:lamayo skrev:Yngve skrev:lamayo skrev:På 4-hörningen fick jag: Drag=8 och Positioner=6, på 3-hörningen: Drag=2 och Positioner=3.
Sedan är väll det inte möjligt att komma till alla positioner på 1 drag?
Vi börjar med 3-hörningen. Den har 6 tillåtna positioner och 5 tillåtna drag, se bild.
Och nej, det är inte möjligt att komma till alla ppsitioner på endast 1 drag.
Knepet här är att inse att alla möjliga positioner är nåbara.
Är det då i en fyrhörning 12 tillåtna positioner och 11 tillåtna drag?
Ja det stämmer.
För varje möjligt hörn den svarta pjäsen kan stå i (dvs 4 st) så kan den vita pjäsen stå i 3 andra hörn. Antalet möjliga placeringar är alltså 4*3.
Betyder det att antal tillåtna drag är 1 mindre än antal tillåtna positioner?
Bra slutsats! Kan du även motivera den så är det toppen.
Yngve skrev:lamayo skrev:Yngve skrev:lamayo skrev:Yngve skrev:lamayo skrev:På 4-hörningen fick jag: Drag=8 och Positioner=6, på 3-hörningen: Drag=2 och Positioner=3.
Sedan är väll det inte möjligt att komma till alla positioner på 1 drag?
Vi börjar med 3-hörningen. Den har 6 tillåtna positioner och 5 tillåtna drag, se bild.
Och nej, det är inte möjligt att komma till alla ppsitioner på endast 1 drag.
Knepet här är att inse att alla möjliga positioner är nåbara.
Är det då i en fyrhörning 12 tillåtna positioner och 11 tillåtna drag?
Ja det stämmer.
För varje möjligt hörn den svarta pjäsen kan stå i (dvs 4 st) så kan den vita pjäsen stå i 3 andra hörn. Antalet möjliga placeringar är alltså 4*3.
Betyder det att antal tillåtna drag är 1 mindre än antal tillåtna positioner?
Bra slutsats! Kan du även motivera den så är det toppen.
Antal tillåtna positioner i trehörningen 6 och tillåtna drag 5. Antal drag är 1 mindre än positioner.
Antal tillåtna positioner i fyrhörningen är 12 och tillåtna drag 11. Antal drag är även här 1 mindre än antal positioner.
Räcker det som motivering?
lamayo skrev:
Antal tillåtna positioner i trehörningen 6 och tillåtna drag 5. Antal drag är 1 mindre än positioner.
Antal tillåtna positioner i fyrhörningen är 12 och tillåtna drag 11. Antal drag är även här 1 mindre än antal positioner.
Räcker det som motivering?
Det är rätt tänkt, men det räcker inte som motivering. Men du kanske inte måste motivera?
Det viktigaste är att du förstår varför det är så, nämligen eftersom alla positioner går att nå och en av positionerna inte behöver nås eftersom det är den man utgår ifrån.
Vad blir då svaret på ursprungsfrågan?
Nu undrar jag hur metoden ser ut för att nå alla positioner. Hur blir det med en fyrhörning? För att slippa rita kan vi säga att hörnen heter 1 2 3 4, och att vi skriver 12 för utgångsställningen där den vita är på 1 och den svarta på 2. Man kan hamna i 13 och i 42 med första draget, men hur kommer man sen till alla tolv positioner?
Laguna skrev:Nu undrar jag hur metoden ser ut för att nå alla positioner. Hur blir det med en fyrhörning? För att slippa rita kan vi säga att hörnen heter 1 2 3 4, och att vi skriver 12 för utgångsställningen där den vita är på 1 och den svarta på 2. Man kan hamna i 13 och i 42 med första draget, men hur kommer man sen till alla tolv positioner?
Nej nu när du säger det så är det inte alls så lätt som jag trodde att nå alla positioner.
@lamayo - är detta verkligen en uppgift från årskurs 9?
Just nu är jag övertygad om att man måste missa fyra av dem, efter att ha gjort en graf med alla positioner. Jag kan inte riktigt skriva ett bevis på rak arm. Men det blir ett trevligt diagram, som kan utökas till större polygoner utan problem.
Laguna skrev:Just nu är jag övertygad om att man måste missa fyra av dem, efter att ha gjort en graf med alla positioner. Jag kan inte riktigt skriva ett bevis på rak arm. Men det blir ett trevligt diagram, som kan utökas till större polygoner utan problem.
Missa fyra av vilka? Inte av de 12 positionerna för en fyrhörning väl? Det är enkelt att i det fallet nå 9 positioner, dvs 8 förflyttningar.
------
Om detta är åk 9 så är uppgiften antagligen felformulerad, om det är eftergymnasiala studier så är det troligtvis relaterat till grafteori.
Yngve skrev:Laguna skrev:Just nu är jag övertygad om att man måste missa fyra av dem, efter att ha gjort en graf med alla positioner. Jag kan inte riktigt skriva ett bevis på rak arm. Men det blir ett trevligt diagram, som kan utökas till större polygoner utan problem.
Missa fyra av vilka? Inte av de 12 positionerna för en fyrhörning väl? Det är enkelt att i det fallet nå 9 positioner, dvs 8 förflyttningar.
------
Om detta är åk 9 så är uppgiften antagligen felformulerad, om det är eftergymnasiala studier så är det troligtvis relaterat till grafteori.
Sant, man behöver inte missa fyra av de 12, men tre.
Det här var ett roligt problem (kanske inte för lamayo). Det verkar som om det går att nå alla positioner om antalet hörn är udda men inte annars. Precis hur många man kan nå har jag inte räknat ut.
Yngve skrev:Laguna skrev:Nu undrar jag hur metoden ser ut för att nå alla positioner. Hur blir det med en fyrhörning? För att slippa rita kan vi säga att hörnen heter 1 2 3 4, och att vi skriver 12 för utgångsställningen där den vita är på 1 och den svarta på 2. Man kan hamna i 13 och i 42 med första draget, men hur kommer man sen till alla tolv positioner?
Nej nu när du säger det så är det inte alls så lätt som jag trodde att nå alla positioner.
@lamayo - är detta verkligen en uppgift från årskurs 9?
Fick det enskilt från min lärare, som tyckte jag skulle lösa den. Vet dock inte vilken nivå den ligger på.
lamayo skrev:Yngve skrev:
Nej nu när du säger det så är det inte alls så lätt som jag trodde att nå alla positioner.
@lamayo - är detta verkligen en uppgift från årskurs 9?
Fick det enskilt från min lärare, som tyckte jag skulle lösa den. Vet dock inte vilken nivå den ligger på.
Men vilken nivå läser du på?
Du har mattefrågor som ligger spridda över ett flertal olika kategorier: Åk 7, åk 8, åk 9, Matte 5, Universitetet.
Har du läst någon grafteori?
Om du låter alla möjliga positioner representeras av noder i en graf och de giltiga förflyttningarna representeras av vägar mellan noderna så handlar problemet om att hitta den längsta stigen i grafen då man utgår från en specifik nod.
Yngve skrev:lamayo skrev:Yngve skrev:Nej nu när du säger det så är det inte alls så lätt som jag trodde att nå alla positioner.
@lamayo - är detta verkligen en uppgift från årskurs 9?
Fick det enskilt från min lärare, som tyckte jag skulle lösa den. Vet dock inte vilken nivå den ligger på.
Men vilken nivå läser du på?
Du har mattefrågor som ligger spridda över ett flertal olika kategorier: Åk 7, åk 8, åk 9, Matte 5, Universitetet.
Har du läst någon grafteori?
Om du låter alla möjliga positioner representeras av noder i en graf och de giltiga förflyttningarna representeras av vägar mellan noderna så handlar problemet om att hitta den längsta stigen i grafen då man utgår från en specifik nod.
vet inte vilken nivå jag läser på riktigt.
har läst lite grafteori.
Varför ska jag hitta den längsta stigen i grafen? Får jag fram antal drag som kan göras på de olika pjäserna då, eller?
lamayo skrev:
vet inte vilken nivå jag läser på riktigt.
har läst lite grafteori.
Varför ska jag hitta den längsta stigen i grafen? Får jag fram antal drag som kan göras på de olika pjäserna då, eller?
Orsaken till att jag frågar är att det är enklare för oss att hjälpa dig på rätt sätt om vi vet vilken kurs/nivå du läser.
Det är väldigt stor skillnad på grundskole-, gymnasie- och högskolematematik.
- Går du i någon skola? I så fall vilken?
- Läser du någon kurs eller följer du någon utbildningsplan? I så fall vilken?
------------
Ja, svaret på din uppgift är lika med antalet vägar i den längsta stigen i motsvarande graf, om startnoden är en där pjäserna står bredvid varandra.
Yngve skrev:lamayo skrev:vet inte vilken nivå jag läser på riktigt.
har läst lite grafteori.
Varför ska jag hitta den längsta stigen i grafen? Får jag fram antal drag som kan göras på de olika pjäserna då, eller?
Orsaken till att jag frågar är att det är enklare för oss att hjälpa dig på rätt sätt om vi vet vilken kurs/nivå du läser.
Det är väldigt stor skillnad på grundskole-, gymnasie- och högskolematematik.
- Går du i någon skola? I så fall vilken?
- Läser du någon kurs eller följer du någon utbildningsplan? I så fall vilken?
------------
Ja, svaret på din uppgift är lika med antalet vägar i den längsta stigen i motsvarande graf, om startnoden är en där pjäserna står bredvid varandra.
Okej! Går just nu i 8an.
För ett jämnt antal hörn, säg 2n hörn:
Färglägg hörnen, varannan röd, varannan grön.
Det finns då två typer av positioner:
1) De där vit pjäs och svart står på hörn av samma färg.
2) De där vit pjäs och svart står på hörn av olika färg.
Antal positioner av typ 1: Vit pjäs kan placeras på någon av 2n hörn, och svart pjäs sedan på någon av n-1 hörn. Totalt 2n^2-2n positioner av typ 1.
Antal positioner av typ 2: Vit pjäs kan placeras på någon av 2n hörn, och svart pjäs sedan på någon av n hörn, Totalt 2n^2 positioner.
I startpositionen befinner vi oss i en position av typ 2, sedan alternerar mellan positioner av typ 1 och typ 2 i varje drag. Så vi får 2-1-2-1-2-1.....-2-1-2 och sedan är det slut på slut på positioner av typ 1 eftersom de är färre.
Vi kommer alltså att göra 2*(2n^2-2n)=4n^2-4n drag.
Smutsmunnen skrev:För ett jämnt antal hörn, säg 2n hörn:
Färglägg hörnen, varannan röd, varannan grön.
Det finns då två typer av positioner:
1) De där vit pjäs och svart står på hörn av samma färg.
2) De där vit pjäs och svart står på hörn av olika färg.
Antal positioner av typ 1: Vit pjäs kan placeras på någon av 2n hörn, och svart pjäs sedan på någon av n-1 hörn. Totalt 2n^2-2n positioner av typ 1.
Antal positioner av typ 2: Vit pjäs kan placeras på någon av 2n hörn, och svart pjäs sedan på någon av n hörn, Totalt 2n^2 positioner.
I startpositionen befinner vi oss i en position av typ 2, sedan alternerar mellan positioner av typ 1 och typ 2 i varje drag. Så vi får 2-1-2-1-2-1.....-2-1-2 och sedan är det slut på slut på positioner av typ 1 eftersom de är färre.
Vi kommer alltså att göra 2*(2n^2-2n)=4n^2-4n drag.
Jag var antagligen alltför "hjälpsam" här, uppriktigt talat vet jag inte hur man gör spoilers på nya pluggakuten, någon får gärna berätta.
Jag var antagligen alltför "hjälpsam" här, uppriktigt talat vet jag inte hur man gör spoilers på nya pluggakuten, någon får gärna berätta.
Det går inte i dagsläget. Vi har förhoppningar om att kunna implementera det vid framtida uppdateringar.
Smutsmunnen skrev:För ett jämnt antal hörn, säg 2n hörn:
Färglägg hörnen, varannan röd, varannan grön.
Det finns då två typer av positioner:
1) De där vit pjäs och svart står på hörn av samma färg.
2) De där vit pjäs och svart står på hörn av olika färg.
Antal positioner av typ 1: Vit pjäs kan placeras på någon av 2n hörn, och svart pjäs sedan på någon av n-1 hörn. Totalt 2n^2-2n positioner av typ 1.
Antal positioner av typ 2: Vit pjäs kan placeras på någon av 2n hörn, och svart pjäs sedan på någon av n hörn, Totalt 2n^2 positioner.
I startpositionen befinner vi oss i en position av typ 2, sedan alternerar mellan positioner av typ 1 och typ 2 i varje drag. Så vi får 2-1-2-1-2-1.....-2-1-2 och sedan är det slut på slut på positioner av typ 1 eftersom de är färre.
Vi kommer alltså att göra 2*(2n^2-2n)=4n^2-4n drag.
Snyggt!
Det var ett bra resonemang som ger ett värde på det maximala antal drag som skulle kunna vara möjligt att göra i en 2n-hörning.
Men det framgår inte att det faktiskt går att nå denna teoretiska maxgräns varje gång.
Yngve skrev:Smutsmunnen skrev:För ett jämnt antal hörn, säg 2n hörn:
Färglägg hörnen, varannan röd, varannan grön.
Det finns då två typer av positioner:
1) De där vit pjäs och svart står på hörn av samma färg.
2) De där vit pjäs och svart står på hörn av olika färg.
Antal positioner av typ 1: Vit pjäs kan placeras på någon av 2n hörn, och svart pjäs sedan på någon av n-1 hörn. Totalt 2n^2-2n positioner av typ 1.
Antal positioner av typ 2: Vit pjäs kan placeras på någon av 2n hörn, och svart pjäs sedan på någon av n hörn, Totalt 2n^2 positioner.
I startpositionen befinner vi oss i en position av typ 2, sedan alternerar mellan positioner av typ 1 och typ 2 i varje drag. Så vi får 2-1-2-1-2-1.....-2-1-2 och sedan är det slut på slut på positioner av typ 1 eftersom de är färre.
Vi kommer alltså att göra 2*(2n^2-2n)=4n^2-4n drag.
Snyggt!
Det var ett bra resonemang som ger ett värde på det maximala antal drag som skulle kunna vara möjligt att göra i en 2n-hörning.
Men det framgår inte att det faktiskt går att nå denna teoretiska maxgräns varje gång.
Den biten tycker jag är så pass enkel.
Något måste lämna till ungdomen.
Smutsmunnen skrev:Yngve skrev:Smutsmunnen skrev:För ett jämnt antal hörn, säg 2n hörn:
Färglägg hörnen, varannan röd, varannan grön.
Det finns då två typer av positioner:
1) De där vit pjäs och svart står på hörn av samma färg.
2) De där vit pjäs och svart står på hörn av olika färg.
Antal positioner av typ 1: Vit pjäs kan placeras på någon av 2n hörn, och svart pjäs sedan på någon av n-1 hörn. Totalt 2n^2-2n positioner av typ 1.
Antal positioner av typ 2: Vit pjäs kan placeras på någon av 2n hörn, och svart pjäs sedan på någon av n hörn, Totalt 2n^2 positioner.
I startpositionen befinner vi oss i en position av typ 2, sedan alternerar mellan positioner av typ 1 och typ 2 i varje drag. Så vi får 2-1-2-1-2-1.....-2-1-2 och sedan är det slut på slut på positioner av typ 1 eftersom de är färre.
Vi kommer alltså att göra 2*(2n^2-2n)=4n^2-4n drag.
Snyggt!
Det var ett bra resonemang som ger ett värde på det maximala antal drag som skulle kunna vara möjligt att göra i en 2n-hörning.
Men det framgår inte att det faktiskt går att nå denna teoretiska maxgräns varje gång.
Den biten tycker jag är så pass enkel.
Något måste lämna till ungdomen.
Hur kan jag ta reda på vilka sätt som inte är möjliga?
Ett annat sätt jag gjorde på var att rita upp en stig i ett kordinatsystem där noderna representerar positioner och fick 120 noder vilket motsvarar 120 positioner.
