Kezdőlap


Feladat:	B.3975	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Cséke Balázs
Füzet:	2008/március, 153 - 154. oldal		PDF \| MathML
Témakör(ök):	Kombinációk, Kombinatorikai leszámolási problémák, Feladat
Hivatkozás(ok):	Feladatok: 2007/február: B.3975

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.

Megoldás. Azt állítjuk, hogy egy tetszőleges $N$ számot $(\binom{N - 1}{2})$ -féleképpen lehet felírni három pozitív egész szám összegeként, ha az összeadandók sorrendje is számít.
Ennek bizonyításához képzeljünk el $N$ darab golyót egy sorban egymás mellé helyezve. Pontosan annyiféleképpen lehet az $N$ -et három szám összegére bontani, ahányféleképpen az $N$ golyót három csoportba tudjuk osztani úgy, hogy a csoportok sorrendje is számít. Ahhoz, hogy az $N$ darab golyót három csoportba osszuk, a köztük levő $N - 1$ darab ‐ képzeletbeli ‐ választóvonal közül kell kiválasztanunk kettőt. Ezt $(\binom{N - 1}{2})$ -féleképpen tehetjük meg.
2007 nem írható fel ilyen alakban, de egy hozzá közeli szám, a 2016 igen: $2016 = (\binom{65 - 1}{2})$ .
A feladat azon feltételét, hogy $1$ és $k$ közötti számokra kell osztanunk a 2007-et, még nem vettük figyelembe.
Ha $k = N - 1$ , akkor a felírások száma ugyanúgy $(\binom{N - 1}{2})$ , hiszen ekkor csak $N$ -et nem használhatjuk fel, de eddig sem használtuk.
Ugyanez igaz $k = N - 2$ esetén is.
Ha $k = N - 3$ , akkor nem számolhatjuk az $(N - 2)$ , $1$ , $1$ esetet és ennek további kétféle sorbarendezését.
Ha $k = N - 4$ , akkor az előzőn kívül nem használhatjuk még az $(N - 3)$ , $2$ , $1$ esetet, aminek összesen 6 permutációja van.
Ezért $k = N - 4$ -re az összes eset: $(\binom{N - 1}{2}) - 3 - 6 = (\binom{N - 1}{2}) - 9$ . Mivel 2007 pontosan 9-cel kevesebb, mint 2016, azért $N = 65$ és $k = 65 - 4 = 61$ esetén a megfelelő felírások száma: $(\binom{65 - 1}{2}) - 9 = 2007$ .

Megjegyzés. Általában,

2 k > N

és

N - 1 > k

esetén a lehetséges felírások száma:

\begin{matrix} (\binom{N - 1}{2}) - 3 \cdot (\binom{N - 1 - k}{2}) . \end{matrix}

A jó esetek számát úgy kapjuk meg, ha az összes eset számából kivonjuk a rossz esetek számát, vagyis azon felbontások számát, ahol az egyik tag

k

-nál nagyobb. (

2 k > N

miatt csak az egyik tag lehet ilyen.)
A rossz eseteket kell összeszámolnunk. Tekintsük az előző golyókat, és vegyük először azokat az eseteket számba, amikor az első csoportban van

k

-nál több golyó. Ez azt jelenti, hogy a

(k + 1)

-edik golyótól kezdve az

N

-edik golyóig a található

N - 1 - k

képzeletbeli választóvonal közül kell 2-t kiválasztani, amit

(\binom{N - 1 - k}{2})

-féleképpen tehetünk meg. A

k

-nál több golyót tartalmazó csoport nem csak az első lehet a három közül, ezért még 3-mal meg kell szorozni

(\binom{N - 1 - k}{2})

-t.
Megoldás még:

N = 121

és

k = 61

;

N = 71

és

k = 53

; valamint

N = 91

és

k = 53