Probleme de colorare pentru pregatirea concursurilor de matematica

CUVANT INAINTE

"Colorarea suprafetelor, desi la inceput a fost doar o chestiune aparent simpla, de estetica, de talent artistic, a devenit, in decursul anilor, o problema complexa, cu multiple ramificatii si implicatii in alte domenii, pentru a carei solutionare a fost nevoie sa se dezvolte un intreg aparat matematic, dublat, in zilele noastre, de utilizarea instrumentelor de calcul, devenind, in acest mod, obiect de studiu al matematicii si al informaticii.

Cu satisfactie am constatat ca specialistii romani (matematicieni, informaticieni, ingineri) s-au inscris, la randul lor, printre cei care au contribuit si contribuie, pe diverse paliere ale stiintei si cercetarii, la dezvoltarea acestui domeniu iar lucrarea de fata constituie o noua dovada in acest sens.

Conceputa ca o culegere de probleme ierarhizate pe grade de dificultate, de la simplu la complex, cartea domnului prof. dr. Daniel Stretcu si-a propus si a reusit sa exploreze progresiv si sistematic un segment atipic si mai putin familiar al matematicii, venind in intampinarea cererii multor rezolvitori de probleme, a pasionatilor de matematica sau chiar a specialistilor in domeniu.

Lucrarea este rodul muncii pasionate, ca profesor de matematica, a autorului si este bazata pe experienta sa de aproape trei decenii; munca de zi cu zi cu generatiile de elevi (la clasa sau cercurile de matematica) i-a fost imbold si sursa de inspiratie, iar motivatia i-a fost sporita succesele acestora la concursurile locale, nationale si intemationale, ca si de reusitele lor in cariera."

INTRODUCERE

"Pavarea, pardosirea, parchetarea, mozaicarea au fost operatii cunoscute si aplicate de vechii egipteni, babilonieni, de popoarele din Orient si de grecii antici. Efectul acestor operatii creste atunci cand materialul folosit nu are o singura culoare, ci este colorat diferit. Fascinatia pentru combinarea culorilor a fost transpusa in matematica inca din Antichitate, astfel aparand o serie de probleme de acoperire (pavare), precursoare ale celor ce astazi sunt numite probleme de colorare.

Sunt demne de amintit in evolutia aparitiei si rezolvarii acestor probleme acoperirea unei suprafete plane cu poligoane regulate de acelasi tip, rezolvata de Pitagora; acoperirea planului cu poligoane convexe de tipuri diferite, rezolvata de Kepler si, nu in ultimul rand, celebra Teorema a celor patu culori formulata de studentul Francis Guthrie (cunoscuta incepand cu anul 1852): ,,Se poate colora o hartii oarecare cu patru culori astfel incat oricare doua tari, care au frontier comuna si care nu se reduc la un punct, sa aiba culori diferite?" ce a fost confirmata abia in 1976 de W. Haken si K. Appel, cu ajutorul calculatorului electronic.

Evident, astazi prin probleme de colorare nu intelegem doar probleme de acoperire, pro­ blematica dezvoltandu-se si spre zone mai abstracte, iar solutiile acestora se obtin cu ajutorul matematicii si al informaticii.

Ideea scrierii acestei carti a venit de la dificultatile intampinate de un numar mare de elevi la concursurile scolare in rezolvarea problemelor de colorare, dificultati cauzate si de inexistenta unor lucrari care sa descrie complet aceasta tema.

Problemele de colorare se caracterizeaza prin natura lor atipica, ce impune din partea rezolvitorilor ingeniozitate, perseverenta in cautarea solutiilor, dar si o anumita experienta in acest domeniu.

Cartea se adreseaza tuturor categoriilor de elevi, de la incepatori pana la cei care vor sa obtina performante la concursurile si olimpiadele de matematica si de informatica. Astfel se explica faptul ca vom intalni in aceasta lucrare atat probleme usoare (unele fiind clasice), cat si numeroase probleme cu grad inalt de dificultate. Volumul acesta se adreseaza in principal elevilor de gimnaziu si celor din clasele a noua si a zecea, interesati sa participe la concursuri matematice si la olimpiade scolare, pana la cel mai inalt nivel, cum sunt olimpiadele intema­ tionale si balcaniadele. Pe de alta parte, consideram ca aceasta culegere este utila si profesorilor de matematica si de informatica in sustinerea unor cursuri optionale si pregatirea elevilor pentru participarea la diverse competitii.

Cititorul interesat va gasi in paginile acestei carti o abordare metodica si sistematica a problematicii enuntate, lucrarea fiind structurata in sapte capitole."

Primul capitol cuprinde probleme de colorare mai usoare, intalnite la diferite concursuri, menite sa trezeasca interesul elevilor pentru studiul acestui tip de probleme.

Capitolul al doilea contine probleme de colorare a tablelor, inclusiv table de sah, de la cele mai mici dimensiuni pana la cele mai mari. Acestea constituie tipul de probleme cel mai frecvent intalnit in concursurile scolare.

In capitolul al treilea sunt prezentate problemele de colorare a cercului, iar apoi pro­bleme in care apar diverse poligoane intr-o ordine crescatoare a numarului de laturi.

Colorarea planului si spatiului euclidian este studiata in diferite cazuri particulare in capitolul al patrulea.

Capitolul al cincilea se refera la problemele de colorare in care apar cubul si diferite paralelipipede sau prisme.

Capitolul al saselea este un capitol cu totul special, dedicat introducerii in studiul problemelor de colorare a grafurilor. Desigur, tema acestui capitol depaseste programa scolara si, din acest motiv, la sfarsitul cartii am introdus un apendix necesar pentru familiarizarea cu notiunile folosite aici.

La final, capitolul al saptelea prezinta probleme si jocuri diverse care nu se incadreaza in vreuna din temele precedente.

Modul recomandat de parcurgere a cartii de fata trebuie sa fie unul interactiv, elevul nefiind invitat ca imediat dupa citirea problemei sa se uite la solutiile acesteia. El trebuie sa incerce singur o metoda de rezolvare si, daca aceasta metoda nu este gasita, poate sa treaca la partea de solutii.

Multumesc tuturor celor care, prin consideratiile lor, au contribuit la cresterea calitatii acestei carti (editia a doua)."

CUPRINS

Cuvant inainte

lntroducere

CAPITOLUL 1

Probleme de ,,incalzire"

CAPITOLUL 2

Probleme de colorare a tablelor

CAPITOLUL 3

Probleme de colorare a punctelor cercului si poligoanelor

CAPITOLUL 4

Probleme de colorare a planului si a spatiului

CAPITOLUL 5

Probleme de colorare a cuburilor, a paralelipipedelor si a prismelor

CAPITOLUL 6

Grafuri

CAPITOLUL 7

Diverse si jocuri

Apendix grafuri

Bibliografie