En logisk uppgift för att placera dominobrickor på ett schackbräde. Matematiska olympiader och olympiadproblem
Givet ett 8×8 schackbräde, från vilket två diagonalt motsatta hörn skurits, och 31 dominobrickor; varje domino kan täcka två rutor på brädet. Är det möjligt att asfaltera hela brädan med ben? Ge en motivering till ditt svar.
Lösning
Vid första anblicken verkar det vara möjligt. Brädan är 8×8, därför finns det 64 celler, vi utesluter två, vilket betyder att det finns kvar 62. Det verkar som att 31 ben borde passa, eller hur?
När vi försöker ordna dominobrickor i första raden har vi bara 7 rutor till vårt förfogande, ett ben går till andra raden. Sedan placerar vi dominobrickor i den andra raden, och igen går en bricka till den tredje raden.
Det kommer alltid att finnas ett ben i varje rad som måste flyttas till nästa rad, oavsett hur många layouter vi försöker kommer vi aldrig att kunna lägga ut alla ben.
Schackbrädet är uppdelat i 32 svarta och 32 vita celler. Genom att ta bort de motsatta hörnen (observera att dessa celler har samma färg) har vi kvar 30 celler av en färg och 32 celler av en annan färg. Anta att vi nu har 30 svarta och 32 vita rutor.
Varje tärning som vi lägger på brädet kommer att uppta en svart och en vit cell. Därför kommer 31 dominobrickor att uppta 31 vita och 31 svarta celler. Men det finns bara 30 svarta och 32 vita celler på vår tavla. Därför är det omöjligt att sönderdela benen.
Analysen är hämtad från översättningen av boken av G. Luckman McDowell och är endast avsedd i informationssyfte.
Om du gillade den rekommenderar vi att du köper boken.
Bevisa att schackbrädan är 10X10 kan inte skäras längs rutnätslinjer till rektanglar 1X4. (Lösningar enligt D.Yu. Kuznetsov.)
Lösning 1 . Dela brädan i 2x2 rutor och färglägg dem i ett rutmönster (Fig. 1). Observera att varje 1x4 rektangel innehåller lika (2) svarta och vita celler, men med denna färgning finns det 52 svarta celler och 48 vita celler på tavlan, dvs. inte lika. Detta innebär att det inte kommer att vara möjligt att skära en 10x10 skiva i 1x4 rektanglar.
Lösning 2 . Låt oss färglägga tavlan med en diagonalfärgning i 4 färger (Fig. 2). Observera att varje rektangel innehåller en cell av var och en av de fyra färgerna, men med en given färgning finns det 25 celler av den 1:a och 3:e färgen på brädet, 26 celler i den 2:a och 24 celler i den 4:e, d.v.s. inte lika. Detta innebär att det inte kommer att vara möjligt att skära en 10x10 skiva i 1x4 rektanglar.
1. Klipp ut de nedre högra och vänstra hörncellerna från schackbrädet. Är det möjligt att skära den resulterande figuren till 1x2 dominobrickor? Och om du skär nere till höger och uppe till vänster?
2. Är det möjligt att skära en 6x6-bräda till dominobrickor så att det finns exakt 11 horisontella bland dem? (Horisontell färgning i två färger.)
3. Färglägg ritningen i fyra färger så att intilliggande delar målas i olika färger. Går det att klara sig med tre färger? (Se Aktivitet 6: Färgläggning geografisk karta- 5-6 klass).
4. I en 4x4 kvadrat är cellerna i den vänstra halvan målade svarta och resten vita. I en operation är det tillåtet att färga om alla celler inuti valfri rektangel i motsatt färg. Hur får man en schackfärgning från den ursprungliga färgläggningen i tre operationer?
5. Flera gräshoppor sitter på samma raka linje, och avstånden mellan grannar är desamma. Varje minut hoppar en av dem till en punkt som är symmetrisk med den i förhållande till en annan gräshoppa. Kan gräshoppan Sasha efter en tid hamna på platsen där hans granne Lyosha satt i början?
6. a) Är det möjligt att klippa ett schackbräde i figurer som består av 4 celler i form av bokstaven "T"?
b) Är det möjligt att skära ett 10x10 schackbräde till sådana figurer?
7. Är det möjligt att dela en 8x8 kvadrat med ett hörn avskuret i 1x3 rektanglar?
8. Kan en 10x10-bräda skäras i bitar om fyra celler i form av bokstaven "G"? (Horisontell färgning i två färger.)
9. En 8x8-bräda skärs till 2x1 dominobrickor. Kan det finnas 15 vertikala och 17 horisontella dominobrickor?
10. Triangeln är uppdelad i trianglar (25 bitar), som visas i figuren. Skalbaggen kan gå i en triangel och röra sig mellan intilliggande (på sidan) trianglar. Vad är det maximala antalet trianglar som skalbaggen kan passera om den inte har besökt varje triangel mer än en gång?
11. Vilket är det största antalet romber, som var och en består av två liksidiga trianglar med sida 1, som kan skäras ut ur en liksidig triangel med sida 5 (se figuren i föregående uppgift).
12. Det triangelformade slottet är uppdelat i 100 identiska triangulära salar. Det finns en dörr i mitten av varje vägg. Hur många rum kan besökas av en person som inte vill besöka någonstans mer än en gång?
kapitel 2
För en utförlig redogörelse för schackmatematiken, som vi nu ska börja med, är det naturligast att börja med matteproblem om själva tavlan, utan att placera några bitar på den ännu. Det är till detta ämne som detta kapitel ägnas.
Låt oss först och främst överväga flera problem med att täcka ett bräde med 2 × 1 dominobrickor. Överallt antas det att varje domino täcker två rutor av brädet, och varje ruta täcks av ena halvan av dominobrickorna. Låt oss börja med nästa gamla problem.
Är det möjligt att täcka med dominobrickor en kvadrat med storleken 8×8, från vilken motsatta hörnceller är utskurna (Fig. 2a)?
Vi skulle kunna använda algebraiska resonemang, men "schack"-lösningen är både enklare och mer elegant. Låt oss färglägga vår trunkerade ruta i svart och vitt, förvandla den till ett schackbräde utan två hörnfält a8 och h1 (Fig. 2b). För varje täckning av brädan täcker varje domino en vit och en svart fyrkant. Vi har två mindre vita fält än svarta (de skurna fälten är vita), och därför finns inte den nödvändiga täckningen! Som vi kan se gör färgläggningen av brädan det inte bara lättare för en schackspelare att navigera under spelet, utan fungerar också som ett sätt att lösa matematiska problem.
I det övervägda problemet var det viktigt att inte hörnfälten skars ut ur brädan, utan att de var av samma färg. Det är klart att oavsett hur du skär ut ett par enfärgade fält så kommer du inte att kunna täcka resten av brädan med dominobrickor. Följande problem uppstår således.
Antag nu att två fält av olika färg är utskurna på schackbrädet. Är det alltid möjligt att täcka resten av brädan med 31 dominobrickor?
Det visar sig alltid. Ett spektakulärt bevis hittades av den berömda amerikanske matematikern R. Gomory. Låt oss på schackbrädet rita gränserna mellan vertikala och horisontella som visas i fig. 3. I labyrinten mellan dessa gränser följer svarta och vita fält varandra, omväxlande som knappar i två färger på en sluten tråd (vägen längs vilken denna labyrint kan förbigås är stängd). Oavsett vilka två fält av olika färger vi skär ut ur brädet, kommer tråden att bryta: på ett ställe om de skurna fälten ligger intill, och på två ställen annars. I det här fallet kommer varje tråd att bestå av ett jämnt antal fält. Följaktligen kan dessa bitar, och därmed hela brädet, täckas med dominobrickor!
Ris. 3. Labyrint Gomori |
Nyfikna idéer relaterade till knappar och trådar finns i kapitel 11.
Antag att några fält är utskurna ur ett schackbräde så att inga dominobrickor kan placeras på den återstående delen av det. Det är lätt att kontrollera att det minsta antalet utklippta fält med denna egenskap är 32 - dessa är alla fält av samma färg (vita eller svarta).
Schackbrädet och dominoproblemen är bara en liten del av en enorm serie problem av detta slag. Den amerikanske matematikern S. Golomb skapade en hel vetenskap, som han kallade polymipo, och hans bok om detta ämne har översatts i många länder i världen, inklusive vår. I allmänhet är en polyomino en enkelt sammankopplad figur som består av kvadrater. Ur en schackspelares synvinkel betyder det att bara vara ansluten att alla polyominorutor kan förbigås av ett torndrag. Beroende på antalet 07 rutor finns polyominoer i olika kvaliteter. En monomino innehåller en ruta, en domino två, en tromino tre, en tetramino fyra, en pentomino fem, en heptomino sex rutor, och så vidare. Vi kommer att uppehålla oss vid ytterligare några frågor relaterade till det vanliga schackbrädet. Uppenbarligen är det omöjligt att täcka dssk med bara raka trominoer, d.v.s. domino 3 × 1, eftersom 64 inte är delbart med 3. Följande problem uppstår.
Är det möjligt att täcka ett schackbräde med 21 raka trominer och en monomino? Om så är fallet, vilka fält kan en monomino uppta?
En av de nödvändiga dapo-beläggningarna i fig. 4a. För att bestämma de möjliga arrangemangen av monominos ritar vi två system med parallella linjer på brädet, som visas i fig. 4b.
Det är lätt att se att för varje beläggning täcker varje tromino exakt ett fält genom vilket den heldragna linjen passerar, och exakt ett genom vilket den streckade linjen passerar. Eftersom antalet fält som skärs av heldragna linjer är 22, liksom antalet fält som skärs av streckade linjer, och det finns 21 trominer, kan monominor bara täcka fält som skärs av båda linjefamiljerna. Och det finns bara fyra sådana rutor: c3, c6, f3 och f6! Genom att rotera brädan 90, 180 och 270° kan du få lämplig täckning för vart och ett av dessa fyra fält.
Nästa uppgift är något annorlunda än de som diskuterats ovan.
Är det möjligt att täcka ett schackbräde med dominobrickor på ett sådant sätt att det är omöjligt att dra en enda gräns mellan vertikala och horisontella utan att korsa dominobrickorna?
Om vi föreställer oss att brädan är en vägg och dominobrickor är tegelstenar, indikerar förekomsten av den angivna gränsen (sömmen) ett bräckligt murverk. Problemet frågar med andra ord om det är möjligt att ordna "tegelstenarna" så att "väggen" inte rasar. En rektangel som kan täckas på det sätt som krävs kallas "stark". Schackbrädets "styrka" kan ses i fig. 5. I det allmänna fallet visar Gardner att dominobrickor kan vikas till en "stark" rektangel om dess yta är jämn och dess längd och bredd är större än fyra, med det enda undantaget är en 6 × 6 kvadrat.
Nedan kommer vi ofta att behandla rektangulära schackbräden av en eller annan storlek. I det här fallet antas alltid att ett m×n-bräde har m vertikaler och n horisontaler (schack). Vi säger att en bräda är "jämn" om antalet fält är jämn, och "udda" annars. Varhelst brädans dimensioner inte är specificerade, menar vi standardschackbrädet för vilket m = n = 8.
100x4 brädan är täckt med dominobrickor. Bevisa att den kan skäras längs en av gränserna mellan vertikala och horisontella utan att påverka någon av dominobrickorna.
Någon av de angivna gränserna delar brädet i två delar, bestående av ett jämnt antal fält. Vi delar upp fälten för varje del i två klasser: täckta dominobrickor som ligger helt i denna del, och täckta dominobrickor som skärs av gränsen. Eftersom antalet fält för varje del är jämnt (kanske noll), liksom antalet fält i den första klassen (varje domino täcker två fält), är antalet fält i den andra klassen jämnt. Och det betyder att antalet dominobrickor som passeras av gränsen är jämnt. Det finns totalt 102 delande gränser (99 vertikala och 3 horisontella), och om var och en av dem korsar dominobrickor, så deltar minst 102 × 2 = 204 dominobrickor i täckningen. Vi har bara 200 av dem! Faktum är att vi har visat att en 100x4 rektangel är "svag".
Frågan om möjligheten att täcka en godtycklig rektangulär bräda med linjära k-minos (dominoer k × 1) löses med följande sats.
En m×n-bräda kan täckas med linjära k-minos om och endast om minst ett av talen m eller n är delbart med k utan rest.
Vi illustrerar satsen med följande exempel.
Är det möjligt att täcka ett 10x10-bräde (hundra kvadratiska pjäser spelas på ett sådant bräde) med raka tetraminoer?
En rak tetramino har måtten 4x1, vilket innebär att i princip 25 brickor skulle kunna täcka alla fält på vår bräda. Men det följer av satsen att detta är omöjligt - 10 är inte delbart med 4.
Låt oss överväga några fler problem om schackbrädet. I lösningen av följande problem viovb används dess färgning.
Låt tavlan bestå av ett udda antal fält. På vart och ett av dess fält kommer vi att sätta några schackpjäs. Är det möjligt att flytta alla dessa bitar till intilliggande rutor (vertikalt eller horisontellt) så att inte två av dem hamnar på samma ruta?
Uppgiften är omöjlig. Faktum är att om den angivna förskjutningen av bitar existerade, skulle varje "vit" bit (som står på ett vitt fält) bli "svart" (falla på ett svart fält), och varje "svart" - "vit".
Alltså skulle tavlan bestå av samma antal vita och svarta fält, och detta motsäger dess "märklighet".
Populära är problemen med att klippa ett schackbräde. Den mest kända av dem är följande, ägd av S. Loyd.
Det finns fyra riddare på fälten a1, b2, c3, d4. Skär brädan i fyra kongruenta delar (sammanfaller när de är överlagrade) så att var och en av dem har en häst.
Vid skärproblem förutsätts alltid att snitt endast görs längs gränserna mellan brädans vertikaler och horisontaler. Lösningen på detta problem visas i fig. 6. Sedan Loyds tid har många nya och svårare problem dykt upp i detta ämne. I synnerhet löstes problemen med att skära brädan i fyra kongruenta delar för olika positioner av riddarna (riddarna spelar naturligtvis bara en symbolisk roll här). Det finns fortfarande många olösta frågor i denna fråga. Till exempel är antalet sätt som en vanlig bräda (utan bitar) kan skäras i två kongruenta bitar fortfarande inte känt.
Ris. 6. Loyds fyra hästar problem |
Låt, efter flera snitt av brädet, de resulterande delarna tillåts flyttas så att nästa snitt kan skära inte en, utan flera delar på en gång. Hur många klipp krävs för att få 64 individuella brädplatser (1×1 rutor)?
Först skär vi brädan på mitten, lägger sedan båda halvorna sida vid sida och skär brädan i fyra identiska delar etc. Totalt kommer 6 snitt att behövas (2 e \u003d 64) och ett mindre antal kan inte undvaras .
Låt nu delar av brädan endast skäras separat. Hur många nedskärningar kommer att behövas för att få 64 fält i det här fallet?
Som regel orsakar denna uppgift (särskilt om den föreslås efter den föregående) vissa svårigheter. Tydligen beror detta på en viss tröghet i vårt tänkande. Det är trots allt direkt klart att det kommer att behövas 63 nedskärningar! Faktum är att varje snitt ökar antalet delar med en; samtidigt, i det första ögonblicket har vi en del (själva brädet), och i det sista ögonblicket - 64 (alla fält i brädet).
Ris. 7. Tre problem på en ovanlig bräda |
I uppgiften i fig. 7a måste du slutföra tre uppgifter, en matematisk och två rent schack:
a) skär brädet i fyra kongruenta delar;
b) schackmatt den svarte kungen på kortaste sätt när vit rör sig;
c) att schackmatt den svarte kungen på kortaste sätt; medan svart rör sig, spelar de trogna samarbetsvilligt).
Lösningar: a) hur man skär brädet, visat i fig. 7b; b) när vit flyttar ges schackmatt på det 12:e draget: 1-12. Be1-b4, Ke3-d3-c4, Be4-c2-b3, Kc4-c3, Bb4-d6, Bb3-d5, Kc3-c2, Bd6-c5, Bd5-c4, Bd6-b4 schackmatt (alla drag av den svarte kungen tvingas och ges inte); c) med korrekt spel efter 1. ... Ke6-e7 schackmatt är omöjligt, eftersom den svarta kungen gömmer sig på e8 - 2. Be1-b4+ Ke7-e8, och den mörkrutade biskopen tvingas lämna a3 - e7 diagonalen på grund av hotet om ett dödläge. Men om svart spelar samarbetsvilligt (hjälper vit schackmatt), så nås målet på bara tre drag:
1. … Ke6-d6
2. Ke3-d4 Ke6-e7
3. Be1-b4+ Ke7-e6
4. Be4-d5 kompis. Ett antal fält på vår bräda används inte under parning, men om de uteslöts skulle det inte vara några problem att klippa brädet.
Ris. 8. Paradox med att klippa schackbrädet: a) 8×8 = 64; b) 13×5 = 65 |
Tänk nu på en välkänd paradox förknippad med att klippa schackbrädet. Vi skär brädan i fyra delar, som visas i fig. 8, a (i det här fallet är det olönsamt för oss att färga dess fält), och från de resulterande delarna kommer vi att lägga till en rektangel (fig. 8, b). Brädans yta är 64, och ytan på den resulterande rektangeln är 65. När du klippte brädan kom ett extra fält någonstans ifrån!
Lösningen på paradoxen är att våra ritningar inte är helt korrekta (vi ritade medvetet tjocka linjer för att dölja felaktigheter). Med noggrann konstruktion av ritningen i fig. 8b, i stället för rektangelns diagonal, kommer en rombformad, något långsträckt figur att dyka upp med sidor som verkar nästan ha gått samman. Arean av denna figur kommer bara att vara lika med den "extra" enheten.
Den välkända populariseraren av matematik i början av århundradet, E. Ignatiev, kom på "schackbrädemetoden", som gör det möjligt att härleda olika formler. Vi ger två enkla exempel på detta ämne.
Låt oss hitta summan av de första n naturliga talen med hjälp av "schackbrädemetoden". För att göra detta, på brädet (n + 1) × n (i fig. 9, a n = 8) färgar vi alla fälten i den första vertikalen, alla fälten i den andra vertikalen (förutom den översta), tredje vertikalen (förutom de två översta), etc. d., slutligen - botten fält n:te vertikal. Som ett resultat kommer vita och svarta fält på vår tavla att vara lika, nämligen 1 + 2 + ... + n. Eftersom hela brädan består av n (n + 1) fält får vi
2 (1 + 2 + … + n) = n(n + 1),
varifrån följer den välkända formeln för summan av en aritmetisk progression:
1 + 2 + … + n = n(n + 1)/2.
Låt oss nu bevisa följande formel:
8(1 + 2 + ... + n) + 1 = (2n + 1)².
För att göra detta, ta en bräda (2n + 1) × (2n + 1) och måla ett antal av dess fält med svart, som visas i fig. 9, 6 (för fallet n = 5). Uppenbarligen innehåller varje svart del (1 + 2 + ... + n) fält. Utan att ta hänsyn till det centrala fältet har vi här fyra identiska vita och svarta delar. Den obligatoriska formeln följer av det faktum att vår tavla innehåller (2n + 1)² fält och består av ett centralt fält och åtta identiska delar (fyra vita och fyra svarta - Fig. 9b).
När du reder ut paradoxen, såväl som när du bekantar dig med "schackbrädemetoden", kan själva brädet säkert ersättas med ett rutigt papper eller ett bord. Det finns ett stort antal problem med sådana föremål, men deras detaljerade övervägande skulle ta oss för långt bort från schack.
Som avslutning på kapitlet presenterar vi ett gammalt bevis på schackbrädet... för Pythagoras sats. Rita en kvadrat på tavlan, som visas i fig. 10, a. Tavlan är uppdelad i denna kvadrat och fyra kongruenta rätvinkliga trianglar. På fig. 10, 6 ser vi samma fyra trianglar, samt två kvadrater. Så, trianglarna i båda fallen upptar samma område. Följaktligen upptar de återstående delarna av brädet utan trianglar samma område, i fig. 10,a - en kvadrat, och i fig. 10b - två. Eftersom den stora fyrkanten är byggd på hypotenusan av en rätvinklig triangel, och de små kvadraterna är på dess ben, så är "pytagoreiska byxor lika i alla riktningar"!
Naturligtvis, strängt taget, bevisar vårt resonemang inte Pythagoras sats (endast ett särskilt fall studerades), utan bara illustrerar det. Men ett sådant bevis går utan att använda ett schackbräde - för vilken rätvinklig triangel som helst kan du välja en kvadrat som går sönder på liknande sätt.
Det är denna lösning som ges i T. Saatis bok "Integer Optimization Methods and Related Extremal Problems" (M., "Mir", 1973).
S. Golomb. Polyomino. M., Mir, 1974.
Det bevisades av A. Soifer i artikeln "Rutiga brädor och polymipo" ("Kvant", 1972, nr 11); ett antal nya polyominoproblem ges också där.
E. Ignatiev. I uppfinningsrikedomen, eller aritmetiken för alla. Bok. 1 - 3. M. - Pg., Gosizdat, 1923.
6. Det finns 235 tändstickor i en låda. Två spelare tar dem i tur och ordning. I ett drag kan du ta från 1 till 6 matcher. Spelaren vinner
tar sista matchen. Vem vinner när man spelar rätt?
62
7. En hörnruta skärs ut ur en 8 × 8 bräda. Är det möjligt att lägga brädan i 1×3 rektanglar?
8. Av 30 matcher tar två spelare efter eget gottfinnande från 1
upp till 6 matcher. Den som tar sista matchen vinner.
9. Det finns tre stenhögar. Ett tillstånd är en trippel av tal
(x
1
, x
2
, x
3
), där x i
- antalet stenar i den i:te högen. Ett drag är operationen att överföra från hög till hög antalet stenar lika med antalet stenar i högen där överföringen görs. Från det initiala tillståndet (11, 7, 6) få tillståndet (8, 8, 8).
10. Dela cirkeln i maximalt antal delar med fyra raka linjer.
11. Skär det grekiska korset med två raka linjer så att
att bilda en rektangel av de resulterande delarna, vars ena sida är dubbelt den andra.
12. Det finns en 12-liters förråd av vätska och tomma kärl i 9
och 5 l. Det krävs att man mäter exakt 6 liter. Hur många liter kan mätas med sådana kärl från en reserv på 12 liter?
13. Bestäm antalet sekvenser med längden n från (0, 1, 2),
där det inte finns två på varandra följande enheter.
14. Är det möjligt att täcka en 10 × 10 kvadrat med figurer av formen
15. Är det möjligt att täcka en 10 × 10 kvadrat med figurer av formen
63
16. Är det möjligt att täcka en 8×8 kvadrat med en utskuren hörncell med figurer av formen
17. Är det möjligt att täcka med figurer av formen ett 8 × 8 schackbräde där en kvadrat är utskuren:
18. Är det möjligt att lägga ett schackbräde med en snidad hörnbur med bitar av formen
19. Är det möjligt att korsa fyra par riddare med hjälp av en tvåmansbåt, om godsägaren inte kan vara på samma strand med någon annans riddare i frånvaro av sin herre?
20. Utveckla en algoritm för att hitta de två minsta talen i en oordnad följd av n tal.
21. Av 27 matcher som ligger på bordet tar två spelare omväxlande minst en och högst fyra matcher. Vinnaren är den som i slutet av spelet kommer att ha ett jämnt antal matcher. Utveckla en algoritm för den första spelarens spel.
64
22. Två deltagare i spelet turas om att ringa ett nummer från 1 till 10.
När spelaren ringer ett nummer lägger spelaren det till den redan befintliga summan av nummer (när spelaren ringer det första numret lägger spelaren det till noll). Spelaren som får 100 vinner.
Utveckla en algoritm för den första spelarens spel.
23. Hitta det minsta antalet frågor (möjliga svar:
"ja", "nej") ett dolt 5-siffrigt tal, om summan av de tre första siffrorna är 17.
24. Hitta det minsta antalet frågor (möjliga svar:
"ja", "nej") ett dolt 4-siffrigt tal, om summan av den andra och fjärde siffran är 7.
25. På hur många sätt kan 100 rubel bytas ut? mynt i
5, 10, 20 och 50 rubel?
26. Beräkna rekursivt antalet sexsiffriga tal vars summa av de fyra första siffrorna är 26 och summan av de två sista är 14.
27. Beräkna rekursivt antalet partitioner av talet 37 med fem termer, varav den första inte överstiger 7, den andra
- 5, och den tredje och fjärde tar värden från setet
{5, 6, 7, 8}.
28. Beräkna rekursivt antalet sjusiffriga tal vars summa av de fyra första talen är 21 och summan av de fem sista är 19.
29. Beräkna rekursivt antalet partitioner av talet 27 med fyra termer, varav den första inte överstiger 7,
den andra är 8, och den tredje och fjärde tar värden från uppsättningen (3, 5, 7).
30. Beräkna rekursivt antalet femsiffriga tal vars första tre siffror summerar till 21 och de sista tre siffrorna summerar till 12.
65
31. Beräkna rekursivt antalet sjusiffriga tal där summan av den första och tredje siffran är 12 och summan av de återstående fem är 19.
32. Beräkna rekursivt
(2n − 2)(2n − 4) × . . . ×2
(n + 1)(n + 3) × . . . × (n + 2n − 1)
a n−5
b
−(n+3)
33. Beräkna rekursivt antalet sjusiffriga tal vars summa av de fyra första siffrorna är 17 och summan av de tre sista är 16.
34. Beräkna rekursivt antalet partitioner av talet 17 med fyra termer, varav den första inte överstiger 4, den andra - 8, och den tredje och fjärde tar värdena (3, 4, 8).
35. Beräkna rekursivt antalet sjusiffriga tal vars kvadratsumma av de fyra första talen är 17, och summan av kvadraterna av de två sista är 16.
36. Beräkna rekursivt antalet partitioner av talet 25 med fyra termer, varav den första inte överstiger 8,
den andra är 3, och den tredje och fjärde tar värden från uppsättningen (2, 5, 9).
37. Beräkna rekursivt antalet N tornplaceringar på brädet
N × N så att tornen är symmetriska med avseende på båda diagonalerna och inte attackerar varandra.
38. Beräkna rekursivt antalet binära sekvenser av n element där två intilliggande saknas.
39. Givet ett gitter N × M:
66
M
N
A
B
Beräkna rekursivt antalet banor från A till B. En bana är en sekvens av rörelser längs rutnätet som leder från vänster till höger och från botten till toppen.
40. Siffrorna a ges
1
, . . . , en
i en viss ordning. För att beräkna produkten a
1
·. . . en
samtidigt som ordningen på faktorerna bibehålls, finns det många sätt att placera parenteser mellan faktorerna. Beräkna rekursivt antalet sätt att placera parenteser.
41. Beräkna rekursivt antalet 8-siffriga tal vars summa av de första fem siffrorna är 29 och summan av de tre sista siffrorna är 21.
67
3
. algoritmanalysmetoder
3.1. Algoritm klasser
I de tidigare avsnitten har vi övervägt olika tillvägagångssätt som kan användas vid konstruktionen av algoritmer. För att hitta en lösning, för att analysera effektiviteten av denna lösning, kan man lägga fram olika antaganden, använda redan kända andra algoritmer, omformulera problemets tillstånd etc. Du kan leta efter några liknande problem med en känd lösning och använda den här lösningen för att hitta en algoritm för det nödvändiga problemet.
Det finns dock många speciella problem som man har hittat lösningar på. Det finns ännu fler uppgifter olösta eller lösta med vissa restriktioner och villkor. Att leta efter liknande problem bland hela uppsättningen av problem, att utvärdera befintliga lösningar efter deras grad av "lämplighet" kan vara ett svårt, tidskrävande och inte alltid lösbart problem. Det skulle vara mer användbart och produktivt att försöka definiera klasser av problem förenade av ett gemensamt problem, gemensamma metoder och tillvägagångssätt för att lösa, och sedan leta efter den klass som vårt specifika problem som behöver lösas kan hänföras till. Naturligtvis ska det inte finnas för många sådana klasser, men å andra sidan ska det inte vara för få av dem, så att varje ny uppgift definiera din egen, nya klass, som då sannolikt inte kommer att användas för att lösa andra problem.
Som ett exempel på ett problem som tillhör en viss klass, betrakta det välkända problemet med att identifiera ett falskt mynt.
Uppgift 3.1 (problem om falska mynt). Det finns n mynt,
bland vilka det kan finnas en falsk. Det falska myntet skiljer sig från resten i vikt och vi har en våg med två koppar till vårt förfogande. Det är nödvändigt att fastställa ett falskt mynt för det minsta antalet vägningar eller att fastställa,
att det inte finns några förfalskade mynt.
68
Lösning. Problemet med falska mynt löstes i Sec. 2.2,
men då var det känt att ett falskt mynt med nödvändighet var lättare. Låt oss nu försöka lösa detta problem för ett mer allmänt fall. Någon lösning på detta problem (inte nödvändigtvis optimal)
kan tolkas som en sekvens av vägningar. Det är dock tydligt att valet av mynt för vägning i vilket steg som helst beror på vilka mynt som användes och resultatet av vägningen i de tidigare stegen. Vi kommer att avbilda vägningssekvensen enligt följande. Vi numrerar om mynten och definierar dem som en uppsättning S = (1, 2, . . . , n). Uppsättningarna med antal mynt som vägs på vågens vänstra och högra panna kan betecknas med S
L
och S
R
respektive. Det är tydligt att viktning endast är meningsfull om kardinaliteterna för uppsättningarna S
L
och S
R
match, dvs. Varje våg har samma antal mynt. Vägningen kommer att betecknas med tecknet ":", sedan varje vägning
(S
L
) : (S
R
) det finns tre möjliga utfall. Massor av mynt
S
L
kan vara lättare, tyngre eller ha samma vikt som setet S
R
. Då kommer vi att beteckna dessa viktningsutfall som
"" respektive "=". Ett exempel på vägningar för fyra mynt visas i fig. 3.1. Ovaler representerar vägningar, rutor representerar utfall, anger det falska myntnumret och om det är lättare eller tyngre än de andra.
Fallet med inget falskt mynt indikeras som "0", överstrukna rutor motsvarar fall som inte kan inträffa.
Vi kommer att uppskatta det maximala antalet vägningar som krävs för att lösa problemet, d.v.s. värsta fall. Som framgår av fig. 3.1, problemet löses i 3 vägningar i värsta fall. Observera att även i bästa fall behöver vi minst 2
vägning. Kan ett bättre resultat uppnås?
På fig. 3.1 presenterar en annan lösning på problemet med att väga fyra mynt. I det första steget väger vi inte ett par mynt, utan alla mynt, och delar upp dem i två uppsättningar. Som ett resultat har vi uppnått att i bästa fall endast en vägning behövs,
men i värsta fall är antalet vägningar återigen 3.
69
(1) : (2)
(1) : (3)
(1) : (4)
0 4 T
4 L
3 T
3 L
(1) : (4)
2 T
1 L
(1) : (4)
2 L
1 T
=
=
=
>
>
>
>
>
=
=
Ris. 3.1. Löser problemet med falska mynt
Observera att, till skillnad från det första vägningsalternativet,
visad i fig. 3.1, i den andra versionen, definierade vi inte bara vägningsschemat, utan introducerade också ett nytt koncept för falska myntkandidater. Tänk faktiskt på resultatet av den första vägningen, (1, 2): (3, 4). Låt (1, 2) L
= (1, 2) och S
R
= (3, 4). Sedan
S
L
R
. Av detta resultat är det inte möjligt att bedöma om det förfalskade myntet är lättare eller tyngre än alla andra,
och i vilken uppsättning det är. Det kan dock antas
(och ännu mer exakt - det kan hävdas) att om ett förfalskat mynt tillhör uppsättningen S
L
, då är det förfalskade myntet lättare än de andra, vi betecknar en sådan uppsättning med bokstaven L. I vårt fall, om mynt med nummer 1 eller 2 är förfalskade, så är de lättare än riktiga. Om de förfalskade mynten med nummer 3 eller
4, då de är tyngre än verkliga, kommer vi att beteckna motsvarande mängd med bokstaven T. I fig. 3.2 lätta och tunga förfalskade kandidater indikeras med markeringar på trädets kanter.
Uppenbarligen kan man svara på frågan om det optimala antalet vägningar genom att fortsätta att sortera igenom de möjliga systemen för val av mynt. Eftersom antalet mynt är begränsat kan en sådan uppräkning förr eller senare göras. Låt oss för närvarande uppehålla oss vid de två lösningarna som erhållits och försöka analysera vad de gav
70
(1.2) L
(3.4) T
(1.2) T
(3.4) L
(1,2) : (3,4)
(3) : (4)
4 T
3 T
(1) : (2)
1 L
=
=
>
>
>
=
0 2 L
(3) : (4)
3 L
4 L
(1) : (2)
2 T
=
>
>
=
1 T
Ris. 3.2. En annan lösning på problemet med ett förfalskat mynt till oss ur synvinkeln av en allmän strategi för att lösa problemet.
Som bekant kan vilken myntvägningsstrategi som helst beskrivas med hjälp av ett ternärt eller ternärt träd. Med andra ord, det aktuella problemet tillhör klassen av problem,
beskrivs av ternära träd. En sådan klassificering av problemet gör det möjligt att analysera inte varje specifik lösning, utan alla lösningar i allmänhet, baserat på trädens kända egenskaper.
Alltså, iterationen över möjliga sätt viktning är faktiskt en sökning genom olika ternära träd, av vilka det naturligtvis finns exponentiellt många. Å andra sidan, låt oss försöka avgöra vad som generellt är möjligt att uppnå när man löser ett givet problem, med hjälp av dess tillhörighet till just denna klass.
Från fig. 3.1 och 3.2, kan det ses att, som visar sekvensen av vägningar med hjälp av ett träd, tillskriver vi varje vägning till en trädpunkt som inte är ett löv (avbildad med ovaler), medan utfall, inklusive omöjliga,
motsvarade trädets löv (visas med rutor). Alla trädnoder kan sorteras efter nivåer,
71
PÅ
a
=
=
>
PÅ
a
Och
Och
Och
=
>
PÅ
a
Och
Och
Och
=
>
PÅ
a
Och
Och
Och
=
>
PÅ
a
Och
Och
Och
=
>
PÅ
a
=
>
PÅ
a
=
>
PÅ
a
>
Till
PÅ
L
På
0
På
1
På
l
-
1
På
l
……
………………
………
…
…
……
…
…
…
…
…
……
……
…
…
G
a =
l
Ris.
3.3.
T
vernal vikt träd
72
de där. på deras avstånd från trädets rot. Nivåtalet är lika med antalet kanter som måste passera från roten för att komma till vertexet. given nivå(Fig. 3.3). Om trädets djup är bladets nivå längst bort från roten, är detta värde lika med antalet viktningar i värsta fall.
Hur många möjliga utfall finns det i vårt problem? Vart och ett av de n mynten kan visa sig vara ett falskt lätt eller falskt tungt mynt, och det kanske inte finns några falska mynt alls.
Således har vi 2n + 1 utfall. Det betyder att i trädet
motsvarande vägningsschemat, måste vara minst
2n + 1 blad. Ett ternärt träd med djup l innehåller högst,
än 3
jag lämnar. Utifrån detta kan vi uppskatta minsta möjliga djup på trädet
3
l
≥ 2n + 1,
och följaktligen
l ≥ logga
3
(2n + 1).
(3.1)
Således, för n = 4, är det minsta möjliga antalet vägningar större än eller lika med 2. Här menar vi inte det minsta antalet vägningar för detta schema - som i fig. 3.2, och det finns fall när lösningen på problemet redan finns efter den första vägningen - vi utvärderar det sämsta alternativet, d.v.s. det maximala antalet viktningar för ett givet schema, med andra ord letar vi efter ett minimum bland de maximala djupen för alla träd med minst 2n + 1 löv.
Det kan dock visas att det inte finns någon viktningsmetod som skulle ge likhet i skattningen (3.1).
SAT 3.1
Antalet vägningar i värsta fall för problemet med falska mynt uppskattas till l > log
3
(2n + 1).
Bevis. Som redan nämnts, för n mynt finns det 2n + 1 möjliga utfall. Varje vägning kan ha tre möjliga resultat, och varje resultat har sitt eget
73
ytterligare vägningar. Samtidigt har schemat sitt eget antal möjliga utfall, med hänsyn till resultatet av den senaste vägningen. Låt vid första vägningen |S
L
| = |S
R
| = k, dvs.
k-mynt används på en skala och k-mynt på den andra,
där k ≤ n/2 . Om samtidigt S
L
R
, sedan mynt från S
L
vi förklarar kandidater för lätta förfalskade mynt och mynt från S
R
- Kandidater för tunga förfalskade mynt. På det här sättet,
med resultatet av den första vägningen är 2k utfall möjliga.
På samma sätt för S
L
>S
R
2k andra resultat är möjliga. Därför, för S
L
=S
R
de återstående 2n + 1 − 4k utfallen är möjliga.
Om jämlikhet håller i sig (3.1) betyder det att det ternära trädet är komplett och alla dess löv är på l:te nivån.
Men för detta är det nödvändigt att efter varje vägning fördelas de möjliga resultaten jämnt över de tre grenarna och jämlikheten
2k = 2n + 1 − 4k,
vilket är omöjligt eftersom 2k alltid är ett jämnt tal, och
2n + 1 − 4k är alltid udda.
En viktig idé användes i beviset för sats 3.1:
För att viktningsträdet ska vara optimalt, eller åtminstone så nära optimalt som möjligt, krävs att utfallen fördelas jämnt över alla resultat av varje vägning.
Således har vi fått en uppskattning för det sämsta antalet vägningar i problemet med falska mynt genom att relatera detta problem till problemklassen
beskrivs av ternära träd. Tänk nu på ett något modifierat problem.
Uppgift 3.2 (problem om ett falskt mynt i närvaro av en standard). Det finns n mynt, bland vilka det kan finnas ett falskt, och ytterligare ett mynt, om vilka man med säkerhet vet att det är äkta. Det är nödvändigt att fastställa det förfalskade myntet i det minsta antalet vägningar eller fastställa att det inte finns några förfalskade mynt.
74
Lösning. Detta problem skiljer sig från det föregående genom närvaron av ett ytterligare referensmynt, men det visar sig att detta extramynt tillåter en att konstruera optimala viktträd för vilka likheten i (3.1) är uppfylld. Beteckna med n l
det antal som jämställdheten gäller
3
l
= 2nl
+ 1.
(3.2)
När vi betraktar det tidigare problemet i sats 3.1 har vi fått fram: för att likhet (3.1) ska vara uppfylld måste viktningsträdet vara komplett. Därför, om det är möjligt att bygga ett sådant optimalt träd med l nivåer, kommer det att specificera ett schema med l vikter för n l
mynt. Observera att följande förhållande är sant:
n l
= 3nl−1
+ 1.
(3.3)
Sedan för n
0
= 0 tum (3.2) får vi likheten, 3 0
= 2 0 + 1,
sedan härifrån med hjälp av (3.3) kan vi få n
1
= 1,n
2
=
4,n
3
= 13 osv. Lösning (3.2) är sekvensen
0, 1, 4, 13, 40, . . ..
Sålunda, när likhet (3.2) gäller, kommer mängden av n
l mynt delas i tre lika delar med n l−1
mynt och det finns fortfarande ett mynt kvar. Låt oss överväga olika situationer som kan uppstå under vägningsprocessen.
Schema 1. Låt i början av vägningen ha n i
mynt, där n i
tillhör sekvensen (3.3) för vissa i. Låt oss sätta n i−1
mynt, där n
i
= 3n i−1
+ 1,
sedan lägger vi till ett referensmynt till den vänstra delen av skalan, och ett av de återstående n i−1
+ 1 mynt. Beteckna de viktade uppsättningarna, som tidigare, med S
L
och S
R
Låt nu som ett resultat av vägning S
L
=S
R
. Eftersom referensmyntet deltog i vägningen är det uppenbart att det falska myntet, om det finns något, är bland de oanvända n
i−1
mynt, och problemet reduceras till ett problem med n i−1
mynt. Vart i
75
Som ett resultat av viktningen har vi fortfarande 2n i−1 möjligt
+ 1 =
3
i−1
resultat. Låt nu S
L
R
. Det betyder att det förfalskade myntet antingen finns i uppsättningen S
L
och samtidigt är den lättare än de andra, eller i uppsättningen S
R
och då är den tyngre än de andra.
Dessutom finns det n i−1
misstänkta lätta mynt och n i−1
+ 1 misstänkt tung och tillsammans ger detta återigen 2n i−1
+ 1 = 3
i−1
möjliga resultat.
Låt slutligen S
L
>S
R
. Då har vi n i−1
tunga myntkandidater och n i−1
+1 kandidater för lungor och totalt 2n i−1
+1 =
3
i−1
resultat. Så med ett sådant schema för den första vägningen får vi faktiskt den 3:an
De initiala resultaten var jämnt fördelade enligt resultaten av vägningen. För att avgöra om det är möjligt att ställa in vägningsschemat så att resultatet efter varje vägning delas upp i lika många delar, överväg vägningsresultaten. Uppenbarligen för S
L
=S
R
vi kommer fram till samma problem, bara med en mindre dimension, och vi kan alltid utföra viktningen enligt schema 1 igen, men med ett mindre värde på i.
Schema 2. Låt nu S
L
R
. I det här fallet definierar vi viktningsstrategin enligt följande. De initiala uppgifterna är att vi vid något steg i i sekvensen av viktningar har 3
i
= 2n i
+ 1 mynt, bland vilka n i
lätta förfalskade kandidater och n i
+ 1 kandidater för tunga, medan antalet n i
är ett nummer av formen (3.3)
n i
= 3n i−1
+ 1.
Sätt på varje skalpanna n i−1
lätta kandidater och n
i−1
+1 tung. Eftersom det bara finns 2n i
+1 = 2(3n i−1
+1)+1 = 6n i−1
+3
mynt, och väga
2n i−1
+ 2n i−1
+ 2 = 4n i−1
+ 2
mynt, så finns det fortfarande 2n i−1
+ 1 mynt, bland vilka n i−1
+ 1
lungor och n i−1
tung. Eftersom det finns samma antal lätta och tunga mynt på båda vågorna, så om vågen inte är balanserad,
detta ger n i−1
kandidater till lätta mynt (från skålen som visade sig vara lättare) och n i−1
+ 1 kandidater för tung (från skålen som visade sig vara
76
tyngre). Detta för oss till de ursprungliga uppgifterna för samma schema
(schema 2), men för 3
i−1
= 2n i−1
+ 1 mynt. Om vågen är balanserad betyder det att vi måste leta efter ett falskt mynt bland ovägda n i−1
+ 1 lungor och n i−1
tunga mynt, vilket motsvarar Schema 3. Uppenbarligen 2n i−1
+1-resultat, dvs. återigen delas uppsättningen av alla möjliga utfall upp i tre lika delar.
Schema 3. Låt nu S
L
>S
R
. I det här fallet har vi 3
i
=
2n i
+ 1 mynt, bland vilka n i
+ 1 tända falska kandidater, och n i
tungviktskandidater. Alla argument liknar Schema 2, med skillnaden att när du väger måste du sätta n i−1
+ 1 lätta kandidater, och n i−1
tung. Om vågen inte är balanserad ger detta oss återigen mönster 3 för 3
i−1
mynt, annars får vi villkoren för vägning som motsvarar Schema 2. Återigen, i alla fall delas uppsättningen av möjliga utfall upp i tre lika delar av 2n i−1
+ 1.
Vi har alltså tre gånger
1 2
3
=
>
=
=
Ris. 3.4. Övergångar mellan viktningsscheman i det personliga statens problem med falska mynt som beskrivs ovan och viktningsregeln för varje stat. Beroende på vägningsresultatet går vi till ett annat tillstånd (eller förblir i samma tillstånd), men för ett mindre antal mynt. Vid varje vägning fördelas antalet möjliga utfall jämnt enligt vägningens resultat. Schemat för övergångar mellan tillstånd visas i fig. 3.4. Ett exempel på vägningar för 27 mynt visas i fig. 3.5.
77
Uppgift 1: Kan en 5 × 5 kvadrat skäras till 1 × 2 rektanglar (dominoer). Uppgift 2: Motsatta hörnrutor skärs från ett 8×8 schackbräde. Kan resten skäras till 1 × 2 rektanglar (dominoer)? Lösning: Nej. Varje domino har en svart och en vit ruta, och det finns olika antal svarta och vita rutor på brädet utan hörn. Uppgift 3: Från motsatta hörn av en 10 × 10 bräda skärs två 3 × 3 rutor ut. Kan resten skäras till dominobrickor? Uppgift 4: Kom på en ansluten pjäs på ett schackbräde, där det finns lika många svarta och vita celler, men som inte kan delas upp i dominobrickor. Uppgift 5:Är det möjligt att skära en 10 × 10 kvadrat i 25 bitar? Uppgift 6:Lösning: Färglägg tavlan i ett rutmönster. Det kommer att finnas ett jämnt antal svarta celler, och en eller tre av dem kommer att falla in i varje figur. Uppgift 7:Är det möjligt att skära en 10 × 10 kvadrat i 25 bitar? Lösning:
Färglägg tavlan i fyra färger (se bild). Varje figur upptar en cell av varje färg, och cellerna i den första och andra färgen har olika nummer.
Riktning: Färglägg tavlan i tre färger.
Uppgift 12: Vad är det maximala antalet 1 × 1 × 4 staplar som kan skäras från en 6 × 6 × 6 kub? Uppgift 13: Rektangeln är indelad i figurer och . En av de förlorade, men ersatte den med. Bevisa att den nya uppsättningen inte kan täcka den ursprungliga rektangeln. Uppgift 14: Kan en 16 × 16 kvadrat delas upp i 64 1 × 4 rektanglar, varav 31 kommer att vara vertikala och de återstående 33 horisontella? Lösning: Färg var fjärde vertikal. Uppgift 15: För vilket n kan kvadraten n × n delas upp i a) ;b)? Lösning: För n delbart med fyra.
Uppgift 16: En m × k rektangel är uppdelad i 1 × n rektanglar. Bevisa att m är delbart med n eller k är delbart med n.c) för varje n. Lösning:
Färg i n färger.
Uppgift 17: Bevisa att en m × n rektangel kan delas upp i a × b rektanglar om och endast om följande villkor är uppfyllda:1) m och n representeras som ka + lb (k och l är icke-negativa heltal)
2) m och n är delbara med a.
3) m eller n är delbart med b.
Uppgift 18: En m × n rektangel kallas stark om den kan delas upp i dominobrickor på ett sådant sätt att varje snitt av rektangeln skär minst en domino. Bevisa det:a) 2 × n rektangel - ömtålig
b) 3 × n rektangel - ömtålig
c) 4 × n rektangel - ömtålig
d) 5×6 och 6×8 rektanglar - starka
e) om en m × n rektangel är stark, så är en m × (n + 2) rektangel också stark.
f) * 6×6 rektangel - ömtålig
g) Vilka rektanglar är starka och vilka är inte? Lösning: f) Tips: Varje linje i en 6×6 ruta korsar ett jämnt antal dominobrickor.
g) Alla m × n rektanglar där mn är jämn, m,n ≥ 5, förutom 6 × 6.
Uppgift 19:Ett hörn är en figur av formen.
a) Kan en 5 × 9 rektangel brytas upp i hörn?
b) Bevisa att en rektangel med sidor större än 100 och area delbar med 3 kan brytas upp i hörn.
c) Vilka rektanglar kan delas i hörn och vilka kan inte?
Uppgift 20:Kan en 2 n × 2 n bräda utan hörnruta delas upp i hörn? Lösning: Jo det kan du. Skiljeväggen är konstruerad genom induktion.
Uppgift 21: För vilket n kan en tavla (2n + 1) × (2n + 1) utan hörncell delas upp i dominobrickor, bland vilka det finns lika vertikala och horisontella? Lösning: För även n.
