сайты - меню - вход - но­во­сти


Задания
Версия для печати и копирования в MS Word

Рас­смот­рим все 7! се­ми­знач­ных чисел, по­лу­ча­ю­щих­ся из числа 1 234 567 все­воз­мож­ны­ми пе­ре­ста­нов­ка­ми цифр. Сколь­ко из них дают оста­ток 5 при де­ле­нии на 7?

Спрятать решение

Ре­ше­ние.

Обо­зна­чим за An, n=0, 1, \ldots, 6 мно­же­ства тех из рас­смат­ри­ва­е­мых чисел, ко­то­рые при де­ле­нии на 7 дают остат­ки 0, 1, 2, ..., 6 со­от­вет­ствен­но. До­ка­жем, что каж­дое из этих мно­жеств со­дер­жит оди­на­ко­во ко­ли­че­ство чисел, рав­ное  дробь: чис­ли­тель: 7!, зна­ме­на­тель: 7 конец дроби =6!. За­ме­тим, что число 1 111 111 при де­ле­нии на 7 даёт оста­ток 1. С каж­дым из рас­смат­ри­ва­е­мых чисел a про­де­ла­ем сле­ду­ю­щее: при­ба­вим к каж­дой цифре a еди­ни­цу, если при этом в не­ко­то­ром раз­ря­де по­лу­ча­ет­ся цифра 8, за­ме­ним её на цифру на 1, да­ю­щую тот же оста­ток от де­ле­ния на 7. Оста­ток от де­ле­ния по­лу­чен­но­го числа на 7 равен остат­ку от де­ле­ния на 7 числа a плюс 1 111 111, то есть на 1 боль­ше, чем оста­ток от де­ле­ния на 7 числа a. Сле­до­ва­тель­но, дан­ное отоб­ра­же­ние од­но­знач­но пе­ре­во­дит каж­дое число мно­же­ства An в не­ко­то­рое число мно­же­ства A_n плюс 1, для всех n=0, 1, \ldots, 6, причём раз­ные числа из An пе­ре­хо­дят в раз­ные числа из A_n плюс 1. Зна­чит, ко­ли­че­ство чисел в A1> не мень­ше, чем в A0, ко­ли­че­ство чисел в A2 не мень­ше, чем в A1 и так далее, ... ко­ли­че­ство чисел в A0 не мень­ше, чем в A6, по­это­му все мно­же­ства An, n=0, 1, \ldots, 6 со­дер­жат оди­на­ко­вое ко­ли­че­ство чисел, рав­ное  дробь: чис­ли­тель: 7!, зна­ме­на­тель: 7 конец дроби =6!.

 

Ответ: 6!.

Спрятать критерии
Критерии проверки:

Идея при­бав­ле­ния 1 во всех раз­ря­дах: 2 балла.

До­ка­за­тель­ство, что такая опе­ра­ция пе­ре­во­дит мно­же­ства An,  n=0, 1, \ldots, 6 друг в друга: 3 балла.

До­ка­за­тель­ство рав­но­мощ­но­сти этих мно­жеств: 2 балла.