Une tâche logique pour placer des dominos sur un échiquier. Olympiades mathématiques et problèmes d'Olympiade
Étant donné un échiquier 8 × 8, à partir duquel deux coins diagonalement opposés ont été coupés, et 31 dominos; chaque domino peut couvrir deux cases du plateau. Est-il possible de paver toute la planche avec des os? Justifiez votre réponse.
La solution
À première vue, il semble que cela soit possible. Le plateau est 8×8, donc il y a 64 cellules, nous en excluons deux, ce qui signifie qu'il en reste 62. Il semble que 31 os devraient tenir, n'est-ce pas ?
Lorsque nous essayons de disposer des dominos dans la première rangée, nous n'avons que 7 cases à notre disposition, un os va à la deuxième rangée. Ensuite, nous plaçons des dominos dans la deuxième rangée, et encore une tuile va à la troisième rangée.
Il y aura toujours un os dans chaque ligne qui devra être déplacé vers la ligne suivante, peu importe le nombre de mises en page que nous essayons, nous ne pourrons jamais disposer tous les os.
L'échiquier est divisé en 32 cases noires et 32 cases blanches. En supprimant les coins opposés (notez que ces cellules sont de la même couleur), il nous reste 30 cellules d'une couleur et 32 cellules d'une autre couleur. Supposons que nous ayons maintenant 30 carrés noirs et 32 carrés blancs.
Chaque dé que nous poserons sur le plateau occupera une case noire et une case blanche. Ainsi, 31 dominos occuperont 31 cases blanches et 31 cases noires. Mais il n'y a que 30 cellules noires et 32 blanches sur notre tableau. Par conséquent, il est impossible de décomposer les os.
L'analyse est tirée de la traduction du livre de G. Luckman McDowell et est destinée à des fins d'information uniquement.
Si vous l'avez aimé, nous vous recommandons d'acheter le livre.
Démontrer que le damier est 10X10 ne peut pas être coupé le long des lignes de la grille en rectangles 1X4. (Solutions selon D.Yu. Kuznetsov.)
La solution 1 . Divisez le tableau en carrés de 2x2 et coloriez-les en damier (Fig. 1). Notez que tout rectangle 1x4 contient également (2) cellules noires et blanches, mais avec cette coloration, il y a 52 cellules noires et 48 cellules blanches sur le tableau, c'est-à-dire pas également. Cela signifie qu'il ne sera pas possible de découper une planche 10x10 en rectangles 1x4.
La solution 2 . Colorons le tableau avec une coloration diagonale en 4 couleurs (Fig. 2). A noter que tout rectangle contient une cellule de chacune des quatre couleurs, mais avec une coloration donnée, il y a 25 cellules des 1ère et 3ème couleurs sur le plateau, 26 cellules de la 2ème et 24 cellules de la 4ème, soit pas également. Cela signifie qu'il ne sera pas possible de découper une planche 10x10 en rectangles 1x4.
1. Découpez les cellules des coins inférieur droit et gauche de l'échiquier. Est-il possible de découper la figure obtenue en dominos 1x2 ? Et si vous coupiez en bas à droite et en haut à gauche ?
2. Est-il possible de découper un plateau 6x6 en dominos pour qu'il y en ait exactement 11 horizontaux parmi eux ? (Coloration horizontale en deux couleurs.)
3. Coloriez le dessin en quatre couleurs afin que les parties adjacentes soient peintes de couleurs différentes. Est-il possible de se débrouiller avec trois couleurs ? (Voir Activité 6 : Coloriage carte géographique- Classe 5-6).
4. Dans un carré 4x4, les cellules de la moitié gauche sont peintes en noir et le reste en blanc. En une seule opération, il est permis de recolorer toutes les cellules à l'intérieur de n'importe quel rectangle dans la couleur opposée. Comment obtenir un coloriage d'échecs à partir du coloriage d'origine en trois opérations ?
5. Plusieurs sauterelles sont assises sur la même ligne droite et les distances entre voisins sont les mêmes. Toutes les minutes l'une d'elles saute vers un point qui lui est symétrique par rapport à une autre sauterelle. Après un certain temps, la sauterelle Sasha peut-elle se retrouver à l'endroit où sa voisine Lyosha était assise au début ?
6. a) Est-il possible de découper un échiquier en figures composées de 4 cases en forme de lettre « T » ?
b) Est-il possible de découper un échiquier 10x10 en de telles figures ?
7. Est-il possible de diviser un carré 8x8 avec un coin coupé en rectangles 1x3 ?
8. Une planche 10x10 peut-elle être découpée en morceaux de quatre alvéoles en forme de lettre « G » ? (Coloration horizontale en deux couleurs.)
9. Un plateau 8x8 est découpé en dominos 2x1. Peut-il y avoir 15 dominos verticaux et 17 dominos horizontaux ?
10. Le triangle est divisé en triangles (25 pièces), comme indiqué sur la figure. Le coléoptère peut marcher dans un triangle, se déplaçant entre des triangles adjacents (sur le côté). Quel est le nombre maximum de triangles que le scarabée peut traverser s'il n'a visité chaque triangle qu'une seule fois ?
11. Quel est le plus grand nombre de losanges, composés chacun de deux triangles équilatéraux de côté 1, que l'on peut découper dans un triangle équilatéral de côté 5 (voir la figure du problème précédent).
12. Le château triangulaire est divisé en 100 salles triangulaires identiques. Il y a une porte au milieu de chaque mur. Combien de chambres peuvent être visitées par une personne qui ne veut visiter nulle part plus d'une fois ?
Chapitre 2
Pour un compte rendu détaillé des mathématiques des échecs, que nous sommes sur le point de commencer, il est plus naturel de commencer par Problèmes mathématiques sur le plateau lui-même, sans placer encore de pièces dessus. C'est à ce sujet que ce chapitre est consacré.
Considérons tout d'abord plusieurs problèmes de recouvrement d'un plateau avec des dominos 2 × 1. Partout on suppose que chaque domino couvre deux cases du plateau, et chaque case est couverte par la moitié des dominos. Commençons par le prochain vieux problème.
Est-il possible de recouvrir de dominos un carré de taille 8 × 8, dans lequel sont découpées des cellules d'angle opposées (Fig. 2a)?
On pourrait utiliser un raisonnement algébrique, mais la solution « aux échecs » est à la fois plus simple et plus élégante. Colorons notre carré tronqué en noir et blanc, en le transformant en un échiquier sans deux champs d'angle a8 et h1 (Fig. 2b). Pour tout recouvrement du plateau, chaque domino recouvre un carré blanc et un carré noir. Nous avons deux champs blancs de moins que noirs (les champs coupés sont blancs), et donc la couverture nécessaire n'existe pas ! Comme nous pouvons le voir, la coloration de l'échiquier facilite non seulement la navigation d'un joueur d'échecs pendant la partie, mais sert également de moyen de résoudre des problèmes mathématiques.
Dans le problème considéré, il était important non pas que les champs d'angle soient coupés du tableau, mais qu'ils soient de la même couleur. Il est clair que peu importe comment vous découpez une paire de champs unicolores, vous ne pourrez pas couvrir le reste du plateau avec des dominos. Ainsi, le problème suivant se pose.
Supposons maintenant que deux champs de couleurs différentes soient découpés sur l'échiquier. Est-il toujours possible de couvrir le reste du plateau avec 31 dominos ?
Il s'avère que toujours. Une preuve spectaculaire a été trouvée par le célèbre mathématicien américain R. Gomory. Dessinons sur l'échiquier les limites entre les verticales et les horizontales comme indiqué sur la Fig. 3. Dans le labyrinthe entre ces bordures, des champs noirs et blancs se succèdent, alternant comme des boutons de deux couleurs sur un fil fermé (le chemin par lequel ce labyrinthe peut être contourné est fermé). Quels que soient deux champs de couleurs différentes que l'on découpe dans la planche, le fil se casse : à un endroit si les champs coupés sont adjacents, et à deux endroits sinon. Dans ce cas, chaque morceau de fil sera composé d'un nombre pair de champs. Par conséquent, ces pièces, et donc tout le plateau, peuvent être recouvertes de dominos !
Riz. 3. Labyrinthe Gomori |
Des idées curieuses liées aux boutons et aux fils seront trouvées dans le chapitre 11.
Supposons que certains champs soient découpés dans un échiquier afin qu'aucun domino ne puisse être placé sur la partie restante de celui-ci. Il est facile de vérifier que le plus petit nombre de champs découpés avec cette propriété est 32 - ce sont tous des champs de la même couleur (blanc ou noir).
Les problèmes de l'échiquier et des dominos ne sont qu'une petite partie d'une énorme série de problèmes de ce genre. Le mathématicien américain S. Golomb a créé toute une science, qu'il a appelée polymipo, et son livre sur ce sujet a été traduit dans de nombreux pays du monde, y compris le nôtre. En général, un polyomino est une figure simplement connexe composée de carrés. Du point de vue d'un joueur d'échecs, être simplement connecté signifie que toutes les cases polyominos peuvent être contournées par un coup de tour. Selon le nombre 07 de carrés, les polyominos se déclinent en différentes qualités. Un monomino contient un carré, un domino deux, un tromino trois, un tétramino quatre, un pentomino cinq, un heptomino six carrés, etc. Nous nous attarderons sur quelques autres problèmes liés à l'échiquier ordinaire. Évidemment, il est impossible de couvrir le dssk avec uniquement des trominos droits, c'est-à-dire des dominos 3 × 1, puisque 64 n'est pas divisible par 3. Le problème suivant se pose.
Est-il possible de recouvrir un échiquier avec 21 trominos droits et un monomino ? Si oui, quels champs un monomino peut-il occuper ?
L'un des revêtements dapo nécessaires de la Fig. 4a. Pour déterminer les arrangements possibles des monominos, nous dessinons deux systèmes de lignes parallèles sur le tableau, comme indiqué sur la fig. 4b.
Il est facile de voir que pour tout revêtement, chaque tromino couvre exactement un champ traversé par la ligne continue, et exactement celui traversé par la ligne pointillée. Étant donné que le nombre de champs intersectés par des lignes pleines est de 22, ainsi que le nombre de champs intersectés par des lignes pointillées, et qu'il y a 21 trominos, les monominos ne peuvent couvrir que les champs intersectés par les deux familles de lignes. Et il n'y a que quatre carrés de ce type : c3, c6, f3 et f6 ! En faisant pivoter la carte de 90, 180 et 270°, vous pouvez obtenir la couverture appropriée pour chacun de ces quatre champs.
La tâche suivante est quelque peu différente de celles décrites ci-dessus.
Est-il possible de recouvrir un échiquier de dominos de telle sorte qu'il soit impossible de tracer une seule frontière entre les verticales et les horizontales sans croiser les dominos ?
Si nous imaginons que la planche est un mur et que les dominos sont des briques, alors l'existence de la bordure spécifiée (couture) indique une maçonnerie fragile. En d'autres termes, le problème demande s'il est possible de disposer les "briques" de manière à ce que le "mur" ne s'effondre pas. Un rectangle qui peut être recouvert de la manière requise est appelé "fort". La "force" de l'échiquier peut être vue sur la Fig. 5. Dans le cas général, Gardner montre que les dominos peuvent être pliés en un rectangle "fort" si sa surface est paire, et si sa longueur et sa largeur sont supérieures à quatre, la seule exception étant un carré 6 × 6.
Ci-dessous, nous traiterons souvent d'échiquiers rectangulaires d'une taille ou d'une autre. Dans ce cas, on suppose toujours qu'un échiquier m×n a m verticales et n horizontales (échecs). On dit qu'un tableau est "pair" si le nombre de ses champs est pair, et "impair" sinon. Partout où les dimensions de l'échiquier ne sont pas précisées, on entend l'échiquier standard pour lequel m = n = 8.
Le plateau 100x4 est recouvert de dominos. Prouver qu'il peut être coupé le long de l'une des limites entre les verticales et les horizontales sans affecter aucun des dominos.
N'importe laquelle des bordures spécifiées divise le tableau en deux parties, constituées d'un nombre pair de champs. On divise les champs de chaque partie en deux classes : les dominos couverts se trouvant entièrement dans cette partie, et les dominos couverts coupés par la frontière. Comme le nombre de champs de chaque partie est pair (peut-être nul), ainsi que le nombre de champs de la première classe (chaque domino couvre deux champs), le nombre de champs de la seconde classe est pair. Et cela signifie que le nombre de dominos traversés par la frontière est pair. Il y a 102 limites de division au total (99 verticales et 3 horizontales), et si chacune d'elles croise des dominos, alors au moins 102 × 2 = 204 dominos participent à la couverture. Nous n'en avons que 200 ! En fait, nous avons montré qu'un rectangle de 100x4 est "faible".
La question de la possibilité de recouvrir une planche rectangulaire arbitraire avec des k-minos linéaires (dominos k × 1) est résolue par le théorème suivant.
Une planche m×n peut être recouverte de k-minos linéaires si et seulement si au moins un des nombres m ou n est divisible par k sans reste.
Nous illustrons le théorème avec l'exemple suivant.
Est-il possible de couvrir un plateau 10x10 (une centaine de pions carrés sont joués sur un tel plateau) avec des tétraminos droits ?
Un tétramino droit a des dimensions de 4x1, ce qui signifie qu'en principe 25 tuiles pourraient couvrir tous les champs de notre plateau. Cependant, il découle du théorème que cela est impossible - 10 n'est pas divisible par 4.
Considérons quelques problèmes supplémentaires concernant l'échiquier. Dans la solution du problème suivant viovb sa coloration est utilisée.
Soit le tableau composé d'un nombre impair de champs. Sur chacun de ses champs nous mettrons quelques pièce d'échecs. Est-il possible de déplacer toutes ces pièces sur des cases adjacentes (verticalement ou horizontalement) afin qu'aucune d'entre elles ne se retrouve sur la même case ?
La tâche est impossible. En effet, si le déplacement de pièces indiqué existait, alors chaque pièce "blanche" (se tenant sur un champ blanc) deviendrait "noire" (tombant sur un champ noir), et chaque "noire" - "blanche".
Ainsi, le plateau serait composé du même nombre de champs blancs et noirs, et cela contredit sa "bizarre".
Populaires sont les problèmes de découpe d'un échiquier. Le plus célèbre d'entre eux est le suivant, propriété de S. Loyd.
Il y a quatre cavaliers sur les champs a1, b2, c3, d4. Découpez la planche en quatre parties congruentes (coïncidantes lorsqu'elles sont superposées) de manière à ce que chacune d'elles ait un cheval.
Dans les problèmes de coupe, on suppose toujours que les coupes ne sont faites que le long des limites entre les verticales et les horizontales de la planche. La solution à ce problème est illustrée à la fig. 6. Depuis l'époque de Loyd, de nombreux problèmes nouveaux et plus difficiles sont apparus sur ce sujet. En particulier, les problèmes de découpage du plateau en quatre parties congruentes ont été résolus pour différentes positions des chevaliers (les chevaliers, bien sûr, ne jouent ici qu'un rôle symbolique). Il y a encore beaucoup de problèmes non résolus à ce sujet. Par exemple, le nombre de façons dont une planche régulière (sans pièces) peut être découpée en deux pièces congruentes n'est toujours pas connue.
Riz. 6. Le problème des quatre chevaux de Loyd |
Laissez, après plusieurs coupes de la planche, les pièces résultantes peuvent être déplacées de sorte que la prochaine coupe puisse couper non pas une, mais plusieurs pièces à la fois. Combien de coupes faudra-t-il pour obtenir 64 espaces de plateau individuels (1×1 cases) ?
Tout d'abord, nous coupons la planche en deux, puis mettons les deux moitiés côte à côte et coupons la planche en quatre parties identiques, etc. Au total, 6 coupes seront nécessaires (2 e \u003d 64) et un plus petit nombre ne peut être dispensé .
Laissez maintenant les parties de la planche ne peuvent être coupées que séparément. Combien de coupes seront nécessaires pour obtenir 64 champs dans ce cas ?
En règle générale, cette tâche (surtout si elle est proposée après la précédente) pose certaines difficultés. Apparemment, cela est dû à une certaine inertie de notre pensée. Après tout, il est immédiatement clair que 63 coupes seront nécessaires ! En effet, chaque coupe augmente le nombre de pièces d'une unité ; en même temps, au moment initial, nous avons une partie (le tableau lui-même) et au moment final - 64 (tous les champs du tableau).
Riz. 7. Trois problèmes sur un tableau inhabituel |
Dans la tâche de la Fig. 7a, vous devez accomplir trois tâches, une mathématique et deux purement échiquéennes :
a) couper la planche en quatre parties congruentes ;
b) mater le roi noir de la manière la plus courte lorsque les blancs se déplacent ;
c) mater le roi noir de la manière la plus courte ; tandis que les noirs se déplacent, les fidèles jouent en coopération).
Solutions : a) comment couper la planche, illustrée à la fig. 7b; b) quand les blancs se déplacent, échec et mat est donné au 12ème coup : 1-12. Be1-b4, Ke3-d3-c4, Be4-c2-b3, Kc4-c3, Bb4-d6, Bb3-d5, Kc3-c2, Bd6-c5, Bd5-c4, Bd6-b4échec et mat (tous les mouvements du roi noir sont forcés et ne sont pas donnés); c) avec un jeu correct après 1. ... Re6-e7 échec et mat impossible, car le roi noir se cache en e8 - 2. Fe1-b4+ Re7-e8, et le fou de case noire est obligé de quitter la diagonale a3 - e7 en raison de la menace d'une impasse. Cependant, si Noir joue en coopération (en aidant Blanc à échec et mat), alors le but est atteint en seulement trois coups :
1. … Re6-d6
2. Re3-d4 Re6-e7
3. Be1-b4+ Ke7-e6
4. Fe4-d5 mat. Un certain nombre de champs de notre planche ne sont pas utilisés lors de l'accouplement, mais s'ils étaient exclus, il n'y aurait aucun problème à couper la planche.
Riz. 8. Paradoxe avec la coupe de l'échiquier : a) 8×8 = 64 ; b) 13×5 = 65 |
Considérons maintenant un paradoxe bien connu associé à la coupe de l'échiquier. Nous avons coupé la planche en quatre parties, comme indiqué sur la Fig. 8, a (dans ce cas, il n'est pas rentable pour nous de colorer ses champs), et à partir des parties résultantes, nous ajouterons un rectangle (Fig. 8, b). L'aire du tableau est de 64 et l'aire du rectangle résultant est de 65. Ainsi, lors de la découpe du tableau, un champ supplémentaire est venu de quelque part!
La solution au paradoxe est que nos dessins ne sont pas tout à fait exacts (nous avons délibérément tracé des lignes épaisses pour masquer les inexactitudes). Avec une construction soignée du dessin de la Fig. 8b, au lieu de la diagonale du rectangle, une figure en forme de losange légèrement allongé apparaîtra avec des côtés qui semblent avoir presque fusionné. L'aire de cette figure sera juste égale à l'unité "supplémentaire".
Le vulgarisateur bien connu des mathématiques au début du siècle, E. Ignatiev, a inventé la «méthode de l'échiquier», qui permet de dériver diverses formules. Nous donnons deux exemples simples sur ce sujet.
Trouvons la somme des n premiers nombres naturels en utilisant la "méthode du damier". Pour ce faire, sur le tableau (n + 1) × n (sur la Fig. 9, a n = 8) on colorie tous les champs de la première verticale, tous les champs de la deuxième verticale (sauf celui du haut), les troisième verticale (sauf pour les deux du haut), etc. d., enfin - en bas champ nième vertical. En conséquence, les champs blancs et noirs sur notre tableau seront égaux, à savoir 1 + 2 + ... + n. Puisque tout le tableau est constitué de n (n + 1) champs, nous obtenons
2 (1 + 2 + … + n) = n(n + 1),
d'où découle la formule bien connue de la somme d'une progression arithmétique :
1 + 2 + … + n = n(n + 1)/2.
Démontrons maintenant la formule suivante :
8(1 + 2 + ... + n) + 1 = (2n + 1)².
Pour ce faire, prenez un tableau (2n + 1) × (2n + 1) et peignez un certain nombre de ses champs en noir, comme indiqué sur la Fig. 9, 6 (pour le cas n = 5). Évidemment, chaque partie noire contient (1 + 2 + ... + n) champs. Sans tenir compte du champ central, nous avons ici quatre parties blanches et noires identiques. La formule requise découle du fait que notre carte contient (2n + 1)² champs et se compose d'un champ central et de huit parties identiques (quatre blanches et quatre noires - Fig. 9b).
Lors de la résolution du paradoxe, en plus de se familiariser avec la «méthode de l'échiquier», le plateau lui-même peut être remplacé en toute sécurité par une feuille de papier à carreaux ou une table. Il existe un grand nombre de problèmes avec de tels objets, mais leur examen détaillé nous éloignerait trop des échecs.
En conclusion du chapitre, nous présentons une ancienne preuve sur l'échiquier... du théorème de Pythagore. Dessinez un carré au tableau, comme illustré à la Fig. 10, a. Le plateau est divisé en ce carré et en quatre triangles rectangles congrus. Sur la fig. 10, 6 on voit les quatre mêmes triangles, ainsi que deux carrés. Ainsi, les triangles dans les deux cas occupent la même zone. Par conséquent, les parties restantes du plateau sans triangles occupent la même zone, sur la Fig. 10,a - un carré, et sur la fig. 10b - deux. Puisque le grand carré est construit sur l'hypoténuse d'un triangle rectangle et que les petits carrés sont sur ses jambes, alors "les pantalons de Pythagore sont égaux dans toutes les directions" !
Bien entendu, à proprement parler, notre raisonnement ne prouve pas le théorème de Pythagore (seul un cas particulier a été étudié), mais seulement l'illustre. Mais une telle preuve va sans utiliser d'échiquier - pour tout triangle rectangle, vous pouvez choisir un carré qui se casse de la même manière.
C'est cette solution qui est donnée dans le livre de T. Saati "Integer Optimization Methods and Related Extremal Problems" (M., "Mir", 1973).
S. Golomb. Polyomino. M., Mir, 1974.
Il a été prouvé par A. Soifer dans l'article "Planches à damier et polymipo" ("Kvant", 1972, n° 11) ; un certain nombre de nouveaux problèmes de polyominos y sont également donnés.
E. Ignatiev. Dans le domaine de l'ingéniosité, ou de l'arithmétique pour tous. Livre. 1 - 3. M. - Pg., Gosizdat, 1923.
6. Il y a 235 allumettes dans une boîte. Deux joueurs les prennent à tour de rôle. En un coup, vous pouvez prendre de 1 à 6 matchs. Le joueur gagne
remporter le dernier match. Qui gagne lorsqu'il est joué correctement ?
62
7. Un carré d'angle est découpé dans une planche 8 × 8. Est-il possible de poser la planche en rectangles 1×3 ?
8. Sur 30 matchs, deux joueurs prennent à leur gré de 1
jusqu'à 6 matchs. Celui qui prend le dernier match gagne.
9. Il y a trois tas de pierres. Un état est un triplet de nombres
(X
1
, X
2
, X
3
), où x i
- le nombre de pierres dans la ième pile. Un déplacement est l'opération consistant à transférer d'un tas à l'autre le nombre de pierres égal au nombre de pierres dans le tas où le transfert est effectué. A partir de l'état initial (11, 7, 6) obtenir l'état (8, 8, 8).
10. Divisez le cercle en un nombre maximum de parties en utilisant quatre lignes droites.
11. Coupez la croix grecque avec deux lignes droites de sorte que
former un rectangle à partir des pièces résultantes, dont un côté est le double de l'autre.
12. Il y a un approvisionnement de 12 litres de liquides et de récipients vides dans 9
et 5 l. Il est nécessaire de mesurer exactement 6 litres. Combien de litres peut-on mesurer avec de tels récipients à partir d'une réserve de 12 litres ?
13. Déterminer le nombre de séquences de longueur n à partir de (0, 1, 2),
dans lequel il n'y a pas deux unités consécutives.
14. Est-il possible de couvrir un carré 10 × 10 avec des chiffres de la forme
15. Est-il possible de couvrir un carré 10 × 10 avec des chiffres de la forme
63
16. Est-il possible de couvrir un carré 8 × 8 avec une cellule d'angle découpée avec des figures de la forme
17. Est-il possible de recouvrir de figures de la forme un échiquier 8 × 8 dans lequel un carré est découpé:
18. Est-il possible de poser un échiquier avec une cage d'angle sculptée avec des pièces de la forme
19. Est-il possible de faire la traversée de quatre paires de chevaliers-écuyers à l'aide d'une embarcation à deux, si l'écuyer ne peut se trouver sur la même rive avec le ou les chevaliers d'un autre en l'absence de son maître ?
20. Développez un algorithme pour trouver les deux plus petits nombres dans une séquence non ordonnée de n nombres.
21. Sur 27 matchs restant sur la table, deux joueurs remportent alternativement au moins un et pas plus de quatre matchs. Le gagnant est celui qui à la fin du jeu aura un nombre pair de matchs. Développer un algorithme pour le jeu du premier joueur.
64
22. Deux participants au jeu appellent à tour de rôle un numéro de 1 à 10.
En appelant un numéro, le joueur l'ajoute à la somme de nombres déjà existante (en appelant le premier numéro, le joueur l'ajoute à zéro). Le joueur qui marque 100 victoires.
Développer un algorithme pour le jeu du premier joueur.
23. Trouvez le nombre minimum de questions (réponses possibles :
"oui", "non") un nombre caché à 5 chiffres, si la somme des trois premiers chiffres est 17.
24. Trouvez le nombre minimum de questions (réponses possibles :
"oui", "non") un nombre caché à 4 chiffres, si la somme des deuxième et quatrième chiffres est 7.
25. De combien de façons peut-on échanger 100 roubles ? pièces de monnaie en
5, 10, 20 et 50 roubles ?
26. Calculez récursivement le nombre de nombres à six chiffres dont la somme des quatre premiers chiffres est 26 et la somme des deux derniers est 14.
27. Calculer récursivement le nombre de partitions du nombre 37 par cinq termes dont le premier ne dépasse pas 7, le second
- 5, et les troisième et quatrième prennent des valeurs de l'ensemble
{5, 6, 7, 8}.
28. Calculez récursivement le nombre de nombres à sept chiffres dont la somme des quatre premiers nombres est 21 et la somme des cinq derniers est 19.
29. Calculer récursivement le nombre de partitions du nombre 27 par quatre termes dont le premier ne dépasse pas 7,
le deuxième est 8, et les troisième et quatrième prennent des valeurs de l'ensemble (3, 5, 7).
30. Calculez récursivement le nombre de nombres à cinq chiffres dont les trois premiers chiffres totalisent 21 et les trois derniers chiffres totalisent 12.
65
31. Calculez récursivement le nombre de nombres à sept chiffres dans lesquels la somme des premier et troisième chiffres est 12 et la somme des cinq autres est 19.
32. Calculer récursivement
(2n - 2)(2n - 4) × . . . ×2
(n + 1)(n + 3) × . . . × (n + 2n − 1)
un n−5
b
−(n+3)
33. Calculez récursivement le nombre de nombres à sept chiffres dont la somme des quatre premiers chiffres est 17 et la somme des trois derniers est 16.
34. Calculez récursivement le nombre de partitions du nombre 17 par quatre termes, dont le premier ne dépasse pas 4, le second - 8, et les troisième et quatrième prennent les valeurs (3, 4, 8).
35. Calculez récursivement le nombre de nombres à sept chiffres dont la somme des carrés des quatre premiers nombres est 17 et la somme des carrés des deux derniers est 16.
36. Calculer récursivement le nombre de partitions du nombre 25 par quatre termes dont le premier ne dépasse pas 8,
le deuxième est 3, et les troisième et quatrième prennent des valeurs de l'ensemble (2, 5, 9).
37. Calculez récursivement le nombre de placements de tours N sur le plateau
N × N tels que les tours sont symétriques par rapport aux deux diagonales et ne s'attaquent pas.
38. Calculez récursivement le nombre de séquences binaires de n éléments dans lesquelles il manque deux séquences adjacentes.
39. Soit un réseau N × M :
66
M
N
UN
B
Calculez récursivement le nombre de chemins de A à B. Un chemin est une séquence de mouvements le long de la grille menant de gauche à droite et de bas en haut.
40. Les nombres a sont donnés
1
, . . . , un
dans un certain ordre. Pour calculer le produit a
1
·. . . un
tout en maintenant l'ordre des facteurs, il existe de nombreuses façons de placer des parenthèses entre les facteurs. Calculez récursivement le nombre de façons de placer les parenthèses.
41. Calculez récursivement le nombre de nombres à 8 chiffres dont la somme des cinq premiers chiffres est 29 et la somme des trois derniers chiffres est 21.
67
3
. méthodes d'analyse d'algorithmes
3.1. Cours d'algorithme
Dans les sections précédentes, nous avons considéré différentes approches qui peuvent être utilisées dans la construction d'algorithmes. Pour trouver une solution, analyser l'efficacité de cette solution, on peut émettre diverses hypothèses, utiliser d'autres algorithmes déjà connus, reformuler l'état du problème, etc. Vous pouvez rechercher des problèmes similaires avec une solution connue et utiliser cette solution pour trouver un algorithme pour le problème requis.
Cependant, il existe de nombreux problèmes particuliers pour lesquels des solutions ont été trouvées. Il y a encore plus de tâches non résolues ou résolues avec certaines restrictions et conditions. Rechercher des problèmes similaires parmi l'ensemble des problèmes, évaluer les solutions existantes en fonction de leur degré de "convenance" peut être un problème difficile, chronophage et pas toujours soluble. Il serait plus utile et productif d'essayer de définir des classes de problèmes unis par un problème commun, des méthodes et des approches communes de résolution, puis de rechercher la classe à laquelle notre problème particulier qui doit être résolu peut être attribué. Bien sûr, il ne devrait pas y avoir trop de telles classes, mais d'un autre côté, il ne devrait pas y en avoir trop peu, de sorte que chaque nouvelle tâche définissez votre propre nouvelle classe, qui ne sera alors probablement pas utilisée pour résoudre d'autres problèmes.
Comme exemple d'un problème appartenant à une certaine classe, considérons le problème bien connu de l'identification d'une pièce contrefaite.
Tâche 3.1 (problème de pièce de monnaie contrefaite). Il y a n pièces,
parmi lesquels il peut y avoir un faux. La pièce contrefaite diffère du reste par son poids et nous avons à notre disposition une balance à deux tasses. Il est nécessaire de déterminer une pièce contrefaite pour le nombre minimum de pesées ou d'établir,
qu'il n'y a pas de pièces contrefaites.
68
La solution. Le problème des pièces contrefaites a été résolu en Sec. 2.2,
mais alors on savait qu'une pièce contrefaite était forcément plus légère. Essayons maintenant de résoudre ce problème pour un cas plus général. Toute solution à ce problème (pas forcément optimale)
peut être interprété comme une séquence de pesées. Cependant, il est clair que le choix des pièces à peser à n'importe quelle étape dépend des pièces qui ont été utilisées et des résultats de la pesée dans les étapes précédentes. Nous allons décrire la séquence des pesées comme suit. Nous renumérotons les pièces et les définissons comme un ensemble S = (1, 2, . . . , n). Les ensembles de nombres de pièces pesées sur les plateaux gauche et droit de la balance peuvent être désignés par S
L
et S
R
respectivement. Il est clair que la pondération n'a de sens que si les cardinalités des ensembles S
L
et S
R
correspondre, c'est-à-dire Chaque échelle a le même nombre de pièces. La pesée sera désignée par le signe ":", puis chaque pesée
(S
L
) : (S
R
) il y a trois résultats possibles. Beaucoup de pièces
S
L
peut être plus léger, plus lourd ou avoir le même poids que l'ensemble S
R
. Ensuite, nous désignerons ces résultats de pondération comme
"" ou "=", respectivement. Un exemple de pesées pour quatre pièces est illustré à la fig. 3.1. Les ovales représentent les pesées, les carrés représentent les résultats, indiquant le numéro de la pièce contrefaite et si elle est plus légère ou plus lourde que les autres.
Le cas d'absence de pièce contrefaite est indiqué par "0", les cases barrées correspondent à des cas qui ne peuvent pas se produire.
On estimera le nombre maximum de pesées nécessaires pour résoudre le problème, c'est-à-dire pire cas. Comme on peut le voir sur la fig. 3.1, le problème est résolu en 3 pesées dans le pire des cas. Notez que même dans le meilleur des cas, nous avons besoin d'au moins 2
pesée. Peut-on obtenir un meilleur résultat ?
Sur la fig. 3.1 présente une autre solution au problème de la pesée de quatre pièces. Lors de la première étape, nous ne pesons pas quelques pièces, mais toutes les pièces, en les divisant en deux ensembles. En conséquence, nous avons réalisé qu'au mieux une seule pesée est nécessaire,
cependant, dans le pire des cas, le nombre de pesées est à nouveau de 3.
69
(1) : (2)
(1) : (3)
(1) : (4)
0 4T
4L
3T
3L
(1) : (4)
2T
1L
(1) : (4)
2L
1T
=
=
=
>
>
>
>
>
=
=
Riz. 3.1. Résoudre le problème des pièces contrefaites
Notez que, contrairement à la première option de pesée,
illustré à la fig. 3.1, dans la deuxième version, nous avons non seulement défini le schéma de pesée, mais également introduit un nouveau concept de pièces candidates contrefaites. En effet, considérons le résultat de la première pesée, (1, 2) : (3, 4). Soit (1, 2) L
= (1, 2), et S
R
= (3, 4). Alors
S
L
R
. A partir de ce résultat, il n'est pas possible de juger si la pièce contrefaite est plus légère ou plus lourde que toutes les autres,
et dans quel ensemble il est. Cependant, on peut supposer
(et encore plus précisément - on peut soutenir) que si une pièce contrefaite appartient à l'ensemble S
L
, alors la pièce contrefaite est plus légère que les autres, on désigne un tel ensemble par la lettre L. Dans notre cas, si les pièces numérotées 1 ou 2 sont des contrefaçons, alors elles sont plus légères que les vraies. Si les fausses pièces portant les numéros 3 ou
4, alors ils sont plus lourds que les vrais, nous désignerons l'ensemble correspondant par la lettre T. Dans la fig. 3.2 Les candidats contrefaits légers et lourds sont indiqués par des marques sur les bords de l'arbre.
Évidemment, on peut répondre à la question du nombre optimal de pesées en continuant à trier les schémas possibles de choix des pièces. Puisque le nombre de pièces est fini, tôt ou tard une telle énumération peut être complétée. Pour l'instant, attardons-nous sur les deux solutions obtenues et essayons d'analyser ce qu'elles ont donné
70
(1.2) L
(3.4) T
(1.2) T
(3.4) L
(1,2) : (3,4)
(3) : (4)
4T
3T
(1) : (2)
1L
=
=
>
>
>
=
0 2L
(3) : (4)
3L
4L
(1) : (2)
2T
=
>
>
=
1T
Riz. 3.2. Une autre solution au problème d'une pièce de monnaie contrefaite pour nous du point de vue d'une approche générale pour résoudre le problème.
Comme on le sait, toute stratégie de pesée de pièces peut être décrite à l'aide d'un arbre ternaire ou ternaire. En d'autres termes, le problème considéré appartient à la classe des problèmes ,
décrit par des arbres ternaires. Une telle classification du problème permet d'analyser non pas chaque solution spécifique, mais toutes les solutions en général, sur la base des propriétés connues des arbres.
Ainsi, l'itération sur les voies possibles la pondération est en fait une recherche dans divers arbres ternaires, dont, bien sûr, le nombre est exponentiel. D'autre part, essayons de déterminer ce qu'il est généralement possible d'obtenir lors de la résolution d'un problème donné, en utilisant son appartenance à cette classe particulière.
De la fig. 3.1 et 3.2, on peut voir que, représentant la séquence des pesées à l'aide d'un arbre, on attribue chaque pesée à un sommet d'arbre qui n'est pas une feuille (représenté à l'aide d'ovales), tandis que les résultats, y compris les impossibles,
correspondait aux feuilles de l'arbre (représentées par des carrés). Tous les nœuds de l'arbre peuvent être classés par niveaux,
71
À
un
=
=
>
À
un
Et
Et
Et
=
>
À
un
Et
Et
Et
=
>
À
un
Et
Et
Et
=
>
À
un
Et
Et
Et
=
>
À
un
=
>
À
un
=
>
À
un
>
À
À
L
À
0
À
1
À
je
-
1
À
je
……
………………
………
…
…
……
…
…
…
…
…
……
……
…
…
g
un =
je
Riz.
3.3.
J
arbre de poids vernal
72
ceux. par leur distance à la racine de l'arbre. Le numéro de niveau est égal au nombre d'arêtes qui doivent passer de la racine pour arriver au sommet. niveau donné(Fig. 3.3). Si la profondeur de l'arbre est le niveau de la feuille la plus éloignée de la racine, alors cette valeur est égale au nombre de pondérations dans le pire des cas.
Combien y a-t-il de résultats possibles dans notre problème ? Chacune des n pièces peut s'avérer être une fausse pièce légère ou une fausse pièce lourde, et il se peut qu'il n'y ait aucune fausse pièce du tout.
Ainsi, nous avons 2n + 1 résultats. Cela signifie que dans l'arbre
correspondant au schéma de pesée, doit être au moins
2n + 1 feuilles. Un arbre ternaire de profondeur l contient au plus,
plus de 3
Je pars. À partir de là, nous pouvons estimer la profondeur minimale possible de l'arbre
3
je
≥ 2n + 1,
et donc
l ≥ log
3
(2n + 1).
(3.1)
Ainsi, pour n = 4, le nombre minimum possible de pesées est supérieur ou égal à 2. Ici, nous ne parlons pas du nombre minimum de pesées pour ce schéma - comme dans la Fig. 3.2, et il y a des cas où la solution du problème est déjà trouvée après la première pesée - nous évaluons la pire option, c'est-à-dire le nombre maximal de pondérations pour un schéma donné, c'est-à-dire que l'on cherche un minimum parmi les profondeurs maximales de tous les arbres ayant au moins 2n + 1 feuilles.
Cependant, on peut montrer qu'il n'y a pas de méthode de pondération qui donnerait l'égalité dans l'estimation (3.1).
THÉORÈME 3.1
Le nombre de pesées dans le pire des cas pour le problème des pièces contrefaites est estimé à l > log
3
(2n + 1).
Preuve. Comme déjà mentionné, pour n pièces, il y a 2n + 1 résultats possibles. Chaque pesée peut avoir trois résultats possibles, et chaque résultat a son propre
73
schéma des pesées ultérieures. Dans le même temps, le schéma a son propre nombre de résultats possibles, en tenant compte du résultat de la dernière pesée. Soit à la première pesée |S
L
| = |S
R
| = k, c'est-à-dire
k pièces sont utilisées sur un plateau de balance et k pièces sur l'autre,
où k ≤ n/2 . Si en même temps S
L
R
, puis les pièces de S
L
nous déclarons des candidats pour les pièces contrefaites légères et les pièces de S
R
- Candidats aux pièces contrefaites lourdes. De cette façon,
avec le résultat de la première pesée, 2k résultats sont possibles.
De même, pour S
L
>S
R
2k autres résultats sont possibles. Donc, pour S
L
= S
R
les 2n + 1 − 4k résultats restants sont possibles.
Si l'égalité est vraie dans (3.1), cela signifie que l'arbre ternaire est complet et que toutes ses feuilles sont au ième niveau.
Mais pour cela il faut qu'après chaque pesée, les résultats possibles soient répartis équitablement sur les trois branches et l'égalité
2k = 2n + 1 − 4k,
ce qui est impossible puisque 2k est toujours un nombre pair, et
2n + 1 − 4k est toujours impair.
Une idée importante a été utilisée dans la preuve du Théorème 3.1 :
Pour que l'arbre de pondération soit optimal, ou du moins aussi proche que possible de l'optimum, il est nécessaire que les résultats soient répartis uniformément sur tous les résultats de chaque pesée.
Ainsi, nous avons obtenu une estimation du pire nombre de pesées dans le problème de la fausse monnaie en rapportant ce problème à la classe de problèmes
décrit par des arbres ternaires. Considérons maintenant un problème légèrement modifié.
Problème 3.2 (problème d'une pièce contrefaite en présence d'un étalon). Il y a n pièces, parmi lesquelles il peut y avoir une contrefaçon, et une pièce de plus, dont on sait avec certitude qu'elle est réelle. Il est nécessaire de déterminer la pièce contrefaite dans le nombre minimum de pesées ou d'établir qu'il n'y a pas de pièces contrefaites.
74
La solution. Ce problème diffère du précédent par la présence d'une pièce de référence supplémentaire, mais il s'avère que cette pièce supplémentaire permet de construire des arbres de poids optimaux pour lesquels l'égalité en (3.1) est vérifiée. Notons n l
le nombre pour lequel l'égalité tient
3
je
= 2n l
+ 1.
(3.2)
En considérant le problème précédent du théorème 3.1, nous avons obtenu : pour que l'égalité (3.1) soit satisfaite, l'arbre de pondération doit être complet. Par conséquent, s'il est possible de construire un tel arbre optimal de l niveaux, alors il spécifiera un schéma de l pondérations pour n l
pièces de monnaie. Notez que la relation suivante est vraie :
n l
= 3nl−1
+ 1.
(3.3)
Puisque pour n
0
= 0 dans (3.2) nous obtenons l'égalité, 3 0
= 2 0 + 1,
puis à partir d'ici en utilisant (3.3) nous pouvons obtenir n
1
= 1,n
2
=
4,n
3
= 13 etc... La solution (3.2) est la suite
0, 1, 4, 13, 40, . . ..
Ainsi, lorsque l'égalité (3.2) est vérifiée, l'ensemble des n
l pièces sont divisées en trois parties égales par n l−1
pièces et il reste encore une pièce. Considérons différentes situations qui peuvent survenir au cours du processus de pesée.
Schéma 1. Soit au début de la pesée nous avons n i
pièces de monnaie, où n i
appartient à la suite (3.3) pour certains i. Posons n i−1
pièces de monnaie, où n
je
= 3n i−1
+ 1,
puis nous ajoutons une pièce de référence au plateau gauche de la balance, et l'un des n i−1 restants
+ 1 pièces. Notons les ensembles pondérés, comme précédemment, par S
L
et S
R
Soit maintenant à la suite de la pesée de S
L
= S
R
. Étant donné que la pièce de référence a participé à la pesée, il est évident que la pièce contrefaite, le cas échéant, fait partie des n inutilisés
i−1
pièces, et le problème se réduit à un problème avec n i−1
pièces de monnaie. Où
75
Du fait de la pondération, nous avons encore 2n i−1 possibles
+ 1 =
3
i−1
résultats. Maintenant, laissez S
L
R
. Cela signifie que la pièce contrefaite est soit dans l'ensemble S
L
et en même temps il est plus léger que les autres, ou dans l'ensemble S
R
et puis il est plus lourd que les autres.
De plus, il existe n i−1
pièces légères suspectes et n i−1
+ 1 lourd suspect et ensemble cela donne à nouveau 2n i−1
+ 1 = 3
i−1
résultats possibles.
Enfin, soit S
L
>S
R
. Alors on a n i−1
candidats pièces lourdes et n i−1
+1 candidats pour les poumons et total 2n i−1
+1 =
3
i−1
résultats. Ainsi, avec un tel schéma de la première pesée, nous obtenons en fait que 3
i les résultats initiaux ont été uniformément répartis en fonction des résultats de la pesée. Pour déterminer s'il est possible de régler le schéma de pesée de sorte qu'après chaque pesée, les résultats soient divisés en un nombre égal de parties, considérez les résultats de la pesée. Évidemment, pour S
L
= S
R
on arrive au même problème, mais avec une dimension plus petite, et on peut toujours refaire la pondération selon le schéma 1, mais avec une valeur de i plus petite.
Schéma 2. Soit maintenant S
L
R
. Dans ce cas, nous définissons la stratégie de pondération comme suit. Les données initiales sont qu'à une certaine étape i dans la séquence de pondérations, nous avons 3
je
= 2n je
+ 1 pièces, dont n i
candidats contrefaits légers et n i
+ 1 candidats pour lourd, tandis que le nombre n i
est un nombre de la forme (3.3)
n je
= 3n i−1
+ 1.
Mettre sur chaque plateau de balance n i−1
candidats faciles et n
i−1
+1 lourd. Puisqu'il n'y a que 2n i
+1 = 2(3n i−1
+1)+1 = 6n i−1
+3
pièces de monnaie et peser
2n i−1
+ 2n i−1
+ 2 = 4n i−1
+ 2
pièces, alors il y a encore 2n i−1
+ 1 pièces, dont n i−1
+ 1
poumons et n i−1
lourd. Puisqu'il y a le même nombre de pièces légères et lourdes sur les deux balances, alors si les balances ne sont pas équilibrées,
cela donne n i−1
candidats pour les pièces légères (du bol qui s'est avéré plus léger) et n i−1
+ 1 candidats pour le lourd (du bol qui s'est avéré être
76
plus lourd). Cela nous amène aux données originales du même schéma
(schémas 2), mais pour 3
i−1
= 2n i−1
+ 1 pièces. Si les balances sont équilibrées, alors cela signifie qu'il faut chercher une pièce contrefaite parmi les n i−1 non pesés
+ 1 poumons et n i−1
pièces lourdes, ce qui correspond au schéma 3. Évidemment, 2n i−1
+1 résultats, c'est-à-dire encore une fois, l'ensemble de tous les résultats possibles est divisé en trois parties égales.
Schéma 3. Soit maintenant S
L
>S
R
. Dans ce cas nous avons 3
je
=
2n je
+ 1 pièces, dont n i
+ 1 candidats légers contrefaits, et n i
candidats poids lourds. Tous les arguments sont similaires au schéma 2, à la différence que lors de la pesée, il faut mettre n i−1
+ 1 candidats faciles, et n i−1
lourd. Si les balances ne sont pas équilibrées, cela nous donne à nouveau le modèle 3 pour 3
i−1
pièces, sinon on obtient les conditions de pesée correspondant au schéma 2. Là encore, dans tous les cas, l'ensemble des résultats possibles est divisé en trois parties égales de 2n i−1
+ 1.
Ainsi, nous avons trois fois
1 2
3
=
>
=
=
Riz. 3.4. Transitions entre les schémas de pondération dans le problème des pièces contrefaites à l'état personnel décrit ci-dessus et la règle de pondération pour chaque état. En fonction du résultat de la pesée, on passe à un autre état (ou on reste dans le même état), mais pour un nombre de pièces moindre. A chaque pesée, le nombre d'issues possibles est équitablement réparti en fonction des résultats de la pesée. Le schéma des transitions entre les états est illustré à la fig. 3.4. Un exemple de pesées pour 27 pièces est représenté sur la fig. 3.5.
77
Tache 1: Un carré de 5 × 5 peut-il être découpé en rectangles de 1 × 2 (dominos). Tâche 2 : Les carrés des coins opposés sont découpés dans un échiquier 8×8. Le reste peut-il être découpé en rectangles 1 × 2 (dominos) ? La solution: Non. Chaque domino occupe un carré noir et un carré blanc, et il y a différents nombres de carrés noirs et blancs sur le plateau sans coins. Tâche 3 : Dans les coins opposés d'un plateau 10 × 10, on découpe deux carrés 3 × 3. Le reste peut-il être découpé en dominos ? Tâche 4 : Créez une pièce connectée sur un échiquier, dans laquelle il y a un nombre égal de cellules noires et blanches, mais qui ne peut pas être divisée en dominos. Tâche 5 : Est-il possible de couper un carré de 10 × 10 en 25 morceaux ? Tâche 6 :La solution: Coloriez le tableau en damier. Il y aura un nombre pair de cellules noires, et une ou trois d'entre elles tomberont dans chaque figure. Tâche 7 : Est-il possible de couper un carré de 10 × 10 en 25 morceaux ? La solution:
Coloriez le tableau en quatre couleurs (voir image). Chaque figure occupe une cellule de chaque couleur, et les cellules des première et deuxième couleurs ont un nombre différent.
Direction : coloriez le tableau en trois couleurs.
Tâche 12 : Quel est le nombre maximum de barres 1 × 1 × 4 pouvant être découpées dans un cube 6 × 6 × 6 ? Tâche 13 : Le rectangle est divisé en chiffres et . L'un des perdus, mais remplacé par. Prouver que le nouvel ensemble ne peut pas couvrir le rectangle d'origine. Tâche 14 : Un carré de 16 × 16 peut-il être divisé en 64 rectangles de 1 × 4, dont 31 seront verticaux et les 33 restants horizontaux ? La solution: Coloriez toutes les quatre verticales. Tâche 15 : Pour quoi n le carré n × n peut-il être divisé en a) ;b) ? La solution: Pour n divisible par quatre.
Tâche 16 : Un rectangle m × k est divisé en 1 × n rectangles. Montrer que m est divisible par n ou que k est divisible par n.c) pour tout n. La solution:
Colorier en n couleurs.
Tâche 17 : Montrer qu'un rectangle m × n peut être partitionné en rectangles a × b si et seulement si les conditions suivantes sont satisfaites :1) m et n sont représentés par ka + lb (k et l sont des entiers non négatifs)
2) m et n sont divisibles par a.
3) m ou n est divisible par b.
Tâche 18 : Un rectangle m × n est dit fort s'il peut être divisé en dominos de telle sorte que toute coupe du rectangle coupe au moins un domino. Prouve-le:a) rectangle 2 × n - fragile
b) rectangle 3 × n - fragile
c) rectangle 4 × n - fragile
d) rectangles 5×6 et 6×8 - fort
e) si un rectangle m × n est fort, alors un rectangle m × (n + 2) est aussi fort.
f) * Rectangle 6×6 - fragile
g) Quels rectangles sont forts et lesquels ne le sont pas ? La solution: f) Indice : Chaque ligne d'un carré 6×6 croise un nombre pair de dominos.
g) Tous les rectangles m × n où mn est pair, m,n ≥ 5, sauf 6 × 6.
Tâche 19 :Un coin est une figure de la forme.
a) Un rectangle de 5 × 9 peut-il être divisé en coins ?
b) Démontrer qu'un rectangle dont les côtés sont supérieurs à 100 et dont l'aire est divisible par 3 peut être divisé en coins.
c) Quels rectangles peuvent être divisés en coins et lesquels ne le peuvent pas ?
Tâche 20 :Une planche de 2 n × 2 n sans carré de coin peut-elle être divisée en coins ? La solution: Oui, vous pouvez. La partition est construite par induction.
Tâche 21 : Pour quel n un tableau (2n + 1) × (2n + 1) sans cellule d'angle peut-il être divisé en dominos, parmi lesquels il y en a également des verticaux et des horizontaux? La solution: Pour n pair.
