Пятничные задачки. 6 августа 2004

← →
Думкин © (2004-08-06 08:01) [0]

MBo в отпуске - пусть отдохнет, а мы в пятнице - порешаем?
1. В гостиницу приехал путешественник. Денег он не имел, а обладал лишь серебряной цепочкой, состоящей из шести звеньев. За каждый день пребывания в гостинице он расплачивался одним звеном цепочки, при этом хозяин предупредил, что согласен взять не более одного распиленного звена.
Как путешественнику распилить цепочку, чтобы прожить в гостинице шесть дней и ежедневно расплачиваться с хозяином.
2. Какое наименьшее число звеньев пришлось бы распилить, если бы путешественник жил в гостинице 100 дней и имел цепочку из 100 звеньев? Каков ответ в общем случае(n дней n звеньев)? Предполагается, что хозяин согласен принять любое число звеньев.
3. В десятичной дроби
0,12345678910111213…..
выписаны подряд все натуральные числа. Доказать, что эта дробь не периодическая.
4. На 44 деревьях, посаженных по окружности, сидели 44 веселых чижа (на каждом дереве по одному). Время от времени какие-то 2 чижа одновременно перелетают на соседние деревья в противоположных направлениях (один – по часовой стрелке, другой - против). Смогут ли чижи когда-нибудь собраться на одном дереве?
5. Докажите, что из любых ста целых чисел можно выбрать одно или несколько так, чтобы сумма их оканчивалась двумя нулями.
6. Из чисел 1,2,3…200 произвольно выбрали 101 число. Доказать, что среди выбранных чисел всегда найдутся два таких числа, из которых одно делиться на другое.
7. Среди чисел, все цифры которых единицы, найти наименьшее, делящееся на число 33..33, составленное из 100 троек.
8. В окружность радиуса 1 вписан правильный десятиугольник. Найти сумму квадратов расстояний от произвольной точки окружности до всех вершин этого десятиугольника.
9. Обозначим через n?(n вопросиал) произведение всех простых чисел, не превосходящих n.(n>=2). Найдите все значения n, для которых n?<=n.

← →
afn © (2004-08-06 08:36) [1]

пилим 3-е звено
1 д - распиленное
2 д - 2 связанных целых
3 д - 3 связанных целых
4 д - как день 2 +распиленное
5д - 3целых +2 целых
6д - отдаем все

← →
afn © (2004-08-06 08:38) [2]

7 распилов. Вроде так

← →
Думкин © (2004-08-06 08:39) [3]

> [1] afn © (06.08.04 08:36)

1. Нет

← →
Думкин © (2004-08-06 08:43) [4]

> [1] afn © (06.08.04 08:36)

И приводи все совместные действия. А то у тебя за 3 дня 6 колец ушло.

← →
Чухонский © (2004-08-06 08:49) [5]

>3.

Допустим, что она периодическая. Пусть цепочка периодичности (или как там она называется) длинной n. Но в ней должно быть натуральное число 10 в степени n, длинна которого n+1.
Противоречие налицо.

← →
afn © (2004-08-06 08:51) [6]

Понял.
Пилим 3 звено.

1д - отдаем распиленное (р)
2д - забираем р отдаем 2 связанных (с)
3д - отдаем р
4д - забираем 2 с отдаем 3 с
5д - забираем р
6д - отдаем р

Насчет 100 колец вроде ошибка

← →
Думкин © (2004-08-06 08:52) [7]

> [5] Чухонский © (06.08.04 08:49)
А оно что в периоде? В чем противоречие?

← →
Чухонский © (2004-08-06 08:53) [8]

2afn © (06.08.04 08:51) [6]
с пятым днём неувязка

>1
наверно так
1д - отдаем распиленое
2д - отдаём двойное и забираем распиленное
3д - отдаем распиленое
4д - отдаем тройное и забираем двойное
5д - отдаем двойное и забираем распиленное
6д - отдаем распиленное

← →
Думкин © (2004-08-06 08:53) [9]

> [6] afn © (06.08.04 08:51)
То есть за 2 дня мы заплатили одно звено? И...акуратнее. Нет.

← →
Думкин © (2004-08-06 08:54) [10]

> [2] afn © (06.08.04 08:38)
> 7 распилов. Вроде так

Нет

← →
afn © (2004-08-06 08:54) [11]

Там просто описка :) (была)

← →
Думкин © (2004-08-06 08:55) [12]

> [8] Чухонский © (06.08.04 08:53)

Нет

← →
afn © (2004-08-06 08:57) [13]

> [9] Думкин © (06.08.04 08:53)

Не понял. На 2-ой день мы заьрали распиленное и отдали 2 связанных

OOO<>OO

<> - распиленное

← →
Чухонский © (2004-08-06 08:57) [14]

2Думкин © (06.08.04 08:55) [12]

Как это нет? :) Да.
Если нет, поясни, пожалуйста, в чём ошибка?

← →
Думкин © (2004-08-06 08:58) [15]

> [8] Чухонский © (06.08.04 08:53)
> [11] afn © (06.08.04 08:54)

Да. Старость не радость. Извиняюсь.

← →
Чухонский © (2004-08-06 09:00) [16]

2Думкин © (06.08.04 08:52) [7]
>А оно что в периоде? В чем противоречие?

Я передполагаю, что оно в периоде с периодом длинной n.
А противоречие в том, что натуральное число "10 в степени n"
в этот период никак не влезет.

← →
Думкин © (2004-08-06 09:01) [17]

> [13] afn © (06.08.04 08:57)
> [14] Чухонский © (06.08.04 08:57)

Все верно. Задача №1 решена.

← →
Думкин © (2004-08-06 09:01) [18]

> [16] Чухонский © (06.08.04 09:00)

Ну период заканчивается на середке. Почему нет?

← →
Чухонский © (2004-08-06 09:04) [19]

2Думкин © (06.08.04 09:01) [18]
А до него ещё n девяток идёт. :)
Получим, что в длинну 2n+1 должен входить один период
полностью, но там только цифры 019

← →
Думкин © (2004-08-06 09:07) [20]

> [19] Чухонский © (06.08.04 09:04)

Так лучше. Задача №3 решена.

← →
afn © (2004-08-06 09:23) [21]

2> для 100 звеньев вроде получается 5 распилов.

← →
Думкин © (2004-08-06 09:28) [22]

> [21] afn © (06.08.04 09:23)

Нет.

← →
afn © (2004-08-06 10:03) [23]

2>
Действительно обошелся 4-мя звеньями. Только не говори, что неправильно. Не получается обобщить, пока вот что:
(x+1)*2^(x+1)-1>n
ответ - min x из этого условия.

← →
Думкин © (2004-08-06 10:07) [24]

> [23] afn © (06.08.04 10:03)

2. Да. Задача №2 решена.

← →
clickmaker © (2004-08-06 11:17) [25]

> 5. Докажите, что из любых ста целых чисел можно выбрать
> одно или несколько так, чтобы сумма их оканчивалась двумя
> нулями.

Берем наименьшее - единицу. 1 * 100 = 100, 2 нуля налицо

← →
Думкин © (2004-08-06 11:19) [26]

> [25] clickmaker © (06.08.04 11:17)

:))) Смешно.

← →
pasha_golub © (2004-08-06 11:28) [27]

2Думкин

Посты про решенные задачи лучше бы жирным выделять.

← →
Думкин © (2004-08-06 11:33) [28]

Хорошо.
Решено №1,2,3.
Ответы в постах:
[6],[8] - №1
[23] -№2
[19] - №3

> 7. Среди чисел, все цифры которых единицы, найти наименьшее,
> делящееся на число 33..33, составленное из 100 троек

Число составленное из 300 единиц

Попробую доказать 5-ое утверждение.
Поскольку оно довольно-таки длиннотекстовое (хоть и не сложное), то я не буду доказывать очевидные утверждения. Если утверждение, объявленное мной очевидным, таковым вам не кажется, укажите на него, я докажу его явно.
Итак

очевидно, что задачка будет верна в том случае, если верно утверждение
1)
"из любых 10 целых чисел можно выбрать одно или несколько так, чтобы сумма их оканчивалась нулем, т.е. была кратна 10"

которое в свою очередь верно, если верно следующее:
2)
"из любых чисел 10 чисел от 1 до 9 можно выбрать одно или несколько так, чтобы сумма их оканчивалась нулем, т.е. была кратна 10."

Доказательство сводится к следующему: берем произвольное число из этих десяти. Обозначим его через X. Тогда утверждение будет верным, если из оставшихся 9-ти можно взять сумму, которая оканчивается цифрой Y=10-X. Поскольку X может быть любым, то и Y тоже может быть любым
Возьмем из этих произвольно выбранных десяти цифр любые две (они могут быть и одинаковыми, кстати):A и B.

1)
A+B=xC, где xC- некое число, заканчивающееся на С. Очевидно, что С<>A, поскольку если С=А, то B=xA-A =x0, а это противоречит условию, что все числа - от 1 до 9.
Итак, использавав два числа из десяти мы гарантированно можем получить суммы, которые заканчиваются на две разных цифры A или С.
2)
Возьмем сумму
xC+D=xE, где D -одно из оставшихся чисел (возможно, равное А или В); xС=A+B

E<>C, E<>D (аналогично см. выше). Если E=A(или любому другому числу, входящему в сумму xC), то исключив А из этой суммы и прибавив D, мы получим число кратное 10, что и требовалось доказать.
Если же E<>A, то получаем
из трех чисел A, B, D мы можем получить суммы, оканчивающиеся на 3 разные цыфры :А, С, E.

Аналогично рассуждая, можно показать, что
из 4 любых чисел можно получить суммы с 4-мя разными цифрами на конце
из 5 любых чисел можно получить суммы с 5-мя разными цифрами на конце и т. д...
из 10 любых чисел всегда можно выбрать сумму, которая будет заканчиваться на любую из 10 цифр, среди которых, будет и 0 (ну или сумма, заканчивающаяся на 0 попадется еще до того, как использованы все 10 чисел).
Утверждение доказано.
Хух. Сумбурно конечно. Может можно элегантнее?

> [31] Bless © (06.08.04 11:47)
> из 4 любых чисел можно получить суммы с 4-мя разными цифрами на конце

Например: 25,35,45,65. Последние цифры 0 и 5. Иля я что-то не допонимаю, написано действительно тяжело. Решение действительно элгантное.

> [26] Думкин © (06.08.04 11:19)
> > [25] clickmaker © (06.08.04 11:17)
>
> :))) Смешно.

> 5.
Можно и посерьезней. Рассмотрим 100 сумм:
s1 = x1, s2 = x1 + x2, ... s100 = x1 + ... + x100.
Допустим, что ни одна из сумм на 100 не делится. Тогда имеем 2 одинаковых остатка, посколько сумм 100, а остатков от деления на 100 - 99. Пусть это будут Sm и Sn, причем m > n
Поскольку Sm-Sn делится на 100, то раскрыв его получаем (X1 + ... Xm) - (X1 + ... Xn) = Xn+1 + Xm - это и есть нужная сумма

>Например: 25,35,45,65. Последние цифры 0 и 5.

из 10 любых чисел всегда можно выбрать сумму, которая будет заканчиваться на любую из 10 цифр, среди которых, будет и 0 (ну или сумма, заканчивающаяся на 0 попадется еще до того, как использованы все 10 чисел).

фраза в скобках применима для любого количества цифр (не только для 10). Просто, чтобы не загромождать и без того громоздкое доказательство, я вынес ее только для 10.
Эта оговорка имеет место, если при суммировании очередного числа получется результат, который оканчивается на цифру, на которую оканчивается одна из слагаемых прежней суммы, что имеет место в вашем примере и оговорено у меня

"...Если E=A(или любому другому числу, входящему в сумму xC), то исключив А из этой суммы и прибавив D, мы получим число кратное 10, что и требовалось доказать.
Если же E<>A..."

Вот если вы приведете пример четырех чисел, из которых нельзя составить сумму, кратную 10 и из которых я не смогу составить четыре суммы с разными последними цифрами, то мое доказательство неверно.

> [33] clickmaker © (06.08.04 12:06)
> > 5.

Да. Верно.

> [34] Bless © (06.08.04 12:06)
> из 10 любых чисел всегда можно выбрать сумму, которая будет
> заканчиваться на любую из 10 цифр, среди которых, будет
> и 0 (ну или сумма, заканчивающаяся на 0 попадется еще до
> того, как использованы все 10 чисел).

Это верно, просто доказательство надо посмотреть, я пока в нем путаюсь, тяжело написано. Я к тому что есть отдельно стоящая фраза:
из 4 любых чисел можно получить суммы с 4-мя разными цифрами на конце
А она отличается от:
> Вот если вы приведете пример четырех чисел, из которых нельзя составить сумму, кратную 10 и из которых я не смогу составить четыре суммы с разными последними цифрами, то мое доказательство неверно.

Поэтому я не отрицаю, но попозже постараюсь разобраться в вашем тексте более тщательно.

Да забыл.

> > [33] clickmaker © (06.08.04 12:06)
> > > 5.
> Да. Верно.

Возможно и > [31] Bless © (06.08.04 11:47) верно.

Надо вникнуть, пока не успеваю.

4. Не смогут.
Назовем деревья с номерами 1, 3, 5, 7, ... 43 нечетными, а остальные - четными, и соответственно назовем чижей. При перелетах четный чиж, становится нечетным, и наоборот. Имеем инвариант - число четных чижей. (да и число нечетных чижей тоже, но это неважно :). Исходно четных 22, и изменить не получится, а для слета на одно дерево надо либо 0 четных, либо 44.
Кстати, на 2 дерева собрать получится, по 22 на каждом, можно даже на соседние. А потом чижи будут друг к другу прыгать :)

> попозже постараюсь разобраться в вашем тексте более тщательно.

Да оно того не стоит, по-моему. Задачка ведь решена (красиво) Clickmaster-oм. Я ж не за значок решаю, а так, для себя :)

Пятничные задачки. 6 августа 2004 Найти похожие ветки