Форум атеистов Рунета http://ateistru.com/ |
|
Забавные задачки http://ateistru.com/viewtopic.php?f=12&t=3310 |
Страница 58 из 390 |
Автор: | sergey [ 14 фев 2018, 10:58 ] |
Заголовок сообщения: | Re: Забавные задачки |
Дано целое число в записи которого встречаются цифры 1, 3, 7. Доказать что всегда можно переставить цифры числа так, что оно будет делиться на 7. |
Автор: | Игнатка [ 14 фев 2018, 17:08 ] |
Заголовок сообщения: | Re: Забавные задачки |
sergey писал(а): Дано целое число в записи которого встречаются цифры 1, 3, 7. Доказать что всегда можно переставить цифры числа так, что оно будет делиться на 7. Это слишком похоже на предыдущую задачу. 137 -- при делении на 7 остаток 4, 173 -- 5, 317 -- 2, 371 -- 0, 713 -- 6, 731 - 3. Таким образом, получаются все шесть возможных вариантов остатков. Ставим все остальные цифры в любом порядке, умножаем его на 1000, находим у произведения остаток деления на 7, а дальше подбираем среди этих шести чисел такое, чтобы при добавлении его оказалось без остатка. |
Автор: | sergey [ 14 фев 2018, 17:21 ] |
Заголовок сообщения: | Re: Забавные задачки |
остатка 1 не вижу. |
Автор: | 5fingers [ 15 фев 2018, 06:55 ] |
Заголовок сообщения: | Re: Забавные задачки |
А с остатком 1 должен быть, видимо, отдельный разговор. Уважаемая Игнатка полностью привела алгоритм для всех прочих остатков. После выборки из числа 1, 3 и 7 - от числа что-то остаётся. Обозначим это X. Ну или же ничего не остаётся. В таком случае переставляем цифры как 371 - и готово. Число делится на 7. Если же X всё-таки непуст - то появляется масса перестановок. X137, X173, X317, X371, X713, X731. Ровно 3!=6 случаев, перестановка из 3-х элементов, когда на первом месте X. Выше уже рассмотрено, когда надо так переставлять - когда остатки кроме 1 у перестановки 137, что фактически означает остаток кроме 6 у X. Однако есть ведь и случаи 137X, 173X, 317X, 371X, 713X, 731X - их тоже 6. Есть ещё случаи когда цифры можно "запихнуть внутрь" X - но мы их сейчас рассматривать не будем. Достаточно и того, что уже есть. Итак, X при делении на 7 даёт остаток 6. Из добавки к нему спереди из цифр 1, 3 и 7 мы должны получить недостающий остаток 1. Вопрос - а сколькозначный X? Сколько в нём цифр? Если одна - то запись 137X по сути 137*10 + X Если две - то 137*100 + X 1370 + X 13700 + X И т.д. Мы говорим о перестановке цифр 1, 3 и 7, умноженной на 10 в степени N - и это число должно давать остаток 1. При делении на 7. Не получилось сзади числа - вдруг получится спереди числа? А давайте вообще разберёмся - какие остатки при делении на 7 дают степени десятки? 10 : 7 - в остатке будет 3 100 : 7 - в остатке будет 2 1000 : 7 - в остатке будет 6 10 000 : 7 = 4 100 000 : 7 = 5 1 000 000 : 7 = 1 10 000 000 : 7 = 3 Ну и дальше поехали по кругу. Итак, нам надо получить при делении на 7 остаток 1. Выходит, если число Х однозначное - то мы выбираем 1 730 + Х. У 173 остаток 5, у десятки 3, получается 1. Если двузначное - выбираем 13 700 + Х. У 137 остаток 4, у сотни 2, снова получится 1. Если трёхзначное - выбираем 713 000. У 713 остаток 6, у тысячи 6, остаток снова 1. Четырёхзначное - 3 170 000 - получится 2*4 и остаток снова 1. Пятизначное - 7 310 000 - снова 3*5 = 1 в остатке. Шестизначное число? Которое даёт остаток 1? Гмммм.... Пока ничего не выбираем. Семизначное - см. однозначное, и т.д. Итак, почти готово. Если Х даёт любой остаток кроме 6 - то сзади приписываем числа по схеме уважаемой Игнатки. Если Х даёт в остатке 6 - то приписываем спереди сочетания, исходя из длины Х. Основная трудность с шести(12, 18 и т.д.)значным числом Х, дающим в остатке 6. Потому как 1 получить не удаётся. Пока всё правильно? Но кто же мешает разбить нам 1, 3 и 7? Часть до числа Х, а часть после? Если число Х имеет 6 цифр - то число, к примеру, 13Х7 = 130 000 000 + Х*10 + 7. Ну и так далее. И видим мы любопытнейшую вещь: число 3Х17, состоящее из: 3*100 000 000 + Х*100 + 10 + 7 должно разделиться на 7 полностью. Ибо у 100 000 000 остаток 2, у 300 000 000 остаток будет 6. У Х, как мы договаривались, остаток 6, значит у Х*100 остаток 600, что суть 5. У числа 10 остаток 3. А семёрка не в счёт. Она делится на 7. И мы получаем сумму остатков: 6+5+3 = 14. Число вида 3X17 разделится на семь, при условии, что Х - шестизначное число, дающее при делении на 7 остаток, равный 6. При всех иных иксах методы перестановки уже были описаны. Наверняка совершенно аналогичные рассуждения будут справедливы и для Х 12-ти, 18-ти и т.д. -значного. Итак, существование и возможность перестановки доказана. Более того, доказательство носит конструктивный характер, ибо был показан алгоритм подобной перестановки. ЧТД. |
Автор: | 5fingers [ 15 фев 2018, 07:53 ] |
Заголовок сообщения: | Re: Забавные задачки |
ПС: По-моему ошибка про остаток Х-а. Ещё раз: если Х при делении на 7 даёт остаток 2, то Х317. Чтобы получилось 2002. Если Х при делении даёт остаток 3, то Х731. Чтобы получилось 3003. И т.д. Ааа, тогда ясно. Чтобы получилось 1001 - и Х, и перестановка 137 должна давать остаток 1. Х должен давать не 6, а 1. Давайте с учётом этого обстоятельства переправим решение? Х однозначный - надо брать 317Х. 317*10 + Х. По остаткам 2*3 + 1 = делится на 7. Х двузначный - надо брать 731Х. 731*100 + Х. По остаткам 3*2 + 1 = делится на 7. Х трехзначный - надо брать чтобы остаток был 1, умножился бы на 6 и снова + 1. Однако такого остатка нет. Позже рассмотрим. Х 4-значный - надо брать 173Х. 173*10 000 + Х. По остаткам 4*5 + 1 = делится на 7. Х 5-значный - надо брать 137Х. 137*100 000 + Х. По остаткам 5*4 + 1 = делится на 7. Х 6-значный - надо брать 317Х. 317*1 000 000 + Х. По остаткам 2*3 + 1 = делится на 7. Итак, всё верно. Просто предыдущее решение должно быть скорректировано. Оно было получено из неправильного рассуждения об остатках. Правильно так: решение получается для всех случаев, кроме трёхзначного Х с остатком 1. (пресловутый 1001). Остаётся рассмотреть лишь его. (что сейчас и пытаюсь сделать) |
Автор: | 5fingers [ 15 фев 2018, 09:14 ] |
Заголовок сообщения: | Re: Забавные задачки |
Итак, имеем некое число шестизначное, в котором есть цифры 1, 3, 7; и ещё какие-то цифры a, b ,c - причём такие, что цифровая запись числа abc делится на 7 с остатком 1. Для такого случая можно предложить вот что (так как я не придумал ничего конкретного) - переставить цифры abc, чтобы остаток от деления на 7 был бы не равен 1. А стал равен любому другому числу. Для других остатков у нас уже есть решения. Всегда ли можно выполнить подобную перестановку? Если число abc превращается в bac - очевидно что мы вносим разницу 90(a-b). Если число abc превращается в acb - вносимая разница 9(b-c). И т.д. Все пары 9(b-c), 90(a-b), 99(a-c) попросту не могут нацело делиться на 7. Поэтому правильно переставить цифры вообще-то можно. Хотя нет. Иногда могут. В тех случаях, когда все цифры одинаковы. Т.е. число имеет вид aaa. Тогда как хошь переставляй - остаток снова будет = 1. Осталось выяснить - какие из трехзначных чисел вида aaa делятся на 7 с остатком 1. aaa = a * 111. aaa / 7 = a * (105 + 6) / 7 = 15a + 6a / 7 a=1 остаток=6; a=2 ост=5; a=3 ост=4; а=4 ост=3; а=5 ост=2; а=6 ост=1; а=7 ост=0; а=8 ост снова = 6 и т.д. Итак, осталось доказать для единственного случая 1, 3, 7, 6, 6, 6 - что существует такая перестановка. Вот она: 136 766. Проверял калькулятором. Неохота делить было. Ну вот, в принципе, и всё. Для чисел, не дающих в остатке 1, ставим в конец последовательности, предложенные Игнаткой. Для чисел, дающих в остатке 1 и при этом не трёхзначных и не 6n+3 значных (конечно же последовательность не 6, 12 и 18, как я ошибочно писал ранее, а 3, 9, 15 и т.д. = 6n+3) - разбиваем 1,3 и 7 по схеме и вписываем внутрь наше число. Для чисел дающих в остатке 1 и 6n+3-значных пытаемся переставить цифры, чтобы остаток не был = 1. Если получается - можно смело переходить к первому пункту. Если и это не получается - то все цифры этого числа равны. А это 666. Превращаем его в 136 766 и спокойно делим на 7. Кстати число 136 766 666 666 также спокойно делится на 7. Ну и т.д. ЧТД. Теперь уж точно всё. |
Автор: | sergey [ 15 фев 2018, 10:24 ] |
Заголовок сообщения: | Re: Забавные задачки |
5fingers писал(а): А это 666. Принимается, хотя ваше решение наводит ужас на православных. Но я рассуждал проще. Для 4х цифр - 1,3,7,9 задача решена. А если будет не 9, а какая-нибудь другая цифра? Оказалось что числа полученные перестановками цифр a137, 1a37,13a7,...7a31,73a1,731a при делении на 7 дают полный набор остатков 0,1,2,3,4,5,6 при любой цифре а (0,1,2,3...9). Т.е. смещаем цифры 1,3,7 в конец числа. Добавляем к ним ту, что стоит на 4м месте справа. И в зависимости от остатка деления (обрезка*10000) на 7, переставляем последние 4 цифры. Таких групп по 4 цифры надо было проверить 10х4!=240. Немного нудно, но в Еxcel’e протяжкой формул делается за 5минут. |
Автор: | Игнатка [ 16 фев 2018, 00:15 ] |
Заголовок сообщения: | Re: Забавные задачки |
sergey писал(а): остатка 1 не вижу. Написала сколько успела придумать. В порядке компенсации могу загадать загадку попроще. Докажите, что СхСхСхР заведомо не равно РФ. (Здесь "х" -- знак умножения, одинаковыми буквами обозначены одинаковые цифры, разными -- разные, двузначное число не может начинаться с нуля. Имеется в виду обычная десятичная запись чисел) |
Автор: | 5fingers [ 16 фев 2018, 00:28 ] |
Заголовок сообщения: | Re: Забавные задачки |
Произведём доказательство от противного. Пусть будет равно. С3*Р = 10*Р + Ф Все Р в одну сторону, Ф в другую: (С3 - 10)*Р = Ф Р, С и Ф - цифры. От 1 до 9, ну может где-то затесался 0. Но не С и не Р. С должен быть > 2, иначе (С3 - 10) получается отриц.числом. Однако первое же большее 2х число С=3 уже даёт 17 в скобке. А для бОльших С значение в скобке будет ещё больше. И уж явно > 10. Что уже не годится для цифры Ф. |
Автор: | Игнатка [ 16 фев 2018, 02:56 ] |
Заголовок сообщения: | Re: Забавные задачки |
5fingers писал(а): Произведём доказательство от противного. И таки провели его верно! |
Страница 58 из 390 | Часовой пояс: UTC + 4 часа |
Powered by phpBB® Forum Software © phpBB Group http://www.phpbb.com/ |