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

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

5. 1001 ki þi lik bir okul da her han gi 500 ki þi lik bir grup oluþ tu rul du ðun da bu grup ta ki her
ki þi ile ar ka daþ olan en az bir ki þi bu lu nu yor. (Ki þi ler ken di ken di le riy le ar ka daþ ola -
ma ya cak la rý için, bu ki þi grup dý þýn dan ola cak.) Bu okul da en çok ar ka da þa sa hip olan
ki þi nin en az kaç ar ka da þý ola bi lir?

A) 501 B) 550 C) 620 D) 750 E) 1000
Çö züm:
Çö züm: (Ce vap E)
Bu okul da her kes le ar ka daþ olan bir ki þi nin var lý ðý ný gös te rir sek so ru nun çö zü mü ta -
mam lan mýþ olur. 500 ki þi lik bir grup ele ala lým. Grup dý þýn da ki bir A ki þi si grup ta ki -
le rin her bi riy le ar ka daþ týr. Grup tan bir B ki þi si ni ala lým. A ile B nin ay ný grup ta ol du -
ðu 500 ki þi lik bir gru bu ele ala lým. Bun la rýn her bi riy le ar ka daþ olan bir C ki þi si var -
dýr. O hal de; A, B, C bir bi riy le ar ka daþ týr. Bu 3 ki þi yi içe in de bu lun du ran 500 ki þi lik
bir grup ele ala lým. Bun la rýn her bi riy le ar ka daþ olan bir D ki þi si var dýr. Bu du rum da
da A, B, C, D ar ka daþ týr di ye bi li riz. Bu þe kil de de vam eder sek bir bi riy le ar ka daþ olan
501 ki þi bu lu ruz. Ge ri ye ka lan 500 ki þi nin oluþ tur du ðu gru bu ele ala lým. Grup ta ki le -
rin her bi riy le ar ka daþ olan bir X ki þi si var. X grup dý þýn da ol du ðun dan, ilk 501 ki þi -
den bi ri dir ve do la yý sýy la her kes ar ka daþ týr.

6. Düz lem de her han gi üçü doð ru sal ol ma yan A, B, C, D ve E nok ta la rý ve ri li yor. Bu beþ
nok ta dan iki li nok ta lar alý na rak her han gi üçü bir üç gen be lirt me ye cek þe kil de ke nar -
lar la bir leþ ti ri li yor. Bu na gö re, bu graf ta ki ke nar sa yý sý en çok kaç ola bi lir?

A) 5 B) 6 C) 7 D) 8 E) 9
Çö züm:
Çö züm: (Ce vap B)
Doð ru sal ol ma yan beþ nok ta için, her han gi iki kö þe yi bir-

leþ ti rir sek, K tam gra fý ke nar ve
5

üç gen içe rir. Graf ta ki ke nar sa yý sý n 7 ol du ðun da
graf tan en çok üç ke nar çý kar ta bi li riz de mek tir. Bu da
en çok 3×3 = 9 üç ge nin bi rer ke na rý ný ip tal ede rek,
üç gen ol ma du ru mu nun bo zul ma sý dýr.Ge ri de da ha bir
üç gen da ha var de mek tir. Bu da so ru da is te nen du rum

ile çe li þir. O hal de graf ta ola bi le cek ke nar sa yý sý n < 7

dir. Bu na gö re, graf ta ki ke nar sa yý sý en çok 6 ola bi lir.
Bu nun için ör nek ise yan da ki gi bi dir.

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