Навчання / Бібліотека / Комбінаторика

Підмножина з фіксованою сумою

КомбінаторикаСереднє

Яке найменше $n$ таке, що кожна множина з $n$ різних цілих чисел, вибраних від $1$ до $50$ , обов’язково містить $2$ числа із сумою $51$ ?

Для перевірки відповіді потрібен JavaScript. Підказка й розв’язок відкриваються і без нього.

Підказка

Згрупуй числа в ящики так, щоб $2$ числа в одному ящику завжди давали потрібну суму.

Розв’язок

Числа розбиваються на $25$ груп $(k, 51 - k)$ для $k = 1, \dots, 25$ , і кожна група має суму $51$ .
Якщо взяти по одному числу з кожної групи, вийде множина з $25$ чисел, де жодні $2$ не дають $51$ .
Будь-яка множина з $26$ чисел за принципом Діріхле мусить узяти обидва числа якоїсь групи.
Отже, найменше $n$ дорівнює $26$ .

Відповідь: $26$