Проверьте три задачи.

[ZARATUSTRA]

Что не так в решении?

1. Докажите, что любое число рублей, большее семи, можно разменять 3 и 5 рублями.

Решение:
Пусть $3 - a_1, 5 - a_2$. 3 рублями можно разменять каждое 3 число. Нам остаётся доказать, что мы можем разменять сумму типа $3\cdot{n}+1$ и $3\cdot{n}+2$. Найдём связь между этими требованиями и $a_1, a_2$. Получаются формулы:
$a_1\cdot n - (a_1\cdot(n-2)+a_2)=1$
$a_1\cdot n-(a_1\cdot(n-4)+2\cdot a_2)=2$
Пусть $T_x = 3\cdot{n}$, тогда $T_{x-1} = a_1\cdot(n-2)+a_2$, $T_{x-2}= a_1\cdot(n-4)+2\cdot a_2$
У каждого $T_x, T_{x-1}, T_{x-2}$ период $3$, что и покрывает все числа.

2. Для любого натурального $k$ докажите неравенство $2^k > k$.
Решение:
$(1+1)_1...(1+1)_k > 1_1+...1_k$
3.Четыре одинаковые банки наполнены красками на три четверти. Цвета всех красок различны. Имеется возможность переливать любую часть жидкости из одной банки в другу. Можно ли во всех банках сделать одинаковую смесь?(Другой посуды нет, выливать краску нельзя).
Решение:
Только на словах знаю как объяснить. Разделим четыре банки на две группы по 2 банки.
Первая группа: из первой банки перельем в другую банку, а затем из второй в первую. Смесь в них будет одинаковая.
Вторая группа: аналогично.
Теперь из первой группы проделаем аналогичную операцию с банкой из второй группы. С оставшимися 2 банками проделаем аналогичную операцию.

[Nemiroff]

Простите, но первая слишком усложнена, а что у вас написано во второй и третьей, я не понял.

[ZARATUSTRA]

Nemiroff в сообщении #584889 писал(а):

Простите, но первая слишком усложнена, а что у вас написано во второй и третьей, я не понял.

Ну я пока только учусь доказывать, ибо с этим совсем туго.
Во второй идея в том, что слева единиц больше, чем справа.
А третья по мотивам этой задачи, которая довольна известная:

Есть два одинаковых стакана, в которые налито поровну: в один — молоко, в другой — кофе. Из первого стакана переливают ложку молока в стакан с кофе. Потом размешивают, и из второго стакана обратно в первый переливают ложку кофе с молоком. Чего теперь больше: молока в кофе или кофе в молоке?

[Nemiroff]

Ну в первой можно доказать, что 8, 9 и 10 можно получить. Далее вроде бы очевидно.
Вторую хоть даже по индукции, там просто совсем.

Ну третья да, что-то такое, я просто не понял ваше решение.

[ewert]

ZARATUSTRA в сообщении #584891 писал(а):

Во второй идея в том, что слева единиц больше, чем справа.

Не нужно никаких идей -- доказывайте тупо по индукции.

[Asker Tasker]

Во второй самый простой (как мне кажется) вариант - метод мат. индукции.
1) $k=1 \rightarrow 2^{1}>1$
2) Предположим, что неравенство верно при $k=n : 2^{n}>n$
3) Докажите, что и при k = n + 1 неравенство выполняется.
Этот вариант в каком-то смысле тоже основан на том, что слева единиц больше, чем справа. Только строго это доказывает.

В первой мне вариант Nemiroff'а очень нравится. Я бы так решал: рассмотрим натуральные, большие трёх. Они представимы в одном из трёх видов:
$n = 3k$ - можно разменять только тройками
$n = 3k + 1$
$n = 3k + 2$
Если Вы докажете, что последние два числа можно представить в виде 10+3l или 8 + 3l соответственно, то и эти числа тоже можно будет разменять так, как нужно.

Третью, если честно, не очень понял. "Одинаковая смесь" - то есть поровну красок разного цвета или как?

P.S. Если задача о кофе с молоком известная, расскажите, пожалуйста решение - я её раньше не встречал.

[ewert]

ZARATUSTRA в сообщении #584886 писал(а):

Первая группа: из первой банки перельем в другую банку, а затем из второй в первую. Смесь в них будет одинаковая.

Не будет. Если концентрация "своего" цвета в каждой банке больше, чем "чужого", то так оно и будет оставаться после каждого переливания. Кроме случая, когда одну из банок удастся опустошить полностью. Поэтому попарными переливаниями ничего не добьёшься -- надо задействовать все банки сразу.

Например, так. Заполнить доверху первую банку из второй, а четвёртую -- из третьей. Теперь вторая и третьи банки заполнены наполовину, поэтому их цвета можно выровнять. Равенство сохранится, если теперь отлить из первой банки по четверти во вторую и в третью, и из четвёртой -- тоже. После этого можно будет выровнять содержимое первой и четвёртой банок. Дальше -- аналогично.

[ZARATUSTRA]

Asker Tasker в сообщении #584912 писал(а):

Во второй самый простой (как мне кажется) вариант - метод мат. индукции.
1) $k=1 \rightarrow 2^{1}>1$
2) Предположим, что неравенство верно при $k=n : 2^{n}>n$
3) Докажите, что и при k = n + 1 неравенство выполняется.
Этот вариант в каком-то смысле тоже основан на том, что слева единиц больше, чем справа. Только строго это доказывает.

В первой мне вариант Nemiroff'а очень нравится. Я бы так решал: рассмотрим натуральные, большие трёх. Они представимы в одном из трёх видов:
$n = 3k$ - можно разменять только тройками
$n = 3k + 1$
$n = 3k + 2$
Если Вы докажете, что последние два числа можно представить в виде 10+3l или 8 + 3l соответственно, то и эти числа тоже можно будет разменять так, как нужно.

Третью, если честно, не очень понял. "Одинаковая смесь" - то есть поровну красок разного цвета или как?

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

2) функция $2^k$ - где $k$ натуральное - постоянно возрастающая
скорость возрастания левой части неравенства $2^k>k$ больше, чем второй на всём интервале натуральных чисел

[Asker Tasker]

Ну, тогда во второй надо доказать, что функция $y(x) = 2^{x}-x$ строго возрастает при $x\geq 1$. По-моему, вариант с индукцией проще.

[ZARATUSTRA]

Asker Tasker в сообщении #584933 писал(а):

Ну, тогда во второй надо доказать, что функция $y(x) = 2^{x}-x$ строго возрастает при $x\geq 1$. По-моему, вариант с индукцией проще.

Можете написать понятное доказательство с помощью мат. индукции?
Я пока доказываю как умею)

[Asker Tasker]

На этом форуме, помнится, нельзя давать решения. Третью задачу я всё равно не понял, как решать. А в первой, думаю, один из правильных вариантов такой:
1) отметим, что "сумму можно разменять 3-мя и 5-ью рублями" означает, что данное натуральное число n (по условию большее семи) можно представить в виде $n = 3a + 5b$, где а и b - какие-то неотрицательные числа.
2) числа 8, 9, 10, очевидно так представить можно
3) Пусть n>7 - произвольное. Если n делится на три, всё понятно. Если n не делится на три, то даёт в остатке 1 или 2. Пусть, например, 1. Тогда $n = 3k + 1$. Если Вы докажете, что число n представимо в виде $8 + 3l$ или $10 + 3l$, то оно представимо так, как нам нужно.
То есть Вам нужно подумать, какое из двух равенств обязательно будет иметь место и доказать это:
$3k + 1 = 8 + 3l$
$3k + 1 = 10 + 3l$

-- 14.06.2012, 14:45 --

Вы знаете, что такое метод мат. индукции?
Если нет, то расскажу. Если да, то опишите его.

[ZARATUSTRA]

Asker Tasker в сообщении #584939 писал(а):

На этом форуме, помнится, нельзя давать решения. Третью задачу я всё равно не понял, как решать. А в первой, думаю, один из правильных вариантов такой:
1) отметим, что "сумму можно разменять 3-мя и 5-ью рублями" означает, что данное натуральное число n (по условию большее семи) можно представить в виде $n = 3a + 5b$, где а и b - какие-то неотрицательные числа.
2) числа 8, 9, 10, очевидно так представить можно
3) Пусть n>7 - произвольное. Если n делится на три, всё понятно. Если n не делится на три, то даёт в остатке 1 или 2. Пусть, например, 1. Тогда $n = 3k + 1$. Если Вы докажете, что число n представимо в виде $8 + 3l$ или $10 + 3l$, то оно представимо так, как нам нужно.
То есть Вам нужно подумать, какое из двух равенств обязательно будет иметь место и доказать это:
$3k + 1 = 8 + 3l$
$3k + 1 = 10 + 3l$

-- 14.06.2012, 14:45 --

Вы знаете, что такое метод мат. индукции?
Если нет, то расскажу. Если да, то опишите его.

Я создавал тему в олимпиадных задачах, ибо они из сборника олимпиадных задач. А в разделе олимпиадных задач решение давать можно.
Мат. индукция: ну например нужно показать, что правильно при n=1, а затем доказать, что при $n+1$.
3 задачу я понял как решать, а 1 я сам решил правильно вроде как.

[Asker Tasker]

Правильно. Но могут придраться.
А при доказательства через индукция придраться не к чему.
Схему доказательства я расписал.
А суть метода в общем случае вот в чём: доказать, что какое-то утверждение верно для единицы. Доказать, что из предположения "справедливость утверждения доказана для числа n" следует, что и для числа n+1 оно также верно.
Докажите, что из неравенства $2^{n} > n$ следует, что $2^{n+1} > n+1$ и тем самым будет завершено доказательство по индукции. Строгое и, если не писать к нему комментарии, предельно короткое.

Со второй задачей разобрались?

P.S.
Если решили третью, расскажите - интересно.

[ewert]

Asker Tasker в сообщении #584946 писал(а):

Если решили третью, расскажите - интересно.

сообщение #584915"]

[ZARATUSTRA]

Asker Tasker в сообщении #584946 писал(а):

Правильно. Но могут придраться.
А при доказательства через индукция придраться не к чему.
Схему доказательства я расписал.
А суть метода в общем случае вот в чём: доказать, что какое-то утверждение верно для единицы. Доказать, что из предположения "справедливость утверждения доказана для числа n" следует, что и для числа n+1 оно также верно.
Докажите, что из неравенства $2^{n} > n$ следует, что $2^{n+1} > n+1$ и тем самым будет завершено доказательство по индукции. Строгое и, если не писать к нему комментарии, предельно короткое.

Со второй задачей разобрались?

P.S.
Если решили третью, расскажите - интересно.

Выше уже привели решение на 3.
$2^{n+1}=2\cdot2^n$, $2\cdot2^2>1+n$ А дальше?