2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Целочисленные точки в пространстве
Сообщение01.04.2011, 17:14 


01/10/10

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

 Профиль  
                  
 
 
Сообщение01.04.2011, 18:01 
Заслуженный участник


12/08/10
1677
$2^n+1$?

 Профиль  
                  
 
 Re:
Сообщение01.04.2011, 18:06 


01/10/10

2116
Израиль (племянница БизиБивера)
Null в сообщении #430019 писал(а):
$2^n+1$?

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

 Профиль  
                  
 
 
Сообщение01.04.2011, 19:08 
Заслуженный участник
Аватара пользователя


01/08/06
3131
Уфа
Красивая задачка.

 Профиль  
                  
 
 Re:
Сообщение01.04.2011, 19:29 


01/10/10

2116
Израиль (племянница БизиБивера)
worm2 в сообщении #430053 писал(а):
Красивая задачка.

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

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

 Профиль  
                  
 
 
Сообщение01.04.2011, 19:42 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Целочисленные точки в пространстве
Сообщение01.04.2011, 19:52 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Целочисленные точки в пространстве
Сообщение01.04.2011, 19:57 


01/10/10

2116
Израиль (племянница БизиБивера)
venco в сообщении #430078 писал(а):
А в качестве $2^n$ точек можно взять вершины 1-ничного гиперкуба.

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

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

 Профиль  
                  
 
 
Сообщение01.04.2011, 20:07 
Заслуженный участник


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

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

 Профиль  
                  
 
 
Сообщение01.04.2011, 20:11 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re:
Сообщение01.04.2011, 20:15 


01/10/10

2116
Израиль (племянница БизиБивера)
MrDindows в сообщении #430091 писал(а):
Та это уже придирки к условию). Просто его не делали излишне нагромождённым.

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

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

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

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 11 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: drzewo


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group