Eine logische Aufgabe zum Platzieren von Dominosteinen auf einem Schachbrett. Mathematische Olympiaden und Olympiadenprobleme
Gegeben sei ein 8×8 Schachbrett, aus dem zwei diagonal gegenüberliegende Ecken geschnitten wurden, und 31 Dominosteine; Jeder Dominostein kann zwei Felder auf dem Brett bedecken. Ist es möglich, das ganze Brett mit Knochen zu pflastern? Begründen Sie Ihre Antwort.
Lösung
Auf den ersten Blick scheint dies möglich zu sein. Das Brett ist 8×8, also gibt es 64 Zellen, wir schließen zwei aus, was bedeutet, dass 62 übrig bleiben.Es scheint, dass 31 Knochen passen sollten, richtig?
Wenn wir versuchen, Dominosteine in der ersten Reihe anzuordnen, stehen uns nur 7 Felder zur Verfügung, ein Knochen kommt in die zweite Reihe. Dann legen wir Dominosteine in die zweite Reihe, und wieder kommt ein Stein in die dritte Reihe.
Es wird immer einen Bone in jeder Reihe geben, der in die nächste Reihe verschoben werden muss, egal wie viele Layouts wir versuchen, wir werden niemals in der Lage sein, alle Bones anzulegen.
Das Schachbrett ist in 32 schwarze und 32 weiße Felder unterteilt. Durch Entfernen der gegenüberliegenden Ecken (beachten Sie, dass diese Zellen dieselbe Farbe haben) bleiben 30 Zellen einer Farbe und 32 Zellen einer anderen Farbe übrig. Angenommen, wir haben jetzt 30 schwarze und 32 weiße Quadrate.
Jeder Würfel, den wir auf das Brett legen, belegt ein schwarzes und ein weißes Feld. Daher besetzen 31 Dominosteine 31 weiße und 31 schwarze Felder. Aber es gibt nur 30 schwarze und 32 weiße Felder auf unserer Tafel. Daher ist es unmöglich, die Knochen zu zersetzen.
Die Analyse stammt aus der Übersetzung des Buches von G. Luckman McDowell und dient nur zu Informationszwecken.
Wenn es Ihnen gefallen hat, empfehlen wir Ihnen, das Buch zu kaufen.
Beweisen Sie, dass das Schachbrett 10 istX10 kann nicht entlang der Rasterlinien in Rechtecke 1 geschnitten werdenX4. (Lösungen nach D.Yu. Kuznetsov.)
Lösung 1 . Teilen Sie das Brett in 2x2 Quadrate und färben Sie sie in einem Schachbrettmuster (Abb. 1). Beachten Sie, dass jedes 1x4-Rechteck gleichermaßen (2) schwarze und weiße Felder enthält, aber mit dieser Färbung gibt es 52 schwarze Felder und 48 weiße Felder auf dem Brett, d.h. nicht gleich. Das bedeutet, dass es nicht möglich ist, ein 10x10-Brett in 1x4-Rechtecke zu schneiden.
Lösung 2 . Färben wir das Brett mit einer diagonalen Färbung in 4 Farben (Abb. 2). Beachten Sie, dass jedes Rechteck eine Zelle jeder der vier Farben enthält, aber bei einer gegebenen Farbe gibt es 25 Zellen der 1. und 3. Farbe auf dem Brett, 26 Zellen der 2. und 24 Zellen der 4., d.h. nicht gleich. Das bedeutet, dass es nicht möglich ist, ein 10x10-Brett in 1x4-Rechtecke zu schneiden.
1. Schneiden Sie die unteren rechten und linken Eckzellen aus dem Schachbrett aus. Ist es möglich, die resultierende Figur in 1x2-Dominos zu schneiden? Und wenn Sie unten rechts und oben links schneiden?
2. Ist es möglich, ein 6x6-Brett so in Dominosteine zu schneiden, dass genau 11 horizontale darunter sind? (Horizontale Färbung in zwei Farben.)
3. Malen Sie die Zeichnung in vier Farben aus, sodass benachbarte Teile in verschiedenen Farben bemalt sind. Kann man mit drei Farben auskommen? (Siehe Aktivität 6: Ausmalen geografische Karte- Klasse 5-6).
4. In einem 4x4-Quadrat sind die Zellen der linken Hälfte schwarz und der Rest weiß gestrichen. In einem Vorgang ist es erlaubt, alle Zellen innerhalb eines beliebigen Rechtecks in der entgegengesetzten Farbe neu einzufärben. Wie bekommt man in drei Arbeitsgängen eine Schachfärbung aus der Originalfärbung?
5. Mehrere Heuschrecken sitzen auf derselben geraden Linie, und die Abstände zwischen Nachbarn sind gleich. Jede Minute springt einer von ihnen zu einem Punkt, der in Bezug auf eine andere Heuschrecke symmetrisch dazu ist. Kann der Grashüpfer Sasha nach einiger Zeit dort landen, wo am Anfang seine Nachbarin Lyosha saß?
6. a) Ist es möglich, ein Schachbrett in Figuren zu schneiden, die aus 4 Feldern in Form des Buchstabens „T“ bestehen?
b) Ist es möglich, ein 10x10-Schachbrett in solche Figuren zu schneiden?
7. Ist es möglich, ein 8x8-Quadrat mit einer abgeschnittenen Ecke in 1x3-Rechtecke zu teilen?
8. Kann ein 10x10-Brett in Stücke von vier Zellen in Form des Buchstabens „G“ geschnitten werden? (Horizontale Färbung in zwei Farben.)
9. Ein 8x8-Brett wird in 2x1-Dominos geschnitten. Kann es 15 vertikale und 17 horizontale Dominosteine geben?
10. Das Dreieck wird in Dreiecke (25 Teile) unterteilt, wie in der Abbildung gezeigt. Der Käfer kann in einem Dreieck laufen und sich zwischen benachbarten (an der Seite) Dreiecken bewegen. Wie viele Dreiecke kann der Käfer maximal passieren, wenn er jedes Dreieck höchstens einmal besucht hat?
11. Wie viele Rauten, die jeweils aus zwei gleichseitigen Dreiecken mit der Seite 1 bestehen, können aus einem gleichseitigen Dreieck mit der Seite 5 (siehe Abbildung der vorherigen Aufgabe) am meisten herausgeschnitten werden?
12. Die dreieckige Burg ist in 100 identische dreieckige Hallen unterteilt. In der Mitte jeder Wand befindet sich eine Tür. Wie viele Räume kann eine Person besuchen, die nirgendwo mehr als einmal hingehen möchte?
Kapitel 2
Für eine detaillierte Darstellung der Schachmathematik, die wir gleich beginnen werden, ist es am natürlichsten, damit zu beginnen Mathe Problemeüber das Brett selbst, ohne noch Figuren darauf zu legen. Diesem Thema ist dieses Kapitel gewidmet.
Betrachten wir zunächst einige Probleme beim Abdecken eines Spielbretts mit 2 × 1 Dominosteinen. Überall wird angenommen, dass jeder Dominostein zwei Felder des Spielbretts bedeckt und jedes Feld von einer Hälfte der Steine bedeckt ist. Beginnen wir mit dem nächsten alten Problem.
Kann man mit Dominosteinen ein Quadrat der Größe 8×8 belegen, aus dem gegenüberliegende Eckzellen ausgeschnitten werden (Abb. 2a)?
Wir könnten algebraisches Denken verwenden, aber die „Schach“-Lösung ist sowohl einfacher als auch eleganter. Färben wir unser abgeschnittenes Quadrat schwarz und weiß und verwandeln es in ein Schachbrett ohne zwei Eckfelder a8 und h1 (Abb. 2b). Für jede Abdeckung des Bretts bedeckt jeder Dominostein ein weißes und ein schwarzes Quadrat. Wir haben zwei weiße Felder weniger als schwarze (die geschnittenen Felder sind weiß), und daher ist die erforderliche Abdeckung nicht vorhanden! Wie wir sehen können, erleichtert die Farbgebung des Bretts einem Schachspieler nicht nur die Navigation während des Spiels, sondern dient auch als Mittel zur Lösung mathematischer Probleme.
Bei der betrachteten Aufgabe war es wichtig, dass Eckfelder nicht aus dem Brett ausgeschnitten wurden, sondern dass sie die gleiche Farbe hatten. Es ist klar, dass Sie, egal wie Sie ein Paar einfarbiger Felder ausschneiden, den Rest des Bretts nicht mit Dominosteinen bedecken können. Somit tritt das folgende Problem auf.
Nehmen wir nun an, dass zwei verschiedenfarbige Felder auf dem Schachbrett ausgeschnitten sind. Ist es immer möglich, den Rest des Bretts mit 31 Dominosteinen zu bedecken?
Das stellt sich immer wieder heraus. Ein spektakulärer Beweis wurde von dem berühmten amerikanischen Mathematiker R. Gomory gefunden. Zeichnen wir auf dem Schachbrett die Grenzen zwischen Vertikalen und Horizontalen, wie in Abb. 3. In dem Labyrinth zwischen diesen Grenzen folgen schwarze und weiße Felder aufeinander, die sich wie zweifarbige Knöpfe auf einem geschlossenen Faden abwechseln (der Weg, auf dem dieses Labyrinth umgangen werden kann, ist geschlossen). Welche zwei verschiedenfarbigen Felder auch immer wir aus dem Brett ausschneiden, der Faden reißt: an einer Stelle, wenn die ausgeschnittenen Felder nebeneinander liegen, und an zwei anderen Stellen. In diesem Fall besteht jedes Fadenstück aus einer geraden Anzahl von Feldern. Folglich können diese Steine und damit das gesamte Brett mit Dominosteinen bedeckt werden!
Reis. 3. Labyrinth Gomori |
Kuriose Ideen rund um Knöpfe und Fäden finden Sie in Kapitel 11.
Angenommen, einige Felder werden aus einem Schachbrett ausgeschnitten, sodass auf dem verbleibenden Teil keine Dominosteine platziert werden können. Es ist leicht zu überprüfen, dass die kleinste Anzahl ausgeschnittener Felder mit dieser Eigenschaft 32 ist - das sind alles Felder der gleichen Farbe (weiß oder schwarz).
Die Schachbrett- und Dominoprobleme sind nur ein kleiner Teil einer riesigen Reihe von Problemen dieser Art. Der amerikanische Mathematiker S. Golomb hat eine ganze Wissenschaft geschaffen, die er Polymipo nannte, und sein Buch zu diesem Thema wurde in viele Länder der Welt übersetzt, einschließlich unseres. Im Allgemeinen ist ein Polyomino eine einfach zusammenhängende Figur, die aus Quadraten besteht. Aus der Sicht eines Schachspielers bedeutet die einfache Verbindung, dass alle Polyomino-Felder von einem Turmzug umgangen werden können. Abhängig von der Anzahl der Quadrate gibt es 07 Polyominos in unterschiedlichen Qualitäten. Ein Monomino enthält ein Quadrat, ein Domino zwei, ein Tromino drei, ein Tetramino vier, ein Pentomino fünf, ein Heptomino sechs Quadrate und so weiter. Wir werden auf einige weitere Probleme im Zusammenhang mit dem gewöhnlichen Schachbrett eingehen. Offensichtlich ist es unmöglich, den dssk nur mit geraden Trominos zu bedecken, d. h. Dominos 3 × 1, da 64 nicht durch 3 teilbar ist. Das folgende Problem tritt auf.
Ist es möglich, ein Schachbrett mit 21 geraden Trominos und einem Monomino zu bedecken? Wenn ja, welche Felder kann ein Monomino besetzen?
Eine der notwendigen Dapo-Beschichtungen in Abb. 4a. Um die möglichen Anordnungen von Monominos zu bestimmen, zeichnen wir zwei Systeme paralleler Linien auf die Tafel, wie in Abb. 4b.
Es ist leicht zu erkennen, dass bei jeder Überdeckung jedes Tromino genau ein Feld abdeckt, durch das die durchgezogene Linie verläuft, und genau eines, durch das die gestrichelte Linie verläuft. Da die Anzahl der Felder, die von durchgezogenen Linien geschnitten werden, 22 beträgt, sowie die Anzahl der Felder, die von gestrichelten Linien geschnitten werden, und es 21 Posaunen gibt, können Monominos nur Felder abdecken, die von beiden Linienfamilien geschnitten werden. Und es gibt nur vier solcher Felder: c3, c6, f3 und f6! Indem Sie die Tafel um 90, 180 und 270° drehen, können Sie für jedes dieser vier Felder die passende Abdeckung erhalten.
Die nächste Aufgabe unterscheidet sich etwas von den oben besprochenen.
Ist es möglich, ein Schachbrett so mit Dominosteinen zu bedecken, dass es unmöglich ist, eine einzige Grenze zwischen Vertikalen und Horizontalen zu ziehen, ohne die Dominosteine zu überqueren?
Wenn wir uns vorstellen, dass das Brett eine Wand ist und Dominosteine Ziegelsteine sind, weist das Vorhandensein der angegebenen Grenze (Naht) auf ein zerbrechliches Mauerwerk hin. Mit anderen Worten, das Problem fragt, ob es möglich ist, die "Ziegel" so anzuordnen, dass die "Mauer" nicht zusammenbricht. Ein Rechteck, das in der gewünschten Weise abgedeckt werden kann, wird als "stark" bezeichnet. Die „Stärke“ des Schachbretts ist in Abb. 5. Im allgemeinen Fall zeigt Gardner, dass Dominosteine zu einem "starken" Rechteck gefaltet werden können, wenn ihre Fläche gleichmäßig ist und ihre Länge und Breite größer als vier sind, mit der einzigen Ausnahme, dass es sich um ein 6 × 6-Quadrat handelt.
Im Folgenden werden wir uns oft mit rechteckigen Schachbrettern der einen oder anderen Größe befassen. Dabei wird immer davon ausgegangen, dass ein m×n Brett m Vertikale und n Horizontale hat (Schach). Wir sagen, dass ein Brett "gerade" ist, wenn die Anzahl seiner Felder gerade ist, und ansonsten "ungerade". Wo die Abmessungen des Bretts nicht angegeben sind, meinen wir das Standardschachbrett, für das m = n = 8 ist.
Das 100x4-Brett ist mit Dominosteinen bedeckt. Beweisen Sie, dass es entlang einer der Grenzen zwischen Vertikalen und Horizontalen geschnitten werden kann, ohne die Dominosteine zu beeinträchtigen.
Jede der angegebenen Grenzen teilt das Brett in zwei Teile, die aus einer geraden Anzahl von Feldern bestehen. Wir unterteilen die Felder jedes Teils in zwei Klassen: bedeckte Dominosteine, die vollständig in diesem Teil liegen, und bedeckte Dominosteine, die von der Grenze geschnitten werden. Da die Anzahl der Felder jedes Teils gerade ist (vielleicht null), ebenso wie die Anzahl der Felder der ersten Klasse (jeder Domino bedeckt zwei Felder), ist die Anzahl der Felder der zweiten Klasse gerade. Und das bedeutet, dass die Anzahl der von der Grenze überquerten Dominosteine gerade ist. Es gibt insgesamt 102 Trenngrenzen (99 vertikal und 3 horizontal), und wenn jede von ihnen Dominos kreuzt, nehmen mindestens 102 × 2 = 204 Dominos an der Abdeckung teil. Wir haben nur 200 davon! Tatsächlich haben wir gezeigt, dass ein 100x4-Rechteck "schwach" ist.
Die Frage nach der Möglichkeit, ein beliebiges rechteckiges Brett mit linearen k-Minos (Dominos k × 1) zu bedecken, wird durch den folgenden Satz gelöst.
Ein m×n-Brett kann genau dann mit linearen k-Minos belegt werden, wenn mindestens eine der Zahlen m oder n ohne Rest durch k teilbar ist.
Wir illustrieren den Satz mit folgendem Beispiel.
Ist es möglich, ein 10x10-Brett (auf einem solchen Brett werden hundert quadratische Dame gespielt) mit geraden Tetraminos zu bedecken?
Ein gerades Tetramino hat die Maße 4x1, was bedeutet, dass im Prinzip 25 Plättchen alle Felder unseres Spielplans bedecken könnten. Aus dem Satz folgt jedoch, dass dies unmöglich ist – 10 ist nicht durch 4 teilbar.
Betrachten wir noch ein paar weitere Probleme mit dem Schachbrett. Bei der Lösung des folgenden Problems wird viovb seine Färbung verwendet.
Lassen Sie das Brett aus einer ungeraden Anzahl von Feldern bestehen. Auf jedes seiner Felder werden wir einige legen Schachfigur. Ist es möglich, alle diese Teile auf benachbarte Felder (vertikal oder horizontal) zu verschieben, sodass keine zwei von ihnen auf demselben Feld landen?
Die Aufgabe ist unmöglich. In der Tat, wenn die angegebene Verschiebung von Steinen vorhanden wäre, dann würde jeder "weiße" Stein (der auf einem weißen Feld steht) "schwarz" werden (auf ein schwarzes Feld fallen) und jeder "schwarze" - "weiß".
Somit würde das Brett aus der gleichen Anzahl weißer und schwarzer Felder bestehen, was seiner "Kuriosität" widerspricht.
Beliebt sind die Probleme beim Schneiden eines Schachbretts. Der berühmteste von ihnen ist der folgende, der S. Loyd gehört.
Auf den Feldern a1, b2, c3, d4 stehen vier Springer. Schneiden Sie das Brett in vier kongruente Teile (übereinanderliegend), so dass jeder von ihnen ein Pferd hat.
Bei Schnittproblemen wird immer davon ausgegangen, dass nur entlang der Grenzen zwischen der Vertikalen und Horizontalen der Platte geschnitten wird. Die Lösung dieses Problems ist in Abb. 6. Seit der Zeit von Loyd sind viele neue und schwierigere Probleme zu diesem Thema aufgetaucht. Insbesondere die Probleme, das Brett in vier kongruente Teile zu schneiden, wurden für unterschiedliche Positionen der Springer gelöst (die Springer spielen hier natürlich nur eine symbolische Rolle). Zu diesem Thema gibt es noch viele ungelöste Probleme. So ist zum Beispiel noch nicht bekannt, auf wie viele Arten ein normales Brett (ohne Stücke) in zwei kongruente Stücke geschnitten werden kann.
Reis. 6. Loyds Vier-Pferde-Problem |
Lassen Sie nach mehreren Schnitten der Platte die resultierenden Teile verschieben, damit beim nächsten Schnitt nicht ein, sondern mehrere Teile gleichzeitig geschnitten werden können. Wie viele Schnitte sind erforderlich, um 64 einzelne Brettfelder (1 × 1-Quadrate) zu erhalten?
Zuerst schneiden wir das Brett in zwei Hälften, legen dann beide Hälften nebeneinander und schneiden das Brett in vier identische Teile usw. Insgesamt werden 6 Schnitte benötigt (2 e \u003d 64) und auf eine kleinere Anzahl kann nicht verzichtet werden .
Nun dürfen Teile der Platine nur noch separat geschnitten werden. Wie viele Schnitte sind in diesem Fall erforderlich, um 64 Felder zu erhalten?
In der Regel bereitet diese Aufgabe (insbesondere wenn sie nach der vorherigen vorgeschlagen wird) gewisse Schwierigkeiten. Anscheinend liegt dies an einer gewissen Trägheit unseres Denkens. Immerhin ist sofort klar, dass 63 Schnitte benötigt werden! Tatsächlich erhöht jeder Schnitt die Anzahl der Teile um eins; Gleichzeitig haben wir im ersten Moment einen Teil (das Brett selbst) und im letzten Moment - 64 (alle Felder des Bretts).
Reis. 7. Drei Probleme auf einem ungewöhnlichen Brett |
Bei der Aufgabe in Abb. 7a müssen Sie drei Aufgaben lösen, eine mathematische und zwei rein schachliche:
a) das Brett in vier kongruente Teile schneiden;
b) den schwarzen König auf dem kürzesten Weg schachmatt setzen, wenn Weiß zieht;
c) den schwarzen König auf dem kürzesten Weg schachmatt setzen; während Schwarz zieht, spielen die Getreuen kooperativ).
Lösungen: a) wie man das Brett schneidet, gezeigt in Abb. 7b; b) Wenn Weiß am 12. Zug zieht, wird Matt gesetzt: 1-12. Le1-b4, Ke3-d3-c4, Le4-c2-b3, Kc4-c3, Lb4-d6, Lb3-d5, Kc3-c2, Ld6-c5, Ld5-c4, Ld6-b4 Schachmatt (alle Züge des schwarzen Königs sind erzwungen und nicht gegeben); c) bei korrektem Spiel nach 1. ... Ke6-e7 ist Schachmatt unmöglich, da sich der schwarze König auf e8 - 2. Le1-b4+ Ke7-e8 versteckt und der schwarzfeldrige Läufer gezwungen ist, die Diagonale a3 - e7 zu verlassen wegen drohendem Patt. Wenn Schwarz jedoch kooperativ spielt (Weiß beim Schachmatt hilft), ist das Ziel in nur drei Zügen erreicht:
1. … Ke6-d6
2. Ke3-d4 Ke6-e7
3. Le1-b4+ Ke7-e6
4. Le4-d5 matt. Eine Reihe von Feldern unseres Bretts werden während der Paarung nicht verwendet, aber wenn sie ausgeschlossen wären, gäbe es kein Problem, das Brett zu schneiden.
Reis. 8. Paradox beim Schneiden des Schachbretts: a) 8×8 = 64; b) 13×5 = 65 |
Betrachten Sie nun ein bekanntes Paradoxon, das mit dem Schneiden des Schachbretts verbunden ist. Wir schneiden das Brett in vier Teile, wie in Abb. 8, a (in diesem Fall ist es für uns unrentabel, die Felder einzufärben), und aus den resultierenden Teilen fügen wir ein Rechteck hinzu (Abb. 8, b). Die Fläche des Bretts beträgt 64 und die Fläche des resultierenden Rechtecks 65. Beim Schneiden des Bretts kam also irgendwo ein zusätzliches Feld her!
Die Lösung für das Paradoxon ist, dass unsere Zeichnungen nicht ganz genau sind (wir haben absichtlich dicke Linien gezeichnet, um Ungenauigkeiten zu verbergen). Bei sorgfältiger Konstruktion der Zeichnung in Abb. 8b erscheint anstelle der Diagonale des Rechtecks eine rautenförmige, leicht verlängerte Figur mit fast verschmolzenen Seiten. Die Fläche dieser Figur entspricht nur der "zusätzlichen" Einheit.
Der bekannte Popularisierer der Mathematik zu Beginn des Jahrhunderts, E. Ignatiev, entwickelte die „Schachbrettmethode“, die es ermöglicht, verschiedene Formeln abzuleiten. Wir geben zwei einfache Beispiele zu diesem Thema.
Lassen Sie uns die Summe der ersten n natürlichen Zahlen mit der "Schachbrettmethode" ermitteln. Dazu färben wir auf der Tafel (n + 1) × n (in Abb. 9 a n = 8) alle Felder der ersten Vertikale, alle Felder der zweiten Vertikale (außer der oberen), die dritte Vertikale (mit Ausnahme der beiden oberen) usw. d. schließlich - unten Feld n vertikal. Als Ergebnis sind weiße und schwarze Felder auf unserem Brett gleich, nämlich 1 + 2 + ... + n. Da das ganze Brett aus n (n + 1) Feldern besteht, erhalten wir
2 (1 + 2 + … + n) = n(n + 1),
woraus die bekannte Formel für die Summe einer arithmetischen Folge folgt:
1 + 2 + … + n = n(n + 1)/2.
Beweisen wir nun die folgende Formel:
8(1 + 2 + ... + n) + 1 = (2n + 1)².
Nehmen Sie dazu ein Brett (2n + 1) × (2n + 1) und bemalen Sie einige seiner Felder mit Schwarz, wie in Abb. 9, 6 (für den Fall n = 5). Offensichtlich enthält jeder schwarze Teil (1 + 2 + ... + n) Felder. Ohne Berücksichtigung des zentralen Feldes haben wir hier vier identische weiße und schwarze Teile. Die benötigte Formel ergibt sich daraus, dass unser Brett (2n + 1)² Felder enthält und aus einem zentralen Feld und acht identischen Teilen besteht (vier weiße und vier schwarze – Abb. 9b).
Wenn Sie das Paradoxon auflösen und sich mit der „Schachbrettmethode“ vertraut machen, kann das Brett selbst sicher durch ein Blatt kariertes Papier oder einen Tisch ersetzt werden. Es gibt eine Menge Probleme mit solchen Objekten, aber ihre detaillierte Betrachtung würde uns zu weit vom Schach wegführen.
Zum Abschluss des Kapitels präsentieren wir einen alten Beweis auf dem Schachbrett … des Satzes des Pythagoras. Zeichnen Sie ein Quadrat auf die Tafel, wie in Abb. 10 A. Das Brett ist in dieses Quadrat und vier kongruente rechtwinklige Dreiecke unterteilt. Auf Abb. 10, 6 sehen wir dieselben vier Dreiecke sowie zwei Quadrate. Die Dreiecke nehmen also in beiden Fällen die gleiche Fläche ein. Folglich nehmen die restlichen Teile des Bretts ohne Dreiecke die gleiche Fläche ein, in Abb. 10,a - ein Quadrat und in Abb. 10b - zwei. Da das große Quadrat auf der Hypotenuse eines rechtwinkligen Dreiecks gebaut ist und die kleinen Quadrate auf seinen Beinen liegen, sind "pythagoräische Hosen in alle Richtungen gleich"!
Natürlich beweist unsere Argumentation streng genommen nicht den Satz des Pythagoras (es wurde nur ein besonderer Fall untersucht), sondern veranschaulicht ihn nur. Aber ein solcher Beweis kommt ohne Schachbrett aus – für jedes rechtwinklige Dreieck kann man ein Quadrat wählen, das auf ähnliche Weise bricht.
Diese Lösung wird in T. Saatis Buch "Integer Optimization Methods and Related Extremal Problems" (M., "Mir", 1973) angegeben.
S. Golomb. Polyomino. M., Mir, 1974.
Es wurde von A. Soifer im Artikel "Schachbrettmuster und Polymipo" ("Kvant", 1972, Nr. 11) bewiesen; Dort werden auch eine Reihe neuer Polyomino-Probleme aufgeführt.
E. Ignatjew. Im Reich des Einfallsreichtums oder Rechnen für Jedermann. Buch. 1 - 3. M. - Pg., Gosizdat, 1923.
6. Es gibt 235 Streichhölzer in einer Schachtel. Zwei Spieler nehmen sie abwechselnd. In einem Zug können Sie 1 bis 6 Streichhölzer nehmen. Der Spieler gewinnt
das letzte Streichholz nehmen. Wer gewinnt, wenn er richtig gespielt wird?
62
7. Aus einem 8 × 8-Brett wird ein Eckquadrat ausgeschnitten. Ist es möglich, die Platte in 1×3-Rechtecken zu verlegen?
8. Von 30 Spielen nehmen zwei Spieler nach eigenem Ermessen ab 1
bis zu 6 Spiele. Derjenige, der das letzte Streichholz nimmt, gewinnt.
9. Es gibt drei Steinhaufen. Ein Zustand ist ein Tripel von Zahlen
(x
1
, x
2
, x
3
), wobei x i
- die Anzahl der Steine im i-ten Stapel. Eine Bewegung ist der Vorgang, bei dem von Haufen zu Haufen eine Anzahl von Steinen übertragen wird, die der Anzahl von Steinen in dem Haufen entspricht, auf dem die Übertragung durchgeführt wird. Aus dem Anfangszustand (11, 7, 6) wird der Zustand (8, 8, 8).
10. Teilen Sie den Kreis mit vier geraden Linien in die maximale Anzahl von Teilen.
11. Schneiden Sie das griechische Kreuz mit zwei geraden Linien so aus
um aus den resultierenden Teilen ein Rechteck zu bilden, dessen eine Seite doppelt so groß ist wie die andere.
12. In 9 gibt es einen 12-Liter-Vorrat an Flüssigkeit und leere Gefäße
und 5l. Es müssen genau 6 Liter gemessen werden. Wie viel Liter können mit solchen Gefäßen aus einer Reserve von 12 Litern gemessen werden?
13. Bestimmen Sie die Anzahl der Folgen der Länge n aus (0, 1, 2),
in dem es keine zwei aufeinanderfolgenden Einheiten gibt.
14. Ist es möglich, ein 10 × 10-Quadrat mit Figuren der Form zu bedecken?
15. Ist es möglich, ein 10 × 10-Quadrat mit Figuren der Form zu bedecken?
63
16. Ist es möglich, ein 8×8-Quadrat mit einer ausgeschnittenen Eckzelle mit Figuren des Formulars zu bedecken?
17. Ist es möglich, mit Figuren der Form ein 8 × 8-Schachbrett zu bedecken, in dem ein Quadrat ausgeschnitten ist:
18. Ist es möglich, ein Schachbrett mit einem geschnitzten Eckkäfig mit Teilen der Form zu belegen?
19. Ist es möglich, mit Hilfe eines Zweimannbootes vier Ritter-Knappen-Paare zu überqueren, wenn der Knappe in Abwesenheit seines Herrn nicht mit einem oder mehreren anderen Rittern am selben Ufer sein kann?
20. Entwickeln Sie einen Algorithmus zum Finden der beiden kleinsten Zahlen in einer ungeordneten Folge von n Zahlen.
21. Von 27 auf dem Tisch liegenden Streichhölzern nehmen zwei Spieler abwechselnd mindestens ein und höchstens vier Streichhölzer. Der Gewinner ist derjenige, der am Ende des Spiels eine gerade Anzahl von Spielen hat. Entwickeln Sie einen Algorithmus für das Spiel des ersten Spielers.
64
22. Zwei Teilnehmer des Spiels rufen abwechselnd eine Nummer von 1 bis 10 an.
Wenn der Spieler eine Nummer anruft, addiert er sie zu der bereits vorhandenen Summe von Zahlen (wenn er die erste Nummer anruft, addiert der Spieler sie zu Null). Der Spieler, der 100 Punkte erzielt, gewinnt.
Entwickeln Sie einen Algorithmus für das Spiel des ersten Spielers.
23. Suchen Sie nach der Mindestanzahl von Fragen (mögliche Antworten:
"ja", "nein") eine versteckte 5-stellige Zahl, wenn die Summe der ersten drei Ziffern 17 ist.
24. Suchen Sie nach der Mindestanzahl von Fragen (mögliche Antworten:
"ja", "nein") eine versteckte 4-stellige Zahl, wenn die Summe der zweiten und vierten Ziffer 7 ist.
25. Auf wie viele Arten können 100 Rubel umgetauscht werden? Münzen ein
5, 10, 20 und 50 Rubel?
26. Berechnen Sie rekursiv die Anzahl der sechsstelligen Zahlen, deren Summe der ersten vier Ziffern 26 und die Summe der letzten beiden Ziffern 14 ist.
27. Berechnen Sie rekursiv die Anzahl der Partitionen der Zahl 37 durch fünf Terme, von denen der erste 7 nicht überschreitet, der zweite
- 5, und die dritte und vierte nehmen Werte aus dem Satz
{5, 6, 7, 8}.
28. Berechnen Sie rekursiv die Anzahl der siebenstelligen Zahlen, deren Summe der ersten vier Zahlen 21 und die Summe der letzten fünf Zahlen 19 ist.
29. Berechnen Sie rekursiv die Anzahl der Partitionen der Zahl 27 durch vier Terme, von denen der erste 7 nicht überschreitet,
der zweite ist 8, und der dritte und vierte nehmen Werte aus dem Satz (3, 5, 7).
30. Berechnen Sie rekursiv die Anzahl der fünfstelligen Zahlen, deren erste drei Ziffern 21 ergeben und deren letzte drei Ziffern 12 ergeben.
65
31. Berechnen Sie rekursiv die Anzahl der siebenstelligen Zahlen, bei denen die Summe der ersten und dritten Ziffer 12 und die Summe der restlichen fünf 19 ist.
32. Rekursiv rechnen
(2n − 2)(2n − 4) × . . . ×2
(n + 1)(n + 3) × . . . × (n + 2n − 1)
ein n-5
b
−(n+3)
33. Berechnen Sie rekursiv die Anzahl der siebenstelligen Zahlen, deren Summe der ersten vier Ziffern 17 und die Summe der letzten drei Ziffern 16 ist.
34. Berechnen Sie rekursiv die Anzahl der Partitionen der Zahl 17 durch vier Terme, von denen der erste 4 nicht überschreitet, der zweite - 8 und der dritte und vierte die Werte (3, 4, 8).
35. Berechnen Sie rekursiv die Anzahl der siebenstelligen Zahlen, deren Quadratsumme der ersten vier Zahlen 17 und die Quadratsumme der letzten beiden Zahlen 16 ist.
36. Berechnen Sie rekursiv die Anzahl der Partitionen der Zahl 25 durch vier Terme, von denen der erste 8 nicht überschreitet,
der zweite ist 3, und der dritte und vierte nehmen Werte aus dem Satz (2, 5, 9).
37. Berechnen Sie rekursiv die Anzahl der N Turmstellungen auf dem Brett
N × N so, dass die Türme in Bezug auf beide Diagonalen symmetrisch sind und sich nicht gegenseitig angreifen.
38. Berechnen Sie rekursiv die Anzahl der binären Folgen von n Elementen, in denen zwei benachbarte Einsen fehlen.
39. Gegeben ein Gitter N × M:
66
M
N
EIN
B
Berechnen Sie rekursiv die Anzahl der Wege von A nach B. Ein Weg ist eine Abfolge von Bewegungen entlang des Gitters, die von links nach rechts und von unten nach oben führen.
40. Zahlen a sind gegeben
1
, . . . , ein
in einer bestimmten Reihenfolge. Zur Berechnung des Produkts a
1
·. . . ein
Während die Reihenfolge der Faktoren beibehalten wird, gibt es viele Möglichkeiten, Klammern zwischen Faktoren zu setzen. Berechnen Sie rekursiv die Anzahl der Möglichkeiten, Klammern zu setzen.
41. Berechnen Sie rekursiv die Anzahl der 8-stelligen Zahlen, deren Summe der ersten fünf Ziffern 29 und die Summe der letzten drei Ziffern 21 ist.
67
3
. algorithmische Analysemethoden
3.1. Algorithmus-Klassen
In den vorangegangenen Abschnitten haben wir verschiedene Ansätze betrachtet, die bei der Konstruktion von Algorithmen verwendet werden können. Um eine Lösung zu finden, um die Wirksamkeit dieser Lösung zu analysieren, kann man verschiedene Annahmen treffen, bereits bekannte andere Algorithmen verwenden, die Bedingung des Problems neu formulieren usw. Sie können nach ähnlichen Problemen mit einer bekannten Lösung suchen und diese Lösung verwenden, um einen Algorithmus für das erforderliche Problem zu finden.
Es gibt jedoch viele spezielle Probleme, für die Lösungen gefunden wurden. Es gibt noch mehr Aufgaben, die ungelöst oder mit einigen Einschränkungen und Bedingungen gelöst sind. Die Suche nach ähnlichen Problemen in der ganzen Menge von Problemen, die Bewertung vorhandener Lösungen nach ihrem Grad der "Angemessenheit" kann ein schwieriges, zeitaufwändiges und nicht immer lösbares Problem sein. Es wäre nützlicher und produktiver zu versuchen, Klassen von Problemen zu definieren, die durch ein gemeinsames Problem, gemeinsame Methoden und Lösungsansätze vereint sind, und dann nach der Klasse zu suchen, der unser spezielles Problem, das gelöst werden muss, zugeordnet werden kann. Natürlich sollte es nicht zu viele solcher Klassen geben, aber andererseits auch nicht zu wenige, damit jede neue Aufgabe Definieren Sie Ihre eigene, neue Klasse, die dann wahrscheinlich nicht zur Lösung anderer Probleme verwendet wird.
Als ein Beispiel eines Problems, das zu einer bestimmten Klasse gehört, sei das wohlbekannte Problem der Identifizierung einer gefälschten Münze betrachtet.
Aufgabe 3.1 (Problem bzgl gefälschte Münze). Es gibt n Münzen,
darunter kann eine Fälschung sein. Die gefälschte Münze unterscheidet sich vom Rest im Gewicht, und wir haben eine Waage mit zwei Bechern zur Verfügung. Es ist erforderlich, eine gefälschte Münze für die Mindestanzahl von Wägungen zu bestimmen oder festzustellen,
dass es keine gefälschten Münzen gibt.
68
Lösung. Das Problem mit gefälschten Münzen wurde in Sec gelöst. 2.2,
aber dann war bekannt, dass eine gefälschte Münze zwangsläufig leichter war. Versuchen wir nun, dieses Problem für einen allgemeineren Fall zu lösen. Jede Lösung für dieses Problem (nicht unbedingt optimal)
kann als Abfolge von Wägungen interpretiert werden. Es ist jedoch klar, dass die Wahl der Münzen zum Wiegen in jedem Schritt davon abhängt, welche Münzen verwendet wurden und welche Ergebnisse beim Wiegen in den vorherigen Schritten erzielt wurden. Wir werden den Ablauf der Wägungen wie folgt darstellen. Wir nummerieren die Münzen neu und definieren sie als Menge S = (1, 2, . . . , n). Die Zahlensätze der Münzen, die auf der linken und rechten Waagschale gewogen werden, können mit S bezeichnet werden
L
und S
R
beziehungsweise. Es ist klar, dass eine Gewichtung nur dann sinnvoll ist, wenn die Kardinalitäten der Mengen S
L
und S
R
übereinstimmen, d.h. Jede Waage hat die gleiche Anzahl von Münzen. Das Wiegen wird mit dem Zeichen ":" gekennzeichnet, dann jedes Wiegen
(S
L
) : (S
R
) gibt es drei mögliche Ergebnisse. Viele Münzen
S
L
kann leichter, schwerer oder gleich schwer sein wie das Set S
R
. Dann werden wir diese Gewichtungsergebnisse als bezeichnen
"" bzw. "=". Ein Beispiel für das Wiegen von vier Münzen ist in Abb. 2 dargestellt. 3.1. Ovale stellen Wägungen dar, Quadrate stellen Ergebnisse dar und geben die Nummer der gefälschten Münze an und ob sie leichter oder schwerer als die anderen ist.
Der Fall, dass keine gefälschte Münze vorhanden ist, wird als „0“ angezeigt, durchgestrichene Quadrate entsprechen Fällen, die nicht auftreten können.
Wir schätzen die maximale Anzahl von Wägungen, die zur Lösung des Problems erforderlich sind, d.h. schlimmsten Fall. Wie aus Abb. 3.1, das Problem wird im schlimmsten Fall in 3 Wägungen gelöst. Beachten Sie, dass wir selbst im besten Fall mindestens 2 benötigen
Wiegen. Kann ein besseres Ergebnis erzielt werden?
Auf Abb. 3.1 präsentiert eine weitere Lösung für das Problem des Wiegens von vier Münzen. Im ersten Schritt wiegen wir nicht ein paar Münzen, sondern alle Münzen und teilen sie in zwei Sätze auf. Dadurch haben wir erreicht, dass bestenfalls nur eine Wägung erforderlich ist,
im schlimmsten Fall beträgt die Anzahl der Wägungen jedoch wieder 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
=
=
=
>
>
>
>
>
=
=
Reis. 3.1. Lösung des Problems mit gefälschten Münzen
Beachten Sie, dass im Gegensatz zur ersten Wiegeoption
in Abb. gezeigt. 3.1 haben wir in der zweiten Version nicht nur das Wiegeschema definiert, sondern auch ein neues Konzept von Kandidaten für gefälschte Münzen eingeführt. Betrachten Sie in der Tat das Ergebnis der ersten Wägung, (1, 2) : (3, 4). Sei (1, 2) L
= (1, 2) und S
R
= (3, 4). Dann
S
L
R
. Anhand dieses Ergebnisses lässt sich nicht beurteilen, ob die gefälschte Münze leichter oder schwerer ist als alle anderen,
und in welchem satz es ist. Es kann jedoch davon ausgegangen werden
(und noch genauer - es kann argumentiert werden), dass, wenn eine gefälschte Münze zur Menge S gehört
L
, dann ist die gefälschte Münze leichter als die anderen, wir bezeichnen einen solchen Satz mit dem Buchstaben L. Wenn in unserem Fall Münzen mit den Nummern 1 oder 2 gefälscht sind, dann sind sie leichter als echte. Wenn die gefälschten Münzen mit den Nummern 3 bzw
4, dann sind sie schwerer als echte, wir bezeichnen den entsprechenden Satz mit dem Buchstaben T. In Abb. 3.2 leichte und schwere Fälschungskandidaten werden durch Markierungen an den Rändern des Baumes angezeigt.
Offensichtlich kann man die Frage nach der optimalen Anzahl von Wägungen beantworten, indem man weiter die möglichen Schemata für die Münzauswahl durchgeht. Da die Anzahl der Münzen endlich ist, kann eine solche Aufzählung früher oder später abgeschlossen werden. Lassen Sie uns zunächst auf die beiden erhaltenen Lösungen eingehen und versuchen zu analysieren, was sie ergaben
70
(1.2)L
(3.4)T
(1.2)T
(3.4)L
(1,2) : (3,4)
(3) : (4)
4T
3 T
(1) : (2)
1 L
=
=
>
>
>
=
0 2 L
(3) : (4)
3 L
4 L
(1) : (2)
2 T
=
>
>
=
1 T
Reis. 3.2. Eine weitere Lösung für das Problem einer gefälschten Münze für uns aus der Sicht eines allgemeinen Ansatzes zur Lösung des Problems.
Wie bekannt ist, kann jede Münzwägestrategie unter Verwendung eines Dreier- oder Dreierbaums beschrieben werden. Mit anderen Worten, das betrachtete Problem gehört zur Klasse der Probleme ,
beschrieben durch ternäre Bäume. Eine solche Klassifizierung des Problems ermöglicht es, nicht jede spezifische Lösung, sondern alle Lösungen im Allgemeinen basierend auf den bekannten Eigenschaften von Bäumen zu analysieren.
Also Iteration vorbei mögliche Wege Die Gewichtung ist eigentlich eine Suche durch verschiedene ternäre Bäume, von denen es natürlich exponentiell viele gibt. Versuchen wir andererseits zu bestimmen, was im Allgemeinen erreicht werden kann, wenn ein bestimmtes Problem gelöst wird, indem es zu dieser bestimmten Klasse gehört.
Von Abb. 3.1 und 3.2 ist ersichtlich, dass wir bei der Darstellung der Abfolge von Wägungen unter Verwendung eines Baums jede Wägung einem Baumscheitel zuordnen, der kein Blatt ist (dargestellt durch Ovale), während Ergebnisse, einschließlich unmöglicher,
entsprach den Blättern des Baumes (dargestellt mit Quadraten). Alle Baumknoten können nach Ebenen geordnet werden,
71
BEI
a
=
=
>
BEI
a
Und
Und
Und
=
>
BEI
a
Und
Und
Und
=
>
BEI
a
Und
Und
Und
=
>
BEI
a
Und
Und
Und
=
>
BEI
a
=
>
BEI
a
=
>
BEI
a
>
Zu
BEI
L
Bei
0
Bei
1
Bei
l
-
1
Bei
l
……
………………
………
…
…
……
…
…
…
…
…
……
……
…
…
G
ein =
l
Reis.
3.3.
T
Frühlingsgewichtsbaum
72
diese. durch ihren Abstand von der Wurzel des Baumes. Die Ebenennummer ist gleich der Anzahl der Kanten, die von der Wurzel passieren müssen, um zum Scheitelpunkt zu gelangen. gegebenes Niveau(Abb. 3.3). Wenn die Tiefe des Baums die Ebene des Blattes ist, das am weitesten von der Wurzel entfernt ist, dann ist dieser Wert im schlimmsten Fall gleich der Anzahl der Gewichtungen.
Wie viele mögliche Ergebnisse gibt es in unserem Problem? Jede der n Münzen kann sich als eine gefälschte leichte oder falsche schwere Münze herausstellen, und es kann sein, dass es überhaupt keine gefälschten Münzen gibt.
Somit haben wir 2n + 1 Ergebnisse. Das bedeutet, dass im Baum
entsprechend dem Wägeschema, muss mindestens sein
2n + 1 Blätter. Ein ternärer Baum der Tiefe l enthält höchstens
als 3
Ich gehe. Daraus können wir die minimal mögliche Tiefe des Baumes abschätzen
3
l
≥ 2n + 1,
und daher
l ≥log
3
(2n + 1).
(3.1)
Somit ist für n = 4 die minimal mögliche Anzahl an Wägungen größer oder gleich 2. Damit meinen wir nicht die minimale Anzahl an Wägungen für dieses Schema – wie in Abb. 3.2, und es gibt Fälle, in denen die Lösung des Problems bereits nach dem ersten Wiegen gefunden wird - wir bewerten die schlechteste Option, d.h. die maximale Anzahl von Gewichtungen für ein gegebenes Schema, mit anderen Worten, wir suchen ein Minimum unter den maximalen Tiefen aller Bäume mit mindestens 2n + 1 Blättern.
Es kann jedoch gezeigt werden, dass es keine Gewichtungsmethode gibt, die eine gleiche Schätzung ergeben würde (3.1).
SATZ 3.1
Die Anzahl der Wägungen im ungünstigsten Fall für das Falschgeldproblem wird mit l > log abgeschätzt
3
(2n + 1).
Nachweisen. Wie bereits erwähnt, gibt es für n Coins 2n + 1 mögliche Ergebnisse. Jede Wägung kann drei mögliche Ergebnisse haben, und jedes Ergebnis hat sein eigenes
73
Schema der weiteren Wägungen. Gleichzeitig hat das Schema eine eigene Anzahl möglicher Ergebnisse, wobei das Ergebnis der letzten Wägung berücksichtigt wird. Lassen Sie beim ersten Wiegen |S
L
| = |S
R
| = k, d.h.
k Münzen werden auf der einen Waagschale und k Münzen auf der anderen verwendet,
wobei k ≤ n/2 . Wenn gleichzeitig S
L
R
, dann Münzen von S
L
Wir erklären Kandidaten für leichte gefälschte Münzen und Münzen von S
R
- Kandidaten für schwere gefälschte Münzen. Auf diese Weise,
mit dem ergebnis der ersten wägung sind 2k ergebnisse möglich.
Ebenso für S
L
>S
R
2k andere Ergebnisse sind möglich. Daher für S
L
= S
R
die restlichen 2n + 1 − 4k Ergebnisse sind möglich.
Wenn in (3.1) Gleichheit gilt, bedeutet dies, dass der ternäre Baum vollständig ist und alle seine Blätter auf der l-ten Ebene liegen.
Dafür ist es aber notwendig, dass nach jeder Wägung die möglichen Ergebnisse gleichmäßig auf die drei Äste und die Gleichheit verteilt werden
2k = 2n + 1 − 4k,
was unmöglich ist, da 2k immer eine gerade Zahl ist, und
2n + 1 − 4k ist immer ungerade.
Beim Beweis von Theorem 3.1 wurde eine wichtige Idee verwendet:
Damit der Wägungsbaum optimal oder zumindest so nah wie möglich am Optimum ist, ist es notwendig, dass die Ergebnisse gleichmäßig über alle Ergebnisse jeder Wägung verteilt werden.
Somit haben wir eine Schätzung für die schlechteste Anzahl von Wägungen im Problem der gefälschten Münzen erhalten, indem wir dieses Problem mit der Klasse der Probleme in Beziehung gesetzt haben
beschrieben durch ternäre Bäume. Betrachten Sie nun ein leicht modifiziertes Problem.
Aufgabe 3.2 (Problem über eine gefälschte Münze in Anwesenheit eines Standards). Es gibt n Münzen, darunter eine Fälschung und eine weitere Münze, von der mit Sicherheit bekannt ist, dass sie echt ist. Es ist erforderlich, die Falschmünze in der Mindestanzahl von Wägungen zu bestimmen oder festzustellen, dass keine Falschmünzen vorhanden sind.
74
Lösung. Dieses Problem unterscheidet sich vom vorherigen durch das Vorhandensein einer zusätzlichen Referenzmünze, aber es stellt sich heraus, dass diese zusätzliche Münze es einem ermöglicht, Bäume mit optimalem Gewicht zu konstruieren, für die die Gleichheit in (3.1) erfüllt ist. Bezeichne mit n l
die Zahl, für die die Gleichheit gilt
3
l
= 2n l
+ 1.
(3.2)
Wenn wir das vorherige Problem in Satz 3.1 betrachten, haben wir erhalten: Damit die Gleichheit (3.1) erfüllt ist, muss der Gewichtungsbaum vollständig sein. Wenn es also möglich ist, einen solchen optimalen Baum aus l Ebenen aufzubauen, dann wird er ein Schema von l Gewichtungen für n l spezifizieren
Münzen. Beachten Sie, dass die folgende Beziehung gilt:
n l
= 3nl−1
+ 1.
(3.3)
Da für n
0
= 0 in (3.2) erhalten wir die Gleichheit, 3 0
= 2 0 + 1,
dann können wir von hier aus mit (3.3) n erhalten
1
= 1,n
2
=
4,n
3
= 13 usw. Lösung (3.2) ist die Folge
0, 1, 4, 13, 40, . . ..
Wenn also Gleichheit (3.2) gilt, ist die Menge von n
l Münzen werden durch n l−1 in drei gleiche Teile geteilt
Münzen und es ist noch eine Münze übrig. Betrachten wir verschiedene Situationen, die während des Wägevorgangs auftreten können.
Schema 1. Zu Beginn des Wägens sei n i
Münzen, wobei n i
gehört zur Folge (3.3) für einige i. Setzen wir n i−1
Münzen, wo n
ich
= 3n i−1
+ 1,
dann fügen wir eine Referenzmünze zur linken Waagschale hinzu und eine der verbleibenden n i−1
+ 1 Münzen. Bezeichne die gewichteten Mengen wie zuvor mit S
L
und S
R
Lassen Sie nun als Ergebnis der Wägung S
L
= S
R
. Da die Referenzmünze an der Wägung teilgenommen hat, ist es offensichtlich, dass die gefälschte Münze, falls vorhanden, zu den unbenutzten n gehört
i-1
Münzen, und das Problem wird auf ein Problem mit n i−1 reduziert
Münzen. Dabei
75
Durch die Gewichtung bleiben noch 2n i−1 möglich
+ 1 =
3
i-1
Ergebnisse. Jetzt lass uns
L
R
. Das bedeutet, dass sich die gefälschte Münze entweder in der Menge S befindet
L
und gleichzeitig ist es leichter als die anderen oder in der Menge S
R
und dann ist es schwerer als die anderen.
Außerdem gibt es n i−1
verdächtige leichte Münzen und n i−1
+ 1 verdächtig schwer und zusammen ergibt das wieder 2n i−1
+ 1 = 3
i-1
mögliche Resultate.
Lassen Sie schließlich S
L
>S
R
. Dann haben wir n i−1
Heavy-Coin-Kandidaten und n i−1
+1 Kandidaten für Lungen und insgesamt 2n i−1
+1 =
3
i-1
Ergebnisse. Mit einem solchen Schema des ersten Wiegens erhalten wir also tatsächlich diese 3
i Anfangsergebnisse wurden gemäß den Wägeergebnissen gleichmäßig verteilt. Um festzustellen, ob es möglich ist, das Wägeschema so einzustellen, dass die Ergebnisse nach jeder Wägung in eine gleiche Anzahl von Teilen aufgeteilt werden, betrachten Sie die Wägeergebnisse. Offensichtlich für S
L
= S
R
wir kommen zum gleichen Problem, nur mit einer kleineren Dimension, und wir können die Gewichtung nach Schema 1 immer wieder durchführen, aber mit einem kleineren Wert von i.
Schema 2. Sei nun S
L
R
. In diesem Fall definieren wir die Gewichtungsstrategie wie folgt. Die Anfangsdaten sind, dass wir bei irgendeinem Schritt i in der Folge der Gewichtungen 3 haben
ich
= 2n ich
+ 1 Münzen, darunter n i
leichte gefälschte Kandidaten und n i
+ 1 Kandidaten für schwer, während die Zahl n i
ist eine Zahl der Form (3.3)
n ich
= 3n i−1
+ 1.
Auf jede Waagschale n i−1 setzen
einfache Kandidaten und n
i-1
+1 schwer. Da es nur 2n i
+1 = 2(3n i−1
+1)+1 = 6n i−1
+3
Münzen und wiegen
2n i−1
+ 2n i−1
+ 2 = 4n i−1
+ 2
Münzen, dann gibt es immer noch 2n i−1
+ 1 Münzen, darunter n i−1
+ 1
Lunge und n i−1
schwer. Da es auf beiden Waagen gleich viele leichte und schwere Münzen gibt, gilt bei nicht ausgeglichener Waage,
dies ergibt n i−1
Kandidaten für leichte Münzen (aus der Schale, die sich als leichter herausstellte) und n i−1
+ 1 Kandidat für schwer (aus der Schüssel, die sich herausstellte
76
schwerer). Dies bringt uns zu den Originaldaten desselben Schemas
(Schemata 2), aber für 3
i-1
= 2n i−1
+ 1 Münzen. Wenn die Waage ausgeglichen ist, bedeutet dies, dass wir unter den ungewogenen n i−1 nach einer gefälschten Münze suchen müssen
+ 1 Lunge und n i−1
schwere Münzen, was Schema 3 entspricht. Offensichtlich ist 2n i−1
+1 Ergebnisse, d. h. wieder wird die Menge aller möglichen Ergebnisse in drei gleiche Teile geteilt.
Schema 3. Sei nun S
L
>S
R
. In diesem Fall haben wir 3
ich
=
2n ich
+ 1 Münzen, darunter n i
+ 1 leichte gefälschte Kandidaten und n i
Schwergewichtige Kandidaten. Alle Argumente ähneln Schema 2, mit dem Unterschied, dass Sie beim Wiegen n i−1 einsetzen müssen
+ 1 einfache Kandidaten und n i−1
schwer. Wenn die Waage nicht ausgeglichen ist, ergibt dies wieder Muster 3 für 3
i-1
Münzen, ansonsten erhalten wir die Wägungsbedingungen entsprechend Schema 2. Auch hier wird die Menge der möglichen Ergebnisse in allen Fällen in drei gleiche Teile von 2n i−1 geteilt
+ 1.
Somit haben wir dreimal
1 2
3
=
>
=
=
Reis. 3.4. Übergänge zwischen Gewichtungsschemata in dem oben beschriebenen persönlichen Zustands-Falschmünzenproblem und der Gewichtungsregel für jeden Staat. Je nach Wägeergebnis gehen wir in einen anderen Zustand über (oder bleiben im gleichen Zustand), jedoch für eine geringere Anzahl von Münzen. Bei jeder Wägung wird die Anzahl der möglichen Ergebnisse entsprechend den Ergebnissen der Wägung gleichmäßig verteilt. Das Schema der Übergänge zwischen den Zuständen ist in Abb. 2 dargestellt. 3.4. Ein Beispiel für das Wiegen von 27 Münzen ist in Abb. 2 dargestellt. 3.5.
77
Aufgabe 1: Kann ein 5 × 5-Quadrat in 1 × 2-Rechtecke geschnitten werden (Dominos). Aufgabe 2: Gegenüberliegende Eckquadrate werden aus einem 8×8-Schachbrett geschnitten. Kann der Rest in 1 × 2 Rechtecke (Dominos) geschnitten werden? Lösung: Nein. Jeder Dominostein belegt ein schwarzes und ein weißes Quadrat, und auf dem Brett ohne Ecken gibt es eine unterschiedliche Anzahl von schwarzen und weißen Quadraten. Aufgabe 3: Aus gegenüberliegenden Ecken eines 10 × 10-Bretts werden zwei Quadrate von 3 × 3 ausgeschnitten. Kann der Rest in Dominosteine geschnitten werden? Aufgabe 4: Denken Sie sich eine zusammenhängende Figur auf einem Schachbrett aus, in der es eine gleiche Anzahl schwarzer und weißer Felder gibt, die aber nicht in Dominosteine geteilt werden können. Aufgabe 5: Ist es möglich, ein 10 × 10 Quadrat in 25 Teile zu schneiden? Aufgabe 6:Lösung: Färben Sie das Brett in einem Schachbrettmuster. Es wird eine gerade Anzahl schwarzer Zellen geben, und ein oder drei davon fallen in jede Figur. Aufgabe 7: Ist es möglich, ein 10 × 10 Quadrat in 25 Teile zu schneiden? Lösung:
Färben Sie das Brett in vier Farben (siehe Bild). Jede Figur belegt ein Feld jeder Farbe, und die Felder der ersten und zweiten Farbe haben eine unterschiedliche Nummer.
Richtung: Malen Sie die Tafel in drei Farben aus.
Aufgabe 12: Wie viele 1 × 1 × 4 Balken können maximal aus einem 6 × 6 × 6 Würfel geschnitten werden? Aufgabe 13: Das Rechteck ist in Ziffern und unterteilt. Einer der verlorenen, aber durch ersetzt. Beweisen Sie, dass die neue Menge das ursprüngliche Rechteck nicht überdecken kann. Aufgabe 14: Kann ein 16 × 16-Quadrat in 64 1 × 4-Rechtecke unterteilt werden, von denen 31 vertikal und die restlichen 33 horizontal sind? Lösung: Färben Sie jede vierte Vertikale. Aufgabe 15: Für welches n lässt sich das Quadrat n × n zerlegen in a) ;b)? Lösung: Für n durch vier teilbar.
Aufgabe 16: Ein m × k Rechteck wird in 1 × n Rechtecke unterteilt. Beweisen Sie, dass m durch n oder k durch n teilbar ist.c) für jedes n. Lösung:
Male in n Farben aus.
Aufgabe 17: Beweisen Sie, dass ein m × n-Rechteck genau dann in a × b-Rechtecke zerlegt werden kann, wenn die folgenden Bedingungen erfüllt sind:1) m und n werden als ka + lb dargestellt (k und l sind nicht negative ganze Zahlen)
2) m und n sind durch a teilbar.
3) m oder n ist durch b teilbar.
Aufgabe 18: Ein m × n-Rechteck heißt stark, wenn es sich so in Dominosteine zerlegen lässt, dass jeder Schnitt des Rechtecks mindestens einen Dominostein schneidet. Beweise das:a) 2 × n Rechteck – zerbrechlich
b) 3 × n Rechteck – zerbrechlich
c) 4 × n Rechteck – zerbrechlich
d) 5×6 und 6×8 Rechtecke – stark
e) Wenn ein m × n-Rechteck stark ist, dann ist auch ein m × (n + 2)-Rechteck stark.
f) * 6×6-Rechteck - zerbrechlich
g) Welche Rechtecke sind stark und welche nicht? Lösung: f) Hinweis: Jede Linie in einem 6×6-Quadrat kreuzt eine gerade Anzahl von Dominosteinen.
g) Alle m × n Rechtecke mit geradem mn, m,n ≥ 5, außer 6 × 6.
Aufgabe 19:Eine Ecke ist eine Figur der Form.
a) Kann ein 5 × 9 Rechteck in Ecken gebrochen werden?
b) Beweisen Sie, dass ein Rechteck mit Seiten größer als 100 und einer durch 3 teilbaren Fläche in Ecken gebrochen werden kann.
c) Welche Rechtecke können in Ecken geteilt werden und welche nicht?
Aufgabe 20:Kann ein 2 n × 2 n-Brett ohne Eckquadrat in Ecken geteilt werden? Lösung: Ja, du kannst. Die Partition wird durch Induktion konstruiert.
Aufgabe 21: Für wie viel n lässt sich ein Brett (2n + 1) × (2n + 1) ohne Eckfeld in Dominosteine unterteilen, unter denen es gleichermaßen senkrechte und waagerechte gibt? Lösung: Für gerade n.
