2. Дирихле принцип н ң дәлел қарапайым, б рақ назар аударуға лайық

2. Дирихле принцип
Дирихле принцип н ң дәлел қарапайым, б рақ назар аударуға лайық,
өйткен ұқсас дәлелдер жи кездесед .
ек адамды ғана асырай алатын лами. Бәдәуи әйел н ң бөтен еркекпен
араласуына рұқсат бере алмайды. Бүк л компания ек нш жаққа өте ала ма?
Дирихле принцип н ң1 б рнеше тұжырымдары бар. Ең қарапайымы
келес дей: «Егер бес қоян ек торда отырса, онда
Кейб р торда кем дегенде үш қоян бар». Жалпылама тұжырымда Дирихле
принцип келес дей ест лед : «Егер k ұяшықта nk-ден көп қоян болса, онда кем
дегенде б реу нде n-ден көп қоян бар».
1
15. Отбасы түнде көп рге жақындады. Әкем оны 1 минутта, анам 2 минутта,
бала 5 минутта, әже 10 минутта өте алады. Олардың б р шамы бар. Көп р ек
адамды ғана көтере алады. Олар көп рден 17 минутта қалай өте алады? (Егер ек
адам өт п бара жатса, онда олар өздер н ң жылдамдығынан төмен жүред .
С з жасай алмайсыз: көп р бойымен фонарсыз қозғалуға, алыстан жарқырауға,
б р-б р н қолдарыңызға алып жүруге, фонарь лақтыруға).
Питер Густав Лежеун Дирихле (1805-1859) - нег зг еңбектер сандар теориясы
мен математикалық талдауға арналған нем с математиг . Маңызды еңбектер
механика мен математикалық физикаға арналған.
Бұл мәл мдеме сәл басқаша былай тұжырымдалған: «Егер n қоян k торда отырса,
онда кем дегенде n / k қоян болатын тор бар және n / тен көп емес тор бар. k қоян».
Қояндардың бөлшек санымен шатастырмаңыз: б р нш тұжырымда торда кем
дегенде 5/2 қоян бар екен белг л болды, бұл кем дегенде үш дегенд
б лд ред .
16. Үш данышпанның көздер н байлап, олардың әрқайсысының басына бес
қақпақтың б реу , оның ш нде екеу жасыл, үшеу қызыл түст екен н
айтады. Содан кей н көздер н шеш п, қалған ек данышпанға қарап, олардың
қалпақтарының түс н анықтауды сұрайды. Үш қалпақ да қызыл түст . Б рнеше
минуттан кей н б р дана адам дұрыс жауап берд . Ол қалпақшасының түс н
қалай белг лед ?
12
Дирихле принцип көгерш ндер мен қораптар принцип рет нде де
белг л , бұл кезде қояндардың рөл н көгерш ндер ойнайды, ал ұяшықтар
қораптар болып табылады. Бұл атау ағылшын және кейб р басқа т лдерде кең таралған.
Machine Translated by Google

Мәселен шешуд ң мысалдарын қарастырайық.
Шеш м (Дирихле принцип н қолдану). Ондай айдың бар екен н
дәлелдеп көрей к. Әрб р оқушы өз н ң туылған айына тура
келет нд ктен, «клетка» рөл н жыл айлары (олардың саны 12), ал
«қояндардың» рөл н студенттер атқарады (ол жерде олардың 40-ы).
Дирихле принцип бойынша кем нде 40-тан тұратын ұяшық бар
Дирихле принцип н жалпылама тұжырымдау үш н қайшылық арқылы
дәлелдеуд орындайық. Кер с нше дел к: әрб р торда k қояннан
артық болмайды. Сонда барлығында ең көб nk қояндар бар, ал шарты
бойынша олардың саны nk-ден көп. Б зд ң болжамды жоққа шығаратын
қарама-қайшылықты алдық.
Есеп 17. Сыныпта 40 оқушы бар. Жылда осы сыныптың кем нде 4
оқушысы туған күн н тойлайтын ай бар ма?
Шеш м (қайшылық әд с ). Ондай ай жоқ деп есептей к. Одан
кей н жылдың әр 12 айында туған күн н үш сыныптастан артық
тойламайды. Бұл жағдайда оқушылардың жалпы саны 12 3 36-дан
аспайды
қояндар, яғни. 4 қоян. Демек, б р ай бар
Дирихле принцип түс н кт болып көр нед , б рақ оны
қолдану үш н нен ң қоян, нен ң ұяшық болып есептелет н н болжау
қиын болуы мүмк н. Мынадай кеңес беруге болады: егер А жиынының
әрб р элемент В жиынының дәл б р элемент не сәйкес келсе, онда А-
ның элементтер н қояндар, ал В элементтер н ұяшықтар деп атауға болады.
12
бұл мәселен ң шарттарына қайшы
келед . Б зд ң болжамымыз дұрыс емес, яғни бұл сыныпта кем нде
төрт оқушының туған күн болатын ай бар.
13
Дирихле принцип үзд кс з болуы мүмк н: «Егер n қоян м кг шөп
жесе, онда кейб р қоян м/н кг-нан кем емес, ал кейб реулер м/н кг-нан
артық емес жед » (ал егер б реу орташадан артық жесе, онда б реу
орташадан аз жед ). Назар аударыңыз, бұл тұжырымда қояндар шөпке
арналған тор рөл н атқарады, ал шөп торларда отырған қояндардың
рөл н атқарады.
сыныпта кем нде 4 оқушы туған күн н тойлайтын мектеп.
,
Ескерту. Бұл өте қарапайым тапсырма. Оқушыларға арналған
математикалық олимпиадада дәлелдеу мәселес туындауы мүмк н
Machine Translated by Google

Шеш м. Мәскеуд ң әрб р тұрғыны басындағы шаштың белг л
б р санына сәйкес келет нд ктен, тұрғындар қоянның рөл н, ал
шаштардың саны жасушалардың рөл н атқарады (олардың 150 001- бар:
0-ден 150 001-ге дей н нөм рлену мүмк н). ), әрб р «қоян» оның
басындағы шаш санына сәйкес келет н «клеткаға» түсед .
басында
ұқсас факт н анықтау күрдел тапсырманың б р бөл г ғана. Бұл
жағдайда, әдетте, олар жай жазады: «Дирихле принцип бойынша, б р
сыныпта (барлығы 40 оқушы бар) кем нде 4 оқушы туған күн н тойлайтын
б р ай бар». Тағы ек күрдел мәселен қарастырайық. Есеп 18.
Мәскеуде 10
миллионға жуық адам тұрады1
Өйткен 150 001 «жасушада» 59 150001 8850059 артық
«қояндар», яғни олардың кем дегенде б реу нде кем нде 60 «қоян»
бар. Демек, Дирихле принцип бойынша Мәскеуде бастарында б рдей
шашы бар кем дегенде 60 адам бар.
,
әрқайсысында 150 000 шаштан аспайды. Мәскеуде бар екен н дәлелдең з
1
18-мәселен шешу кез нде кейде қател к ж бер лед : мүмк н
болатын опциялардың саны («ұяшықтар») 150 000-ға тең деп есептелед ,
рұқсат ет лген опция 0 шашты ұмытып
кетед . Есеп 19. Футбол чемпионатына 12 команда қатысады, олардың
әрқайсысы б р-б р мен б р матч өтк зу керек. Жарыстың кез келген
сәт нде б рдей матчтар өтк зген ек команда бар екен н дәлелдең з.
кем дегенде 60 адам басындағы шаштары б рдей.
2009 жылдың 1 қаңтарындағы статистикалық мәл меттер бойынша
Мәскеуде 10 миллион 509 мың адам тұрады.
Шеш м. Әр команда өтк зет н матчтар саны 0-ден (чемпионаттың
басында) 11-ге дей н (чемпионаттың соңында) өзгеред . Егер жарыстың
б р кезең нде барлық командалар әр түрл матчтар өтк зген деп
болжасақ, онда бұл б р команда әл б рде-б р матч өтк збеген н
б лд ред , ек нш с - 1, үш нш - 2, ..., он ек нш - барлығы 11
матч. Сонда он ек нш команда барлық командалармен, ал б р нш с
ешқайсысымен ойнап үлгерген белг л болды. Б зде қайшылық бар.
Демек, жарыстың кез келген сәт нде кем дегенде ек команда тең
матчтар санын ойнады.
14
Machine Translated by Google