2014 dxdy logo

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

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




На страницу 1, 2  След.
 
 Комбинаторная задача
Сообщение27.04.2015, 14:41 
У меня есть шесть друзей. За некоторое время каждый из них был у меня на обеде 7 раз, каждые двое встретились у меня на обеде 5 раз, каждые трое 4 раза, каждые четверо 3 раза, с каждыми пятью я обедал 2 раза, со всеми шестью 1 раз, каждый друг отсутствовал у меня на обеде 8 раз. Сколько раз я обедал один, сколько всего было обедов?

По принципу включений-исключений:
$N(\bar{a_1}\dots\bar{a_6})=N-\binom{1}{6}\cdot 7+\binom{4}{6}\cdot 5 - \binom{3}{6}\cdot 4 + \binom{4}{6}\cdot 3 - \binom{5}{6}\cdot 2 + 1$
В итоге мы получаем, что $13$ раз обедал не один: $N(\bar{a_1}\dots\bar{a_6})=N - 13$

Как использовать информацию, что "каждый друг отсутствовал у меня на обеде 8 раз"?

 
 
 
 Re: Комбинаторная задача
Сообщение27.04.2015, 18:48 
2old в сообщении #1008506 писал(а):
Как использовать информацию, что "каждый друг отсутствовал у меня на обеде 8 раз"?

Первый друг присутствовал 7 раз, отсутствовал 8 раз. Вопрос на засыпку: сколько всего было обедов?

 
 
 
 Re: Комбинаторная задача
Сообщение27.04.2015, 20:16 
mihiv
:facepalm: спасибо

 
 
 
 Re: Комбинаторная задача
Сообщение19.05.2015, 11:47 
добрый день!

2old
скажите, пожалуйста, у Вас описка в третьем слагаемом 2 из 6 пять раз, а у Вас 4 из 6 пять раз? не могли бы Вы объяснить почему некоторые Вы включаете, а другие исключаете?

кто-нибудь может объяснить решение, предложение Виленкиным? я совсем его не понимаю. пытаюсь нарисовать схему, но результата нет.

https://yadi.sk/i/sy27fB75gj3PG

 
 
 
 Re: Комбинаторная задача
Сообщение19.05.2015, 14:16 
Аватара пользователя
Ducmod в сообщении #1017099 писал(а):
в третьем слагаемом 2 из 6 пять раз, а у Вас 4 из 6 пять раз?

Но это ведь не принципиально, разве что из соображений наглядности. Понятно, что $C_6^2=C_6^4$ (очевидно, что нет разницы, выбрать 2 предмета левой рукой, а 4 правой, или наоборот).

Ducmod в сообщении #1017099 писал(а):
кто-нибудь может объяснить решение, предложение Виленкиным? я совсем его не понимаю.

Давайте разбирать по частям с самого начала не спеша. Но хоть что-то Вам должно быть понятно. Начнём с первого предложения.

 
 
 
 Re: Комбинаторная задача
Сообщение19.05.2015, 21:20 
Ducmod
Да это лучше в том же Виленкине, например, прочитать, про включения-исключения. Но если не строго, то понять совсем просто, Нарисуйте диаграмму Эйлера для двух множеств ( с непустым пересечением) и выпишите мощность объединения. Потом тоже самое с тремя и станет понятно.

 
 
 
 Re: Комбинаторная задача
Сообщение20.05.2015, 10:55 
2old в сообщении #1017466 писал(а):
Ducmod
Да это лучше в том же Виленкине, например, прочитать, про включения-исключения. Но если не строго, то понять совсем просто, Нарисуйте диаграмму Эйлера для двух множеств ( с непустым пересечением) и выпишите мощность объединения. Потом тоже самое с тремя и станет понятно.

спасибо, попробую.

-- 20.05.2015, 11:56 --

grizzly в сообщении #1017185 писал(а):
Ducmod в сообщении #1017099 писал(а):
в третьем слагаемом 2 из 6 пять раз, а у Вас 4 из 6 пять раз?

Но это ведь не принципиально, разве что из соображений наглядности. Понятно, что $C_6^2=C_6^4$ (очевидно, что нет разницы, выбрать 2 предмета левой рукой, а 4 правой, или наоборот).

Ducmod в сообщении #1017099 писал(а):
кто-нибудь может объяснить решение, предложение Виленкиным? я совсем его не понимаю.

Давайте разбирать по частям с самого начала не спеша. Но хоть что-то Вам должно быть понятно. Начнём с первого предложения.

спасибо. я самостоятельно изучаю, поэтому навыка пока нет, и не заметила сразу, что $C_6^2=C_6^4$ одно и тоже.
Вы правда готовы помочь пройтись по решению?

 
 
 
 Re: Комбинаторная задача
Сообщение20.05.2015, 11:28 
Аватара пользователя
Ducmod в сообщении #1017717 писал(а):
Вы правда готовы помочь пройтись по решению?

Конечно, что за странный вопрос. Я посмотрел решение -- мне оно понятно. Вопрос только в Вашем терпении и желании.
Я не вижу в данном решении какой-то скрытой идеи -- всё на виду, и если мы попытаемся идти по нему пошагово, то после двух-трёх разобранных предложений дальнейшая помощь Вам уже не понадобится. А если уже в начале пути возникнут трудности, мы просто уменьшим цифры в задаче, чтобы картинка решения стала доступна непосредственному умозрительному восприятию. Разберём упрощённую задачу и вернёмся к исходному условию.

-- 20.05.2015, 11:29 --

Итак, по первому предложению нужна помощь? Или озвучьте своё понимание, если оно есть, но Вы в нём не уверены.

 
 
 
 Re: Комбинаторная задача
Сообщение20.05.2015, 13:31 
grizzly в сообщении #1017736 писал(а):
Ducmod в сообщении #1017717 писал(а):
Вы правда готовы помочь пройтись по решению?

Конечно, что за странный вопрос. Я посмотрел решение -- мне оно понятно. Вопрос только в Вашем терпении и желании.
Я не вижу в данном решении какой-то скрытой идеи -- всё на виду, и если мы попытаемся идти по нему пошагово, то после двух-трёх разобранных предложений дальнейшая помощь Вам уже не понадобится. А если уже в начале пути возникнут трудности, мы просто уменьшим цифры в задаче, чтобы картинка решения стала доступна непосредственному умозрительному восприятию. Разберём упрощённую задачу и вернёмся к исходному условию.

-- 20.05.2015, 11:29 --

Итак, по первому предложению нужна помощь? Или озвучьте своё понимание, если оно есть, но Вы в нём не уверены.


Большое спасибо! ) желание огромное, а главное надежда пока есть. я не знаю, почему мне это так сложно дается (я не верю, что люди бывают такие несообразительные, мне кажется любой человек может все что угодно понять; поэтому я стараюсь).

Первое предложение:

Согласно условию задачи, обед со всеми шестью друзьями состоялся 1 раз.

С 5ью одновременно обедал 2 раза. Поскольку 5 можно выбрать из 6 шестью способами, то получается, что есть 12 вариантов выбора 5 друзей для 2х обедов. Но нужно ли считать варианты размещения друзей, то есть сколько раз можно выбрать по 5 из шести?

С другой стороны, я не совсем понимаю причинно-следственную связь, а именно "то еще по одному разу я обедал с каждой пятеркой друзей в отсутствие шестого".

Написала, но вдруг поняла: может быть в этом предложении нет какого-то сложного смысла и оно означает именно, что
1 раз обедал с 6
2 раза обедал с 5, то есть эти два раза исключают одного человека
Так?

Нет, не так, потому что дальше он пишет, что на "этих семи". По условию каждый обедал у него 7 раз.

 
 
 
 Re: Комбинаторная задача
Сообщение20.05.2015, 15:07 
Аватара пользователя
1) Да, со всеми шестью ровно 1 раз.
2) А вот с условием "с каждыми пятью -- 2 раза" нужно быть чуть внимательнее. Давайте посмотрим на одну такую пятёрку. Он с ними обедал 1 раз в составе шестёрки из прошлого пункта. И ещё 1 раз -- когда шестого с ними не было. И всё, это и есть те самые 2 раза с данной пятёркой.
3) А теперь посмотрим то же самое для каждой такой пятёрки. С каждой пятёркой 2 обеда. Первый обед (тот, что из п.1) у них всех повторяется один и тот же, а меняется второй: для каждой пятёрки он свой -- без шестого друга.

И это по первому предложению всё, не нужно ничего усложнять :)
Подытожим: один общий обед в п.1 и для каждой пятёрки ещё один свой обед (это ещё 6 обедов -- как Вы сами сказали, что есть 6 способов выбрать пятёрку друзей из шести). Вот и получается в сумме те самые 7 обедов, с которых начинается второе предложение в решении Виленкина.

Если с первым предложением понятно, пойдём дальше. Если нет, смело задавайте вопросы. (Пусть Вас не смущает, что я пока не отвечаю на все Ваши вопросы -- я их не всегда могу однозначно понять. Но это не означает, что к ним нельзя возвращаться.)

 
 
 
 Re: Комбинаторная задача
Сообщение20.05.2015, 15:27 
grizzly в сообщении #1017828 писал(а):
1) Да, со всеми шестью ровно 1 раз.
2) А вот с условием "с каждыми пятью -- 2 раза" нужно быть чуть внимательнее. Давайте посмотрим на одну такую пятёрку. Он с ними обедал 1 раз в составе шестёрки из прошлого пункта. И ещё 1 раз -- когда шестого с ними не было. И всё, это и есть те самые 2 раза с данной пятёркой.
3) А теперь посмотрим то же самое для каждой такой пятёрки. С каждой пятёркой 2 обеда. Первый обед (тот, что из п.1) у них всех повторяется один и тот же, а меняется второй: для каждой пятёрки он свой -- без шестого друга.

И это по первому предложению всё, не нужно ничего усложнять :)
Подытожим: один общий обед в п.1 и для каждой пятёрки ещё один свой обед (это ещё 6 обедов -- как Вы сами сказали, что есть 6 способов выбрать пятёрку друзей из шести). Вот и получается в сумме те самые 7 обедов, с которых начинается второе предложение в решении Виленкина.

Если с первым предложением понятно, пойдём дальше. Если нет, смело задавайте вопросы. (Пусть Вас не смущает, что я пока не отвечаю на все Ваши вопросы -- я их не всегда могу однозначно понять. Но это не означает, что к ним нельзя возвращаться.)


спасибо! теперь вижу.
к сожалению, есть вопросы.
согласно условию, обед со всеми 6-ью был только один.
а в отношении 5 друзей написано, что с "каждой пятеркой", то есть все 6 вариантов (5 из 6) комбинации друзей обедали по 2 раза.

тогда почему мы не оставляем только одну пятерку (какую-то), которая один раз обедала в рамках 6-ти и один раз без участия шестого? а остальные пять пятерок обедали по два раза.
если каждая пятерка один раз обедала в рамках шестерки, то и тогда обедов со всем 6-ью было 6, а не 1.
запуталась )

 
 
 
 Re: Комбинаторная задача
Сообщение20.05.2015, 15:55 
Аватара пользователя
Как я вижу, Вы неправильно понимаете, что означают эти разы.
Давайте на секунду отвлечёмся от задачи. И рассмотрим на простых примерах.

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

Другой пример. Пусть у автора только 3 друга (А, Б, В) и он пообедал 4 раза:
1) с А, Б, В;
2) с А, Б;
3) с А, В;
4) с Б, В.
Про эти обеды можно сказать так: со всеми я пообедал 1 раз, с каждыми двумя 2 раза, с каждым другом 3 раза (просто пересчитайте буквы в списке).
А можно сказать по-другому: со всеми я пообедал 1 раз, кроме того ещё с каждыми двумя по одному разу. (Вот в этом случае уже нельзя продолжить "кроме того, с каждым".)

Попытайтесь понять эти примеры и посмотреть, поможет ли это понимание понять Ваши последние вопросы.

 
 
 
 Re: Комбинаторная задача
Сообщение21.05.2015, 10:32 
grizzly в сообщении #1017844 писал(а):
Как я вижу, Вы неправильно понимаете, что означают эти разы.
Давайте на секунду отвлечёмся от задачи. И рассмотрим на простых примерах.

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

Другой пример. Пусть у автора только 3 друга (А, Б, В) и он пообедал 4 раза:
1) с А, Б, В;
2) с А, Б;
3) с А, В;
4) с Б, В.
Про эти обеды можно сказать так: со всеми я пообедал 1 раз, с каждыми двумя 2 раза, с каждым другом 3 раза (просто пересчитайте буквы в списке).
А можно сказать по-другому: со всеми я пообедал 1 раз, кроме того ещё с каждыми двумя по одному разу. (Вот в этом случае уже нельзя продолжить "кроме того, с каждым".)

Попытайтесь понять эти примеры и посмотреть, поможет ли это понимание понять Ваши последние вопросы.


Огромное спасибо ) я поняла. Сейчас напишу дальше

-- 21.05.2015, 11:43 --

Ducmod в сообщении #1018131 писал(а):
grizzly в сообщении #1017844 писал(а):
Как я вижу, Вы неправильно понимаете, что означают эти разы.
Давайте на секунду отвлечёмся от задачи. И рассмотрим на простых примерах.

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

Другой пример. Пусть у автора только 3 друга (А, Б, В) и он пообедал 4 раза:
1) с А, Б, В;
2) с А, Б;
3) с А, В;
4) с Б, В.
Про эти обеды можно сказать так: со всеми я пообедал 1 раз, с каждыми двумя 2 раза, с каждым другом 3 раза (просто пересчитайте буквы в списке).
А можно сказать по-другому: со всеми я пообедал 1 раз, кроме того ещё с каждыми двумя по одному разу. (Вот в этом случае уже нельзя продолжить "кроме того, с каждым".)

Попытайтесь понять эти примеры и посмотреть, поможет ли это понимание понять Ваши последние вопросы.


Перечитала, и снова не вполне понимаю, но зато очевиднее стало, что проблема пока не совсем в математике, а в … русском языке ))
Написано в задаче: "со всеми шестью обедал 1 раз". Я это читаю именно как написано, что был только 1 обед, на котором были все 6 друзей.

А дальше написано: "с каждыми пятью я обедал 2 раза" - эта фраза ставит меня в тупик. Я читаю, что поскольку "каждых" пятерок (то есть совокупность людей, равная 5, группа из 5) могло быть 6 вариантов, и с каждым из этих вариантов он обедал по 2 раза, тогда всего с пятерками он обедал 12 раз.

Дальше, Вы написали: "Тогда бы автор сказал про этот обед так: с шестью друзьями я обедал один раз, с каждой пятёркой -- один раз, с каждой четвёркой -- один раз, ..., с каждым другом -- 1 раз. Это всё верно, хотя обед был только один.". Насколько я понимаю, Вы здесь говорите именно про один единственный обед, в рамках которого присутствовали все 6 человек, и в зависимости от того, как мы рассматриваем эту шестерку, получается, что на этом обеде были и все варианты пятерок (прямо на обеде можно было бы "перетасовать" всех), все варианты четверок (тоже самое, потому что на этом обеде в зависимости от того, как считать, можно было бы пересчитать все варианты четверок) и так далее.

В этом смысл этой непонятной мне фразы "с каждой пятеркой"? Правильно тогда я понимаю, что слово "каждая" как раз говорит о том, что на одном общем обеде можно как угодно "пересчитать" присутствующих? Если так, то тогда я поняла, почему каждая пятерка обедала один раз в рамках шестерки (даже не знаю как это назвать - в более абстрактном, математическом смысле, да?) и далее было 6 обедов, на каждом из которых была только 1 пятерка. Тогда всего 7 обедов.

Я не уверена, что хорошо объясняю свою мысль.

-- 21.05.2015, 11:56 --

Сейчас думаю над следующим, но поняла, что видимо это loop :) как в языках программирования, или как в фильме Inception (Начало) ))

-- 21.05.2015, 12:07 --

Следующее:
"Но тогда на этих семи обедах с каждыми четырьмя я обедал именно 3 раза (два обеда впятером и 1 обед вшестером)"

1 обед - все варианты 4-ок в рамках общего обеда со всеми шестью друзьями (также как и с пятерками ранее)

1 обед - все варианты 4-ок в рамках обеда в каждой пятерке, но это тот же самый первый общий обед, на котором
присутствуют все 6 друзей, среди которых все варианты 5-ок, среди которых все варианты 4-ок

1 обед - 4ки в рамках обеда каждой пятерки без шестого друга. Здесь я снова не понимаю:

с пятерками 6 обедов; на каждом из них можно также предположить, что есть все варианты четверок,
то есть по пять 4-ок на каждом из 6 обедов; почему же обед только один?

 
 
 
 Re: Комбинаторная задача
Сообщение21.05.2015, 11:29 
Аватара пользователя
Всё нормально у Вас с объяснением мысли :)
Дальше откомментирую по порядку Вашего сообщения, не злоупотребляя цитированием.

Да, очевидно, что основная сложность у Вас пока не в математике, а в трактовке написанного. Понятно, что в бытовой речи такие объяснения никто не будет использовать, поэтому приходится воспринимать как некоторую абстракцию (здесь лучше подошло бы слово "формализм", а не абстракция).

Подтверждаю, что Ваше (первоначальное) понимание про 12 обедов с пятёрками ошибочно.

В следующем абзаце Вы были абсолютно точны и правы. И у меня и в задаче дела обстоят именно так.

Ну и Ваш окончательный вывод в целом верен, только привязка к слову "каждая" в нём не совсем уместна. Правильно было бы с Вашей стороны сказать так:
Ducmod в сообщении #1018131 писал(а):
В этом смысл этой непонятной мне фразы "с каждой пятеркой"? Правильно тогда я понимаю,что слово "каждая" как раз говорит о том,что на одном общем обеде можно как угодно "пересчитать" присутствующих? ...

Я ещё раз подробнее остановлюсь на этом. Такая вот трактовка (когда мы учитываем все варианты на одном обеде) она считается (формально) верной по умолчанию. Я ещё раз приведу пример с тремя друзьями, немного его видоизменив.
Пример 3. Пусть у автора только 3 друга (А, Б, В) и он пообедал 3 раза:
1) с А, Б, В;
2) с А, Б;
3) с Б, В.
Про эти обеды мы должны сказать так: со всеми я пообедал 1 раз, с друзьями А и Б я обедал 2 раза, с друзьями Б и В тоже 2 раза. (И наоборот -- по этому описанию мы можем однозначно восстановить сколько и каких было обедов.)
Внимание! когда мы говорим "обедал с А и Б" это не означает, что там больше никого не было. Даже в разговорной речи, чтобы собеседник понял, что кроме А и Б на обеде никого не было, нужно это оговаривать: например, говорить "только с А и Б". Поэтому и говорят: "обедал раз со всеми тремя, а кроме того ещё и с А и Б отдельно".

 
 
 
 Re: Комбинаторная задача
Сообщение22.05.2015, 10:24 
grizzly в сообщении #1018138 писал(а):
Всё нормально у Вас с объяснением мысли :)
Дальше откомментирую по порядку Вашего сообщения, не злоупотребляя цитированием.

Да, очевидно, что основная сложность у Вас пока не в математике, а в трактовке написанного. Понятно, что в бытовой речи такие объяснения никто не будет использовать, поэтому приходится воспринимать как некоторую абстракцию (здесь лучше подошло бы слово "формализм", а не абстракция).

Подтверждаю, что Ваше (первоначальное) понимание про 12 обедов с пятёрками ошибочно.

В следующем абзаце Вы были абсолютно точны и правы. И у меня и в задаче дела обстоят именно так.

Ну и Ваш окончательный вывод в целом верен, только привязка к слову "каждая" в нём не совсем уместна. Правильно было бы с Вашей стороны сказать так:
Ducmod в сообщении #1018131 писал(а):
В этом смысл этой непонятной мне фразы "с каждой пятеркой"? Правильно тогда я понимаю,что слово "каждая" как раз говорит о том,что на одном общем обеде можно как угодно "пересчитать" присутствующих? ...

Я ещё раз подробнее остановлюсь на этом. Такая вот трактовка (когда мы учитываем все варианты на одном обеде) она считается (формально) верной по умолчанию. Я ещё раз приведу пример с тремя друзьями, немного его видоизменив.
Пример 3. Пусть у автора только 3 друга (А, Б, В) и он пообедал 3 раза:
1) с А, Б, В;
2) с А, Б;
3) с Б, В.
Про эти обеды мы должны сказать так: со всеми я пообедал 1 раз, с друзьями А и Б я обедал 2 раза, с друзьями Б и В тоже 2 раза. (И наоборот -- по этому описанию мы можем однозначно восстановить сколько и каких было обедов.)
Внимание! когда мы говорим "обедал с А и Б" это не означает, что там больше никого не было. Даже в разговорной речи, чтобы собеседник понял, что кроме А и Б на обеде никого не было, нужно это оговаривать: например, говорить "только с А и Б". Поэтому и говорят: "обедал раз со всеми тремя, а кроме того ещё и с А и Б отдельно".


что-то проясняется )) спасибо )

получается, что

с каждой 4-кой было 3 обеда (для каждой 4ки):
1) 1 обед в общей 6ке
2) 1 обед в 5ке, которая внутри 6ки
3) 1 обед в 5ке, которая без шестого человека

с каждой 3-кой было 4 обеда (для каждой 4ки):
1) 1 обед в 5ке, которая внутри 6ки
2) 1 обед в 5ке, которая без шестого человека
3) 1 обед в 4ке, которая внутри 5ки, которая внутри 6ки
4) 1 обед в 4ке, которая внутри 5ки без шестого человека

с каждым 2-м было 5 обедов:
1) 1 обед в 5ке, которая внутри 6ки
2) 1 обед в 4ке, которая внутри 5ки, которая внутри 6ки
3) 1 обед в 4ке, которая внутри 5ки без шестого человека
4) 1 обед в 3ке, которая внутри 4ки из пункта 2
5) 1 обед в 3ке, которая внутри 4ки из пункта 3
это верно? )

 
 
 [ Сообщений: 24 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group