2
1

Из чисел $% 1 \cdots 100 $% выбираются без возвращения $% k $% чисел. Вероятность что их сумма четная равна $% \frac{1}{2} $% . Найти $%k$% при которых это возможно. Решал так: $% \frac{1}{2} = \frac{A_l}{A} $%. $% A_l $% - количество четных сумм из $%k$%-выборки.В четной выборке нечетных чисел должно быть четное количество. Тогда $% \frac{1}{2} = \frac{ C_{50}^{2l}C_{50}^{k-2l} }{C_{100}^k} $%. Но как упростить этого монстра?

задан 3 Июн '13 14:01

изменен 7 Июн '13 18:44

Deleted's gravatar image


126

@voipp, Если вы получили исчерпывающий ответ, отметьте его как принятый.

(26 Апр '14 15:09) Angry Bird
10|600 символов нужно символов осталось
2

Начнём с лёгкого случая. Пусть $%k$% нечётно. Докажем, что в этом случае вероятность равна $%1/2$%. Без ограничения общности можно считать, что $%k\ge50$% с учётом возможности перейти к дополнению, а также чётности суммы всех чисел. Это касается как чётных, так и нечётных $%k$%.

Все случаи можно разбить на типы $%(0,k)$%, $%(1,k-1)$%, ..., $%(s,t)$%, ..., $%(k,0)$%, где $%s+t=k$%, где $%s$% -- количество чётных, а $%t$% -- количество нечётных чисел среди того, что мы взяли. Чётность суммы совпадает с чётностью $%t$%, и здесь случай $%(0,k)$%, где $%k$% нечётно, симметричен случаю $%(k,0)$%, где $%0$% чётно; $%(k-1,1)$% симметричен $%(1,k-1)$%, и так далее, а в середине ничего не остаётся. Это доказывает, что случаев с чётным $%t$% столько же, сколько и с нечётным.

Для чётных значений $%k$% аналогичное рассуждение уже не проходит, так как симметричные случаи относятся к одной и той же категории. Поэтому имеет смысл прибегнуть к подсчётам. Нас интересует следующая знакочередующаяся величина: $$C_{50}^0C_{50}^k-C_{50}^1C_{50}^{k-1}+\cdots+(-1)^mC_{50}^mC_{50}^{k-m}+\cdots+C_{50}^kC_{50}^0.$$ Смысл её понятен: это разность между числом способов выбрать $%k$% чисел с чётной суммой и числом способов с нечётной суммой. Мы сравниваем её с нулём, что эквивалентно Вашему сравнению "плюсовой" части этой суммы с $%1/2$%. Точное значение рассматриваемой суммы можно найти при помощи производящих функций. Введём функцию $$f(x)=(1+x)^{50}=C_{50}^0+C_{50}^1x+\cdots+C_{50}^mx^m+\cdots+C_{50}^{50}x^{50}.$$ Если мы теперь умножим её на $%f(-x)=(1-x)^{50}$%, то получим $%(1-x^2)^{50}$%, и из вида "развёрнутых" сумм ясно, что при их перемножении интересующая нас величина будет равна коэффициенту при $%x^k$% у многочлена $%(1-x^2)^{50}$%. Очевидно, что этот коэффициент равен $%(-1)^{k/2}C_{50}^{k/2}$%. Уже отсюда ясно, что это ненулевая величина. Легко понять, что она положительна тогда и только тогда, когда $%k$% делится на $%4$%, то есть в этом случае вероятность выбрать числа с чётной суммой будет чуть больше $%1/2$%, а при нечётном $%k/2$% более вероятным является выбор чисел с нечётной суммой (как в случае $%k=2$%).

Ответ наводит на мысль о том, что здесь возможно какое-то кодирование, устанавливающее симметрию между большинством вариантов, но я пока не знаю, как оно выглядит. В любом случае, расхождение с $%1/2$% весьма незначительно -- особенно при $%k$% близких к $%50$%.

Добавление. Я придумал прямое комбинаторное доказательство для случая чётного $%k$%, не использующее вычислений. Разобьём все числа от 1 до 100 на пары: $%\{1,2\}$%, $%\{3,4\}$%, ..., $%\{99,100\}$%. Каждое $%k$%-элементное подмножество отнесём к одному из двух типов. У подмножеств первого типа каждая пара либо целиком входит в это подмножество, либо целиком не входит. Ясно, что число таких подмножеств равно $%C_{50}^{k/2}$%: из $%50$% пар мы выбираем $%k/2$%, объединяя которые, получаем $%k$%-элементное подмножество. У всех таких подмножеств чётность суммы чисел совпадает с чётностью числа $%k/2$%, так как именно столько нечётных чисел туда входит.

Все остальные подмножества отнесём ко второму типу. Для каждого из них выберем наименьшее $%m$% от $%1$% до $%50$%, для которого один из элементов $%2m-1$%, $%2m$% входит в подмножество, а один не входит (в любом порядке). Совершим в этом случае обмен: если $%2m-1$% входит, то обменяем его на $%2m$%, а если он не входит, то обменяем $%2m$% на $%2m-1$%. Ясно, что этим установлена биекция между множеством подмножеств второго типа с чётной суммой и множеством подмножеств с нечётной суммой, так как в результате обмена чётность суммы меняется. В итоге разница в количестве определяется подмножествами первого типа, которых имеется $%C_{50}^{k/2}$%, и где чётность суммы одна и та же.

ссылка

отвечен 3 Июн '13 17:03

изменен 3 Июн '13 19:28

10|600 символов нужно символов осталось
0

А нельзя решать следующим образом:

Пусть событие $%A$% - сумма всех чисел чётная, $%B$% - сумма всех чисел нечётная.

Очевидно, что $%A\cap B=\emptyset, A\cup B=\Omega$%, где $%\Omega$% - найдена сумма чисел.

Таким образом, $%A$% и $%B$% образуют полную группу равновероятных событий. Далее классическое определение.

ссылка

отвечен 4 Июн '13 12:49

изменен 4 Июн '13 12:56

А откуда следует, что события равновероятные? Мы же не можем рассуждать по принципу "либо встречу (динозавра), либо нет"? События здесь зависят от параметра $%k$%. Понятно, что если $%k=1$%, то вероятность выбрать чётное или нечётное число (оно же будет здесь суммой выбранных чисел в количестве одной штуки) равна 1/2. Но если $%k=100$%, мы гарантированно получаем чётное число как сумму всех 100 чисел. В общем случае тут нет симметрии, то есть нет равновероятных исходов.

(4 Июн '13 13:56) falcao

Решил задачу другим путем: Для искомого k количество четных и нечетных сумм одинаково. Пусть $%k$% нечетно и пусть $%Ч,Н$% - кол-во четных и нечетных чисел в выборке. Если Одних чисел четное число, то других - нечетное. Можно заметить, что в выборке, где Ч-чисел нечетное кол-во и Н-чисел четное число сумма есть четное число. Если наоборот, то сумма есть нечетное число. Ч и Н числа равнозначны , поэтому очевидно, что в этом случае вероятность равна половине.

(6 Июн '13 22:26) voipp

Можно каждой выборке сопоставить выборку по такому правилу : если сумма четная, то к каждому числу которое вошло в сумму прибавить 1 , 100 станет 1. Если нечетная - отнять 1. Очевидно, что это изоморфизм. Рассмотрим теперь четное k. Четных и нечетных может быть либо четное число в одной выборке либо нечетное. дальше я не знаю...

(6 Июн '13 22:45) voipp

@voipp: а чем Вас не устраивает моё рассуждение? Случай нечётного $%k$% очевиден, а для чётного в явной форме строится биекция, оставляющая в стороне $%C_n^{k/2}$% вариантов и дающая асимметричный эффект.

(6 Июн '13 22:49) falcao
10|600 символов нужно символов осталось
0

Я правильно понял условие? Найти k, при которых вероятность четной суммы будет 1/2?

Ответ - при всех.

Пусть четные числоа написаны на белых шарах , а несчетные на черных, Посчитайте вероятность достать четное число черных шаров из мешка с K=2N черными и K=2N белыми. Она равна 1/2. Известное свойство ком,инаторной суммы: $$\\C_{n}^{0}+C_{n}^{2}+C_{n}^{4}+...+C_{n}^{2k}+... =
C_{n}^{1}+C_{n}^{3}+C_{n}^{5}+...+C_{n}^{2k+1}+... =
2^{n-1}$$

Надо только отдельно оговорить, случай, когда достают все шары (или ни одного). Тогда четность суммы всегда предопределена и определятся числом черных шаров.

ссылка

отвечен 7 Июн '13 10:25

изменен 7 Июн '13 11:53

Вероятность не равна 1/2, если мы достаём $%k$% чисел, где $%k$% чётно. Например, если $%k=100$%, то вероятность получить чётную сумму, очевидно, равна единице: это будет сумма всех чисел. Можно также вручную исследовать случай $%k=2$%, когда извлекаются две карточки: вероятность того, что сумма окажется нечётной, больше вероятности того, что сумма будет чётной. Выписанное Вами равенство показывает, что подмножеств с чётным числом элементов имеется столько же, сколько с нечётным, но это совсем другая задача.

(7 Июн '13 11:31) falcao

Вероятность не равна 1/2,

Я условие правильно понял?
Если правильно, то почему не равна?

Например, если k=100,

Да если достаём все шары, то вероятность, очевидно определяется суммой. Этот случай я оговаривал, но нельзя на его основании отвергать все доказательство для всех остальных?

(7 Июн '13 11:50) behemothus

Для каждого $%k$% возникает отдельная задача. Если $%k$% нечётно, то вероятность равна $%1/2$%. Если $%k$% чётно, то вероятность НЕ равна $%1/2$%. См. мой ответ, где это доказывается. В качестве частного случая можно рассмотреть $%k=2$%, чтобы стал виден эффект несовпадения. Пусть карточки достаются не вместе, а друг за другом (это равносильно). Тогда вариант ЧЧ может быть в $%50\cdot49$% случаях, и вариант НН в стольких же. Варианты же ЧН и НЧ, где сумма нечётна, возникают в $%50\cdot50$% и $%50\cdot50$% случаях. При $%k=2$% вероятность нечётной суммы больше.

(7 Июн '13 12:07) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,747

задан
3 Июн '13 14:01

показан
2278 раз

обновлен
26 Апр '14 15:09

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

по почте:

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

по RSS:

Ответы

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

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