23 мар. 2012 г.

Ленивее лентяя

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

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

На листе бумаги написаны в строчку 13 единиц.
а) Докажите, что между этими единицами можно расставить знаки сложения, умножения и скобки так, что после выполнения действий получится число, делящееся на 108.
б) Докажите, что если единицы, стоящие на чётных местах, заменить семёрками, всё равно между числами полученного набора можно будет расставить знаки сложения, умножения и скобки так, что после выполнения действий получится число, делящееся на 108.
в) Докажите, что если семёрки, стоящие на чётных местах, заменить произвольными нечётными числами, всё равно между числами полученного набора можно будет расставить знаки сложения, умножения и скобки так, что после выполнения действий получится число, делящееся на 108.
г) Докажите, что если единицы, стоящие на нечётных местах, заменить произвольными простыми числами, всё равно между числами полученного набора можно будет расставить знаки сложения, умножения и скобки так, что после выполнения действий получится число, делящееся на 108.
д) Докажите, что между любыми 13 натуральными числами можно расставить знаки сложения, умножения и скобки так, что после выполнения действий получится число, делящееся на 108.
е) Обобщение (это ещё большая подсказка, чем вариант Д, поэтому не трогайте эту ссылку раньше времени).


Пояснение: в этих задачах, как и во всех нормальных автобусных билетиках, мы не можем «склеивать» цифры (например, из двух единиц мы можем получить 1+1 и 1*1, но никак не можем сделать 11).

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

Главное искусство здесь — придумать правильную гипотезу. Например, решать задачу про поле 128 на 128 клеток достаточно тяжело, но если сообразить, что это поле 2^n на 2^n клеток, то сразу станет обозримее и проще.

В предложенной задачке все гипотезы (кроме Е) уже сформулированы, поэтому надо лишь выбрать ту, что по силам. Например, решивший В, автоматически справляется с Б. И так далее. А с какой буквы начнёте решать задачку вы? :)

Ну и раз у нас сегодня день блога «Живая Геометрия», то вот ещё одна старинная задачка из него: Найти 100 натуральных чисел, сумма которых равна их произведению (и сразу же даю ссылку на мысли о решении, которую призываю раньше времени не открывать). Кстати, не забудьте, что по первой ссылке есть не только задача про делимость на 108, но и ещё пара забавных формулировок.

Хорошего дня!

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

  1. Анонимный23.03.2012, 09:07

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

    ОтветитьУдалить
  2. 1. для любых X и Y: X*Y mod 2 = 0 OR X+Y mod 2 = 0
    X*Y mod 2 = 1 => X mod 2 = 1 AND Y mod 2 = 1 => X + Y mod 2 = 0

    Обозначим F2(X,Y) = такая комбинация Х и Y используя + и * что F2(X,Y) mod 2 = 0

    2. для любых X,Y и Z: X*Y*Z mod 3 = 0 OR X+Y+Z mod 3 = 0 OR (X+Y)*Z mod 3 = 0 OR X*(Y+Z) mod 3 = 0
    X*Y*Z mod 3 != 0 => X mod 3 != 0 AND Y mod 3 != 0 AND Z mod 3 != 0
    X+Y+Z mod 3 != 0 => NOT(X mod 3 = Y mod 3 = Z mod 3) т.к. X mod 3 = Y mod 3 = Z mod 3 => X+Y+Z mod 3 = 0
    X mod 3 != Y mod 3 => (X+Y)*Z mod 3 = 0
    X mod 3 = Y mod 3 => Y mod 3 != Z mod 3 => X*(Y+Z) mod 3 = 0

    Обозначим F3(X,Y) = такая комбинация Х,Y и Z используя + и * что F3(X,Y,Z) mod 3 = 0

    3. A mod a = 0 AND B mod b = 0 => A*B mod a*b = 0 (очевидно)

    4. F2(X1,X2)*F2(X3,X4)*F3(X5,X6,X7)*F3(X8,X9,X10)*F3(X11,X12,X13) mod 2*2*3*3*3 = 0

    QED

    ОтветитьУдалить
    Ответы
    1. Отлично! Осталось понять только вариант Е.

      Удалить
  3. А зачем в задаче е нужна простота?
    Пусть a1, ..., an - произвольные элементы Z/nZ. Докажем, что можно найти несколько идущих подряд с суммой 0.
    Рассмотрим значения a1, a1 + a2, a1 + a2 + a3, ..., a1 + a2 + an. Если все из этих n значений различны, то среди них есть и 0. Если есть одинаковые a1 + ... + ak = a1 + ... + am, то a{k+1} + ... + am = 0

    ОтветитьУдалить
    Ответы
    1. Вместо a1 + a2 + an имелось в виду a1 + a2 + ... + an

      Удалить
    2. > А зачем в задаче е нужна простота?
      Я воспользовался формулировкой из блога "Живая геометрия". Конечно, в Вашей более общей постановке задачка стала ещё лучше. Благодарю за активное участие в развитии этой заметки!

      Удалить
  4. Анонимный24.03.2012, 10:34

    Похоже, что так. И условие простоты здесь не существенно. Осталось перевести это на понятный школьнику, далекому от Z/nZ, язык.

    ОтветитьУдалить
    Ответы
    1. Да что там переводить-то? Говорим о целых числах, а не вычетах. И все равенства понимаем mod n. Другими словами, остатки от деления на n равны.
      А простота вылазит в общем слуачае для того, чтобы получить минимальное количество чисел (в данном примере 13). Поскольку для натуралаьных чисел, больших 1 выполняется a+b <= ab, то самым эффективным будет именно разбиение на простые.

      Удалить
  5. А что там переводить-то? Пусть будут целые числа, а не вычеты. И все равенства понимаем mod n. Другими словами, остатки от деления на n равны.
    А простота вылазит в общем слуачае для того, чтобы получить минимальное количество чисел (в данном примере 13). Поскольку для натуралаьных чисел, больших 1 выполняется a+b <= ab, то самым эффективным будет именно разбиение на простые.

    ОтветитьУдалить
  6. Анонимный24.03.2012, 16:38

    Да, разумеется, перевод стандартный.

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

Понравилась заметка? Подпишитесь на RSS-feed или email-рассылку.

Хотите поделиться ссылкой с другими? Добавьте в закладки:



Есть вопросы или предложения? Пишите письма на адрес mytribune АТ yandex.ru.

С уважением,
      Илья Весенний