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

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

Çö züm:
Çö züm:
So ru yu gra fa dö nüþ tü re lim. Uçuþ la rý yön lü ke nar la ve þe hir le ri de nok ta (kö þe)lar la
gös te re lim. Ken di sin den en çok uçuþ olan þeh rin baþ kent ola bi le ce ði ni gös ter me ye ça -
lý þa lým. Ken di sin den en çok uçuþ olan þeh ri A ile gös te re lim. A dan uçuþ olan kent ler
A , A , A , …, A ol sun. Farz ede lim bir B ken ti ne bir ak tar ma ile uçu la ma sýn. Bu du -
1 2 3 n
rum da A : B uçuþ la rý hep B A ya doð ru dur. Ay ný za man da AB uçu þu da B den baþ -
lar ise n + 1 uçuþ var dýr fa kat A ken ti ni biz en çok uçuþ olan þe hir ol sun de miþ tik.
Çe liþ ki el de edil di ðin den A baþ kent ol ma þart la rý ný sað la mak ta dýr.

n
+
14. n Z ol mak üze re, bir 2 ge nin kö þe le ri ne A ve ya B ya zý lý yor. Her han gi iki kö þe den
baþ la yýp sa at yö nü nün ter si ne n ta ne harf ten olu þan ke li me le ri ala lým. Tüm ke li me -
ler fark lý ola cak þe kil de A ve B harf le ri ni diz me nin müm kün ol du ðu nu gös te ri niz.
Çö züm:
Çö züm:
Kö þe le ri n – 1 uzun lu ðun da ki di zi le ri tem sil eden 2 n – 1 kö þe li yön lü bir graf çi ze lim.
Bi ri nin son n – 2 har fi baþ ka bir ke li me nin n – 2 har fiy le ay nýy sa ara la rý na ke nar ko -
ya lým. Bu graf ta her kö þe ye tam ola rak iki ta ne gi ren ve iki ta ne çý kan var. (Tam ola -
rak 2 ta ne de il mek (lo op) var.) Do la yý sýy la her ke nar dan ge çen yön lü bir yol var dýr.
Bu yo lu ele ala lým. Her han gi bir kö þe den baþ la ya rak is te nen çem be ri el de ede lim. Bu -
nun için ilk ke li me yi ya zýp on dan son ra ge len ke li me nin son har fi ni ek le yip bu na gö -
re, de vam eder sek is te nen þart lar sað lan mýþ olur.

15. Yet miþ se kiz öð ret me ni olan bir okul da her bir öð ret men en az 52 öð ret men le ta nýþ -
mak ta dýr. (A, B ile ta ný þý yor sa, B de A ile ta ný lý yor) Öy le dört öð ret men var dýr ki, eþit
sa yý da öð ret men ta ný dýk la rý ol du ðu nu gös te ri niz.
Çö züm:
Çö züm:
Bir öð ret men 52, 53, …, 76, 77 ki þi ta ný yor ola bi lir. Her

öð ret men yir mi al tý fark lý sa yý da öð ret men le ta ný þýk ola bi -
lir. O za man 4 öð ret me nin eþit sa yý da öð ret men le ta ný þýk
ol ma ma sý için bu 26 fark lý de ðer den her bi ri ni üçer öð ret -
men den top lam 78 öð ret men ol ma lý. 78 öð ret me ni
A , A , A , …, A ola rak ala lým ve ta ný þýk olan la rýn ara sý -
1 2 3 78
na çiz gi çe ke lim. A nin ta ný þýk ol du ðu ki þi sa yý sý ný a ola -
i i
rak gös te re lim.
77 a , a , …, a 52 dir. her bir de ðe re üç öð ret men
1 2 78
düþ tü ðü için a +a +…+a =3(52+53+...+77)=3.13.129 tek tir. Bir graf ta de re ce ler
1 2 78
top la mý çift ola ca ðýn dan bu du rum bir çe liþ ki dir. O hal de en az dört öð ret me nin eþit
sa yý da ta ný dý ðý var dýr.

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