Somatie la a folosi indicatia:

E clar ca avem nevoie de sertare.
In fiecare sertar trebuie sa avem doar numere dintre care oricum luam doua de acolo, a si b sa zicem, avem fie a|b, fie b|a.

E rau de exemplu daca luam 3, 5 si 15 in acelasi sertar...

In orice caz, problema nu face prea mare economie la sertare.
Daca avem indicatia clara a scrierii fiecarui numar sub forma

2^k . (numar impar)

si ne uitam la ce informatie asupra divizibilitatii putem extrage de aici,
cum ne alegem atunci sertarele?
(Numarul sertarelor este "cam jumatate plus unu"... mi se zbate un ochi deja.)

[Citat] In acest caz problema este ...pentru ciclul primar.

Folosind ideea de mai sus, am construit multimea A = {1001, 1002, 1003, ... ,2001, 2003, 2005, 2007, 2009, 2011}, card A = 1006.

Numerele ramase le grupez in doua multimi, astfel :

B = {1, 2, 3, ... , 1000}, C = {2002, 2004, 2006, 2008, 2010, 2012}

Daca as dori sa duc (si problema impune aceasta actiune)un al 1007 - lea numar in multimea A, atunci acest numar trebuie sa-l iau din B sau din C.

Acest ultim numar , cand va ajunge in A, va gasi aici un alt numar si va forma o pereche (x, y) , cu proprietatea ca x|y sau y|x.

Acesta a fost jocul.

Indicatia, aparuta mai tarziu, exista si mai devreme...

Asejam cele 2012 numere in 1006 multimi disjuncte, de forma

In fiecare multime (sertar) avem doar numere dintre care oricum luam doua, a si b sa zicem, fie a|b, fie b|a.

Dar, problema ne cere sa alegem 1007 numere, si noi avem 1006 sertare !

Atunci, acest al 1007-lea numar se afla, sigur, in oricare sertar din cele 1006 de mai sus, care contine cel putin 2 numere.

Bun.
Problema este rezolvata, dar pentru ca cineva care citeste sa nu fie nevoit sa treaca prin miscarea browniana printre multele postari, incerc sa surprind cat de repede si in descriere cat de nepretentioasa ideea.

Impartim / partitionam multimea 1,2...,2012 in mai multe parti / sertare,
fiecare numar intra in exact un sertar, in modul urmator:

Sertarele sunt numerotate cu numerele impare 1,3,5,...,2011 .
Sertarul numerotat cu N (impar) contine numerele N, 2N, 4N, 8N, ... mai mici sau egale decat 2012.
De exemplu:

Sertarul 1: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024
Sertarul 3: 3, 6, 12, 24, 48, 96, 192, 384, 768, 1536
Sertarul 5: 5, 10, 20, 40, 80, 160, 320, 640, 1280
Sertarul 7: 7, 14, 28, 56, 112, 224, 448, 896, 1792
Sertarul 9: 9, 18, 36, 72, 144, 288, 576, 1152
Sertarul 11: 11, 22, 44, 88, 176, 352, 704, 1408
Sertarul 13: 13, 26, 52, 104, 208, 416, 832, 1664
Sertarul 15: 15, 30, 60, 120, 240, 480, 960, 1920
Sertarul 17: 17, 34, 68, 136, 272, 544, 1088
Sertarul 19: 19, 38, 76, 152, 304, 608, 1216
Sertarul 21: 21, 42, 84, 168, 336, 672, 1344
Sertarul 23: 23, 46, 92, 184, 368, 736, 1472
Sertarul 25: 25, 50, 100, 200, 400, 800, 1600
Sertarul 27: 27, 54, 108, 216, 432, 864, 1728
Sertarul 29: 29, 58, 116, 232, 464, 928, 1856
Sertarul 31: 31, 62, 124, 248, 496, 992, 1984
Sertarul 33: 33, 66, 132, 264, 528, 1056
Sertarul 35: 35, 70, 140, 280, 560, 1120
Sertarul 37: 37, 74, 148, 296, 592, 1184
Sertarul 39: 39, 78, 156, 312, 624, 1248
Sertarul 41: 41, 82, 164, 328, 656, 1312
:
:
:
Sertarul 1005: 1005, 2010
Sertarul 1007: 1007
Sertarul 1009: 1009
:
:
:
Sertarul 2009: 2009
Sertarul 2011: 2011

(Din motive didactice sunt mereu pentru o scriere explicita, daca aceasta este "convingatoare" si daca ea poate atrage un public mai larg. Ce-i drept scriu mai mult, dar nu fac nici o actiune care sa atraga atentia pe un drum laturalnic, de exemplu nu impart mai departe sertarele in cele pana la 1000, apoi cele pana la 1005 si asa mai departe.)

Cate sertare avem?
Avem la fel de multe sertare cate numere
1,3,5,...,2011.
Operatia de adunare cu unu pe fiecare inca le lasa diferite, deci ajunge sa numaram "celelalte numere"
2,4,6,...,2012.
Impartim cu doi si obtinem o noua suita de numere
1,2,...,1006 .
Deci avem 1006 de sertare.
(Am construit la nivel de clasa a IV-a o bijectie de la {1,3,...,2011} la {1,2,...,1006}.)

Pasul esential este aplicarea principiului lui Dirichlet.
Plecam cu toate sertarele goale.
Alegem 1007 de numere dintre cele 2012.
Fiecare numar are un sertar predestinat...
Daca plasam 1007 numere in cele 1006 sertare unde le e locul, cel putin unul dintre sertare va contine doua numere.
Ei bine, dintre aceste doua numere unul il divide pe celalalt pentru ca asa am ales sertarele si continutul lor.

Problema este terminata didactic.

Se poate da si solutia minitehnicus:
Fie N numar natural.
Fie X = {1,2,...,N} .
Pentru k<2N impar fie A(k) = { n din X | n:k este o putere a lui 2 } .
Atunci X = U A(k) este o partitie cu N parti.
Plasand N+1 dintre cele 2N numere din X in partile partitiei, cel putin o parte va avea doua elemente. Aceste doua elemente satisfac o relatie de divizibilitate. Q.E.D.

Desigur ca nici o solutie nu vinde usor argumentul.
Este o chestie de gust... unii elevi vor fi atrasi de o solutie, altii de alta.

[Citat] Desigur ca nici o solutie nu vinde usor argumentul. Este o chestie de gust... unii elevi vor fi atrasi de o solutie, altii de alta.

Ca fost elev, prins, nu rareori, intr-o autocenzura
imperfecta ( atunci, si mai putin acum ), indraznesc sa va intreb:

De ce plecam cu sertarele goale ?

(Mai ales ca tocmai au fost, foarte distinct, si conturate si pe deplin umplute !! )

Eu m-am gandit fenomenologic cum sa fac sa se vada foarte bine la sfarsit in care sertar avem mai mult de doua numere alese.
Asa ca plec cu toate sertarele goale.
Alegem 1007 numere pe care le bagam in sertare.
Pe acestea le punem la locul lor.
Acum ne uitam (in timp ce punem) in care sertar sunt mai mult de doua numere...