Форум атеистов Рунета

Текущее время: 29 мар 2024, 00:28

Часовой пояс: UTC + 4 часа




Начать новую тему Ответить на тему  [ Сообщений: 3887 ]  На страницу Пред.  1 ... 55, 56, 57, 58, 59, 60, 61 ... 389  След.
Автор Сообщение
 Заголовок сообщения: Re: Забавные задачки
СообщениеДобавлено: 14 фев 2018, 10:58 
Не в сети
Аватара пользователя

Зарегистрирован: 17 авг 2012, 21:37
Сообщения: 32141
Откуда: Новороссийск
Дано целое число в записи которого встречаются цифры 1, 3, 7.
Доказать что всегда можно переставить цифры числа так, что оно будет делиться на 7.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Забавные задачки
СообщениеДобавлено: 14 фев 2018, 17:08 
Не в сети

Зарегистрирован: 18 авг 2012, 15:18
Сообщения: 2756
sergey писал(а):
Дано целое число в записи которого встречаются цифры 1, 3, 7.
Доказать что всегда можно переставить цифры числа так, что оно будет делиться на 7.

Это слишком похоже на предыдущую задачу.

137 -- при делении на 7 остаток 4, 173 -- 5, 317 -- 2, 371 -- 0, 713 -- 6, 731 - 3. Таким образом, получаются все шесть возможных вариантов остатков. Ставим все остальные цифры в любом порядке, умножаем его на 1000, находим у произведения остаток деления на 7, а дальше подбираем среди этих шести чисел такое, чтобы при добавлении его оказалось без остатка.

_________________
Что нам действительно нужно, так это воображение, но воображение в надёжной смирительной рубашке. (Ричард Фейнман)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Забавные задачки
СообщениеДобавлено: 14 фев 2018, 17:21 
Не в сети
Аватара пользователя

Зарегистрирован: 17 авг 2012, 21:37
Сообщения: 32141
Откуда: Новороссийск
остатка 1 не вижу.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Забавные задачки
СообщениеДобавлено: 15 фев 2018, 06:55 
Не в сети

Зарегистрирован: 18 авг 2012, 17:06
Сообщения: 8277
А с остатком 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-ти и т.д. -значного.

Итак, существование и возможность перестановки доказана. Более того, доказательство носит конструктивный характер, ибо был показан алгоритм подобной перестановки.

ЧТД.
:P


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Забавные задачки
СообщениеДобавлено: 15 фев 2018, 07:53 
Не в сети

Зарегистрирован: 18 авг 2012, 17:06
Сообщения: 8277
ПС: По-моему ошибка про остаток Х-а.

Ещё раз: если Х при делении на 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).

Остаётся рассмотреть лишь его.
(что сейчас и пытаюсь сделать)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Забавные задачки
СообщениеДобавлено: 15 фев 2018, 09:14 
Не в сети

Зарегистрирован: 18 авг 2012, 17:06
Сообщения: 8277
Итак, имеем некое число шестизначное, в котором есть цифры 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.
Ну и т.д.

ЧТД.
Теперь уж точно всё.
;) :P


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Забавные задачки
СообщениеДобавлено: 15 фев 2018, 10:24 
Не в сети
Аватара пользователя

Зарегистрирован: 17 авг 2012, 21:37
Сообщения: 32141
Откуда: Новороссийск
5fingers писал(а):
А это 666.
:twisted:
Принимается, хотя ваше решение наводит ужас на православных. Но я рассуждал проще. Для 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минут.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Забавные задачки
СообщениеДобавлено: 16 фев 2018, 00:15 
Не в сети

Зарегистрирован: 18 авг 2012, 15:18
Сообщения: 2756
sergey писал(а):
остатка 1 не вижу.

:oops: Написала сколько успела придумать. В порядке компенсации могу загадать загадку попроще.

Докажите, что СхСхСхР заведомо не равно РФ.

(Здесь "х" -- знак умножения, одинаковыми буквами обозначены одинаковые цифры, разными -- разные, двузначное число не может начинаться с нуля. Имеется в виду обычная десятичная запись чисел)

_________________
Что нам действительно нужно, так это воображение, но воображение в надёжной смирительной рубашке. (Ричард Фейнман)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Забавные задачки
СообщениеДобавлено: 16 фев 2018, 00:28 
Не в сети

Зарегистрирован: 18 авг 2012, 17:06
Сообщения: 8277
Произведём доказательство от противного.
Пусть будет равно.
С3*Р = 10*Р + Ф
Все Р в одну сторону, Ф в другую:

3 - 10)*Р = Ф
Р, С и Ф - цифры. От 1 до 9, ну может где-то затесался 0. Но не С и не Р.
С должен быть > 2, иначе (С3 - 10) получается отриц.числом.
Однако первое же большее 2х число С=3 уже даёт 17 в скобке. А для бОльших С значение в скобке будет ещё больше. И уж явно > 10. Что уже не годится для цифры Ф.

;)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Забавные задачки
СообщениеДобавлено: 16 фев 2018, 02:56 
Не в сети

Зарегистрирован: 18 авг 2012, 15:18
Сообщения: 2756
5fingers писал(а):
Произведём доказательство от противного.

И таки провели его верно!

_________________
Что нам действительно нужно, так это воображение, но воображение в надёжной смирительной рубашке. (Ричард Фейнман)


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3887 ]  На страницу Пред.  1 ... 55, 56, 57, 58, 59, 60, 61 ... 389  След.

Часовой пояс: UTC + 4 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 9


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения

Найти:
Перейти:  
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB