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

zykov · Сообщение **zykov** » 18 июл 2020, 19:48

zykov писал(а):Source of the post Если , то степень будет 23.

Если $P(x)=x^{10}+x^3$ , то $P(P(X)) - P^{10}(x) = (x^{10}+x^{3})^3 = x^{30}+3 x^{23}+3 x^{16}+x^9$ .

zykov · Сообщение **zykov** » 18 июл 2020, 19:59

Ian писал(а):Source of the post Сидели бы в одной комнате минут на 10 быстрее сдали

Если решить все 25 задач без ошибок, то это будет 8500 балов (1000 начальных + 7500=5*1500 за 25 задач).
Лидер получил 9000 балов, у него ещё бонус на 500.
Думаю,что честно все 25 задач решить без ошибок за 2 часа невозможно.

Похоже, одни и те же люди кучу команд зарегестрировали и там открыли сразу все задачи, потом параллельно их решали, да ещё ответы тестировали, а потом уже правильные ответы вводили в основных группах.

zykov · Сообщение **zykov** » 18 июл 2020, 20:24

Лог лидеров (за 1 час 41 минуту все 25 решили):

: log; pro.png (199.57 KiB) 24562 просмотра

Ian · Сообщение **Ian** » 18 июл 2020, 21:05

Ну представьте если бы я говорил "открывай А300 и вводи 47" между покупкой и сдачей было бы несколько секунд. И это бы доказывало существование фарм-команды. А тут везде не меньше 3 минут, там где огромный счет 10-30.Теоретически возможна и честная игра у этой конкретно команды.

zykov · Сообщение **zykov** » 18 июл 2020, 21:49

zykov писал(а):Source of the post Как дальше на пальцах сделать - не знаю.

Вот придумал.
$\sum_{k=1}^{2019} 2^k=2^{2020}-2$
Значит нужно взять остаток от $101 \; b_{2020} - 200 = 37776$ . Будет 876.
Осталось только найти $b_{2020}$ лёгким способом.

zykov · Сообщение **zykov** » 18 июл 2020, 22:07

zykov писал(а):Source of the post Осталось только найти $b_{2020}$ лёгким способом.

Ну тут тоже легко.
$2020 = 2 \cdot 2 \cdot 5 \cdot 101$
Т.е. сначала возводим в степень 101, будет $x_1 = 2^{64} \cdot 2^{32} \cdot 2^5$ .
Потом возводим в степень 5, будет $x_2 = x_1^4 \cdot x_1$ .
Потом $x_2$

два раза возводим в квадрат. Всё это по модулю 900.
На первом этапе можно учесть, что $2^9 = 512$

. Значит $y_1 = 2^{18} = 512^2 (mod 900)$ , $y_2 = 2^{27} = y_1 \cdot 512 (mod 900)$ .
Тогда $2^{32} = y_2 \cdot 2^5 (mod 900)$ .

zykov · Сообщение **zykov** » 18 июл 2020, 22:09

Ian писал(а):Source of the post А тут везде не меньше 3 минут, там где огромный счет 10-30

Они могли маскироваться...
Например, как оно - 5 минут на эту задачу со степенями двойки? Тут только счёта будет изрядно...

zykov · Сообщение **zykov** » 19 июл 2020, 06:56

zykov писал(а):Source of the post Например, как оно - 5 минут на эту задачу со степенями двойки?

Впрочем на компьютере можно в лоб решить за 2-3 минуты, если под рукой есть ПО для работы с числами произвольной длины (например Python умеет).
$2^{2020}$ имеет 609 десятичных цифр ( $2020 \ln 2 / \ln 10 \approx 608.08$ ).
Значит всё $N$

имеет где-то 615000 десятичных цифр - для компьютера семички.

zykov · Сообщение **zykov** » 19 июл 2020, 07:24

zykov писал(а):Source of the post Значит всё имеет где-то 615000 десятичных цифр - для компьютера семички.

Точнее, оказалось 615476 цифр.
Вот код на Python:

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

buf=""
for k in range(1,2021):
  buf = buf + str(2**k)
print int(buf) % 900

Зная Python написать это - пара минут. Считает у меня секунды 3.

Ian · Сообщение **Ian** » 19 июл 2020, 07:52

Ч-400. Число разбиений числа n на k упорядоченных натуральных слагаемых равно

C^{k-1}_{n-1} - в сумме 1+1+...+1 (n раз) из (n-1) промежутков между единицами надо выбрать (k-1). Значит сумма длин всех разбиений

\sum_{k=1}^nkC^{k-1}_{n-1}=f'(1)

f'(x)=\sum_{k=1}^nkC^{k-1}_{n-1}x^{k-1}

f(x)=\sum_{k=1}^nC^{k-1}_{n-1}x^k=x(1+x)^{n-1}
(а у меня , когда спешил, получился просто бином

(1+x)^{n-1}.И получилась табличка значений в Excel, в которой сумма 1280. Дальше я минут 5 искал ошибку, почему же в ответе не степень двойки. Правильный ответ

2^{n-1}+(n-1)2^{n-2}=256+1024 )
Ну зачем они взяли n=9, взяли бы n=2049 и спросили бы в ответе сумму цмфр этого числа в двоичной записи. А так задача не на 400, решается сложением. А кто знает производящие функции, проигрывает

zykov · Сообщение **zykov** » 19 июл 2020, 08:09

Ian писал(а):Source of the post Ч-400. Число разбиений числа

Я это тоже на компьютере не думаю за пару минут посчитал.
Там список строится рекурсивно.
Для 1 в списке только (1) - одно слагаемое.
Далее для каждого k в список добавляем (1) - одно слагаемое и добавляем все предыдущие списки, увеличивая значение на 1.

Наприме для 2 будет ((1) (2)) = (1 2).
Для 3 будет ((1) (2) (2 3)) = (1 2 2 3).
Для 4 будет ((1) (2) (2 3) (2 3 3 4)) = (1 2 2 3 2 3 3 4).
И т.д.
Для 9 в списке 256 значений. Просто суммируем их - вот и ответ.
Matlab код:

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

z{1}=[1];
for k=2:9
  z{k} = [1];
  for k1=1:k-1
    for k2=1:length(z{k-k1})
      z{k} = [z{k} (z{k-k1}(k2)+1)];
    endfor
  endfor
endfor
sum(z{9})

zykov · Сообщение **zykov** » 19 июл 2020, 08:16

Отсюда уже видно рекурсивное отношение для самой суммы.
P(1)=1
P(2)=2*1+1=3
P(3)=2*3+2=8
P(4)=2*8+4=20
P(5)=2*20+8=48
P(6)=2*48+16=112
P(7)=2*112+32=256
P(8)=2*256+64=576
P(9)=2*576+128=1280

Ian · Сообщение **Ian** » 19 июл 2020, 08:17

И к тому же Ч-400 скорее комбинаторика, а мы ждали матан.
А Ч-500 вообще переборная, тут никакого математического аппарата не подтянешь.
Сгенерил все что явно меньше 10000, стал стирать большие и повторяющиеся, тут тоже трудно ошибиться. Трудно посчитать они же оказались разбросаны, генерятся по-разному. И с 1-го раза не прошло. Но команда.

zykov · Сообщение **zykov** » 19 июл 2020, 08:24

zykov писал(а):Source of the post Ну тут тоже легко.
$2020 = 2 \cdot 2 \cdot 5 \cdot 101$
Т.е. сначала возводим в степень 101, будет $x_1 = 2^{64} \cdot 2^{32} \cdot 2^5$ .
Потом возводим в степень 5, будет $x_2 = x_1^4 \cdot x_1$ .
Потом два раза возводим в квадрат. Всё это по модулю 900.

Эти 3-значные числа можно даже на бумаге умножать и быстро вычислить $2^{2020} \; (mod \; 900)$ .
А если на калькуляторе, то он без проблем работает с числами порядка $2^{32}$ . Тут ещё быстрее.
Например так на Matlab без циклов:

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

rem(rem(rem(rem(2^32,900)^3*2^5,900)^5,900)^4,900)
ans =  376

А полный ответ (если "по умному"):

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

rem(101*rem(rem(rem(rem(2^32,900)^3*2^5,900)^5,900)^4,900)-200,900)
ans =  876

zykov · Сообщение **zykov** » 19 июл 2020, 09:15

Ian писал(а):Source of the post А Ч-500 вообще переборная,

А что там было? Уже забыл.

Ian · Сообщение **Ian** » 19 июл 2020, 10:30

Ч-500 по памяти. На доске есть 3 числа 2,4,6 Можно назначить каждое из чисел

x,y,z из чисел, имеющихся на доске-(может быть равными) и записать на доску число

(x+1)(y+1)(z+1)-1 Сколько максимум на доске может получиться чисел, не больших 2020?
Счет можно оптимизировать, заменив каждое число на единицу большим. Тогда просто трехместная операция

X,Y,Z\to XYZ , пока результат не превышает 2021

zykov · Сообщение **zykov** » 19 июл 2020, 10:36

Ian писал(а):Source of the post Счет можно оптимизировать, заменив каждое число на единицу большим

Хорошая оптимизация!

zykov · Сообщение **zykov** » 19 июл 2020, 10:41

Можно ещё дальше оптимизировать - взять логарифм, тогда вместо $XYZ$

будет

.
Т.е. любое число - это целочисленный вектор (x,y,z), так что значение равно $x \ln 3 + y \ln 5 + z \ln 7$ .
$x+y+z$

должно делится на 3, ну и ограничение $x \ln 3 + y \ln 5 + z \ln 7 \leq \ln 2021 = \ln 43 + \ln 47$ .

Ian · Сообщение **Ian** » 19 июл 2020, 11:46

zykov писал(а): должно делится на 3, ну и ограничение $x \ln 3 + y \ln 5 + z \ln 7 \leq \ln 2021 = \ln 43 + \ln 47$ .

Не совсем так, например x=2,y=2,z=1 соответствует числу на доске 1574
Но уже не только переборная. Число целых точек в тетраэдре, что

x+y+z-любое нечетное

zykov · Сообщение **zykov** » 19 июл 2020, 12:36

zykov писал(а):Source of the post должно делится на 3

Это я поторопился. Тут просто должно быть нечётное.

Портал Естественных Наук, версия 1.1