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

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

8. {1, 2, 3, …, 99} kü me sin den her han gi iki si nin top la mý 99 ve ya 100 ol ma ya cak þe kil de
50 ele man se çi li yor. Bu na gö re se çi len 50 sa yý nýn 50, 51, …, 99 ola ca ðý ný gös te ri niz.
Çö züm:
Çö züm:
{1, 2, 3, …, 99} kü me si nin ele man la rý ný (99, 1), (98, 2), (97, 3), …, (51, 49), 50 þek -
lin de dü zen le di ði miz de yan ya na bu lu nan iki sa yý nýn top la mý 100 ve ya 99 dur. Ýki si
ay ný an da ola maz. 1, 98, 2, 97, 3, …, 51, 49, 50 di zi li min de ki sa yý la rý yan ya na olan -
la rý ya ni top lam la rý 100 ve ya 99 ola cak þe kil de iki li grup la dý ðý mýz da 49 iki li el de ede -
riz ve her za man 1 sa yý ar tar. Bu du ru mun el li sa yý ile ger çek leþ ti ri le bi le ce ði açýk týr.

{1, 2, 3, …, 99} kü me si nin ele man la rý ný kom þu iki kö þe nin ele man la rý top la mý 100
ve ya 99 ola cak þe kil de graf ola rak ta çi zip; so ru da is te nen du ru mu sað la ya cak þe kil de
se çi le cek 50 sa yý nýn 50, 51, …, 99 ola ca ðý gö rü lür.

9. 102 öð ren ci den her bi ri nin en az 68 ar ka da þý var dýr. En az dört ki þi nin ar ka daþ sa yý -
sý nýn ay ný ol du ðu nu gös te ri niz.
Çö züm:
Çö züm:
Grup ta ki bir ki þi nin en az 68 ve en çok 101 ar ka da þý ola bi lir. Bu na gö re ar ka daþ sa -
yý sý 101 – 68 = 34 fark lý de ðer alýr.
Ter si ni dü þü ne lim. En faz la üç ki þi nin ar ka daþ sa yý sý ay ný ol sun. Bu du rum da, 3.34 = 102
ola ca ðýn dan ki þi le rin ar ka daþ sa yý la rý 68, 68, 68, 69, 69, 69, 70, …, 101, 101, 101 olup

top lam ar ka daþ lýk sa yý sý çarpý mý tek sa yý dýr. Tüm ar ka daþ lýk lar top -

la mý çift sa yý ola ca ðýn dan çe liþ ki el de edi lir. Çün kü A ile B ta ný þý yor sa, B ile A da ta -
ný þý yor dur.

10. Bir ül ke de her þeh ri di ðer le ri ne bað la yan100 yol var dýr. Bir þe hir den di ðe ri ne ulaþ mak
her za man müm kün dür. Her han gi iki þeh ri bir leþ ti ren bir yol ba kým için ka pa týl dý ðýn da
her han gi bir þe hir den baþ ka bir þeh re ulaþ ma nýn ha la müm kün ol du ðu nu gös te ri niz.
Çö züm:
Çö züm:
Farz ede lim A ile B þe hir le ri ni bir leþ ti ren AB yo lu ka pan sýn. Bu na gö re ha la A dan B
ye ula þa bi le ce ði mi zi gös te re lim. Þa yet A dan B ye ula þým ol maz sa, AB yo lu nu ka pat -
tý ðý mýz da el de edi len ye ni alt grup ta bü tün kö þe le rin dereceleri A da da hil çift ola cak.
Bu da "Bir graf ta tek de re ce li kö þe le rin sa yý sý çift tir" te ore mi ile çe li þir.

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