Problem C. 1661. (March 2021)

C. 1661. In a lottery game, the player bets 5 numbers out of the positive integers 1 to 90. Otto Lotter insists on increase, and he always keeps the following rules when making his bets: he marks 5 numbers such that every digit may only occur once, and if the five numbers are listed in increasing order, the digits must be ascending, too. For example, 1, 2, 3, 46, 78. How many suitable selections of five numbers are there?

Proposed by Berkó Erzsébet, Szolnok

(5 pont)

Deadline expired on April 12, 2021.

Sorry, the solution is available only in Hungarian. Google translation

Megoldás. A feltételek teljesüléséhez az szükséges, hogy a számok növekvő sorrendjében a számjegyeknek is növekednie kell, a fenti példában például 1, 2, 3, 4, 6, 7, 8 a számjegyek kérdéses sorrendje. Világos, hogy a jegyek között nem szerepelhet a 0, és az is, hogy a jegyek száma legalább öt és legfeljebb kilenc.

Megfordítva, ha vesszük az \(\displaystyle 1-9\) számjegyek közül \(\displaystyle k\) darabnak egy növekvő sorozatát, az egyértelműen meghatároz egy megfelelő számötöst. Ugyanis, mivel egyjegyű és kétjegyű számok szerepelhetnek, pontosan \(\displaystyle (k-5)\) darab kétjegyű kell legyen közöttük, amelyeknek – hogy növekvő sorrendet kapjunk – a végén kell szerepelniük. (Vagyis ha a számjegyek sorozata \(\displaystyle a_1<a_2<\dots<a_k\), akkor a kihúzott számok \(\displaystyle a_1,\dots,a_{10-k},\overline{a_{11-k}a_{12-k}},\dots,\overline{a_{k-1}a_k}\), ahol \(\displaystyle k=6\) esetén a két felülvonásos szám megegyezik és csak egy kétjegyű szám van.)

A 9 számjegy közül \(\displaystyle k\) különbözőt \(\displaystyle \binom{9}{k}\)-féleképpen válszthatunk ki, és a korábbiak alapján \(\displaystyle 5\leq k\leq 9\) esetén ez már meghatározza a számötöst. Így a feltételeknek megfelelő számötösök száma:

\(\displaystyle \binom{9}{5}+\binom{9}{6}+\binom{9}{7}+\binom{9}{8}+\binom{9}{9}=126+84+36+9+1=256.\)

Megjegyzés. A megoldás végén számolás helyett úgy is érvelhetünk, hogy a 9 számjegyből álló halmaznak \(\displaystyle 2^9=512\) részhalmaza van, és ezeknek pontosan a fele, vagyis 256 megfelelő, hiszen egy részhalmaz és a komplementere közül mindig pontosan az egyiknek lesz legalább öt eleme.

Statistics:

161 students sent a solution.
5 points:	107 students.
4 points:	12 students.
3 points:	7 students.
2 points:	7 students.
1 point:	12 students.
0 point:	5 students.
Unfair, not evaluated:	8 solutionss.
Not shown because of missing birth date or parental permission:	3 solutions.

Problems in Mathematics of KöMaL, March 2021