Математическое и загадочное

[sputnikk]

 

 

Можно ли найти другое число, которое делится на 17 и состоит только из нулей и единиц?

Кажется ограничений недостаточно. Например 10 можно поделить на 17.

[Никита Гайнанов]

Сразу вспоминается двоичная система 
10001₂ / 17₁₀ = 1₁₀

Изменено 28 сентября, 2017 пользователем Никита Гайнанов

[Roma1]

 

 

Сразу вспоминает двоичная система

Я бы по другому искал ответ. Сейчас не на чем писать программу, а так решается просто.

1. берем число х=1.

2. прибавляем 1 (х=х+1).

3. умножаем на 17 у=х*17

4. считаем кол-во символов (во многих языках есть такая функция)

5. делаем цикл от 1 до кол-во символов с шагом 1.

6. проверяем на 0 или 1

7. если да то продолжаем цикл иначе возврат к шагу 2

8. если цикл закончен, то выводим у

[Kapral]

Берём число 17. Можно ли найти другое число, которое делится на 17 и состоит только из нулей и единиц?

 

P.S. Да! Попробуйте решить задачу на листке бумаги, а не перебором.

11101/17 = 653

 

Перебор будет в любом случае

или угадать с первого раза, либо любое второе вычисление это уже перебор

[E.K.]

 

P.S. Да! Попробуйте решить задачу на листке бумаги, а не перебором.

11101/17 = 653

 

Перебор будет в любом случае

или угадать с первого раза, либо любое второе вычисление это уже перебор

Перебором её любая школьница решит!

Давайте без перебора.

[Kapral]

 

 

Давайте без перебора.

Кхм... Ответ нашел на 5 итерации

А как сразу, сказать не знаю, и даже не представляю с какой стороны подступаться

[E.K.]

Попробуйте признак деления на 17.

[santax]

А такой есть? Его загуглить можно?

[thyrex]

Их даже два

[Kapral]

Хм... а вот признака деления на 17 я и не знал, даже не знал что такой существует

Буду думать

[E.K.]

Ну что - надумали?

 

P.S. -----

 

Не получилось? - ну, тогда я подумаю..

 

17 нужно умножить на что-то, чтобы получились единицы и нули.

Если умножать на два - то как-то последняя цифра никак не 1, а также не 0.

Чтобы последняя цифра было 0 или 1 надо умножать на 3 (сами попробуйте умножить на нечто другое, ага).

 

Ого, нам нужно получить 17*??? = {много 1,0}.

Какие умножения на 7 дают нам 0 или 1 в самом конце?

0 не надо, оно же просто сдвигает задачу влево.

1 = 3.

То есть, чтобы в результате было {много 1,0} с другой стороны должно быть 17 * (???...?3)

 

Дальше сами - или опять звонок другу?

[Никита Гайнанов]

В конце должна быть тройка это мы поняли.

17 умножаем на 3 получаем - 51. Чтобы вместо 5 получить 0 или единицу надо 17 умножить на такую цифру, чтобы в результате произведение оканчивалось на 5 или на 6. Соответственно нам подходят цифры 5 и 8. Дальше уже два пути в зависимости от того какую цифру выберем. 

1) Выбрали цифру 5.
17*53 = 901. Чтобы вместо 9 получить 0 или 1 надо 17 умножить на такую цифру, чтобы в результате произведение оканчивалось на 1 или на 2. Соответственно нам подходят цифры 3 и 6. Дальше уже два пути в зависимости от того какую цифру выберем.

1.1) выбираем цифру 3.
17*353= 6001 Чтобы вместо 6 получить 0 или 1 надо 17 умножить на такую цифру, чтобы в результате произведение оканчивалось на 5 или на 4. Соответственно нам подходят цифры 2 и 5. Дальше уже два пути в зависимости от того какую цифру выберем. и т.д. будет ветвиться до тех пор пока в каждой ветви не найдется число удовлетворяющее значению ну или пока не зациклится.

 

1.2) выбираем цифру 6.
17*653= 1101 Получили искомое число - 653. Также нам подойдут числа 65300653, 6530065300653. 653006530065300653 и т.д.

2) Если на первом этапе выбрать цифру 8, а не цифру 5, то получим вторую половину дерева.
17*83 = 1411. Чтобы вместо 4 получить 0 или 1 надо 17 умножить на такую цифру, чтобы в результате произведение оканчивалось на 6 или на 7. Соответственно нам подходят цифры 1 и 8. Дальше уже два пути в зависимости от того какую цифру выберем.

1.1) выбираем цифру 1.
17*183= 3111 Чтобы вместо 3 получить 0 или 1 надо 17 умножить на такую цифру, чтобы в результате произведение оканчивалось на 7 или на 8. Соответственно нам подходят цифры 1 и 4. Дальше уже два пути в зависимости от того какую цифру выберем. и т.д. будет ветвиться до тех пор пока в каждой ветви не найдется число удовлетворяющее значению ну или пока не зациклится.

Это дерево бесконечно т.к. любую ветвь можно зациклить и выйти из цикла в любой момент, например 6535353535353535353 * 17 = 111101010101010101001
Еще можно взять 653 добавить 00 и снова написать 653 получим 65300653 *17 = 1110111101, и так с каждым полученным числом.
В итоге мы будем иметь иметь бесконечно много чисел которые при умножение на 17 дадут результат состоящий из 0 и 1, ниже некоторые примеры.

653 * 17 = 11101
65300653 * 17 = 1110111101

6530065300653 * 17 = 111011110111101
653006535353 *17 = 11101111101001
5882353 * 17 = 100000001
5883 *17 = 100011
6477124183 * 17 = 110111111111

Изменено 29 сентября, 2017 пользователем Никита Гайнанов

[Kapral]

Ну что - надумали?

Без перебора все равно не получается

17*3=51

Одна единица есть и остается нивелировать 5ку, допустим 17*50=850

53*17=901, 2 крайние правые позиции 01 удовлетворяют условию задачи

теперь надо привести 9 к 0 или 1

попытаемся опять умножить на 3 (9+1=10) для получения 0 в сотнях

353*17=6001, приводим 6 к 0/1, в разряде тысяч

Для этого надо умножить, допустим умножаем на 2000

2353*17=40001, приводим 4 к 0/1

82353*17=140001, опять таки 4 к 0/1,

все уперлись в начало перебора - начинаем перебирать, на что еще можно умножить 17 что бы получить 0/1 в разряде 10 тысяч

 

Тут вычисления мы делали параллельно с @Никита Гайнанов,

 

Но @Никита Гайнанов, я бы хотел заметить что твои пункты 1.1 и 1.2 это уже перебор

 

Тут надо менять условие, например снять из условий перебор , например вообще условие любого перебора, например оставить условие "обратного перебора", (т.е. перебор подходящих под одно, формальное условие ответов и проверять соответсвие другим условиям), например как в №274, я проверял 101, 111, 1101 на условие делимости на 17

 

А вот как постом выше или в этом "прямой перебор" можно и оставить.

[E.K.]

Деление на 17: признаки делимости => "модуль суммы числа десятков и числа двенадцать умноженной на кол-во единиц делится на 17".

 

17*?? = {1,0}много раз, но заканчивается на 1

 

НЧ = 10*х + 1

 

Множитель '??' заканчивается на тройку (чтобы умножение получило 1 на хвосте), то есть:

 

10*x + 1 = 17*(10*a + 3) = 170*a + 51

10*x = 170*a + 50

x = 17*a + 5

 

Напоминаю, что 'x' состоит только из 0 и 1. Ну, пусть оно заканчивается на 0.

(здесь можно пойти по параллельной ветке "заканчивается на 1")

 

x = 10*x₁

 

Тогда 'a' как-бы оканчивается на '5' ->

 

a = 10*a₁ + 5

10*x₁ = 17*(10*a₁ + 5) + 5 = 170*a₁ + 90

x₁ = 17*a₁ + 9

 

А пусть этот "икс-один" будет не просто набором единиц и нулей, а тупо "10...0".

(это для упрощения, здесь тоже можно пойти по параллельным веткам...)

 

Тогда ->

 

17*a₁ = 9...91

 

Эти девятки с единицой в хвосте делятся на 17. Ага... Но поскольку "признак делимости на 17", то есть такое 'y', что ->

 

9...9 + 12 = 17*y

10...011 = 17*y (здесь уже можно подбирать подходящее количество нулей вместо точек)

 

Делимость на 17 =>

 

10...01 + 12 = 17*z

10...013 = 17*z

10...01 + 36 (36 = 17*2 + 2) =>

10...01 + 2 = 17*что-то

10...03 = 17*что-то

10..0 + 36 (то есть 2) = 17*еще что-то

10..0 + 2 = 17*k

 

То бишь, k = чётное.

50..01 = 17*k/2

 

Ну, пусть будет "51" вообще без нулей. Откручиваем обратно снизу наверх по всем этим формулам...

51 -> 102 -> 10013 -> 100011

 

Засовываем в калькулятор: 100011 / 17 = 5883

Ура!

 

Можно попробовать пройтись по параллельным веткам.

 

Вот так получается, без перебора.

[E.K.]

Ладно, по просьбам радиослушателей усложняю задачку.

 

Для всех чисел от 01 до 99 доказать (или опровергнуть), что существует другое натуральное число, произведение с которым в 10-ной системе счисления состоит только из единиц и нулей.

 

'??' * Y = {1,0, ...}

 

'??' = любое от 01 до 99.

Y = некоторое натуральное

{1,0, ...} = единицы и нули в 10-ной записи.