Найти вероятность

[dima_1985]

Из множества $\left\lbrace1,..., 2n\right\rbrace$ случайным образом выбирается $n+1$ элемент.С какой вероятностью среди них найдутся два таких элемента, что один делится на другой? Посмотрел при не больших $n$ и сделал вывод, что вероятность будет $1$. Как доказать это для произвольного $n$? Возьмем $n$ элементов из $\left\lbrace n+1,..., 2n\right\rbrace$. Из этого множества ни один элемент не делится на другой($2(n+1)>2n$).Любой элемент из $\left\lbrace n+1,..., 2n\right\rbrace$ можно представить как $ki$, где $k\in \mathbb{N} $,а $i \in \left\lbrace 1,..., n\right\rbrace $. Вот тут два вопроса 1) почему такое разбиение исходного множество на $2$ является оптимальным2) любой элемент из $\left\lbrace n+1,..., 2n\right\rbrace$ можно представить как $ki$ ? Это правильное направление к решению или тут нужно действовать по другому ?

[mihaild]

dima_1985 в сообщении #1553657 писал(а):

Любой элемент из $\left\lbrace n+1,..., 2n\right\rbrace$ можно представить как $ki$, где $k\in \mathbb{N} $,а $i \in \left\lbrace 1,..., n\right\rbrace $.

И даже можно сказать что $i \in \{1\}$. Только непонятно, что вам это даст.

Доказывать по индукции. Пусть нам принесли $n+1$-элементное подмножество множества $\{1, \ldots, 2n\}$, в котором ни один элемент не делится на другой. Как из него изготовить $n$-элементное подмножество множества $\{1, \ldots, 2n-2\}$ с тем же свойством?

[nnosipov]

Можно также каждый из $n+1$ выбранных элементов записать в виде $2^kl$, где $l$ нечетно, и воспользоваться принципом Дирихле.

dima_1985 в сообщении #1553657 писал(а):

Любой элемент из $\left\lbrace n+1,..., 2n\right\rbrace$ можно представить как $ki$, где $k\in \mathbb{N} $,а $i \in \left\lbrace 1,..., n\right\rbrace $.

Возможно, Вы имели в виду следующее утверждение: для любого $a \in \{1,2,\ldots,n\}$ существует такое $b \in \{n+1,\ldots,2n\}$, что $b$ делится на $a$.

[dima_1985]

Сделаем предположение, что из $\left\lbrace 1,...,2n \right\rbrace$ можно взять $n+1$ элемент ни один элемент не делится на другой(база индукции). Шаг индукции: из
$\left\lbrace 1,...,2n-2 \right\rbrace$ (из исходного множества удалить два последних элемента) можно выбрать $n$ элемент ни один элемент не делится на другой. При $n = 1 $ множество будет состоять из $\left\lbrace 1,2 \right\rbrace$ элементов нам надо будет взять 2 которые не делятся друг на друга. Это сделать нельзя. Исходное утверждение не верно.

-- 30.04.2022, 15:52 --

nnosipov в сообщении #1553673 писал(а):

Возможно, Вы имели в виду следующее утверждение: для любого $a \in \{1,2,\ldots,n\}$ существует такое $b \in \{n+1,\ldots,2n\}$, что $b$ делится на $a$.

Да, это я и хотел сказать.

[mihaild]

dima_1985 в сообщении #1553681 писал(а):

Шаг индукции: из $\left\lbrace 1,...,2n-2 \right\rbrace$ (из исходного множества удалить два последних элемента) можно выбрать $n$ элемент ни один элемент не делится на другой

Это нельзя называть "шагом индукции" (шаг индукции - это переход к большему, а не к меньшему). Плюс удаление двух последних элементов не обязательно оставляет вас с $n$ выбранными - возможно останется только $n - 1$ выбранный.

Правильная схема должна быть примерно такая.
База индукции: при $n = 1$ нельзя выбрать элементы нужным образом (очевидно).
Шаг индукции: пусть при $n = k$ нельзя выбрать элементы нужным образом. Тогда докажем, что при $n = k+1$ тоже нельзя выбрать элементы нужным образом - а именно, соорудим из такой выборки выборку для $n = k$, и придем к противоречию с предположением индукции.

[TOTAL]

Пусть нам принесли $n+1$-элементное подмножество множества $\{1, \ldots, 2n\}$, в котором ни один элемент не делится на другой. Удвоим самый маленький элемент. Получим подмножество, в котором тоже ни один не делится на другой.

[dima_1985]

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

Тогда докажем, что при $n = k+1$

множество у нас получится $\left\lbrace 1...2k-1,2k,2(k+1)-1,2(k+1)\right\rbrace$. Для $n=k$ приняли за утверждение. Как для себя я это понял(дальше мысли в слух). Берем проверяем для маленьких $n=1,2,3,...$ далее делаем предположение, что это верно для произвольного $n=k$. Когда переходим к шагу индукции $n=k+1$ мы видим, что множество $\left\lbrace 1...2k-1,2k,2(k+1)-1,2(k+1)\right\rbrace$ по сути то же самое, что и при $n=k$ так как $k$ произвольное. Так как при $n=k$ нельзя выбрать $k+1$ элемент, что ни один элемент не делиться на другой. При $n=k+1$ нельзя выбрать $k+2$ элемента, что ни один элемент не делиться на другой.

[mihaild]

dima_1985, вы знаете, как устроены доказательства по индукции?
У нас есть некоторое утверждение $P(n)$, зависящее от числового параметра $n$. Мы как-то доказываем $P(1)$ и еще доказываем, что для любого $n$ верно, что из $P(n)$ (которое в данном контексте называется предположением индукции) следует $P(n + 1)$ (сама импликация $P(n) \rightarrow P(n + 1)$ называется шагом индукции). Тогда $P(n)$ выполнено для всех $n$.
Никаких "т.к. $k$ произвольное" и "сути" там нет.
Я предлагал доказать следующее утверждение: если $k > 1$ и из множества $\{1, \ldots, 2k+2\}$ можно выбрать $k + 2$ элементов, то из множества $\{1, \ldots, 2k\}$ можно выбрать $k + 1$ элемент.

Впрочем, идея TOTAL гораздо проще.

[melnikoff]

ИМХО, проще всего так.
Разбиваем исходное множество на $n$ "корзин": $\lbrace{k, 2k: k < n+1\rbrace}$.
По принципу Дирихле при выборе любых $n+1$ элементов как минимум 2 из них будут взяты из одной корзины.

[nnosipov]

melnikoff в сообщении #1554627 писал(а):

Разбиваем исходное множество на $n$ "корзин": $\lbrace{k, 2k: k < n+1\rbrace}$.

А ничего, что корзины пересекаются? (И, как следствие, их объединение не дает все множество?)

[Gagarin1968]

melnikoff в сообщении #1554627 писал(а):

По принципу Дирихле при выборе любых $n+1$ элементов как минимум 2 из них будут взяты из одной корзины.

Принцип Дирихле не будет работать в условиях пересекающихся множеств.

[melnikoff]

nnosipov, Gagarin1968, да, логично...

[dima_1985]

Из множества $\left\lbrace1,..., 2n\right\rbrace$ случайным образом выбирается $n+1$ элемент. Обозначим множество из $n+1$ элементов $A$. Каждый четный элемент множества $A$ разделим на $2^p$ так, чтобы частное было не четно. Обозначим новое множество $A'$. В $A'$ содержится $n+1$ нечётных элементов. Каждый элемент из $A'$ меньше $2n$. Следует, что хотя бы два элемента в $A'$ совпадают. Обозначим совпадающие элементы $m$. Следует, что в $A$ есть два числа $2^im$ и $2^jm$.