Matematikos Maratonas Nr. 1

na jau antra diena ;] Gal įkelti sprendimą?

Trikampis smailus, todėl O ir H yra jo viduje.

Tegul A', B' ir C' būna taško H atspindžiai atitinkamai kraštinių BC, CA ir AB atžvilgiu. A', B' ir C' priklauso apibrėžtiniam apskritimui (pagal apibrėžimą <A'CB = <BCH ir A' priklauso spinduliui AH; tarkime, kad A" yra spindulio AH susikirtimo su apibrėžtiniu apskritimu taškas; tuomet <A"CB = <BAA" = 90 - <ABC = <BCH = <A'CB, taigi A' = A"; analogiškai su B' ir C').

Tegul E būna AB ir OC', F --- BC ir OA' ir G --- CA ir OB' susikirtimo taškas. Šie trys taškai priklauso trikampio kraštinėms. Tuomet OE + EH = OE + EC' = apibrėžtinio apskritimo spindulys = OF + FH = OG + GH. Lieka įrodyti, kad AE * BF * CG = EB * FC * GA (tuomet AF, BG ir CE kirstųsi viename taške dėl Čevos teoremos).

Iš tiesų, <AOE = 2<ACH = 180 - 2a (kur a = <CAB) ir <EOB = 2<HCB = 180 - 2b (kur b = <ABC). Taigi AE : BE = ( AO * EO * sin(180 - 2a) ) * ( BO * EO * sin(180 - 2b) ) = sin(2a) : sin(2b). Analogiškai BF : FC = sin(2b) : sin(2c) ir CG : GA = sin(2c) : sin(2a). Taigi (AE * BF * CG) : (EB * FC * GA) = ( sin(2a) * sin(2b) * sin(2c) ) : ( sin(2a) * sin(2b) * sin(2c) ) = 1, ką ir reikėjo įrodyti.

sprendimas, aišku, geras :)

Konferencijos dalyviai kartu moka 2n (n ≥ 2) kalbas. Kiekvienas dalyvis moka lygiai dvi kalbas, ir bet kurie du dalyviai moka daugiausiai vieną bendrą kalbą. Taip pat bet kokiam sveikam skaičiui k (1 ≤ k ≤ n - 1) yra daugiausiai k - 1 kalba, kurią moką ne daugiau nei k dalyvių (t.y. yra bent 2n - k + 1 kalba, kurią moka daugiau nei k dalyvių). Įrodykite, kad galime rasti grupę iš 2n dalyvių, kurie kartu moka visas 2n kalbų, ir kiekvieną kalbą moka lygiai du dalyviai iš šios grupės.

Truputį ne taip. :|

Netempiam gumos, jau šiandien dedam sprendimą.

Susidarykime grafą G, kurio viršūnės yra kalbos, o tarp dviejų viršūnių yra briauna tokiu atveju, jei jas abi moka koks nors dalyvis. Įrodysime, kad šis grafas turi Hamiltono ciklą (Hamiltono ciklas yra jungus ciklas, kuris aplanko visas viršūnes, t.y. v_1 v_2 ... v_2n v_1, kur v_1, ..., v_2n yra visos G viršūnės, o tarp viršūnių v_i ir v_(i+1) bei v_2n ir v_1 yra po briauną).

Naudosime prieštarą. Tarkime, kad G neturi Hamiltono ciklo. Tuomet G negali būti pilnas (pilnas grafas yra toks, tarp kurio bet kurių dviejų viršūnių yra po briauną). Mums duota, kad

(*) yra ne daugiau nei k - 1 viršūnė, kuri turi ne daugiau nei k briaunų, jei 1 ≤ k ≤ n - 1.

Taip pat galime tarti, kad

(**) jei pribrėžtume bent vieną papildomą briauną, G turėtų Hamiltono ciklą.

[Taip tarti galime todėl, kad jei G netenkintų šios savybės, tai galėtume pribrėžinėti briaunas taip, kad G vis dar neturėtų Hamiltono ciklo, kol galiausiai nebegalėtume taip pribrėžti jokios briaunos; tuomet G tenkins (**) savybę, neturės Hamiltono ciklo ir vis dar tenkins (*) savybę].

Paimkime dvi negretimas viršūnes v ir v' (t.y. tokias, tarp kurių nėra briaunos). Jei nubrėžtume briauną tarp jų, atsirastų Hamiltono ciklas dėl (**). Kadangi be šios briaunos nėra Hamiltono ciklų, tai naujai atsiradęs ciklas eina per šią briauną. Tai reiškia, kad yra Hamiltono kelias iš v į v' (Hamiltono kelias aplanko visas viršūnes po vieną kartą kaip ir Hamiltono ciklas, bet neturi prasidėti ir baigtis ten pat).

Tarkime, kad viršūnės v ir v' tenkina d(v) ≥ n ir d(v') ≥ n. Jei jos nėra gretimos, tai yra Hamiltono kelias v_1 v_2 ... v_2n, kur v_1 = v ir v_2n = v'. Tarkime, kad v = v_1 yra gretima viršūnėms v_(i_1), ..., v_(i_m), kur m = d(v) ≥ n. Aišku, kad 2 ≤ i_1, ..., i_m ≤ 2n - 1. Jei v_(2n) ir v_(i_j - 1) būtų gretimos su kokiu nors 1 ≤ j ≤ m, tai v_1 v_2 ... v_(i_j - 1) v_2n v_(2n - 1) ... v_(i_j) v_1 būtų Hamiltono ciklas, ko būti negali. Taigi v_2n nėra gretima su bent m + 1 ≥ n + 1 viršūnių (plius vienas atsiranda todėl, kad v_2n nėra gretima sau). Tačiau ji yra gretima su d(v') ≥ n viršūnių, o d(v') + n + 1 > 2n. Prieštara. Taigi v ir v' yra gretimos.

Taigi jei visos viršūnės turėtų bent n briaunų, tai G būtų pilnas grafas ir turėtų Hamiltono ciklą - prieštara. Todėl yra bent viena viršūnė su mažiau nei n briaunų. Tarkime, kad v_1 turi daugiausiai briaunų iš tokių viršūnių (t.y. d(v_1) < n, ir jei d(v) > d(v_1), tai d(v) ≥ n) ir pažymėkime d(v_1) = m < n. Paėmę k = n - 1 (*) sąlygoje gauname, kad yra bent 2n - (n - 2) = n + 2 viršūnės, kurios turi bent n briaunų. Kadangi v_1 yra gretima tik m < n briaunų, tai yra tokia briauna v_2n, kuri tenkina d(v_2n) ≥ n ir nėra gretima v_1. Egzistuoja Hamiltono kelias v_1 v_2 ... v_2n. Sakykime, kad v_1 yra gretima su v_(i_1), ..., v_(i_m). Kaip ir anksčiau, v_2n negali būti gretima jokiai v_(i_j - 1), 1 ≤ j ≤ m. Tačiau dėl (*) sąlygos bent viena iš šių viršūnių turi bent m + 1 jungtį, tarkime, kad tai yra viršūnė v_p. Pagal m apibrėžimą d(v_p) ≥ n. Tačiau tuomet v_p ir v_2n nėra gretimos, bet abi turi bent po n briaunų. Prieštara.

Taigi G turi Hamiltono ciklą. Paimkime tuos dalyvius, kuriuos atitinkančios briaunos priklauso šiam ciklui. Šie dalyviai ir sudarys norimą grupę.

Duota languota m x n lentelė. Į kiekvieną jos langelį yra įrašyta po realųjį skaičių. Žinome, kad
1) jei eilutė ir stulpelis kertasi langelyje, į kurį įrašytas skaičius nėra 0, tai toje eilutėje ir stulpelyje įrašytų skaičių suma yra ta pati;
2) nėra eilutės ar stulpelio, kuriame įrašytų skaičių suma būtų 0.
Įrodykite, kad m = n.

Sudarome matrica [math]a_ij[/math]
Tegul eiluteje yra n elementu, o stulpelyje- m.
Tegul 1-os eilutes suma yra S (tegul [math]a_11<>0[/math], kitaip parenkame elementa nelygu 0) ir 1-ojo stulpelio suma yra S.
Sumuojame 1-a eilute ir 1-a stulpeli, 1-a eilute ir 2-a stulpeli, ... 1-a eilute ir n-a stulpeli. I sia suma ieina n sumu 1-os eilutes.
Gauname (sumavimas pagal i ir j):
[math]nS=a_ij[/math]
Analogiskai sumuojame pagal 1-a stulpeli, i suma ieina m stulpelio sumu:
[math]mS=a_ij[/math]
Atemus viena is kito, gauname
(n-m)S=0.
Kadangi S≠0, tai n=m.

zzzoakSudarome matrica [math]a_ij[/math]
Sumuojame 1-a eilute ir 1-a stulpeli, 1-a eilute ir 2-a stulpeli, ... 1-a eilute ir n-a stulpeli. I sia suma ieina n sumu 1-os eilutes.
Gauname (sumavimas pagal i ir j):
[math]nS=a_ij[/math]