Page 528 - OLİMPİK SONLU MATEMATİK

ALIÞTIRMALAR VE ÇÖZÜMLERÝ 12.2 ÇÝZGE KURAMI (GRAF)

11. On üç ken ti olan bir ül ke de, her þe hir di ðer al tý þeh re tren yo lu ile di rekt bað lan tý lý dýr.
Bu na gö re bu ül ke nin her han gi bir þeh rin den di ðe ri ne di rekt ve ya en az bir ak tar ma
ile ula þý la bi le ce ði ni gös te ri niz.
Çö züm:
Çö züm:
Bu ül ke de 13 kent ara sýn da ki tren aðý ný graf la gös te re lim. Her bir þeh ri bir kö þe ve iki
þe hir ara sýn da ki tren yo lu bað lan tý sý ný da ke nar la gös te re lim. A ve B bu gra fýn iki kö -
þe si ol sun. A ile B tren yo lu ile bir bi ri ne bað lý ise so ru da ve ri len du rum ger çek le þir. A
ile B bir bi ri ne tren yo lu ile bað lý ol ma sýn. C ve D kö þe le ri A ve B ye sý ra sýy la bir bir le ri -
ne bað lý iki kö þe ol sun. C ve D tam ola rak al tý ke nar içer sin. C, A dan ve D, B den fark -
lý ol ma sý du ru mun da 14 kö þe el de edi lir. Oy sa so ru da ve ri len graf ta 13 kö þe var dý. Bu -
na gö re, bu ül ke nin her han gi bir þeh rin den di ðe ri ne di rekt ve ya en az bir ak tar ma ile
ula þý la bi le ce ði ni gös ter miþ ol duk.

12. Düz lem üze rin de 2k + 2 ta ne nok ta (kö þe) ve ri li yor. K nin her ke na rý kýr mý zý ve ya
2k+2
mavi renk ten bi ri ne bo ya ný yor. Bu na gö re, üç ke na rý da tek renk li olan en az

üç gen bu lun du ðu nu gös te ri niz.
Çö züm:
Çö züm:
Ve ri len 2k + 2 nok ta lar(kö þe ler) A , A , A , …, A ol sun. A kö þe sin den d ta ne ma -
1 2 3 2k+2 i i
vi ke nar çýk mýþ ol sun. Bu du rum da ay ný kö þe den 2k + 1 – d ke nar çýk mýþ olur. Bu na
i
gö re, d (2k + 1 – d ) k(k + 1) ise 2k + 2 nok ta var dýr. Bu iþ lem le ri tüm kö þe ler için
i i
uy gu lar sak, tek renk li ol ma yan üç gen sa yý sý her du -

ru mu iki de fa say dý ðý mýz için çar pý mý 2 ye böl dük.

Top lam üç gen sa yý sý,

Tek renk li üç gen sa yý sý

13. Bir ül ke de tüm þe hir le r a ra sýn da tek yün lü uçuþ lar var dýr. Bir þe hir baþ kent se çil mek
is te ni yor öy le ki, baþ kent ten en az bir ak tar ma ya pa rak di ðer tüm þe hir le re ula þý la bil -
sin. Uçuþ la rýn yö nü na sýl olur sa ol sun, ül ke nin baþ ken ti ola bi le cek böy le bir þeh rin ol -
du ðu nu gös te ri niz.

Tübitak Ulusal Matematik Olimpiyatlarýna Hazýrlýk 527