Kezdőlap


Feladat:	F.3104	Korcsoport: 18-	Nehézségi fok: átlagos
Megoldó(k):	Kutalik Zoltán , Szobonya László , Zakariás Ildikó
Füzet:	1996/december, 530 - 531. oldal		PDF \| MathML
Témakör(ök):	Szélsőérték-feladatok differenciálszámítás nélkül, Kombinatorikai leszámolási problémák, Feladat
Hivatkozás(ok):	Feladatok: 1996/január: F.3104

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

A kijelölt $n$ pont legyen a derékszögű koordináta-rendszer $n$ rácspontja. Ekkor a pontok koordinátái egész számok. A koordináták paritása alapján a pontokat négy osztályba soroljuk:
1. Mindkét koordináta páros, az osztályba tartozó pontok száma $n_{1}$ ,
2. az első koordináta páros, a második páratlan, a pontok száma $n_{2}$ ,
3. az első koordináta páratlan, a második páros, a pontok száma $n_{3}$ ,
4. mindkét koordináta páratlan, a pontok száma $n_{4}$ .
Nyilván $n_{1} + n_{2} + n_{3} + n_{4} = n$ , és az is világos, hogy az egy osztályba tartozó pontpárok ,,jó'' szakaszokat határoznak meg, két különböző osztályba tartozó pont pedig nem.
Nézzük most példaként azt az esetet, amikor $n_{1} \geq n_{2} + 2$ . Hagyjunk el az első osztályból egy pontot, és helyette vegyünk fel egy új pontot a második osztályba. Így az első osztályban $n_{1} - 1$ ,,jó'' szakasszal kevesebb lesz, a másodikban pedig $n_{2}$ -vel több. Ezért a ,,jó'' szakaszok száma változatlan $n$ mellett csökkent. Ugyanezt mondhatjuk el bármilyen $n_{i} \geq n_{j} + 2$ ( $i$ , $j = 1$ , $2$ , $3$ , $4$ ; $i \neq j$ ) esetén. Minimális számú ,,jó'' szakaszt tehát akkor kapunk, ha $| n_{i} - n_{j} | < 2$ .
Ezek szerint, ha $n = 4 k$ ( $k$ pozitív egész), akkor a legkevesebb ,,jó'' szakasz az $n_{1} = n_{2} = n_{3} = n_{4} = k$ esetben lesz, és a ,,jó'' szakaszok száma: $4 (\binom{k}{2})$ . Ez $n$ -nel kifejeze: $\frac{n (n - 4)}{8}$ .
Ha $n = 4 k + 1$ , akkor a ,,jó'' szakaszok száma úgy lesz minimális, ha három osztály mindegyikében $k$ darab pont van, egyben pedig $k + 1$ , a ,,jó'' szakaszok száma most $3 (\binom{k}{2}) + (\binom{k + 1}{2}) = \frac{(n - 1) (n - 3)}{8}$ .
Az $n = 4 k + 2$ esetben az előbbihez hasonlóan a ,,jó'' szakaszok számának minimuma: $2 (\binom{k}{2}) + 2 (\binom{k + 1}{2}) = \frac{{(n - 2)}^{2}}{8}$ .
Végül az $n = 4 k + 3$ esetben: $(\binom{k}{2}) + 3 (\binom{k + 1}{2}) = \frac{n - 1) (n - 3)}{8}$ .

Zakariás Ildikó Székesfehérvár, (Teleki Blanka Gimn., III.o.t.)

Megjegyzés: A függvény megfogalmazható az

r

-dimenziós tér pontpárjai meghatározta szakaszokra is. Ekkor egy osztályba soroljuk azokat a rácspontokat, amelyek első, második, stb. koordinátája azonos paritású. Ezért összesen

2^{r}

osztály lesz. Egy szakasz akkor és csak akkor lesz ,,jó'', ha végpontjai ugyanabba az osztályba tartoznak. Minimális számú ,,jó'' szakaszt kapunk, ha

| n_{i} - n_{j} | < 2

(

i

j = 1

2

...

2^{r}

;

i \neq j

n_{1} + n_{2} + ... + n_{2^{r}} = n

. A további számolások ugyanúgy végezhetők, mint az eredeti feladatban.