Sarcină logică pentru aranjarea oaselor de domino pe o tablă de șah

5. Un pătrat de colț este decupat dintr-o placă de 9 × 9. Această placă poate fi așezată în dreptunghiuri de 1×5?
6. Într-o cutie sunt 235 de chibrituri. Doi jucători le iau pe rând. Într-o singură mișcare, poți lua de la 1 la 6 meciuri. Jucătorul câștigă

luând ultimul meci. Cine câștigă când este jucat corect?
62

7. Un pătrat de colț este decupat dintr-o placă de 8 × 8. Este posibil să așezi tabla în dreptunghiuri de 1×3?
8. Din 30 de meciuri, doi jucători iau la discreție de la 1
până la 6 meciuri. Câștigă cel care ia ultimul meci.

9. Sunt trei mormane de pietre. Un stat este un triplu de numere
(X
1
, X
2
, X
3
), unde x i
- numărul de pietre în i-a grămada. O mișcare este operația de transfer de la grămadă la grămadă a numărului de pietre egal cu numărul de pietre din grămada în care se face transferul. Din starea inițială (11, 7, 6) obțineți starea (8, 8, 8).
10. Împărțiți cercul în numărul maxim de părți folosind patru linii drepte.
11. Tăiați crucea greacă cu două linii drepte astfel încât
pentru a forma un dreptunghi din părțile rezultate, a cărui latură este de două ori cealaltă.
12. Există o rezervă de 12 litri cu lichid și vase goale în 9

și 5 l. Este necesar să se măsoare exact 6 litri. Câți litri se pot măsura cu astfel de vase dintr-o rezervă de 12 litri?
13. Determinați numărul de secvențe de lungime n din (0, 1, 2),
în care nu există două unităţi consecutive.
14. Este posibil să acoperiți un pătrat de 10 × 10 cu figuri de formă
15. Este posibil să acoperiți un pătrat de 10 × 10 cu figuri ale formei
63

16. Este posibil să acoperiți un pătrat de 8×8 cu o celulă de colț decupată cu figuri de formă
17. Este posibil să acoperiți cu figuri de forma unei table de șah 8 × 8 în care este decupat un pătrat:
18. Este posibil să așezați o tablă de șah cu o cușcă de colț sculptată cu piese din formă
19. Se poate face incrucisarea a patru perechi de cavaler-schire cu ajutorul unei barci duble, daca scutierul nu poate fi pe acelasi mal cu cavalerul(i) altcuiva(i) in lipsa stapanului sau?
20. Elaborați un algoritm pentru găsirea celor mai mici două numere dintr-o secvență neordonată de n numere.
21. Din 27 de meciuri aflate pe masă, doi jucători iau alternativ cel puțin unul și cel mult patru meciuri. Câștigătorul este cel care la sfârșitul jocului va avea un număr par de meciuri. Dezvoltați un algoritm pentru jocul primului jucător.
64

22. Doi participanți la joc apelează pe rând un număr de la 1 la 10.
Apelând un număr, jucătorul îl adaugă la suma de numere deja existentă (apelând primul număr, jucătorul îl adaugă la zero). Câștigă jucătorul care înscrie 100.
Dezvoltați un algoritm pentru jocul primului jucător.
23. Găsiți numărul minim de întrebări (răspunsuri posibile:
„da”, „nu”) un număr ascuns din 5 cifre, dacă suma primelor trei cifre este 17.
24. Găsiți numărul minim de întrebări (răspunsuri posibile:
„da”, „nu”) un număr ascuns din 4 cifre, dacă suma a doua și a patra cifrei este 7.
25. În câte moduri pot fi schimbate 100 de ruble? monede în

5, 10, 20 și 50 de ruble?
26. Calculați recursiv numărul de numere din șase cifre a căror sumă a primelor patru cifre este 26 și suma ultimelor două este 14.
27. Calculați recursiv numărul de partiții ale numărului 37 cu cinci termeni, primul dintre care nu depășește 7, al doilea
- 5, iar al treilea și al patrulea iau valori din set
{5, 6, 7, 8}.
28. Calculați recursiv numărul de numere de șapte cifre a căror sumă a primelor patru numere este 21, iar suma ultimelor cinci este 19.
29. Calculați recursiv numărul de partiții ale numărului 27 cu patru termeni, primul dintre care nu depășește 7,
al doilea este 8, iar al treilea și al patrulea iau valori din set (3, 5, 7).
30. Calculați recursiv numărul de numere din cinci cifre ale căror primele trei cifre însumează până la 21 și ultimele trei cifre însumează până la 12.
65

31. Calculați recursiv numărul de numere de șapte cifre în care suma primei și a treia cifre este 12, iar suma celor cinci rămase este 19.
32. Calculați recursiv
(2n − 2)(2n − 4) × . . . ×2
(n + 1)(n + 3) × . . . × (n + 2n − 1)
un n−5
b
−(n+3)
33. Calculați recursiv numărul de numere de șapte cifre a căror sumă a primelor patru cifre este 17 și suma ultimelor trei este 16.
34. Calculați recursiv numărul de partiții ale numărului 17 cu patru termeni, primul dintre care nu depășește 4, al doilea - 8, iar al treilea și al patrulea iau valorile (3, 4, 8).
35. Calculați recursiv numărul de numere de șapte cifre a căror sumă a pătratelor primelor patru numere este 17, iar suma pătratelor ultimelor două este 16.
36. Calculați recursiv numărul de partiții ale numărului 25 cu patru termeni, primul dintre care nu depășește 8,
al doilea este 3, iar al treilea și al patrulea iau valori din set (2, 5, 9).
37. Calculați recursiv numărul de plasări de N turnuri pe tablă
N × N astfel încât turnurile să fie simetrice față de ambele diagonale și să nu se atace reciproc.
38. Calculați recursiv numărul de secvențe binare de n elemente din care lipsesc două adiacente.
39. Având în vedere o rețea N × M:
66

M
N
A
B
Calculați recursiv numărul de căi de la A la B. O cale este o succesiune de mișcări de-a lungul grilei care conduc de la stânga la dreapta și de jos în sus.
40. Sunt date numerele a
1
, . . . , un n
într-o anumită ordine. Pentru a calcula produsul a
1
·. . .a n
păstrând ordinea factorilor, există multe modalități de a plasa paranteze între factori. Calculați recursiv numărul de moduri de a plasa paranteze.
41. Calculați recursiv numărul de numere din 8 cifre a căror sumă a primelor cinci cifre este 29 și suma ultimelor trei cifre este 21.
67

3
. metode de analiză a algoritmului
3.1. Clasele de algoritm
În secțiunile anterioare, am luat în considerare diferite abordări care pot fi utilizate în construcția algoritmilor. Pentru a găsi o soluție, pentru a analiza eficacitatea acestei soluții, se pot înainta diverse ipoteze, se pot folosi alți algoritmi deja cunoscuți, se pot reformula starea problemei etc. Puteți căuta unele probleme similare cu o soluție cunoscută și puteți utiliza această soluție pentru a găsi un algoritm pentru problema necesară.
Cu toate acestea, există o mulțime de probleme speciale pentru care s-au găsit soluții. Există și mai multe sarcini nerezolvate sau rezolvate cu anumite restricții și condiții. Căutând probleme similare între întregul set de probleme, evaluarea soluțiilor existente în funcție de gradul lor de „adecvare” poate fi o problemă dificilă, consumatoare de timp și nu întotdeauna rezolvabilă. Ar fi mai util și mai productiv să încercăm să definim clase de probleme unite printr-o problemă comună, metode și abordări comune de rezolvare și apoi să căutăm clasa căreia i se poate atribui problema noastră particulară care trebuie rezolvată. Desigur, nu ar trebui să existe prea multe astfel de clase, dar, pe de altă parte, nu ar trebui să fie prea puține, astfel încât pentru fiecare sarcină nouă să nu fie necesară definirea propriei clase noi, care atunci este puțin probabil să fie utilizată. pentru a rezolva alte probleme.
Ca exemplu de problemă aparținând unei anumite clase, luați în considerare problema binecunoscută a identificării unei monede contrafăcute.
Problema 3.1 (problema monedelor contrafăcute). Sunt n monede,
printre care poate exista unul fals. Moneda contrafăcută diferă de restul prin greutate, iar la dispoziție avem un cântar cu două căni. Este necesar să se determine o monedă contrafăcută pentru numărul minim de cântăriri sau să se stabilească,
că nu există monede contrafăcute.
68

Soluţie. Problema monedelor contrafăcute a fost rezolvată în Sec. 2.2,
dar apoi se știa că o monedă falsă era neapărat mai ușoară. Acum să încercăm să rezolvăm această problemă pentru un caz mai general. Orice soluție la această problemă (nu neapărat optimă)
poate fi interpretat ca o succesiune de cântăriri. Cu toate acestea, este clar că alegerea monedelor pentru cântărire la orice pas depinde de monedele folosite și de rezultatele cântăririi în pașii anteriori. Vom descrie succesiunea cântăririlor după cum urmează. Renumerotăm monedele și le definim ca un set S = (1, 2, . . . , n). Seturile de numere de monede cântărite pe tăvile din stânga și din dreapta ale balanței pot fi notate cu S
L
si S
R
respectiv. Este clar că ponderarea are sens numai dacă cardinalitățile mulțimilor S
L
si S
R
potrivire, adică Fiecare cântar are același număr de monede. Cântărirea va fi notată prin semnul „:”, apoi fiecare cântărire
(S
L
): (S
R
) există trei rezultate posibile. O mulțime de monede
S
L
poate fi mai ușor, mai greu sau cu aceeași greutate ca setul S
R
. Apoi vom nota aceste rezultate de ponderare ca
„” sau „=", respectiv. Un exemplu de cântărire pentru patru monede este prezentat în fig. 3.1. Ovalele reprezintă cântăriri, pătratele reprezintă rezultate, indicând numărul de monedă falsă și dacă este mai ușoară sau mai grea decât celelalte.
Cazul fără monedă falsă este indicat cu „0”, pătratele tăiate corespund cazurilor care nu pot apărea.
Vom estima numărul maxim de cântăriri necesare pentru a rezolva problema, adică. cel mai rău caz. După cum se poate observa din fig. 3.1, problema se rezolvă în 3 cântăriri în cel mai rău caz. Rețineți că, chiar și în cel mai bun caz, avem nevoie de cel puțin 2

cântărind. Se poate obține un rezultat mai bun?
Pe fig. 3.1 prezintă o altă soluție la problema cântăririi a patru monede. La primul pas, cântărim nu câteva monede, ci toate monedele, împărțindu-le în două seturi. Drept urmare, am reușit că, în cel mai bun caz, este nevoie de o singură cântărire,
cu toate acestea, în cel mai rău caz, numărul de cântăriri este din nou de 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
=
=
=
>
>
>
>
>
=
=
Orez. 3.1. Rezolvarea problemei monedelor false
Rețineți că, spre deosebire de prima opțiune de cântărire,
prezentată în fig. 3.1, în cea de-a doua versiune, nu numai că am definit schema de cântărire, dar am introdus și un nou concept de candidați pentru monede contrafăcute. Într-adevăr, luați în considerare rezultatul primei cântăriri, (1, 2) : (3, 4). Fie (1, 2) L
= (1, 2) și S
R
= (3, 4). Apoi
S
L
R
. Din acest rezultat nu se poate aprecia dacă moneda falsă este mai ușoară sau mai grea decât toate celelalte,
și în ce set este. Cu toate acestea, se poate presupune
(și chiar mai precis - se poate argumenta) că dacă o monedă falsă aparține setului S
L
, atunci moneda falsă este mai ușoară decât celelalte, notăm un astfel de set cu litera L. În cazul nostru, dacă monedele cu cifrele 1 sau 2 sunt false, atunci sunt mai ușoare decât cele reale. Dacă monedele contrafăcute cu numerele 3 sau
4, atunci sunt mai grele decat cele reale, vom nota multimea corespunzatoare cu litera T. In fig. 3.2 candidații contrafăcuți ușori și grei sunt indicați prin marcaje pe marginile arborelui.
Evident, se poate răspunde la întrebarea despre numărul optim de cântăriri continuând sortarea scheme posibile selecția monedelor. Deoarece numărul de monede este finit, mai devreme sau mai târziu o astfel de enumerare poate fi finalizată. Deocamdată, să ne oprim asupra celor două soluții obținute și să încercăm să analizăm ce au dat
70

(1,2) L
(3,4) T
(1.2) T
(3,4) L
(1,2) : (3,4)
(3) : (4)
4 T
3 T
(1) : (2)
1 L
=
=
>
>
>
=
0 2 L
(3) : (4)
3 L
4 L
(1) : (2)
2 T
=
>
>
=
1 T
Orez. 3.2. O altă soluție la problema unei monede contrafăcute pentru noi din punctul de vedere al unei abordări generale a rezolvării problemei.
După cum se știe, orice strategie de cântărire a monedelor poate fi descrisă folosind un arbore ternar sau ternar. Cu alte cuvinte, problema luată în considerare aparține clasei de probleme,
descrise de arbori ternari. O astfel de clasificare a problemei face posibilă analizarea nu a fiecărei soluții specifice, ci a tuturor soluțiilor în general, pe baza proprietăților cunoscute ale arborilor.
Astfel, iterația s-a încheiat moduri posibile ponderarea este de fapt o căutare prin diverși arbori ternari, dintre care, desigur, sunt exponențial mulți. Pe de altă parte, să încercăm să determinăm ce este, în general, posibil de realizat atunci când rezolvăm o anumită problemă, folosind apartenența acesteia la această clasă particulară.
Din fig. 3.1 și 3.2 se poate observa că, ilustrând succesiunea cântăririlor folosind un arbore, atribuim fiecare cântărire unui vârf de arbore care nu este o frunză (reprezentat folosind ovale), în timp ce rezultatele, inclusiv cele imposibile,
corespundea frunzelor copacului (prezentate cu pătrate). Toate nodurile arborelui pot fi ordonate pe nivele,
71

LA
A
=
=
>
LA
A
Și
Și
Și
=
>
LA
A
Și
Și
Și
=
>
LA
A
Și
Și
Și
=
>
LA
A
Și
Și
Și
=
>
LA
A
=
>
LA
A
=
>
LA
A
>
La
LA
L
La
0
La
1
La
l
- 1
La
l
……
………………
………
…
…
……
…
…
…
…
…
……
……
…
…
G
a =
l
Orez.
3.3.
T
arbore cu greutate primară
72

acestea. prin distanța lor față de rădăcina copacului. Numărul nivelului este egal cu numărul de muchii care trebuie să treacă de la rădăcină pentru a ajunge la vârful acestui nivel (Fig. 3.3). Dacă adâncimea copacului este nivelul frunzei cel mai îndepărtat de rădăcină, atunci această valoare este egală cu numărul de ponderi în cel mai rău caz.
Câte rezultate posibile există în problema noastră? Fiecare dintre cele n monede se poate dovedi a fi o monedă falsă ușoară sau grea falsă și este posibil să nu existe deloc monede false.
Astfel, avem 2n + 1 rezultate. Aceasta înseamnă că în copac
corespunzătoare schemei de cântărire, trebuie să fie cel puțin
2n + 1 frunze. Un arbore ternar de adâncime l conține cel mult,
decat 3
Plec. Din aceasta putem estima adâncimea minimă posibilă a copacului
3
l
≥ 2n + 1,
și, prin urmare
l ≥ log
3
(2n + 1).
(3.1)
Astfel, pentru n = 4, numărul minim posibil de cântăriri este mai mare sau egal cu 2. Aici ne referim la numărul minim de cântăriri pentru această schemă - ca în Fig. 3.2, și există cazuri când soluția problemei este deja găsită după prima cântărire - evaluăm cea mai proastă variantă, adică. numărul maxim de ponderi pentru o schemă dată, cu alte cuvinte, căutăm un minim printre adâncimile maxime ale tuturor arborilor cu cel puțin 2n + 1 frunze.
Cu toate acestea, se poate demonstra că nu există o metodă de ponderare care să dea egalitate în estimare (3.1).
TEOREMA 3.1
Numărul de cântăriri în cel mai rău caz pentru problema monedelor contrafăcute este estimat ca l > log
3
(2n + 1).
Dovada. După cum sa menționat deja, pentru n monede, există 2n + 1 rezultate posibile. Fiecare cântărire poate avea trei rezultate posibile, iar fiecare rezultat are propriile sale rezultate
73

schema de cântăriri ulterioare. În același timp, schema are propriul său număr de rezultate posibile, ținând cont de rezultatul ultimei cântăriri. Se lasa la prima cantarire |S
L
| = |S
R
| = k, adică
k monede sunt folosite pe o scară și k monede pe cealaltă,
unde k ≤ n/2 . Dacă în același timp S
L
R
, apoi monede din S
L
declarăm candidați pentru monede ușoare contrafăcute și monede de la S
R
- Candidați pentru monede grele contrafăcute. În acest fel,
cu rezultatul primei cântăriri, sunt posibile 2k de rezultate.
În mod similar, pentru S
L
>S
R
Sunt posibile alte 2.000 de rezultate. Prin urmare, pentru S
L
=S
R
celelalte 2n + 1 - 4k rezultate sunt posibile.
Dacă egalitatea este valabilă în (3.1), aceasta înseamnă că arborele ternar este complet și toate frunzele sale sunt la al 1-lea nivel.
Dar pentru aceasta este necesar ca după fiecare cântărire, rezultatele posibile să fie distribuite uniform pe cele trei ramuri și egalitatea
2k = 2n + 1 − 4k,
ceea ce este imposibil deoarece 2k este întotdeauna un număr par și
2n + 1 − 4k este întotdeauna impar.
O idee importantă a fost folosită în demonstrarea teoremei 3.1:
Pentru ca arborele de ponderare să fie optim, sau cel puțin cât mai aproape de optim, este necesar ca rezultatele să fie distribuite uniform pe toate rezultatele fiecărei cântăriri.
Astfel, am obținut o estimare pentru cel mai slab număr de cântăriri în problema monedelor contrafăcute prin raportarea acestei probleme la clasa de probleme.
descrise de arbori ternari. Acum luați în considerare o problemă ușor modificată.
Problema 3.2 (problema legată de o monedă contrafăcută în prezența unui standard). Există n monede, printre care poate fi o singură contrafăcută și încă o monedă, despre care se știe cu siguranță că este reală. Este necesară determinarea monedei contrafăcute în numărul minim de cântăriri sau stabilirea faptului că nu există monede contrafăcute.
74

Soluţie. Această problemă diferă de cea anterioară prin prezența unei monede de referință suplimentare, dar se dovedește că această monedă suplimentară permite construirea arborilor de ponderare optimă pentru care egalitatea din (3.1) este satisfăcută. Notăm cu n l
numărul pentru care este valabilă egalitatea
3
l
= 2n l
+ 1.
(3.2)
Considerând problema anterioară din teorema 3.1, am obținut: pentru ca egalitatea (3.1) să fie satisfăcută, arborele de ponderare trebuie să fie complet. Prin urmare, dacă este posibil să se construiască un astfel de arbore optim de l niveluri, atunci se va specifica o schemă de ponderi l pentru n l
monede. Rețineți că următoarea relație este adevărată:
nl
= 3nl−1
+ 1.
(3.3)
Deoarece pentru n
0
= 0 în (3.2) obținem egalitatea, 3 0
= 2 0 + 1,
apoi de aici folosind (3.3) putem obține n
1
= 1,n
2
=
4,n
3
= 13 etc. Soluția (3.2) este șirul
0, 1, 4, 13, 40, . . ..
Astfel, când egalitatea (3.2) este valabilă, mulțimea lui n
l monedele sunt împărțite în trei părți egale cu n l−1
monede și a mai rămas o monedă. Să luăm în considerare diferite situații care pot apărea în timpul procesului de cântărire.
Schema 1. Fie că la începutul cântăririi avem n i
monede, unde n i
aparține șirului (3.3) pentru unii i. Să punem n i−1
monede, unde n
i
= 3n i−1
+ 1,
apoi adăugăm o monedă de referință în panoul din stânga al cântarilor și una dintre n i−1 rămase
+ 1 monedă. Notați seturile ponderate, ca mai înainte, prin S
L
si S
R
Acum, ca rezultat al cântăririi S
L
=S
R
. Deoarece moneda de referință a participat la cântărire, este evident că moneda contrafăcută, dacă există, se numără printre n-urile neutilizate.
i−1
monede, iar problema se reduce la o problemă cu n i−1
monede. în care
75

Ca rezultat al ponderării, mai avem 2n i−1 posibil
+ 1 =
3
i−1
rezultate. Acum hai să
L
R
. Aceasta înseamnă că moneda falsă se află fie în setul S
L
și în același timp este mai ușor decât celelalte, sau în mulțimea S
R
si atunci este mai greu decat celelalte.
Mai mult, există n i−1
monede ușoare suspecte și n i−1
+ 1 grea suspectă și împreună aceasta dă din nou 2n i−1
+ 1 = 3
i−1
rezultate posibile.
În sfârșit, să fie S
L
>S
R
. Atunci avem n i−1
candidați pentru monede grele și n i−1
+1 candidați pentru plămâni și total 2n i−1
+1 =
3
i−1
rezultate. Deci, cu o astfel de schemă a primei cântăriri, obținem de fapt acel 3
i rezultatele inițiale au fost distribuite uniform în funcție de rezultatele cântăririi. Pentru a determina dacă este posibil să setați schema de cântărire astfel încât, după fiecare cântărire, rezultatele să fie împărțite într-un număr egal de părți, luați în considerare rezultatele cântăririi. Evident, pentru S
L
=S
R
ajungem la aceeași problemă, doar cu o dimensiune mai mică, și oricând putem efectua din nou ponderarea conform schemei 1, dar cu o valoare mai mică a lui i.
Schema 2. Fie acum S
L
R
. În acest caz, definim strategia de ponderare după cum urmează. Datele inițiale sunt că la un pas i din succesiunea de ponderi avem 3
i
= 2n i
+ 1 monede, printre care n i
candidați ușoare contrafăcute și n i
+ 1 candidați pentru grea, în timp ce numărul n i
este un număr de forma (3.3)
n i
= 3n i−1
+ 1.
Puneți pe fiecare scară pan n i−1
candidați ușori și n
i−1
+1 grea. Deoarece există doar 2n i
+1 = 2(3n i−1
+1)+1 = 6n i−1
+3
monede și cântăresc
2n i−1
+ 2n i−1
+ 2 = 4n i−1
+ 2
monede, atunci mai sunt 2n i−1
+ 1 monede, printre care n i−1
+ 1
plămânii și n i−1
greu. Deoarece există același număr de monede ușoare și grele pe ambele cântare, atunci dacă cântarul nu este echilibrat,
aceasta dă n i−1
candidații pentru monede ușoare (din castronul care s-a dovedit a fi mai ușor) și n i−1
+ 1 candidați pentru grea (din castronul care s-a dovedit a fi
76

mai grele). Acest lucru ne aduce la datele originale ale aceleiași scheme
(schemele 2), dar pentru 3
i−1
= 2n i−1
+ 1 monedă. Dacă cântarul este echilibrat, atunci aceasta înseamnă că trebuie să căutăm o monedă falsă printre n i−1 necântărit
+ 1 plămâni și n i−1
monede grele, care corespunde Schemei 3. Evident, 2n i−1
+1 rezultate, de ex. din nou, setul tuturor rezultatelor posibile este împărțit în trei părți egale.
Schema 3. Fie acum S
L
>S
R
. În acest caz avem 3
i
=
2n i
+ 1 monede, printre care n i
+ 1 candidați contrafăcuți ușor și n i
candidați la categoria grea. Toate argumentele sunt similare cu schema 2, cu diferența că atunci când cântăriți, trebuie să puneți n i−1
+ 1 candidați simpli și n i−1
greu. Dacă cântarul nu este echilibrat, acest lucru ne oferă din nou modelul 3 pentru 3
i−1
monede, altfel obținem condițiile de cântărire corespunzătoare Schemei 2. Din nou, în toate cazurile, setul de rezultate posibile este împărțit în trei părți egale de 2n i−1
+ 1.
Astfel, avem de trei ori
1 2
3
=
>
=
=

Orez. 3.4. Tranzițiile între schemele de ponderare în problema monedelor falsificate de stat personal descrisă mai sus și regula de ponderare pentru fiecare stat. În funcție de rezultatul cântăririi, trecem în altă stare (sau rămânem în aceeași stare), dar pentru un număr mai mic de monede. La fiecare cântărire, numărul de rezultate posibile este distribuit uniform în funcție de rezultatele cântăririi. Schema tranzițiilor între stări este prezentată în fig. 3.4. Un exemplu de cântărire pentru 27 de monede este prezentat în fig. 3.5.
77

Sarcina 1: Un pătrat de 5 × 5 poate fi tăiat în dreptunghiuri de 1 × 2 (dominos). Sarcina 2: Pătrațele de colț opus sunt tăiate dintr-o tablă de șah de 8×8. Restul poate fi tăiat în dreptunghiuri de 1 × 2 (dominos)? Soluţie: Nu. Fiecare domino ocupă un negru și unul celule albe, iar pe o tablă fără colțuri de celule albe și negre, un număr diferit. Sarcina 3: Din colțurile opuse ale unei table de 10 × 10, sunt tăiate două pătrate de 3 × 3. Restul poate fi tăiat în piese de domino? Sarcina 4: Vino cu o piesă conectată pe o tablă de șah, în care există un număr egal de celule albe și negre, dar care nu poate fi împărțită în piese de domino. Sarcina 5: Este posibil să tăiați un pătrat de 10 × 10 în 25 de bucăți? Sarcina 6:Soluţie: Colorează tabla într-un model de șah. Va exista un număr par de celule negre și una sau trei dintre ele vor cădea în fiecare cifră. Sarcina 7: Este posibil să tăiați un pătrat de 10 × 10 în 25 de bucăți? Soluţie:

Colorează tabla în patru culori (vezi poza). Fiecare figură ocupă o celulă din fiecare culoare, iar celulele primei și celei de-a doua culori au un număr diferit.

Sarcina 8: Este posibil să tăiați un pătrat de 10 × 10 în 25 de bucăți? Soluţie: Pictați verticala printr-una. Sarcina 9: Demonstrați că o placă de 8 × 8 fără un pătrat de colț nu poate fi tăiată în dreptunghiuri de 1 × 3. Sarcina 10: Se poate tăia o placă de 8×8 într-un pătrat de 2×2 și 15 bucăți din formă? Sarcina 11: Pătratul a)5 × 5b)8 × 8 este împărțit în mai multe dreptunghiuri 3 × 1 și un pătrat 1 × 1. Unde poate fi un pătrat 1 × 1? Soluţie: a) În centru, b) Pe al treilea pătrat în diagonală din orice colț.

Direcție: Colorează tabla în trei culori.

Sarcina 12: Care suma maxima 1 × 1 × 4 bare pot fi tăiate dintr-un cub de 6 × 6 × 6? Sarcina 13: Dreptunghiul este împărțit în figuri și . Unul dintre pierduți, dar l-a înlocuit cu. Demonstrați că noul set nu poate acoperi dreptunghiul original. Sarcina 14: Un pătrat de 16 × 16 poate fi împărțit în 64 dreptunghiuri 1 × 4, dintre care 31 vor fi verticale și restul de 33 orizontale? Soluţie: Colorează fiecare a patra verticală. Sarcina 15: Pentru ce n poate fi împărțit pătratul n × n în a) ;

b)? Soluţie: Pentru n divizibil cu patru.

Sarcina 16: Un dreptunghi m × k este împărțit în 1 × n dreptunghiuri. Demonstrați că m este divizibil cu n sau k este divizibil cu n.

c) pentru orice n. Soluţie:

Culoare în n culori.

Sarcina 17: Demonstrați că un dreptunghi m × n poate fi împărțit în a × b dreptunghiuri dacă și numai dacă sunt îndeplinite următoarele condiții:

1) m și n sunt reprezentați ca ka + lb (k și l sunt numere întregi nenegative)

2) m și n sunt divizibile cu a.

3) m sau n este divizibil cu b.

Sarcina 18: Un dreptunghi m × n se numește puternic dacă poate fi împărțit în piese de domino în așa fel încât orice tăietură a dreptunghiului să intersecteze cel puțin un domino. Demonstrați că:

a) 2 × n dreptunghi - fragil

b) dreptunghi 3 × n - fragil

c) dreptunghi 4 × n - fragil

d) dreptunghiuri 5×6 și 6×8 - puternice

e) dacă un dreptunghi m × n este puternic, atunci un dreptunghi m × (n + 2) este de asemenea puternic.

f) * dreptunghi 6×6 - fragil

g) Care dreptunghiuri sunt puternice și care nu? Soluţie: f) Sugestie: Fiecare linie dintr-un pătrat de 6×6 traversează un număr par de piese de domino.

g) Toate m × n dreptunghiuri unde mn este par, m,n ≥ 5, cu excepția lui 6 × 6.

Sarcina 19:

Un colț este o figură a formei.

a) Un dreptunghi de 5 × 9 poate fi împărțit în colțuri?

b) Demonstrați că un dreptunghi cu laturile mai mari de 100 și aria divizibilă cu 3 poate fi împărțit în colțuri.

c) Ce dreptunghiuri pot fi împărțite în colțuri și care nu?

Sarcina 20:

O placă de 2 n × 2 n fără un pătrat de colț poate fi împărțită în colțuri? Soluţie: Da, poti. Partiția este construită prin inducție.

Sarcina 21: Pentru ce n poate fi împărțită o placă (2n + 1) × (2n + 1) fără celulă de colț în piese de domino, printre care sunt în egală măsură verticale și orizontale? Soluţie: Pentru chiar n.

Demonstrați că tabla de șah este 10X10 nu poate fi tăiat de-a lungul liniilor grilei în dreptunghiuri 1X4. (Soluții conform lui D.Yu. Kuznetsov.)

Soluţie 1 . Împărțiți tabla în pătrate de 2x2 și colorați-le într-un model de șah (Fig. 1). Rețineți că orice dreptunghi de 1x4 conține în mod egal (2 fiecare) celule albe și negre, dar cu această colorare, există 52 de celule negre și 48 de celule albe pe tablă, adică. nu la fel. Aceasta înseamnă că nu va fi posibil să tăiați o placă de 10x10 în dreptunghiuri de 1x4.

Soluţie 2 . Să colorăm tabla cu o colorare diagonală în 4 culori (Fig. 2). Rețineți că orice dreptunghi conține câte o celulă din fiecare dintre cele patru culori, dar cu o colorare dată, există 25 de celule din prima și a treia culoare pe tablă, 26 de celule din a 2-a și 24 de celule din a patra, adică. nu la fel. Aceasta înseamnă că nu va fi posibil să tăiați o placă de 10x10 în dreptunghiuri de 1x4.

1. Decupați celulele din colțul din dreapta jos și din stânga de pe tabla de șah. Este posibil să tăiați figura rezultată în piese de domino 1x2? Și dacă tăiați dreapta jos și stânga sus?

2. Este posibil să tăiați o tablă de 6x6 în piese de domino astfel încât să fie exact 11 orizontale printre ele? (Colorare orizontală în două culori.)

3. Colorează desenul în patru culori, astfel încât părțile adiacente să fie pictate în culori diferite. Este posibil să te descurci cu trei culori? (Vezi Activitatea 6: Colorare harta geografica- clasa 5-6).

4. Într-un pătrat de 4x4, celulele din jumătatea stângă sunt vopsite în negru, iar restul în alb. Într-o singură operație, este permisă recolorarea tuturor celulelor din interiorul oricărui dreptunghi în culoarea opusă. Cum să obțineți o colorare de șah din colorarea originală în trei operații?

5. Mai multe lăcuste stau pe aceeași linie dreaptă, iar distanțele dintre vecini sunt aceleași. În fiecare minut, unul dintre ei sare într-un punct simetric față de el față de o altă lăcustă. Poate după ceva timp lăcusta Sasha să ajungă în locul în care stătea la început vecina lui Lyosha?

6. a) Este posibil să tăiați o tablă de șah în figuri formate din 4 celule în forma literei „T”?

b) Este posibil să tăiați o tablă de șah 10x10 în astfel de figuri?

7. Este posibil să împărțiți un pătrat de 8x8 cu un colț tăiat în dreptunghiuri de 1x3?

8. Se poate tăia o placă de 10x10 în bucăți de patru celule în forma literei „G”? (Colorare orizontală în două culori.)

9. O tablă de 8x8 este tăiată în piese de domino 2x1. Pot exista 15 piese de domino verticale și 17 orizontale?

10. Triunghiul este împărțit în triunghiuri (25 de bucăți), așa cum se arată în figură. Gândacul poate merge într-un triunghi, mișcându-se între triunghiuri adiacente (pe laterale). Care este numărul maxim de triunghiuri prin care poate trece gândacul dacă a vizitat fiecare triunghi nu mai mult de o dată?

11. Care este cel mai mare număr de romburi, fiecare fiind alcătuit din două triunghiuri echilaterale cu latura 1, care pot fi tăiate dintr-un triunghi echilateral cu latura 5 (vezi figura problemei anterioare).

12. Castelul triunghiular este împărțit în 100 de săli triunghiulare identice. Există o ușă în mijlocul fiecărui perete. Câte camere poate fi vizitată de o persoană care nu dorește să viziteze nicăieri de mai multe ori?

În această lecție, vom vorbi despre paginile de colorat și despre modul în care acestea ajută la rezolvarea problemelor. Luați în considerare problemele non-standard de tăiere și placare și modalități de a le rezolva.

Rezumatul lecției „Tăiere. Teselare. Colorare”.

Planse de colorat. tăiere. Teselații.

Mulți oameni de știință au fost pasionați de problemele de tăiere din cele mai vechi timpuri. Soluții la multe probleme simple de tăiere au fost găsite de grecii antici și chinezi, dar primul tratat sistematic pe această temă a fost scris de Abul-Vef, celebrul astronom persan din secolul al X-lea, care a locuit la Bagdad. Geometrii s-au ocupat serios de rezolvarea problemelor de tăiere a figurilor în cel mai mic număr de părți și apoi de a compune din ele una sau alta figură nouă abia la începutul secolului al XX-lea. Unul dintre fondatorii acestei ramuri fascinante a geometriei a fost faimosul compilator de puzzle Henry E. Dudeney. Un număr deosebit de mare de cifre preexistente de tăiere recorduri au fost doborâte de examinatorul Oficiului Australian de Brevete Harry Lindgren. El este un taietor de figuri de frunte.

Astăzi, iubitorii de puzzle-uri sunt pasionați de rezolvarea problemelor de tăiere, în primul rând pentru că nu există o metodă universală de rezolvare a unor astfel de probleme, iar oricine își asumă soluția își poate demonstra pe deplin ingeniozitatea, intuiția și capacitatea de a gândi creativ. Deoarece aici nu sunt necesare cunoștințe profunde de geometrie, amatorii pot uneori chiar să depășească matematicienii profesioniști.

Pentru a demonstra că este posibil să se rezolve problema tăierii unei figuri în bucăți, este suficient să se furnizeze un fel de metodă de tăiere. Găsirea tuturor soluțiilor, adică a tuturor modalităților de tăiere, este puțin mai dificilă. Și să dovedești că tăierea este imposibilă este deja destul de dificil. În unele cazuri, colorarea figurii ne ajută să facem acest lucru.

Sarcina 1: Am luat un pătrat de hârtie în carouri de 8 × 8, am tăiat două celule din el (stânga jos și dreapta sus). Este posibil să acoperiți complet figura rezultată cu „domino” - 1 × 2 dreptunghiuri?

Sarcina 2. Este posibil să așezați o tablă de șah cu treizeci și două de piese de domino, astfel încât 17 dintre ele să fie așezate orizontal și 15 pe verticală?

Sarcina 3: Este posibil să tăiați un pătrat de hârtie în carouri la dimensiune

4×4 pentru un piedestal, un pătrat, o coloană și un zig-zag?

Sarcina 4: Este posibil să așezați un pătrat de 8×8 folosind 15 dreptunghiuri 1×4 și un colț de vedere?

Sarcina 5: Este posibil să așezi un dreptunghi de 6×10 cu dreptunghiuri de 1×4?

Sarcina 6: Este posibil să pliați un pătrat de 6×6 folosind 11 dreptunghiuri 1×3 și un colț de vedere?

Sarcina 7: Există un gândac pe fiecare celulă a plăcii 5 × 5. La un moment dat, toți gândacii decolează și aterizează pe celulele adiacente din lateral. Demonstrați că în acest caz va exista cel puțin o celulă goală.

Sarcina 8: Decupați o cușcă de colț dintr-o placă de 8×8. Restul poate fi tăiat în dreptunghiuri de 3×1?

Sarcina 9: Piesa de cămilă se mișcă pe tabla de șah cu o mișcare ca (1, 3). Este posibil să mutați „cămila” dintr-un câmp arbitrar în cel adiacent?

Sarcina 10: O tablă de 10 × 10 poate fi acoperită cu figuri de formă?

Sarcina 11: Dată o tablă de 12 × 12. Există 9 piese în colțul din stânga jos, formând un pătrat de 3 × 3. Într-o mișcare, puteți alege două dame și rearanjați una dintre ele simetric față de cealaltă (fără a părăsi tabla) . Este posibil să mutați aceste dame în mai multe mișcări, astfel încât să formeze un pătrat de 3 × 3 în colțul din dreapta jos?

Sarcina 12: Există un gândac în fiecare celulă a unui pătrat de 9 × 9. La comandă, fiecare gândac zboară către una dintre celulele adiacente în diagonală. Demonstrați că cel puțin 9 celule vor fi apoi libere.

Sarcina 13: Castelul are forma unui triunghi regulat, împărțit în 25 de săli mici de aceeași formă. S-a făcut câte o ușă în fiecare perete dintre holuri. Călătorul se plimbă în jurul castelului fără să viziteze niciuna dintre săli de mai multe ori. Găsiți cel mai mare număr de săli pe care le poate vizita.

Sarcina 14:Care este numărul maxim de romburi care pot fi tăiate într-un triunghi echilateral împărțit în 36 de triunghiuri echilaterale?

Sarcina 15. Există 16 plăci 1x3 și o placă 1x1 într-un pătrat de 7x7. Demonstrați că țigla 1×1 fie se află în centru, fie este adiacentă marginilor pătratului.

Sarcina 16.În colțul din stânga jos al unei table de șah 8×8, nouă jetoane sunt plasate sub forma unui pătrat de 3×3. Un cip poate sări într-un câmp liber printr-un cip din apropiere, adică poate fi reflectat simetric în jurul centrului său (puteți sări vertical, orizontal și diagonal). Este posibil ca un anumit număr de astfel de mișcări să pună din nou toate jetoanele sub forma unui pătrat de 3 × 3, dar într-un colț diferit.