Комбинаторика

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Комбинаторика

Сообщение Ian » 14 июл 2020, 20:14

Дано множество чисел {1,2,...15}. Сколько Существует его подмножеств, в которых не представлены соседние друг другу четные числа (то есть числа 2k и 2k+2 не могут быть в подмножестве одновременно)
Я давал разные ответы, но бездушный автомат все их признал неверными. Где же я ошибся
Конечно число подмножеств из нечетных [math] надо умножить на число подмножеств из четных, включая пустое.
1 пустое
7 из одного четного числа
15=5+4+3+2+1 из двух четных
10 из трех четных
1 из 4х четных
34*256=8704 не принимает система

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Комбинаторика

Сообщение zykov » 15 июл 2020, 03:05

У меня тоже так получается.
На всяки случай перебрал все $2^{15}$ вариантов на компьютере - тоже 8704 получается.
Matlab код:

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

s=0;for k=0:(2^15-1);v=bitget(k, 1:15);b=v(2:2:14);bb=b(2:end)+b(1:end-1);if sum(bb==2)==0;s=s+1;end;end;s


Может Вы условие не так поняли? Можно условие сюда в исходном виде?

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Комбинаторика

Сообщение Ian » 15 июл 2020, 13:02

Screenshot_20200715_102656_com.yandex.browser.jpg
Screenshot_20200715_102656_com.yandex.browser.jpg (69.45 KiB) 17865 просмотра
нашелся скрин. Это тренировочные задачи какого-то будущего соревнования.

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Комбинаторика

Сообщение Ian » 16 июл 2020, 08:02

Но есть и похуже проблемы
a300+500.png
a300+500.png (62.42 KiB) 17814 просмотра

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Комбинаторика

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

У меня в "алгебра-300" тоже -7007 получается.
Может они имели ввиду не $f(1)$, а $g(1)$, т.е. -77.
Последний раз редактировалось zykov 16 июл 2020, 16:14, всего редактировалось 1 раз.

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Комбинаторика

Сообщение Ian » 16 июл 2020, 14:40

А почему не принимала 8407 и -7007 ответ простой.
fake_ans.png
fake_ans.png (105.73 KiB) 17792 просмотра

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

Псевдосфера
Сообщений: 73
Зарегистрирован: 16 июл 2020, 14:40

Комбинаторика

Сообщение Псевдосфера » 16 июл 2020, 15:43

Доброго времени суток! По Алгебра 500 обсуждается такое коллективное решение. Период [math] в виде десятичной дроби будет [math], если [math]
[math]
[math]
Период [math] , если для этого [math] выражение справа станет целым числом. Оно легко анализируется.Сокращаем на 9, сверху число из n единиц. Сокращается на 11 тогда и только тогда когда[math] четное. Получится сверху число с [math] единицами 10101010...01

Оно должно делиться на 9, по признаку делимости m должно делиться на 9.Также m должно делиться на 11 чтобы число сверху еще раз разделилось на 11. Значит [math] имеет 198 девяток

Но нам то надо узнать сумму цифр частного от деления 10101010...101 (99 единиц, 98 нулей) на 99 с помощью экспериментов соображаем что это частное -подряд написанные 01,02,03...09,10,11,12,....97,98 -как раз 195 -значное число, получающееся от деления 197-значного на 99. таким образом надо найти сумму цифр натурального ряда 1,2...98.

Тут на месте единиц 10 единиц,10 двоек,...10 восьмерок, и только 9 девяток. Сумма цифр, стоящих на месте единиц [math]

На месте десятков та же история, 441 =сумма цифр на месте десяток. Получаем сумму цифр периода 882

Но за ними 99 потом 00 потом 01 (то есть не правда что должно стать целым числом - и новый период

Тогда сумма цифр периода 900
Последний раз редактировалось Псевдосфера 16 июл 2020, 16:01, всего редактировалось 1 раз.

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Комбинаторика

Сообщение Ian » 16 июл 2020, 15:44

И эти 900 не прошли сегодня. Где-то какая-то ошибка.А ведь есть люди которые ее решили.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Комбинаторика

Сообщение zykov » 16 июл 2020, 15:53

В "алгебра-500" ответ 883.
Период начинается сразу после запятой и имеет длину 198.

(Здесь удобно считать разложение не по основанию 10, а по основанию 100. Идут "00", "01", "02" и т.д.. Только в конце нет "98", а за "97" сразу идет "99".)

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Комбинаторика

Сообщение zykov » 16 июл 2020, 15:58

Раз они требуют только ответ, но не само решение, то экономичнее по времени в некоторых задачах (например "комбинаторика-100", "алгебра-500") не ломать голову, а просто быстро это посчитать в Matlab/Octave.
Вот код Matlab для "алгебра-500":

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

b=99*99;x=10;v=[];for k=1:400;d=floor(x/b);v(k)=d;x=10*(x-d*b);end;v

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Комбинаторика

Сообщение Ian » 16 июл 2020, 16:35

25_ans.png
25_ans.png (17.92 KiB) 17718 просмотра

ну вот сделали себе имя

Псевдосфера
Сообщений: 73
Зарегистрирован: 16 июл 2020, 14:40

Комбинаторика

Сообщение Псевдосфера » 17 июл 2020, 04:38

Спасибо всем за решения! Ждем вас на регате)

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Комбинаторика

Сообщение zykov » 17 июл 2020, 07:01

zykov писал(а):Source of the post (Здесь удобно считать разложение не по основанию 10, а по основанию 100. Идут "00", "01", "02" и т.д.. Только в конце нет "98", а за "97" сразу идет "99".)

Подробнее, здесь можно применить алгоритм, как его в школе называют - деление в столбик, чтобы получить цифры после запятой по любому основанию $B$ (обычно $B=10$).
Пусть нам надо разложить рациональное число $a/b$, где $0<a<b$ и оба целые.
Тогда алгоритм:

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

x = a
i = 1
цикл
  поделить B*x на b с остатком -> d=целая часть, q=остаток
  D[i] = d  (новая цифра в позиции i)
  x = q  (новое состояние)
  i = i + 1
конец цикла

Когда состояние $x$ примет значение, которое уже принимало ранее, то это будет новый цикл в циклической дроби.

В нашем случае $a=1$, $b=99^2=9801$. Для $B$ удобно выбрать $100$.
Тогда в начале $d$ будет принимать значения $00$, $01$, $02$ и т.д.
А $x$ будет $1$, $1+99$, $1+2*99$, $1+3*99$ и т.д.
При $i=98$ в начале цикла $x=9604=1+97*99$. При делении с остатком $960400$ на $b$ будет $97$ и остаток $9703=1+98*99$.
Но при $i=99$ деление с остатком $970300$ на $b$ будет $99$ и остаток $1$. Т.е. $98$ было пропущено, т.к. произошло переполнение (новый остаток должен был быть $1+99*99$, но это больше чем $99*99$, поэтому новый остаток равен $1$, а целая часть увеличивается на $2$, а не на $1$). При этом состояние $x$ вернулось обратно к $1$, как в начале. Значит начинается новый цикл. Длина цикла получилась 99.


Вернуться в «Математика»

Кто сейчас на форуме

Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 4 гостей