Задача: зубрежка - повторение (возможно, без решения)

[granit201z]

Есть дни (1, 2, 3...) и есть порции материала (1, 2, 3...). В один день может подаваться (зубриться) одна порция материала, а повторяться две (ну или несколько, но фиксированное количество) порции. При следующем графике "зубрежек-повторений" - дата следующего повторения сильно зависят от номера дня зубрежки:

№_Дня; Зубрежка; Повторение

1 1 (1, 1)
2 2 (1, 2)
3 3 (1, 2)
4 4 (3, 4)
5 5 (1, 2)
6 6 (3, 4)
7 7 (5, 6)
8 8 (7, 8)
9 9 (1, 2)
...

То есть на 1025 день до повторения 1025 материала останется 512 дней, но это будет только первое повторение. А для первого повторения неприемлема такая большая задержка.

Возможно ли составить график повторений, чтобы он был расходящимся (что то наподобие 2, 6, 12, 30, 64..., где числа-элементы - дни между последующими повторениями, а порядковые номера этих элементов - номера повторений), одинаковым для любого материала независимо от номера дня зубрежки этого материала?

[ozheredov]

Верно ли я понимаю:

1) есть упорядоченное множество порций материала 1, 2, .., при этом зубрить порцию 4 можно только если 1, 2 и 3 зубрились? При этом не важно, были ли они повторены.

2) в день можно зубрить не более одной порции и повторять не более, скажем, двух (потом будем менять). При этом повторять можно только то, что уже зубрилось.

А вот теперь одни вопросы:

Когда алгоритм считается завершённым? Когда все порции материала зазубрены по разу и повторены тоже по разу?

В чем критерий оптимальности алгоритма? В том что он завершается за наименьшее время, и при этом максимальное (по всем порциям материала) расстояние между зубрежкой и повторением не превосходит некоторую заданную величину?

Тогда чем вот эта вот тривиальщина не подходит (100 порций)

День | Что зубрим | Что повторяем
1 1 -
2. 2. 1
3. 3. 2
.......................................
100. 100. 99
101. - 100

Что, есть более оптимальное решение? Или вам нужно рандомизировать повторяемые порции?

[granit201z]

ozheredov в сообщении #1317097 писал(а):

1) есть упорядоченное множество порций материала 1, 2, .., при этом зубрить порцию 4 можно только если 1, 2 и 3 зубрились? При этом не важно, были ли они повторены.

Да.

ozheredov в сообщении #1317097 писал(а):

2) в день можно зубрить не более одной порции и повторять не более, скажем, двух (потом будем менять). При этом повторять можно только то, что уже зубрилось

Да. Только в процессе алгоритма нельзя менять количество повторяемых порций. То есть, если мы выбрали две, то на протяжении всего алгоритма придерживаться двух. Если изначально выбрали три, то трех.

ozheredov в сообщении #1317097 писал(а):

Когда алгоритм считается завершённым? Когда все порции материала зазубрены по разу и повторены тоже по разу?

Нет. В идеале алгоритм не завершается. Каждая конкретная порция должна повторяться бесконечное количество раз. С увеличением интервалов между её повторениями по мере удаления от момента ее подачи (зубрежки).

ozheredov в сообщении #1317097 писал(а):

В чем критерий оптимальности алгоритма? В том что он завершается за наименьшее время, и при этом максимальное (по всем порциям материала) расстояние между зубрежкой и повторением не превосходит некоторую заданную величину?

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

Например, материал подан (неважно первый это день или, скажем, сотый). Первое его повторение должно произойти через M дней с момента подачи, второе через N дней с момента первого повторения, третье через K дней с момента второго повторения. И т.д.

1. M<N<K<...
2. Для любых материалов последовательность (M, N, K, ...) должна быть одной и той же.

P.S. некоторый сумбур получается с первым материалом, поскольку он подан и надо бы еще два чего-то повторить в этот день, но повторять пока что нечего. Поэтому возможно в этом случае (только для нескольких первых дней) воспользоваться повторениями "мнимого" материала: 0, -1, -2...

[granit201z]

Нельзя ли эту тему перенести в раздел "помогите разобраться"? Поскольку самостоятельно разобраться я не могу, а в этом разделе этот вопрос не вызывает ни у кого интереса.

[granit201z]

прошу прощения за навязчивость. Ответьте кто-нибудь, пожалуйста:
1. решения у этой задачи нет?
2. задача простая, но нет желания заострять на ней внимание?
3. задача сложная и никто не знает ее решение?
4. условие задачи поставлено некорректно и неясно, что требуется решить?

[Dendr]

Похоже, что вариант 1.
Наглядно: просто представьте, что вы сделали "механический повторятор". Условие требует, чтобы материал, изученный день N повторялся в дни N+a, N+b, N+c... Причем a, b, c жестко заданы и одинаковы для всех N.
Нарисуем на бумаге строку из квадратов - это будут дни, и пометим те, в которые будет повторяться материал первого дня. Теперь сделаем гребенку, чье основание лежит параллельно строке вне квадратов, а зубцы накрывают отмеченные квадраты; к гребенке прикрепим ярлык "1".
Теперь скопируем ее и сместим на один квадрат, это будет "2", повторим этот процесс много раз, не забывая нумеровать гребенки. Полный набор этих гребенок и будет упомянутым "повторятором".

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

Все это можно доказать строго, но стоит ли? Просто обращу внимание на арифметику. Пусть мы в день повторяем материал m ранних дней.
За N дней мы совершим не более Nm повторений.
Пусть каждый материал в течение первых k дней (со дня изучения данного материала) повторяется F(k) раз. Тогда точное число повторений за N дней всего обучения равно S(N)=F(N)+F(N-1)+...+F(1).
Достаточно показать, что, начиная с некоторого N величина S(N)/N будет больше любого наперед заданного числа m. Здесь, конечно, не прогрессия - которая дала бы (N-1)/2 - но и асимптоты тут не возникает: при больших N ожидается, что F(N)=O(N).

[mihaild]

Dendr в сообщении #1320126 писал(а):

Но множество всех зубцов всех гребенок, хотя и тоже счетно, мощнее множества натуральных чисел

Это как вообще?

Ответ на задачу и правда отрицательный, что легко видеть из следующего соображения: пусть материал повторяется через $a_1, a_2, \ldots$ дней после первого изучения. Вопрос: что мы будем повторять в день $1 + a_1 + \ldots + a_k$?

Dendr в сообщении #1320126 писал(а):

при больших N ожидается, что F(N)=O(N)

Это конечно будет, но это неинтересно, т.к. скажем $0 = O(N)$. А вот $F(N) = \theta(N)$ уже совершенно необязательно.

[granit201z]

mihaild в сообщении #1320129 писал(а):

Вопрос: что мы будем повторять в день $1 + a_1 + \ldots + a_k$?

простите, я не совсем понял вопрос. Из того же, как я его понял, - в этот день будет повторение материала $B$, изученного с задержкой на один день относительно материала $A$

-- 15.06.2018, 16:51 --

Dendr в сообщении #1320126 писал(а):

Но множество всех зубцов всех гребенок, хотя и тоже счетно, мощнее множества натуральных чисел (в нашем случае - множество квадратов в таблице).

Стоп. Множество гребенок бесконечно и счетно. Множество зубцов у каждой гребенки тоже бесконечно и счетно. Получается, что множество всех зубцов всех гребенок имеет мощность счетного множества счетных множеств. Разве оно счетно в этом случае?

[mihaild]

granit201z в сообщении #1320177 писал(а):

Из того же, как я его понял, - в этот день будет повторение материала $B$, изученного с задержкой на один день относительно материала $A$

Какие $B$, какие $A$, это про что?
Пусть материал, изученный в день $t$, мы будем повторять в дни $t + a_1, t + a_2, \ldots, t + a_k, \ldots$.

granit201z в сообщении #1317125 писал(а):

Первое его повторение должно произойти через M дней с момента подачи, второе через N дней с момента первого повторения, третье через K дней с момента второго повторения.

Давайте в этих обозначениях: $M = a_1$, $N = a_2$, $K = a_3$ и т.д.
Какие материалы мы будем повторять в день $1 + a_1 + a_2 + \ldots + a_k$?
Подсказка: в какой день мы в $k$-й раз повторим материал, изученный в первый день? А в какой день мы в $k-1$-й раз повторим материал, изученный в $1 + a_k$-й день?

granit201z в сообщении #1320177 писал(а):

множество всех зубцов всех гребенок имеет мощность счетного множества счетных множеств. Разве оно счетно в этом случае?

Счетность счетного объединения счетных множеств - широко известный факт. Подумайте, как можно пронумеровать скажем все точки на плоскости с целыми положительными координатами (т.е. пары положительных целых чисел).

[ozheredov]

mihaild в сообщении #1320179 писал(а):

Подумайте, как можно пронумеровать скажем все точки на плоскости с целыми положительными координатами (т.е. пары положительных целых чисел).

Змейкой по побочным диагоналям

1,1
1,2
2,1
3,1
2,2
1,3
...

[granit201z]

mihaild в сообщении #1320179 писал(а):

Подумайте, как можно пронумеровать скажем все точки на плоскости с целыми положительными координатами (т.е. пары положительных целых чисел).

Думаю так можно:

mihaild в сообщении #1320179 писал(а):

Давайте в этих обозначениях: $M = a_1$, $N = a_2$, $K = a_3$ и т.д.
Какие материалы мы будем повторять в день $1 + a_1 + a_2 + \ldots + a_k$?
Подсказка: в какой день мы в $k$-й раз повторим материал, изученный в первый день? А в какой день мы в $k-1$-й раз повторим материал, изученный в $1 + a_k$-й день?

в $k$-й раз мы повторим материал, изученный в первый день как раз в $1 + a_1 + a_2 + \ldots + a_{k-1} + a_k$ день.

а материал, изученный в $1 + a_k$-й день мы повторим в $k-1$-й раз вот в этот день:

$(1 + a_k) + a_1 + a_2 + \ldots + a_{k-1} = 1 + a_1 + a_2 + \ldots + a_{k-1} + a_k$

то есть в тот же самый день. А что из этого следует?

-- 16.06.2018, 22:45 --

granit201z в сообщении #1320445 писал(а):

А что из этого следует?

А, я понял:

$(1 + a_k + a_{k-1}) + a_1 + a_2 + \ldots + a_{k-2} = 1 + a_1 + a_2 + \ldots + a_{k-2} + a_{k-1} + a_k$

материал $1 + a_k + a_{k-1}$ -го дня мы повторим в $k-2$ -й раз тоже в этот же день

[mihaild]

granit201z в сообщении #1320445 писал(а):

материал $1 + a_k + a_{k-1}$ -го дня мы повторим в $k-2$ -й раз тоже в этот же день

Ага. И суммарно в этот день повторим $k-1$ материалов. А $k$ было произвольным.