Целочисленные точки в пространстве

[Xenia1996]

Какое наименьшее количество целочисленных точек нужно отметить в n-мерном пространстве, чтобы гарантированно нашлись две различные отмеченные точки A и B такие, что отрезок AB содержит целочисленную точку (не обязательно отмеченную) строго между A и B?

[Null]

$2^n+1$?

[Xenia1996]

Null в сообщении #430019 писал(а):

$2^n+1$?

У меня тоже вышло $2^n+1$
Но почему знак вопроса? Вы не уверены? Там, вроде, не так уж сложно (хоть и Putnam).

[worm2]

Красивая задачка.

[Xenia1996]

worm2 в сообщении #430053 писал(а):

Красивая задачка.

Я только одного не поняла. Что эта задача делает на Putnam Competition? Знаний, необходимых для её решения, достаточно уже в седьмом классе (принцип Дирихле).

Каждая из координат точки может быть либо чётной, либо нечётной. Всего $2^n$ вариантов. Если взять $2^n+1$ точек, то по принципу Дирихле, найдутся две точки, чётности всех координат которых совпадут. Середина отрезка между ними и будет искомой целочисленной точкой.
Я что-то упустила?

[MrDindows]

Не вижу доказательства того, что именно это число является наименьшим...
Но в принципе это мелочь. $n$-мерный куб со стороной $1$ имеет $2^n$ точек, которые нам нужны для примера)

[venco]

А в качестве $2^n$ точек можно взять вершины 1-ничного гиперкуба.

[Xenia1996]

venco в сообщении #430078 писал(а):

А в качестве $2^n$ точек можно взять вершины 1-ничного гиперкуба.

А на форуме Мехмата мне заявили, что задача сформулированна некорректно:

http://www.mathforum.ru/forum/read/1/35888/

[MrDindows]

Та это уже придирки к условию). Просто его не делали излишне нагромождённым.

А на скольких форумах вы постите задачи?)

[worm2]

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

[Xenia1996]

MrDindows в сообщении #430091 писал(а):

Та это уже придирки к условию). Просто его не делали излишне нагромождённым.

А на скольких форумах вы постите задачи?)

Именно эту задачу - ровно на трёх форумах. А вообще, как правило, ровно на двух.
Теперь вот про гиперкуб не смогу там написать, будет выглядеть, будто у Вас слизала, хотя, по-моему, пример с таким кубом очевиден.

-- Пт апр 01, 2011 20:16:03 --

worm2 в сообщении #430093 писал(а):

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

Спасибо
Сама с инглиша переводила.