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

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

Çö züm:
Çö züm:
Þe kil de gö rül dü ðü gi bi 49 bað lan tý ile is te nen du rum
ger çek leþ ti ri le bil mek te dir. 49 dan az ol ma sý du ru -
mun da bu du rum ger çek leþ ti ri le mez. Çünkü n kö þe -
li bir graf ta her kö þe nin bað lan tý lý ola bil me si için en

az n – 1 ke nar içe rir.

6. Bir ül ke nin baþ ken tin den 100, di ðer kent le rin her bi rin den tam ola rak 10 ken te kar -
þý lýk lý uçak se fer le ri dü zen le ni yor ve her bir kent ten di ðer bir ken te ula þý la bi li yor. Baþ -
kent ten di ðer 50 þeh re olan uçuþ lar kal dý rýl dý ðýn da, ula þým da her han gi bir ak sa ma ol -
ma ya ca ðý ný gös te ri niz.
Çö züm:
Çö züm:
Þe hir le ri ken di için de ula þým olan grup la ra ayý ra lým.

Her grup ta bir A nok ta sý var dýr. Öy le ki, baþ kent le
ara sýn da se fer ol sun. De re ce ler top la mý çift ol du -
ðun dan en az iki nok ta baþ ken te se fer ya par. Bu se -
fer den bi r tanesi hariç diğerleri ni ata bi li riz.

7. 1982 öð ren ci si bu lu nan bir okul da her han gi dört öð ren ci den bi ri di ðer üç öð ren ci ile
ta ný þý yor. Okul da her kes le ta ný þan öð ren ci sa yý sý en az kaç týr?
Çö züm:
Çö züm:
Okul da her kes bir bi ri ni ta ný yor sa so ru da ve ri len þart það la nýr fa kat bu her kes le ta ný -
þan en az öð ren ci sa yý sý ný ver mez. A, B, C, D bu oku lun her han gi dört öð ren ci si ol sun.
Farz ede lim A ile B ta nýþ ma sýn. (A, B, C, D) dört lü sün de C ile D bir bi ri ni ta ný mak zo -
run da dýr. Ben zer þe kil de A ve B dý þýn da ki 1980 ki þi nin bir bi ri ni ta ný dý ðý ný söy le ye bi li -
riz. Eðer bu ki þi ler A ve B yi ta nýr sa çö züm bi ter. Oku lun öð ren ci le rin den olan E, A ve
B yi ta ný ma sýn. Bu du rum da bir F öð ren ci si için, (A, B, E, F) dört lü sün de F di ðer le ri -
ni ta nýr. Bu na gö re en az 1979 öð ren ci A ve B yi ta nýr. O hal de en az 1979 ki þi den bir -
bi ri ni ta nýr.

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