20. FEJEZET: Vegyes feladatok
Feladat: 20.1.
Legyen
G egy 2-átmérőjű gráf, és tekintsük a belőle a Mycielski-konstrukcióval kapott gráfot (l. a
GR.II.1.21. feladat megoldását). Lehet-e a kapott gráf átmérője nagyobb 2-nél?
Feladat: 20.2.
[
176]
Három fívér egy napon látogatott me egy beteget. Ugyanazon a napon mindegyiknek a felesége is járt ott. Egyikük sem volt ott aznap többször. Mindhárom fívér találkozott a betegágynál mindkét sógornőjével. Bizonyítandó, hogy valamelyikük a feleségével is találkotott ott. (Kürschák-verseny, 1959.)
Feladat: 20.3.
Egy 1999 tagú társaságban mindenki a társaság
k másik tagjával szimpatizál. Milyen
k esetén lehetünk biztosak abban, hogy van két ember, akinek azonosak az érzelmei egymás iránt, vagyis vagy mindketten szimpatizálnak egymással, vagy egyikük sem szimpatizál a másikkal? (Arany Dániel-verseny/H)
Feladat: 20.4.
Igaz-e, hogy ha adott az egyenesen 26 intervallum, akkor vagy kiválasztható közülük hat olyan, amelyeknek közös pontja van, vagy kiválasztható hat olyan, amelyek közül semelyik kettőnek nincs közös pontja? (Szőkefalvi-Nagy Gyula Matematikai Emlékverseny, 1987, döntő.)
Feladat: 20.5.
Fel akarjuk bontani a pozitív egész számok halmazát olyan, páronként diszjunkt számpárokra, hogy minden pozitív
n egészhez pontosan egy kiválasztott
{u,v} számpár legyen, amelyben a számok különbségének abszolútértéke pontosan
n. Lehetséges-e ez?
És mi a helyzet, ha az összes egész szám halmazát akarjuk ilyen számpárokra bontani?
Feladat: 20.6.
Egy sakktáblán ,,gyenge királyok" állnak. A gyenge király csak a vízszintesen és függőlegesen szomszédos mezőre léphet, ha azon nem áll bábu. Egy adott pillanatban minden bábu visszatért a helyére, miután a tábla minden mezejét bejárta. Biazonyítsuk be, hogy volt olyan pillanat, amikor egyetlen bábu sem állt a helyén.
Feladat: 20.7.
Van-e olyan tízjegyű szám, amelynek első jegye megmutatja, hogy a számban hányszor szerepel a
0 számjegy,
második jegye megmutatja, hogy hányszor szerepel az
1 számjegy, és így tovább, a tizedik jegye azt mutatja meg, hogy hányszor
szerepel a számban a
9 számjegy?
Feladat: 20.8.
Általánosítsuk és oldjuk meg
20.7. feladatot
n alapú számrendszerre!
Feladat: 20.9.
Bizonyítsuk be, hogy egy száz csúcsú konvex poliéder élei megszámozhatók a
1 és
-1 számokkal úgy, hogy minden csúcsra
teljesül, hogy az oda befutó élekre írt számok szorzata
-1.
Feladat: 20.10.
Adott két kupac kavics, az egyikben 4, a másikban 10 kő. Ketten a következő játékot játsszák: felváltva lépnek; a soron következő
játékos minden olyan kupacot kettéoszt, amelyben legalább két kavics van; az nyer, aki eléri, hogy mindegyik kupacban egy kavics
legyen. Kinek van nyerő stratégiája?
Feladat: 20.11. [
158]
Hanoi tornyai. Van három rúd és
n különböző nagyságú korong az
első rúdon nagyság szerint sorba rakva. A legnagyobb van legalul.
Át kell pakolni a korongokat egy másik rúdra ugyanilyen sorrendben
úgy, hogy nagyobb korongot közben sem szabad soha kisebbre tenni.
Hány lépésben lehet ezt megtenni?
Feladat: 20.12.
Egy osztályba 20 diák jár. Tudjuk, hogy bármely két diáknak van közös nagyapja. (Minden diáknak két nagyapja van.) Bizonyítsuk be, hogy van köztük 14 olyan tanuló, akiknek közös nagyapja van! (Arany Dániel-verseny, 2004H)
Feladat: 20.13.
Adjunk a
20.12. feladatra megoldást a
9.6. feladat segítségével!
Feladat: 20.14.
Egy 8x8-as sakktáblára 8 bástyát helyeztünk el úgy, hogy semelyik kettő nem üti egymást. Bizonyítsuk be, hogy páros sok bástya áll fekete mezőn! (Arany Dániel-verseny, 2004H)
Feladat: 20.15. [
158]
Olivér és Xénia egy végtelen sakktáblán a következőt játsszák:
O. kezd, és minden lépésben egy O-t tesz valamelyik még üres mezőbe, utána
X. tesz két még üres mezőbe egy-egy X-et. Meg tudja-e akadályozni Olivér Xéniát abban, hogy ezer X-et tegyen egymás melletti mezőkbe ugyanabban a sorban, vagy ugyanabban az oszlopban?
Feladat: 20.16. [
158]
Olivér és Xénia most is a
20.15. feladatban ismertetett játékot játsszák. Meg tudja-e akadályozni Olivér Xéniát abban, hogy végtelen sok X-et tegyen egymás melletti mezőkbe ugyanabban a sorban vagy ugyanabban az oszlopban?
Feladat: 20.17.
*
Kutató munka:
Megadható-e akárhány általános helyzetű pont a sikon úgy, hogy bármely kettő távolsága egész legyen? (Általános helyzetű pontokon azt értjük, hogy semelyik három nincs egy egyenesen.)
Feladat: 20.18.
* [
183]
Döntsük el, kiválasztható-e az egységkörön 1975 pont úgy, hogy közülük bármely kettő által meghatározott húr hossza racionális szám legyen. (IMO, 1975.)
Feladat: 20.19.
*
Bizonyítsuk be, hogy nem adható meg végtelen sok általános helyzetű pont a síkon úgy, hogy bármely kettő távolsága egész legyen. (Általános helyzetű pontokon azt értjük, hogy semelyik három nincs egy egyenesen.)
Feladat: 20.20.
Kiszínezhetők-e a sík racionális rácspontjai két színnel, pirossal és kékkel úgy, hogy minden függőleges egyenesen csak véges sok piros pont legyen, és minden vízszintes egyenesen csak véges sok piros pont legyen?
Feladat: 20.21.
Hány egymást nem metsző gömbbel takarható el egy pontszerű, minden irányba sugárzó fényforrás? (KöMaL)
Feladat: 20.22.
[
187] Book 5.
Legyen adott az
n csúcsú
P sokszög, legyenek a csúcsai
P1
,
P2
,
Pn
. Legyen továbbá adva
P belsejében
m pont,
Q1
,
Q2
,…
Qm
. Ennek az alakzatnak egy háromszögelése azt jelenti, hogy
Pi
és
Qj
pontokat illetve két
Qj
pontot összekötő szakaszokat húzunk be, úgy, hogy e szakaszok ne messék egymást, az alakzatot csupa háromszögre bontsák és e háromszögek egyike se tartalmazzon sem a belsejében, sem a határán további
Pi
vagy
Qj
pontot. Lásd az
1. ábrát.
1. ábra
Mutassuk meg, hogy minden ilyen háromszögelésben ugyanannyi lesz a háromszögek száma és fejezzük ki
n és
m segítségével a számukat.
Feladat: 20.23.
** [komal]
a) Bizonyítsuk be, hogy
∑(-1
)i
(
n
i
)
ik
=0, ha
k<n, ahol az összegzés
i=0,1,…n-re történik.
b) Mennyi az összeg értéke
k=n-re?