flaass: идея линейности

идея линейности
Вчера рассказывал деткам, что это такое. В качестве одного из примеров рассказал задачку:

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

Пусть заголовок послужит подсказкой.
А про геометрические прогрессии - не знаю. Там должно быть интереснее.

(Добавить комментарий)

	ptitza@lj 2009-01-09 08:23 (ссылка)
	вот интересно, а сколько "деткам" лет? (Ответить) (Ветвь дискуссии)

	flaass@lj 2009-01-09 08:29 (ссылка)
	10-11 класс. Но были и 9классники. Но они все олимпиадники, им легче. (Ответить) (Уровень выше)

anna_frid@lj
2009-01-09 10:14 (ссылка)

В точности про геометрические не знаю, но две похожие вещи знаю: во-первых, пример 1 отсюда (http://www14.plala.or.jp/kamae/complexity.lzh) (там окошко в виде геометрической прогрессии пробегает все возможные начала), во-вторых, мощную статью Y. Moshe On the subword complexity of the Thue-Morse polynomial extractions (у меня на бумаге есть, весной на семинаре докладывала, кстати). В частности, оттуда: по номерам, образующим квадратичный полином с несложными ограничениями - тоже все что угодно.

(Ответить) (Ветвь дискуссии)

	flaass@lj 2009-01-10 10:52 (ссылка)
	Про сдвиги совсем просто: 4^i+b, нужное b подбирается сразу. Это и есть пример 1? (Ответить) (Уровень выше) (Ветвь дискуссии)

	anna_frid@lj 2009-01-10 10:54 (ссылка)
	Угу. Окошко (0, 3,...,4^i-1) движется. Вот вторая вещь хоть и не в тему вопроса, зато хороша. (Ответить) (Уровень выше)