Matematikos Maratonas Nr. 1

Ar kas bandė spręst uždavinį?

bachukas
Naujas uždavinys (mano sugalvotas):
Raskite kiek yra stačiųjų trikampių, kurių kraštinių ilgiai sveikieji skaičiai, o perimetras lygus 6^n (n-natūralusis skaičius). Atsakymą išreikškite vienetais per n.

Plokštumoje nubrėžtas baigtinis skaičius skritulių. Jokie du skrituliai nepersidengia ir joks skritulys nesiliečia su daugiau nei 6 kitais skrituliais. Kiekvienam skrituliui, kuris liečiasi su mažiau nei 6 kitais skrituliais, yra priskirta po realųjį skaičių. Įrodykite, kad yra daugiausiai vienas būdas, kaip priskirti skrituliams, kurie liečiasi su 6 kitais skrituliais, po realųjį skaičių taip, kad kiekvienam tokiam skrituliui priskirtas skaičius būtų lygus aritmetiniui vidurkiui skaičių, priskirtų 6 jį liečiantiems skrituliams.

Manau reikėtų pridėti taisyklę, kad jei per 24 val. niekas neišsprendžia, tai tas kas įdeda uždavinį, įdeda ir sprendimą :)

O gal reikėtų 48 val. padaryti?

Palaukiam gal iki vakaro bent.

Ok, bet tik iki vakaro :)
Aš jau pasiduodu :D

Jau velus vakaras o sprendimo dar nėra :)

Pažymėkime skritulius s_1, s_2, ..., s_n. Kiekvienam skrituliui s apibrėžikime aibę F(s), sudarytą iš tokių skritulių s', į kuriuos galime nueiti iš s eidami tik per besiliečiančius skritulius. Formaliai,

F(s) = { s' : yra tokie skrituliai t_1, t_2, ..., t_m, kad s liečia t_1, t_1 liečia t_2, ..., t_(m-1) liečia t_m, t_m liečia s' }.

Tarkime, kad yra du skirtingi priskyrimai a_1, ..., a_n ir b_1, ..., b_n (pirmame priskyrime skrituliui s_i priskiriame a_i, o antrame --- b_i). Atkreipkime dėmesį, kad kai kurie skrituliai neturi 6 juos liečiančių skritulių. Jei s_i yra toks skritulys, tai a_i = b_i yra sąlygoje užfiksuotas skaičius tam skrituliui.

Išsirinkime didžiausią skaičių iš |a_1 - b_1|, ..., |a_n - b_n|. Sakykime, kad tai yra |a_N - b_N| (jei yra keli didžiausi skaičiai, išsirinkime bet kurį iš jų). Kadangi priskyrimai skirtingi, |a_N - b_N| > 0. Pažymėkime d = a_N - b_N.

Sakykime, kad a_i - b_i = d. Tuomet visiems s_i kaimynams s_j galioja a_j - b_j = d:

1) tarkime, kad s_(j_1), ..., s_(j_6) yra skritulio s_i kaimynai;
2) tuomet a_i = 1/6 ( a_(j_1) + ... + a_(j_6) ) ir b_i = 1/6 ( b_(j_1) + ... b_(j_6) );
3) taigi 6d = 6( a_i - b_i ) = ( a_(j_1) - b_(j_1) ) + ... + ( a_(j_6) - b_(j_6) );
4) jei bent vienas iš a_(j_p) - b_(j_p) būtų mažesnio modulio arba priešingo ženklo nei d, tai bent vienas iš jų turėtų būti to paties ženklo ir didesnio modulio nei d, tačiau tai yra neįmanoma, nes d = max{|a_i - b_i|}.

Tai reiškia, kad jei skritulys s_i priklauso F(s_N), tai a_i - b_i = d. Formaliai tai galima įrodyti taip: jei s_i priklauso F(s_N), tai yra tokie skrituliai s_(j_1), ..., s_(j_m), kad s_N liečia s_(j_1), s_(j_1) liečia s_(j_2), ..., s_(j_m) liečia s_i. Kadangi a_N - b_N = d, o s_(j_1) yra s_N kaimynas, tai a_(j_1) - b_(j_1) = d. Tačiau s_(j_2) yra s_(j_1) kaimynas, taigi a_(j_2) - b_(j_2) = d, ir taip toliau, kol galiausiai gauname a_i - b_i = d.

Tačiau parodysime, kad F(s_N) priklauso bent vienas skritulys, turintis mažiau nei 6 kaimynus. Paimkime mažiausio spindulio skritulį, priklausantį F(s_N). Jei yra keli tokie skritulį, paimkime tokį, kurio centro x koordinatė yra mažiausia. Tokio skritulio niekaip negali liesti šeši skrituliai iš F(s_N) (nes jie visi yra didesnio spindulio arba jų centras yra dešiniau).

Šį teiginį griežtai įrodyti galima taip: tarkime, kad turime septynis skritulius U, u_1, ..., u_6 plokštumoje, ir kitų šešių skritulių spinduliai yra ne didesni nei U spindulys. Tarkime, kad visi u_i liečia U. Nubrėžkime iš U centro spindulius, liečiančius kitus šešis skrituliai. Šie spinduliai išpjauna iš plokštumos šešias išpjovas, kiekvienoje kurių yra po vieną skritulį u_i. Kadangi kiekvieno skritulio u_i spindulys yra ne mažesnis už U spindulį ir u_i liečia U, tai išpjovos, kuriai priklauso u_i, kampas turi būti bent 60 laipsnių (čia trupučio geometrijos reikia). Kadangi šešios išpjovos turi bent po 60 laipsnių, o pilnas kampas yra 360 laipsnių, tai visos išpjovos turi lygiai po 60 laipsnių. Tačiau tuomet skritulių u_1, ..., u_6 išsidėstymas apie U yra fiksuotas ir tikrai bent vieno iš jų centras bus kairiau nei U centras.

Galima ir kitaip įrodyti. Apskritai teiginys paprastas: įrodymo aprašymo sudėtingumas didesnis nei paties teiginio sudėtingumas.

Taigi F(s_N) turi bent vieną skritulį, kuris liečia mažiau nei 6 skritulius. Tarkime, kad tai s_I. Tačiau tuomet a_I - b_I = 0. Bet s_I priklauso F(s_N), taigi a_I - b_I = d ≠ 0. Prieštara.

Tai reiškia, kad nėra dviejų skirtingų priskyrimų.

Kažkaip jaučiu, kad verta parašyti sutrumpintą sprendimo versiją, kad pagrindinės mintys nebūtų užgožtos detalių.

1. Tariame, kad yra du skirtingi priskyrimai. Paimame skritulį S, kuriam priskirti skaičiai skiriasi labiausiai. Pažymėkime tą skirtumą d.
2. Plintame iš skritulio S tolyn per kaimynus. Visiems S kaimynams du kartus priskirtų skaičių skirtumas irgi turi būti d (jei bent vienas iš skirtumų būtų mažesnis, tai bent vienas turėtų būti ir didesnis, nes d yra aritmetinis vidurkis šių skirtumų, o taip būti negali, nes d yra maksimalus skirtumas).
3. Taip plisdami visada prieiname skritulius, kurių skirtumas turi būti d, tačiau kažkada prieisime skritulį, kuris neturi šešių kaimynų, todėl jo skirtumas turi būti 0. Prieštara.

Vienas skrydžio keleivis yra aklas. Kai jis įlips į lėktuvą, jis atsisės į bet kurią laisvą vietą. Kiti keleiviai paeiliui lips į lėktuvą ir sėsis į savo vietą, jei ji laisva. Tačiau jei keleivio vieta užimta, jis sėsis į bet kurią atsitiktinę laisvą vietą. Kokia tikimybė, kad paskutinis keleivis atsisės į savo vietą, jei žinome, kad aklas keleivis įlips į lėktuvą ne paskutinis? Visi bilietai į skrydį parduoti.