Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

Categories:

шестая задача олимпиады

Шестая задача Международной математической олимпиады тоже оказалось в этом году одной из сложных - ее целиком решили 37 участников (самую легкую, четвертую задачу целиком решили 309 участников).



У меня интересно вышло с этой задачей. Я долго над ней думал на прошлых выходных и в начале недели. Немного с ручкой и бумагой, но в основном в уме, просто пялился в пространство и думал. Мне казалось, что у меня есть правильный подход и надо только довести его до конца. Там в условии написано, что числа необязательно положительные; так вот, если они обязательно положительные, то я довольно быстро нашел решение, но отрицательные числа его "ломают", и мне все казалось, что можно этот ущерб как-то ограничить и нейтрализовать, и все никак не получалось. Наверное, часов восемь или десять в общей сложности думал над этой задачей, и ничего.

А сейчас, вот полчаса назад, я читал запись в блоге американского профессора Кала Ньюпорта. Он вообще-то профессор информатики, но известен своими книгами о продуктивности умственной работы, и особенно тезисом о важности "глубокой работы" - способности думать о чем-то долго, не отвлекаясь на мессенджеры и соц. сети, грубо говоря (сразу скажу, что не читал его книг, и не имею собственного мнения об этом пока). Так вот, у себя в блоге он цитирует другого ученого, который толкает следующую простую мысль: мы любим читать истории про "Эврика!", про озарение, про внезапно приходящую идею, но обычно такой момент случается после того, как много часов или дней бьешься над задачей, и ничего не получается.

Я это прочитал и подумал, ну вот я над шестой задачей столько думал и безрезультатно; может, я уже достаточно натренировал свой мозг на нее, чтобы теперь ниоткуда появилось бы решение, вот было бы здорово! Стал опять праздно думать над задачей и... через три минуты ниоткуда появилось решение. Честное слово, я не преувеличиваю. Это случилось полчаса назад.

После этого долгого введения предлагаю свое решение. Если хотите решать сами, не читайте дальше.
[Spoiler (click to open)]

В задаче дано, что с помощью элементов A мы можем составить суммы m, m^2, m^3.. и так далее до m^m. Если мы запишем эти числа наглядности ради в m-ричной системе счисления, они будут выглядеть так: 10, 100, 1000. Например, если m=10, то это собственно и будут числа десять, сто, тысяча итд., а если m=2, надо смотреть на 10, 100 итд. как на двоичные числа.

Теперь ясно, что с помощью этих сумм, равных 10, 100, 1000 итд. до 10000..0 (m+1 нулей), мы можем, складывая их вместе много раз, получить любое число из m m-ричных цифр (и 0 в конце). Например, возьмем m=10: если мы хотим получить 45670, нам нужно взять сумму, которая дает 10000 4 раза, сумму 1000 5 раз, итд. Таким образом, складывая эти суммы вместе, мы получим любое из m^m чисел от 0 до XXXXXXXX...X0, где X "цифра" m-1 в m-ричной системе записи. Таких разных чисел ровно m^m, потому что каждая из m "цифр" может быть чем угодно от 0 до m-1.

При этом в каждой такой мега-сумме каждый элемент исходного множества A присутствует не более m^2-1 раз. Действительно, мы берем сумму вида 1000 для каждого разряда не больше m-1 раз, и всего таких разрядов m. Значит, все m^m чисел могут быть получены как суммы чисел из A, причем каждое число берется не больше (m-1)m = m^2-m раз, и нам достаточно даже будет сказать, что не больше m^2-1 раз.

Но сколько есть вообще разных способов составить такую сумму из A? Если бы в A было ровно m/2 чисел, и для коэффициента при каждом из них m^2 возможностей (от 0 раз до m^2-1 раз берется это число), то всего разных сумм (m^2)^(m/2) = m^m. Если же в A меньше, чем m/2 элементов, то разных сумм точно меньше m^m, так что получить m^m разных чисел невозможно. Выходит, что в A не меньше m/2 элементов, что и требовалось доказать.
Tags: математика
Subscribe

  • учебник огласовок

    Вот интересная книга, выложенная полностью бесплатно: Никудену: Курс огласовок в современном иврите Скорее всего будет интересна только тем, кто…

  • о статуе джефферсона

    Муниципальный совет Нью-Йорка единогласно проголосовал за то, чтобы убрать из зала заседаний муниципалитета статую Томаса Джефферсона, потому что он…

  • этого ещё неоперившегося подонка

    Прекрасная находка bbb ( здесь): историк теории вероятности и статистики Оскар Шейнин и его труд "Чёрная книга: Ошибки и неточности в…

  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 19 comments

  • учебник огласовок

    Вот интересная книга, выложенная полностью бесплатно: Никудену: Курс огласовок в современном иврите Скорее всего будет интересна только тем, кто…

  • о статуе джефферсона

    Муниципальный совет Нью-Йорка единогласно проголосовал за то, чтобы убрать из зала заседаний муниципалитета статую Томаса Джефферсона, потому что он…

  • этого ещё неоперившегося подонка

    Прекрасная находка bbb ( здесь): историк теории вероятности и статистики Оскар Шейнин и его труд "Чёрная книга: Ошибки и неточности в…