Пусть у нас даны натуральные числа от 1 до $%n$%. Назовём непустое подмножество множества этих чисел путным, если среднее геометрическое элементов этого подмножества является натуральным числом. Как определить, чётно или нечётно количество путных подмножеств, в зависимости от $%n$%?

задан 2 Май '17 10:47

Боюсь, что это даже для компьютерного перебора тяжеловато выглядит. Хорошей закономерности тут, наверное, не получится. Вот, скажем, пусть очередное число является простым. Тогда добавляется только оно само как 1-элементное подмножество. Получается, что мы неявно должны учитывать как минимум закон распределения простых чисел.

Если запоминать все подмножества, то перебором примерно 2^n случаев можно всё узнать для "малых" значений n, а чего-то лучшего тут, наверное, и не предложить.

(2 Май '17 14:19) falcao

@falcao , хорошо, давайте решим эту задачу для двух частных случаев: 2017 и 2004.

(2 Май '17 16:29) Аллочка Шакед

@Танюшка Мадр...: я могу ошибаться, не разглядев какую-то идею, но, по-моему, тут ничего интересного не получается. Надо анализировать число новых наборов с участием чисел от 2005 до 2017. Добавление нового простого числа ничего не даёт. Если новое число имеет вид pq, то надо смотреть, что к нему подходит из предыдущего, что составляется из степеней p,q как минимум. Потом ещё брать варианты с домножением. Это работа для компьютера, причём даже процесс написания программы выглядит "уныло".

(2 Май '17 20:14) falcao

Здесь кажется нашли закономерность http://dxdy.ru/topic117779.html

(2 Май '17 23:50) abc

@abc: тогда всё становится намного интереснее, так как появляется естественная гипотеза, и её можно пытаться доказывать или опровергать.

Я недооценил эту задачу: когда смотрел значения для нескольких начальных n, то где-то обсчитался, и чередования у меня не получилось.

(3 Май '17 0:06) falcao

Чтобы четность числа геометрически путных подмножеств в $%\{1, \dots,n \}$% совпадала с четностью числа $%n$%, необходимо, чтобы четность числа арифметически путных подмножеств в $%\{0, \dots, n-1 \}$% совпадала с четностью числа $%n$%, Последнее условие я проверил для всех $%n \le 26$%. Вот эти числа: 1, 2, 5, 8, 15, 26, 45, 76, 135, 238, 425, 768, 1399, 2570, 4761, 8856, 16567, 31138, 58733, 111164, 211043, 401694, 766417, 1465488, 2807671, 5388782...

(5 Май '17 18:06) Urt

@Urt: а почему третье число равно 5? Видимо, я не понял обозначений. Ведь для {1,2,3} у нас будут только одноэлементные подмножества.

(5 Май '17 18:20) falcao

@falcao, это подмножества:$% \{0\}, \{1\}, \{2\}, \{0,2\}, \{1 ,2, 3\}.$% Я скорректировал комментарий (заменл n на n-1). Возможно, эта неточность внесла неясность.

(5 Май '17 18:28) Urt

@Urt: а почему одна задача будет эквивалентна другой?

(5 Май '17 18:36) falcao

@falcao, свойство для арифметически путных чисел - это только необходимое условие. Оно следует из того, что при подсчете числа геометрически путных чисел мы можем рассмотреть добавление в общее множество N числа вида $%p^n, (p$% - простое). При этом число геометрически путных чисел должно возрастать на нечетную величину. Значит, четность и нечетность числа геометрически путных чисел в прогресиях $% 1, p, \dots, p^n $% также должна чередоваться в зависимости от n.

(5 Май '17 18:55) Urt

@Urt: связь одной задачи с другой всё равно не до конца ясна -- даже в одну сторону. Понятно, что если есть m натуральных чисел, у которых произведение равно m-й степени, то это верно для любой простой "координаты" p. Однако m чисел у нас попарно различны, а в проекциях мы вполне можем получать какие-то координаты одинаковыми. Например, числа 3, 6, 12 в произведении дают куб, а координатно это будет (0,1), (1,1), (2,1).

(5 Май '17 19:17) falcao

@falcao, похоже, что доказательство свойства арифметически путных множеств потребует решения исходной задачи. Можно, конечно, положить p=2, но это пока решение не продвинуло. Беру timeout...

(6 Май '17 1:25) Urt
показано 5 из 12 показать еще 7
10|600 символов нужно символов осталось
2

Здесь доказательство от DeBill (dxdy) – именно то, которое хотелось найти!!! Приведу его, чтобы оно было...

«Среднее геометрическое нетривиального подмножества из чисел, не больших $%n$% , также не больше $%n$% . Если оно не входит в подмножество, добавим его к подмножеству - и получим новое "путнинское" (а если входит - удалим). (В двухэлементное - не входит). Поэтому все нетривиальные путные подмножества разбиваются на пары. Поэтому их кол-во - четно.» DeBill

ссылка

отвечен 6 Май '17 20:03

изменен 6 Май '17 20:05

1

Да, красиво! То есть тут изначально имелось в виду истинно олимпиадное решение. Забавно, что если бы задача с самого начала была сформулирована в утвердительной форме (доказать чётность, без учёта одноэлементных), то такое соответствие было бы найти психологически проще.

(6 Май '17 20:10) falcao
1

@falcao, я как раз пытался доказать эту четность без одноэлементных множеств. Доказательство проходило для арифметически путных множеств (также на основе обнаруженных симметрий). Однако обобщить этот результат на систему показателей степени не удалось.

(6 Май '17 20:20) Urt
2

@Urt: если одноэлементные сразу отбросить, и исходить из того, что "естественное" разбиение на пары точно имеется, то его не так трудно восстановить при анализе небольших значений n. Здесь, как и во многих других случаях, важное значение имеет вера в то, что объект поиска в самом деле существует. Вспомнился старый анекдот (в разных вариациях) про абсолютно чёрную кошку в абсолютно чёрной комнате :)

(6 Май '17 20:24) falcao

@Urt, @falcao, большое спасибо!

(12 Май '17 12:03) Аллочка Шакед
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,399
×1,114
×370
×211
×3

задан
2 Май '17 10:47

показан
719 раз

обновлен
12 Май '17 12:03

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru