7 дек. 2009 г.

И так можно

Совершенно понятная и очень правильная мысль иногда мешает. Например, некоторые ученики часто пытаются одолеть задачу не новым подходом (которому посвящён урок), а своими старыми умениями. При этом каждый из них говорит: «Не хочу вникать в новую тему, потому что я и так эту задачу смогу решить». В самом деле, если ответ правильный, то какая разница, как именно решать?

Но разница есть: ученики, освоившие новый метод, справляются с каждой задачкой за 3-5 минут, постепенно переходя от простых упражнений к тяжёлым. А наш упорный любитель старых методов на каждую из простых задач тратит по 20-30 минут и несколько тетрадных листов. Поэтому до средних и сложных упражнений он вообще не добирается. И из-за этого он даже не понимает, что его желание доказать ненужность нового подхода не позволяет ему увидеть те сложности, которые невозможно одолеть старыми методами.

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

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

Приведу классическую задачку, на примере которой данный эффект хорошо виден:

Кубок по футболу разыгрывается по олимпийской системе; ничьих не бывает, к следующему туру допускается только победившая команда, проигравшая же выбывает из розыгрыша. Для завоевания кубка команда должна только побеждать (нельзя проигрывать). На участие в розыгрыше кубка поданы заявки от 16389 команд. Сколько матчей будет сыграно, пока определится обладатель кубка? (Не путать число матчей с числом туров!)

Мы тут часто решаем забавные математические задачки с подвохом, но сегодня не тот случай. Это простая постановка, в которой никто никого не собирается обманывать :)

Я предлагаю сделать сейчас небольшую паузу и найти свой собственный ответ на эту задачу.






Итак, поздравляю с успешным решением задачи. Да, она простая, но всеми силами приглашает решить себя сложным путём.

Сначала расскажу сложный путь:
- в финале играют две команды - это один матч,
- в двух полуфиналах играют две пары команд - это два матча,
- в четырёх четвертьфиналах играет четыре пары команд - это ещё четыре матча,

И так далее. Честно выписываем эти степени двойки, пока не доходим до строчки
- в 8192-ти 8192-финалах играет 16384 команд - это ещё 8192 матча.

Что делать дальше? У нас участвует 16389 команд, а мы придумали как устроить игру для 16384 команд. Куда деть ещё пять? Можно выбрать для них случайно пятерых соперников, чтобы они за дополнительные пять игр установили, кто из них лучше.

Выходит, наш ответ такой: 1+2+4+8+16+32+...+8192+5.

Это Длинно? Да, длинно! Скучно? Конечно, очень скучно!

Тем, кто решил задачку подобным образом, я предлагаю прерваться на несколько минут, потому что есть очень простое и короткое рассуждение. Оно не позволяет наделать ошибок в таком большом суммировании, не требует воображения, чтобы определиться с тем, куда деть «лишние пять команд»... Оно короткое и изящное.






Если вы это читаете, значит уже нашли быстрое решение, а сейчас хотите узнать, бывает ли ещё быстрее. Или пока не нашли, но узнать уже хочется - тоже понятное желание. Итак, в результате каждого матча одна из команд выбывает, а нам надо определить, сколько пройдёт матчей до того, как останется всего одна команда. Раз команд изначально 16389, значит надо, чтобы выбыли 16388 из них, чтобы осталась ровно одна. Это значит, что требуется 16388 матчей. Всё! :)

Данная задачка была опубликована, например, в книге «Смотри в корень!» Петра Маковецкого. Саму книгу я уверенно рекомендую для чтения школьникам и их родителям, так как в ней приводятся интересные постановки проблем, совместное обсуждение которых открывает глаза на интересные моменты в устройстве нашего мира. Увы, её давно не переиздавали, поэтому остаётся только читать в интернете (или на электронной читалке).

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

Хорошей недели!

50 комментариев:

  1. Анонимный07.12.2009, 22:09

    Простенькое с модулями:

    |x - 4| + |x - 9| = 5.

    Длинное решение - рассматривать промежутки и честно раскрывать модули.
    Короткое - осознать, что |x - 4| - это расстояние от точки x до точки 4, посмотреть внимательно на числа в примере и получить решение сразу.

    ОтветитьУдалить
  2. Дано: 16389 команд

    матчей - остаток команд
    8194 - 8195
    4097 - 4098
    2049 - 2049
    1024 - 1025
    512 - 513
    256 - 257
    128 - 129
    64 - 65
    32 - 33
    16 - 17
    8 - 9
    4 - 5
    2 - 3
    1 - 2
    1 - 1

    16388 матчей

    Просто, но совсем не элегантно

    ОтветитьУдалить
  3. Есть массив из миллиона чисел, в котором записаны числа от 1 до 1000001. Числа расположены в произвольном порядке (случайно перемешаны). Одно из чисел пропущено. Какое?

    ОтветитьУдалить
  4. Анонимный08.12.2009, 00:01

    > Есть массив из миллиона чисел...

    sum(1..1000001) - sum(array)

    ОтветитьУдалить
  5. Есть шикарная задачка такого же типа.

    От А до Б 60 километров. Велосипедист выезжает из А в Б со скоростью 20 км/ч. Навстречу ему со скоростью 30 км/ч. вылетает муха. Муха летит навстречу велосипедисту, разворачивается, летит в точку Б, разворачивается, и так пока велосипедист не доедет до Б. Вопрос - какое расстояние пролетит муха?

    Решать через ряды очень сложно и муторно, простой ответ - велосипедист ехал 3 часа, значит муха тоже летала 3 часа, итого - 90 км.

    ОтветитьУдалить
  6. Видел задачу полностью аналогичную этой в книге "Как сдвинуть гору Фудзи" Уильяма Паундстоуна. Но там описывался реальный исторический пример, как такую задачу задали на собеседовании на работу во второй половине 20 века. Очень рекомендую и книгу полностью и эту историю в частности.

    ОтветитьУдалить
  7. Огромное Вам спасибо за блог! Это, наверное, единственный блог в моем ридере, обновлений которого ждешь каждый день. И один из очень не многих, которые интересно прочитать не глупому человеку (не увлекающимся "пиво-сиськи-ггг" стилем жизни).

    ОтветитьУдалить
  8. В данной конкретной задачи простое решение мне в голову пришло раньше сложного, но в целом идея понятно.

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

    ОтветитьУдалить
  9. В 8 классе учитель математики давала устную задачку.
    Есть бревно. Нужно разрезать его на 12 частей. Сколько распилов необходимо сделать ???
    Формула решения простая: Число распилов - на единицу меньше количества необходимых частей, но многие пытаются решить эту задачу на пальцах... пальцев естественно не хватает...

    ОтветитьУдалить
  10. Сложный путь с извращенными упрощениями вычислений:
    Туров: N=ceil(ln(16389)/ln(2))=15
    Матчей в заполненном туре: q(n)=2^n
    Матчей в заполненном турнире: Q(N)=\sum_{i=0}^{N-1}(2^i)=2^N-1
    Матчей всего: Z(N)=Z(15)=Q(14)+5=16383+5

    О простом догадался только когда ответ получил.

    ОтветитьУдалить
  11. Овчаренко Дмитрий, а если сложить уже распиленые куски стопочной и пилить одним распилом? Тогда их понадобится всего 4 :)

    ОтветитьУдалить
  12. упростить выражение
    sin(alpha)*sin(beta)*...*sin(omega)
    где в скобках все буквы греческого алфавита

    ОтветитьУдалить
  13. а в задаче про бревно, если можно перекладывать части, то можно обойтись одним распилом. один человек пилит а второй быстренько подкладывает всё новые куски под пилу.

    ОтветитьУдалить
  14. Анонимный08.12.2009, 12:46

    Таких задач много. Достаточно взять задачи какой-нибудь олимпиады по математике старших классов. К примеру, в этом году была хорошая задача: сколько корней имеет уравнение sin[x] = {x} на промежутке от -2009 до 2010? [x] - целая часть, {x} - дробная.

    ОтветитьУдалить
  15. Действительно. Если внимательно вчитаться в постановку задачи, то приходит простое решение )
    Спасибо!

    ОтветитьУдалить
  16. "...Мы тут часто решаем забавные математические задачки с подвохом, но сегодня не тот случай..."

    Решайте эту задачку простым способом, а для затравки вам - картинка, и посмотрим, скольких из вас эта картинка направит по сложному пути..-)

    ОтветитьУдалить
  17. Анонимный08.12.2009, 14:30

    В вершинах квадрата ABCD со стороной 1 метр находятся 4 жука. В некоторый момент все они начинают движение со скоростью 1см/с и движутся таким образом, что в каждый момент времени скорость жука A направлена строго на жука B, скорость жука B - на жука С, скорость жука C - на жука D и скорость жука D - на жука A.
    Понятно, что через некоторое время жуки окажутся в центре квадрата.
    Найти время, которое пройдет к этому моменту и расстояние, которое они проползут.

    Если подходить "по-честному", то придется решать дифференциальное уравнение, а потом интегрировать по длине получившейся кривой...
    Но можно проще.

    ОтветитьУдалить
  18. eyeless-watcher, AAbrosov, avsmal и уважаемый аноним, спасибо, что напомнили интересные задачки!

    NutipA, спасибо за рекомендацию книги.

    iZombie, благодарю за тёплые слова! :)

    abyrvalg, опыт показывает, что очень многие сами рисуют подобную иллюстрацию через 30 секунд после прочтения условия :)

    ОтветитьУдалить
  19. iZombie
    Пиво - полезно для здоровья.
    ггг - смех продлевает жизнь.
    что вы имеете против сисек - вообще как то не ясно...

    ОтветитьУдалить
  20. Помнится, была классе в восьмом-девятом на уроках физики задачка:
    Есть велосипед, есть количество зубьев на передней и задней звёздочках, есть радиус колеса. Найти расстояние, которое проезжает велосидед за один оборот педалей.

    Пятёрки ставили за сложные решения: замуты с линейными/угловыми скоростями звёздочек, линейной скоростью цепи и пр.

    За простые решения - передадочное отношение помноженное на длину окружности колеса, получали втык :S

    ОтветитьУдалить
  21. Как правильно сказал NutipA, эта задачка описана в "Как сдвинуть гору Фудзи". Согласно книге эту задачку задаdfл Уильям Шокли на интервью, набирая людей в Shockley Semiconductor в конце пятидесятых.

    Книга оставляет смешанное впечатление, но для расширения кругозора пролистать стоит. Заставила задуматься о доверии результатам тестирования воообще и о достоверности IQ тестов в частности. Опять же - в ней много головоломок и попадаются очень интересные.

    ОтветитьУдалить
  22. Сергей Корнилов, спасибо, что подтвердили актуальность книши :)

    Кстати, про IQ мы недавно как раз говорили.

    ОтветитьУдалить
  23. Анонимный11.12.2009, 16:36

    Илья, ваш блог активно поднимает во мне интерес к математике :) Что школа (физико математический лицей, кстати) сделать за 4 года так и не смогла.

    ОтветитьУдалить
  24. Анонимный11.12.2009, 16:41

    Уважаемый Аноним (Илья, кстати, тоже). Очень хочется узнать решение задачи про жуков.
    Пройденное расстояние у меня вышло в 78,5 см. Здесь есть одно но, траектории их движения - параболы-гиперболы, если это так, то они образуют окружность (повернуть траектории никто не мешает), ну и дальше через периметр.
    Вот только как доказать, что это парабола?

    ОтветитьУдалить
  25. Анонимный12.12.2009, 05:14

    Владик, доказать, что траектория является параболой, невозможно: ведь на самом деле это http://ru.wikipedia.org/wiki/Логарифмическая_спираль конечной длины, но с бесконечным числом витков. Впрочем, задача решается и без нахождения траектории.

    ОтветитьУдалить
  26. К задаче про жуков.
    В любой момент времени во время движения жуки ABCD образуют квадрат.
    Рискну предположить (строго еще не доказал), что длина стороны (или диагонали - как удобнее) этого квадрата уменьшается с постоянной скоростью. Поэтому задача сводится к нахождению этой скорости.

    ОтветитьУдалить
  27. Анонимный12.12.2009, 20:05

    про жуков- в первый момент времени они движутся к центру с постоянной скоростью 1/корень из2 (см/с), поскольку вектор скорости направлен под 45 градусов к радиусу. В следующий момент времени квадрат повернулся, сторона квадрата уменьшилась, но расклад остался- скорость 1 см/с под 45 градусов к радиусу, и радиальная скорость та же- 1/корень из 2 (см/с). Радиус, который надо пройти с этой скоростью- 100/корень из2, поэтому получаем 100 секунд понадобится жукам на решение их проблем.

    ОтветитьУдалить
  28. Анонимный12.12.2009, 20:15

    про расстояние забыл- метр конечно же проползут.

    ОтветитьУдалить
  29. Задача про муху летающую между поездами:

    http://elkin52.narod.ru/biograf/myxa.htm

    ОтветитьУдалить
  30. Илья, спасибо за блог!

    про жуков предлагаю следующее решение: рассматривать систему отсчета, где один жук зафиксирован. Тогда в этой системе будет поворачиваться квадрат. И жук, который ползет на фиксированного жука, проползет один метр.

    А про перемножение синусов не понял в чем смысл.

    ОтветитьУдалить
  31. Задача про безумную старушку.
    В самолёте N мест. И у каждого из N пассажиров билет на определённое место. Но первой в самолёт входит сумасшедшая старушка и садиться на случайное место (на любое с равной вероятностью). Далее, пассажиры входят по одному и если входящий пассажир видит, что его место свободно, он садиться на него, в противном случае на случайное из свободных. Вопрос. Какова вероятность, что последний пассажир сядет на своё место?

    ОтветитьУдалить
  32. Ivan, это хороший и интересный взгляд.

    Alexey, спасибо за задачку!

    ОтветитьУдалить
  33. Уважаемый автор, у Вас неверное решение. По условию, каждая команда должна победить в каждом туре. А эти оставшиеся пять команд сформировали ещё один тур, в котором остальные 16384 команды не участвовали, а значит и не выиграли.

    ОтветитьУдалить
  34. dlazerka, благодарю за внимательность!

    В самом деле, в формулировке "Для завоевания кубка команда должна победить во всех турах" подразумевается, что речь идёт только о тех турах, в которых команда участвует. Но лучше такие вещи не подразумевать, а явно указывать, поэтому сейчас я поправил условие.

    ОтветитьУдалить
  35. К сожалению, в таком случае мы можем устроить "несправедливое" соревнование. А именно: устроить N-1 тур. В первом туре играет первая команда со второй. Во втором туре играет выигравшая команда с третьей командой. В третьем туре играет выигравшая команда с четвёртой. И так далее. Решение заметно упрощается :)

    И я боюсь, в такой системе невозможно устроить интуитивно "справедливое" соревнование.

    ОтветитьУдалить
  36. Ну почему же невозможно? Это очень гибкая система, поэтому она позволяет пойти обычным путём (описанным выше), когда более-менее справедливая ситуация имеет место.

    Можно было усложнить условие, потребовав, чтобы все команды начинали на одном из двух нижних уровней. Но для данной задачи я не вижу в этом смысла. Предложенное Вами заметно упрощённое решение является очень симпатичным, поэтому не стоит его блокировать более хитрым условием задачи :)

    Спасибо за содержательную критику!

    ОтветитьУдалить
  37. Кирилл31.12.2009, 02:05

    Задача о резинке и улитке.
    На земле лежит резиновая лента длиной 1 метр, способная растягиваться на бесконечную длину. С левого конца ленты к правому ползёт улитка со скоростью 1 см. в минуту.
    В конце каждой минуты лента мгновенно растягивается на 1 метр.
    Вопрос: доползет ли улитка до правого конца ленты?
    Улитка бессмертная.

    ОтветитьУдалить
  38. Хорошая задачка о резинке и улитке.
    В конце-концов друг нашёл решение, причём очень простое.

    Пытался решить в лоб -- большие расчёты(считал в Mathematica).

    Если сделать непрерывный случай, когда резинка растягивается линейно непрерывно -- что-то не могу решить ДУ: x' = 1/100 + t/x.

    Ответа говорить не буду, но скажу лишь что через 10 млн. ходов улитка ещё не достигнет конца.

    ОтветитьУдалить
  39. Кирилл, спасибо за интересную задачку!

    ОтветитьУдалить
  40. Можно вспомнить одно из опеделений дерева через граф: Связный граф, в котором ребер на 1 меньше, чем вершин.
    Картинка очень напоминает дерево.

    ОтветитьУдалить
  41. Анонимный12.01.2010, 13:18

    Математика мне нравилась, но не настолько чтоб я ушла дальше тригонометрии. Поэтому я в экселе вбила начальное число команд и разделала на 2. Результат опять на 2. И так до 1. Дальшу сумируем. Так как получались нечетные числа, то и число десятичных знаков было задано 0. Ответ получился верный. Вот только на пальцах так не посчитаешь, так как эксель округлял по очереди то в меньшую, то в большую стороны.

    ОтветитьУдалить
  42. Анонимный10.09.2010, 01:30

    Задачка про улитку а я честно говоря не понимаю почему нет если лента тянется влево левее улитки в конце каждой минуты на 1 мер улитка ползет себе вправо 1 см и он растягивается на метр через *** минут приползет

    ОтветитьУдалить
  43. Уважаемый аноним, я не понимаю, в чём вопрос.

    ОтветитьУдалить
  44. Анонимный01.02.2011, 00:00

    Про синусы тоже не понял.

    ОтветитьУдалить
  45. alexzzzzz, дело в том, что есть одна константа, записываемая буквой из предложенного ряда, синус которой определяет значение произведения.

    ОтветитьУдалить
  46. Анонимный25.03.2011, 08:52

    Какова бы ни была начальная скорость улитки (если она больше нуля), она доползет до правого конца, как бы это ни выглядело странным. Причина в том что ряд 1+1/2+1/3+1/4+1/5... не имеет конечной суммы или другими словами расходится.

    ОтветитьУдалить
  47. Уважаемый аноним, мы вариацию этой задачки разбирали в другой заметке.

    ОтветитьУдалить
  48. Анонимный28.03.2011, 09:03

    ...поскольку вектор скорости направлен под 45 градусов к радиусу. В следующий момент времени квадрат повернулся, сторона квадрата уменьшилась, но расклад остался- скорость 1 см/с под 45 градусов к радиусу, и ...

    ...про жуков предлагаю следующее решение: рассматривать систему отсчета, где один жук зафиксирован. Тогда в этой системе будет поворачиваться квадрат. И жук, который ползет на фиксированного жука, проползет один метр.
    ...

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

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

    Так что доказательство в студию.

    ОтветитьУдалить
  49. Я провёл эксперимент, намазав жуков мёдом. У меня вышло 94 секунды на достижение центра, но из-за конечного размера жуков, точность воссоздания эксперимента под вопросом. С крысами и сыром этот эксперимент осуществить не удалось - хитрые твари просто разбились на парные команды :( Так что тоже жду аналитической выкладки.

    ОтветитьУдалить