Афтерпати к регате

[zykov]

Да, тоже легко 22 получается.
Вот Matlab код:

Код: Выбрать все

s=0;
for x=0:6; for y=0:4; for z=0:3;
  if rem(x+y+z,2)==0; continue; end
  if x*log(3)+y*log(5)+z*log(7) < log(2021); s=s+1; end
end; end; end
s


Если догадатся про "+1", то дальше на компьютере за 5 минут делается.
Такое ощущение, что эта олимпиада больше для програмистов.

[zykov]

Можно в принципе и руками перебрать.
Для пар (y,z) есть 14 вариантов. Для каждого можно проверить, какие x подходят - всего 7 разных x, половина сразу по чётности отпадает.

[zykov]

Source of the post Число целых точек в тетраэдре, что x+y+z-любое нечетное

Там всего 22 нечётных и 24 чётных.

[Ian]

Итоги аппеляции: в задаче алгебра 500 правильным считается ответ 9 и 23. С поправкой на это сейчас происходит пересчет итогов + обновление бонусов, но это не так быстро и просто, как может показаться (да, это кажется одним скриптом на питоне, но нет).

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

Нам +750 ко вчеращней цифре.Второй ответ как раз был 9

[zykov]

Я как раз думал об апелляции по этой задаче, ведь они не написали, что коэффициенты действительные.

[Ian]

В-5. "Игра с монеткой". Иван играет в игру. Изначально у него есть 2 доллара. Игра
состоит из нескольких раундов. В каждом раунде подбрасывается монетка, далее:
• Если монетка падает орлом вверх, Иван получает 2 доллара.
• Если монетка падает решкой вверх, Иван теряет половину всех своих денег.
• Если монетка падает решкой вверх во второй раз подряд, игра заканчивается (в
этом раунде Иван не теряет деньги).
Сколько в среднем долларов будет у Вани после окончания игры? Ответ умножьте на
100 и округлите до ближайшего целого числа. Если дробная часть равна 0.5, округлите
вверх.
Среднее должно быть [math]\frac 83долл. Надо подумать почему.

[Ian]

Ну например обозначим [math]f(x) средний выигрыш при условии, что начальный капитал [math]x и предыдущая не решка.
До следующей решки игрок нарастит свой капитал в среднем на [math]\sum_{k=1}^{\infty}\frac k{2^k}=2. А на решке этот капитал [math]x+2 разделится пополам и 2 варианта: либо он будет окончательным выигрышем либо средний выигрыш будет [math]f(\frac x2+3)
Получаем функциональное уравнение
[math]f(x)=\frac {x+2}4+\frac 12f(\frac x2+3)
Стандартными линейными заменами получаем формулу [math]f(x)=2+\frac x3
и в частности [math]f(2)=\frac 83

[Ian]

Комбинаторика-300 (тут скорей надо знать алгебру) Среди функций [math]f:A\to A=\{1,2,3,4,5,6,7\} найти количество таких, что [math]f(f(f(x)))=x для всех [math]x\in A.
Тогда функция должна быть биекцией, другими словами -перестановкой. Перестановка должна удовлетворять алгебраическому равенству [math]f^3=e (перестановки образуют группу относительно операции композиции). Тогда разложение перестановки в произведение независимых циклов должно содержать только циклы длины кратной 3 , то есть 1 или 3
1 перестановка [math]e с 0 циклов длины 3
70=[math]2!C^3_7 перестановок с 1 циклом длины 3
280=[math]2!2!\frac {C^3_7C^3_4}{2!} перестановок с 2 циклами длины 3
(число циклов, которые можно составить из данной тройки, 2!. Но и две тройки выбираются неупорядоченно, неважно какая сначала, поэтому разделили на 2!)
Итого 351. Кто не знает теорию разложения перестановки на независимые циклы- сможет решить как-то иначе?

[zykov]

Source of the post Среднее должно быть долл. Надо подумать почему.

Если бы её открыли, то оно тоже за 5 минут считается методом Монтекарло на компьютере.
Matlab код:

Код: Выбрать все

% USE: v500(10^5, 5)*100
function r = v500(N, nn)
  r = [];
  for k1 = 1:nn
    s = 0;
    for k = 1:N
      v = 1;
      m = 2;
      while true
        c = floor(rand*2);
        if c == 0
          v = 1;
          m = m + 2;
        else
          v = v + 1;
          if v == 3, break; endif
          m = m / 2;
        endif
      endwhile
      s = s + m;
    endfor
    r = [r s/N];
  endfor
endfunction


Считает 40 секунд
Результат:

Код: Выбрать все

v500(10^5,5)*100
ans =

   266.39   266.66   266.52   267.12   265.97


[zykov]

Source of the post Кто не знает теорию разложения перестановки на независимые циклы- сможет решить как-то иначе?

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

Matlab код:

Код: Выбрать все

v = perms([1:7]);
s = 0;
for k1 = 1:size(v, 1)
  p = v(k1, :);
  s = s + 1;
  for k = 1:7
    if p(p(p(k))) != k
      s = s - 1;
      break;
    endif
  endfor
endfor
s


Считает менее 1 секунды, выдаёт 351.

[Ian]

Как-то жаль что К-300 не мотивирует знать алгебру. Может при суперкомпьютерах ни алгебра ни примыкающая к ней дискретка вообще будут не нужны? Хотя компьютеры на ней и базируются, но я имею в виду -для пользователя.
к-400. "Фишки в ряду". Несколько фишек двух цветов расположены в ряд (встречаются
оба цвета). Известно, что фишки, между которыми 10 или 15 фишек, одинаковы. Какое
наибольшее число фишек может быть?
Номера фишек принимают значения 1...n, пусть 1-я фишка имеет цвет 1, это будем обозначать как [math]I_1=1. У нас [math]I_{k+11}=I_k,I_{k+16}=I_k, пока оба индекса допустимые. Если мы сможем с помощью операций [math]\pm 11,\pm 16 прийти от индекса 1 по допустимым индексам к любому [math]\{1,...n\}- то все фишки одного цвета, значит n слишком велико. А если нет - остальные фишки имеем право задать другого цвета, противоречия с условием не будет.Каждое противоречие означало бы что из цвета 1 можно прийти за один шаг в другой цвет, а мы предполагаем, что все эти возможности уже были реализованы. Пусть [math]11x+16y+1 допустимый индекс,полученный такими операциями, [math]0\leq 11x+16y\leq n-1 должно быть целочисленной решеткой на плоскости (х,у), связанной ходом ладьи. Последовательно допуская все большие n, получим, что при n=26 в эту решетку попадут уже все номера от 1 до n. А при n=25 номера k=5,10,16,21 останутся недоступтны (из-за недоступтности 26 и 27)-и значит, могут быть назначены 2-го цвета. Значит, максимальное n=25. Правда потребовался час. чтобы аккуратно и надежно организовать это визуальное гуляние по решетке (в которой написаны [math]11x+16y+1) . Зато окончательный ответ в таком виде что очевиден

Код: Выбрать все

№ шага   х   у   k
1   0   0   1
10   3   -2   2
15   6   -4   3
20   9   -6   4
         -
4   -1   1   6
6   2   -1   7
13   5   -3   8
18   8   -5   9
         -
9   -2   2   11
2   1   0   12
11   4   -2   13
16   7   -4   14
21   10   -6   15
         -
3   0   1   17
8   3   -1   18
14   6   -3   19
19   9   -5   20
         -
7   -1   2   22
5   2   0   23
12   5   -2   24
17   8   -4   25


[zykov]

Source of the post Правда потребовался час. чтобы аккуратно и надежно организовать это визуальное гуляние по решетке

Мне кажется тут довольно просто.
Во-первых, сразу видно, что первое ограничение позволяет только 11 переменных, дальше идёт период 11.
x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11
Потом, если фишек от 22 и больше, то ещё ограничение, что номер 17 (он же номер 6) равен номер 1, и т.д.
x1 x2 x3 x4 x5 x1 x2 x3 x4 x5 x1
Т.е. уже 5 переменных.
Далее, если количество фишек 23 (номер 23 равен номер 23-22=1 и номер 23-16=7), то x2=x1.
Далее, если количество фишек 24, то x3=x2=x1.
Далее, если количество фишек 25, то x4=x3=x1.

Т.е. при 25 фишках ещё можно сделать x1=x2=x3=x4 и не равно x5.
Далее, если количество фишек 26 (и более), то x5=x4=x1. Значит x1=x2=x3=x4=x5.

[zykov]

Source of the post Как-то жаль что К-300 не мотивирует знать алгебру. Может при суперкомпьютерах ни алгебра ни примыкающая к ней дискретка вообще будут не нужны?

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

Другое дело, что конкретно в этой мат. регате они выбрали в основном такие задачи, что легко, не думая, решаются на компьютере за 3-5 минут, хотя у них есть и "правильное" математическое решение "на бумажке", но уже нужно потратить 15, 30, 45 минут.
Даже вот неплохая задача со степенями двойки решается "не думая" на Python за 3-5 минут просто "в лоб".

[zykov]

Если кто пропустил, они все задачи первого тура выложили в открытый доступ:

Tinkoff_1_July2020.pdf

(169.79 KiB) Загружено 624 раз