Kombinatorik Problem.
Hej!
Jag har fastnat på två problem inom kombinatorik som jag tycker är riktigt kluriga. Förstår inte hur jag ska ställa upp lösningen eller börja..
Problem 1: (a) På en skolgård ritade barnen ett rutnät med sex rader och sex kolonner. I var och en av de 36 rutorna ställde sig ett barn. På lärarens signal hoppade varje barn till en angränsande ruta (två rutor är angränsande om de har en gemensam sida). Kan denna förflyttning organiseras så att det efteråt återigen finns ett barn i varje ruta?
(b) Ett av barnen fick ont i magen och avbröt leken, varför de övriga ritade ett nytt rutnät med sju rader och fem kolonner. Hur kan barnen organisera förflyttningen om de vill fortsätta leka samma sak?
Problem 2: En hörnruta i ett 3 x 3- rutnät är målad svart och de övriga rutorna är vita. I ett drag får man byta färg i alla rutor i en rad eller i en kolonn. Kan man efter ett antal sådana drag få alla rutor svarta?
Misstänker att problemen kan lösas på liknande sätt?? All hjälp skulle uppskattas. Tack på förhand!
Problem 1: a) Skulle du kunna göra det på en 2x2 ruta? På en 4x4 ruta? På en 6x6 ruta?
b) Om du färglägger rutorna som ett schackbräde. Detta delar upp barnen i svarta och vita grupper, dvs dom tillhör samma grupp som färgen på deras ruta. Säg att det då finns ett jämnt antal vita barn och ett udda antal svarta barn. Efter hoppet så kommer alla barn att byta grupp, är detta möjligt?
Problem 2: Markera varje ruta med a, b, c på följande sätt
a b c
b c a
c a b
Låt A, B, C vara 0 eller 1, beroende på om du har ett jämnt eller udda antal svarta rutor på a, b, c. Så man börjar med att A = 1, B = 0, C = 0 (om man har att översta vänstra hörnet startar som svart). Vad händer med A, B, C när du byter färg på en rad eller kolumn? Är det möjligt att få A = B = C = 1?
Stokastisk skrev :Problem 1: a) Skulle du kunna göra det på en 2x2 ruta? På en 4x4 ruta? På en 6x6 ruta?
b) Om du färglägger rutorna som ett schackbräde. Detta delar upp barnen i svarta och vita grupper, dvs dom tillhör samma grupp som färgen på deras ruta. Säg att det då finns ett jämnt antal vita barn och ett udda antal svarta barn. Efter hoppet så kommer alla barn att byta grupp, är detta möjligt?
Problem 2: Markera varje ruta med a, b, c på följande sätt
a b c
b c a
c a b
Låt A, B, C vara 0 eller 1, beroende på om du har ett jämnt eller udda antal svarta rutor på a, b, c. Så man börjar med att A = 1, B = 0, C = 0 (om man har att översta vänstra hörnet startar som svart). Vad händer med A, B, C när du byter färg på en rad eller kolumn? Är det möjligt att få A = B = C = 1?
Hej och tack för ditt svar!
Förstår uppgift 1 nu men har förstår inte uppgift 2.
Uppgift 2: Förstår att det är omöjligt att måla hela kuben svart, då detta isåfall måste kunna göras oberoende av vilket hörn som först är svartmålat. Alltså, om det var möjligt att måla hela kuben svart måste man kunna gå ifrån:
endast ett hörn svartmålat -> hela kuben svartmålat -> endast ett annat hörn svartmålat
men då det är omöjligt att gå ifrån:
endast ett hörn svartmålat -> endast ett annat hörn svartmålat
måste det därför vara omöjligt att måla hela kuben svart.
Förstår inte hur jag ska visa matematiskt att det är omöjligt att gå ifrån
endast ett hörn svartmålat -> endast ett annat hörn svartmålat?.. :(
Vet inte riktigt om jag förstår dig, men du har samma fråga i denna tråd https://www.pluggakuten.se/trad/rutnat-1/ och DrNej föreslog en bättre lösning än den jag hade, så se om du kan förstå den lösningen.
Det går inte att få alla rutor svarta.
larsolof skrev :Det går inte att få alla rutor svarta.
Exakt, det är det jag vill visa! Kan logiskt resonera mig fram till att det inte går, men vet inte hur jag ska visa det med paritetsargument :( Har du någon aning?
Om man har bara två rutor, i startläget en svart, en vit, inses lätt
att det inte går vända så alla blir svarta.
Lika om man har ett 2x2-rutnät.
Varför skulle det gå lättare med ett större rutnät?
Att visa med paritetsargumentering, nej det vet jag inte hur man gör.
xyzABCDE skrev :larsolof skrev :Det går inte att få alla rutor svarta.
Exakt, det är det jag vill visa! Kan logiskt resonera mig fram till att det inte går, men vet inte hur jag ska visa det med paritetsargument :( Har du någon aning?
Har du gjort ett försök med att svara på de frågor jag ställde i andra tråden?
Stokastisk skrev :xyzABCDE skrev :larsolof skrev :Det går inte att få alla rutor svarta.
Exakt, det är det jag vill visa! Kan logiskt resonera mig fram till att det inte går, men vet inte hur jag ska visa det med paritetsargument :( Har du någon aning?
Har du gjort ett försök med att svara på de frågor jag ställde i andra tråden?
Tänker att jag istället vill färglägga alla rutor vita (och att alla rutor från början är svarta, som i den andra tråden), för att då svara på dina frågor:
Jag tänker att pariteten av antalet svarta hörn måste vara jämn (vill ju ha 0 svarta hörn, för att hela ska målas vit). Dock är pariteten för antalet vita hörn udda, för att antalet vita hörn kan endast ändras med 0, 2, eller -2 beroende på vilket "drag" man utför, alltså man kan endast erhålla 1 eller 3 vita hörn samtidigt. För att hela nätet ska målas vitt måste pariteten av antalet svarta rutor också vara ojämn, för annars är det invariant? Är detta på rätt spår?
xyzABCDE skrev :Stokastisk skrev :xyzABCDE skrev :larsolof skrev :Det går inte att få alla rutor svarta.
Exakt, det är det jag vill visa! Kan logiskt resonera mig fram till att det inte går, men vet inte hur jag ska visa det med paritetsargument :( Har du någon aning?
Har du gjort ett försök med att svara på de frågor jag ställde i andra tråden?
Tänker att jag istället vill färglägga alla rutor vita (och att alla rutor från början är svarta, som i den andra tråden), för att då svara på dina frågor:
Jag tänker att pariteten av antalet svarta hörn måste vara jämn (vill ju ha 0 svarta hörn, för att hela ska målas vit). Dock är pariteten för antalet vita hörn udda, för att antalet vita hörn kan endast ändras med 0, 2, eller -2 beroende på vilket "drag" man utför, alltså man kan endast erhålla 1 eller 3 vita hörn samtidigt. För att hela nätet ska målas vitt måste pariteten av antalet svarta rutor också vara ojämn, för annars är det invariant? Är detta på rätt spår?
Den fetmarkerade meningen är jag inte med på. Men oavsett, du verkar ha löst problemet utan att märka det :)
Du har kommit fram till att antalet vita hörn alltid är udda, men om hela nätet är vitt så ska det vara ett jämnt antal. Då har du alltså kommit fram till att alla rutor inte kan vara vita.
Stokastisk skrev :xyzABCDE skrev :Stokastisk skrev :xyzABCDE skrev :larsolof skrev :Det går inte att få alla rutor svarta.
Exakt, det är det jag vill visa! Kan logiskt resonera mig fram till att det inte går, men vet inte hur jag ska visa det med paritetsargument :( Har du någon aning?
Har du gjort ett försök med att svara på de frågor jag ställde i andra tråden?
Tänker att jag istället vill färglägga alla rutor vita (och att alla rutor från början är svarta, som i den andra tråden), för att då svara på dina frågor:
Jag tänker att pariteten av antalet svarta hörn måste vara jämn (vill ju ha 0 svarta hörn, för att hela ska målas vit). Dock är pariteten för antalet vita hörn udda, för att antalet vita hörn kan endast ändras med 0, 2, eller -2 beroende på vilket "drag" man utför, alltså man kan endast erhålla 1 eller 3 vita hörn samtidigt. För att hela nätet ska målas vitt måste pariteten av antalet svarta rutor också vara ojämn, för annars är det invariant? Är detta på rätt spår?Den fetmarkerade meningen är jag inte med på. Men oavsett, du verkar ha löst problemet utan att märka det :)
Du har kommit fram till att antalet vita hörn alltid är udda, men om hela nätet är vitt så ska det vara ett jämnt antal. Då har du alltså kommit fram till att alla rutor inte kan vara vita.
Åh, tack för hjälpen! Haha är så lost på Kombinatorik :p..
Den fetmarkerade meningen: Jag tänker att om det skulle vara möjligt att måla hela nätet vitt, så måste båda pariteter (den för antalet vita rutor samt den för antalet svarta rutor) antingen vara jämna eller båda udda. Jag tänker att om det är en jämn och en udda paritet (som i detta fall) så är det invariant, och inte möjligt att måla alla rutor vita.
xyzABCDE skrev :Den fetmarkerade meningen: Jag tänker att om det skulle vara möjligt att måla hela nätet vitt, så måste båda pariteter (den för antalet vita rutor samt den för antalet svarta rutor) antingen vara jämna eller båda udda. Jag tänker att om det är en jämn och en udda paritet (som i detta fall) så är det invariant, och inte möjligt att måla alla rutor vita.
Fast om alla är vita så har du 9 stycken vita rutor och 0 stycken svarta. Du har alltså ett udda antal vita och ett jämnt antal svarta. Så pariteten måste inte vara lika för att alla ska vara vita.
Stokastisk skrev :xyzABCDE skrev :Den fetmarkerade meningen: Jag tänker att om det skulle vara möjligt att måla hela nätet vitt, så måste båda pariteter (den för antalet vita rutor samt den för antalet svarta rutor) antingen vara jämna eller båda udda. Jag tänker att om det är en jämn och en udda paritet (som i detta fall) så är det invariant, och inte möjligt att måla alla rutor vita.Fast om alla är vita så har du 9 stycken vita rutor och 0 stycken svarta. Du har alltså ett udda antal vita och ett jämnt antal svarta. Så pariteten måste inte vara lika för att alla ska vara vita.
Ja såklart.. Det är ju sant, tänkte inte på det! Kan man då säga att invarianten beror på att man inte kan erhålla annat än 1 eller 3 vita hörn samtidigt?
xyzABCDE skrev :Stokastisk skrev :xyzABCDE skrev :Den fetmarkerade meningen: Jag tänker att om det skulle vara möjligt att måla hela nätet vitt, så måste båda pariteter (den för antalet vita rutor samt den för antalet svarta rutor) antingen vara jämna eller båda udda. Jag tänker att om det är en jämn och en udda paritet (som i detta fall) så är det invariant, och inte möjligt att måla alla rutor vita.Fast om alla är vita så har du 9 stycken vita rutor och 0 stycken svarta. Du har alltså ett udda antal vita och ett jämnt antal svarta. Så pariteten måste inte vara lika för att alla ska vara vita.
Ja såklart.. Det är ju sant, tänkte inte på det! Kan man då säga att invarianten beror på att man inte kan erhålla annat än 1 eller 3 vita hörn samtidigt?
Ja, det är korrekt.
Stokastisk skrev :xyzABCDE skrev :Stokastisk skrev :xyzABCDE skrev :Den fetmarkerade meningen: Jag tänker att om det skulle vara möjligt att måla hela nätet vitt, så måste båda pariteter (den för antalet vita rutor samt den för antalet svarta rutor) antingen vara jämna eller båda udda. Jag tänker att om det är en jämn och en udda paritet (som i detta fall) så är det invariant, och inte möjligt att måla alla rutor vita.Fast om alla är vita så har du 9 stycken vita rutor och 0 stycken svarta. Du har alltså ett udda antal vita och ett jämnt antal svarta. Så pariteten måste inte vara lika för att alla ska vara vita.
Ja såklart.. Det är ju sant, tänkte inte på det! Kan man då säga att invarianten beror på att man inte kan erhålla annat än 1 eller 3 vita hörn samtidigt?
Ja, det är korrekt.
Superstort tack för hjälpen! :)
