2014 dxdy logo

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

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


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 Странный пример задачки по комбинаторике
Сообщение24.03.2016, 11:54 
Аватара пользователя


05/01/13

3968
В процессе шатания по сети наткнулся вот на эту страничку:
Общие правила комбинаторики

И там кое-что вынесло мне мозг. :) Цитирую:

Цитата:
Пример. Переплетчик должен переплести $12$ различных книг в красный, зеленый и коричневые переплеты. Сколькими способами он может это сделать?

Решение. Имеется $12$ книг и $3$ цвета, значит по правилу произведения возможно $12 \cdot 3 = 36$ вариантов переплета.

Сколько я ни думал, у меня не получается такого же рассуждения, как у автора задачи. :) Мне кажется, так могло бы быть только в том случае, если бы переплётчику надо было переплести одну из $12$ книг. Но никак не все $12$.

Если надо переплести $12$ книг, каждую в один из трёх цветов на выбор, то количество возможных способов, по-моему, должно быть $3^{12} = 531441$. (Ну, мне так интуитивно кажется.)

Если же внимательнее приглядеться к формулировке задачи: "красный, зелёный и коричневые переплёты", то можно предположить, что у переплётчика есть один зелёный, один красный и до фига коричневых переплётов. :) Соответственно, десять из $12$ книг будут в итоге иметь коричневый переплёт, ещё одна — зелёный, и одна — красный. И тогда, если исходить из того, что коричневые переплёты неразличимы между собой, у нас всё сводится к $12 \cdot 11 = 132$ возможным вариантам. (Вроде бы.)

Как бы то ни было, предлагаемого решения не выходит никак! Может, я излишне самонадеян, но-моему, всё-таки сама задача сформулирована некорректно.

И если так, то где можно почитать нормально об азах комбинаторики?.. Подскажите хорошую книжку, пожалуйста. :)

 Профиль  
                  
 
 Re: Странный пример задачки по комбинаторике
Сообщение24.03.2016, 12:04 
Аватара пользователя


04/10/15
291
Так ведь книги все одинаковые. Есть $12$ книг, $3$ цвета: берем $1$ книгу, её либо в красный, либо в зеленый, либо в коричневый, вторую и все последующие аналогично, итого $12\cdot3=36$, то есть если мы вначале $3$ книги покрасим в красный или в конце - всё равно.
А книга - "Комбинаторика" Виленкин Н.Я.

 Профиль  
                  
 
 Re: Странный пример задачки по комбинаторике
Сообщение24.03.2016, 12:13 
Заслуженный участник
Аватара пользователя


09/09/14
6328
iou в сообщении #1108771 писал(а):
Так ведь книги все одинаковые.

 Профиль  
                  
 
 Re: Странный пример задачки по комбинаторике
Сообщение24.03.2016, 12:19 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
iou в сообщении #1108771 писал(а):
Так ведь книги все одинаковые.
А в задаче сказано, что
Цитата:
Переплетчик должен переплести $12$ различных книг.
Вот и понимай, как хочешь. Простор для интерпретации открыт.
Denis Russkih в сообщении #1108766 писал(а):
Как бы то ни было, предлагаемого решения не выходит никак!
После объяснения, данного iou, стало понятно, как можно его получить?
Denis Russkih в сообщении #1108766 писал(а):
всё-таки сама задача сформулирована некорректно.
Не совсем так. Она сформулирована недостаточно чётко; это не одно и то же.
Denis Russkih в сообщении #1108766 писал(а):
Подскажите хорошую книжку, пожалуйста.
Ф. А. Новиков. Дискретная математика. "Питер", 2011. Гл. 5. "Комбинаторика".

 Профиль  
                  
 
 Re: Странный пример задачки по комбинаторике
Сообщение24.03.2016, 12:27 
Заслуженный участник
Аватара пользователя


13/08/08
14494
У меня такая интерпретация: Переплётчик хочет подарить подруге книжку в красиво сделанном переплёте. Вариантов книг 12, вариантов переплёта 3. Вариантов подарка 36.
+++ 14:22 Ой, у ТС уже есть такая версия. Ну тогда скажем, что составитель задачи торопился и.

 Профиль  
                  
 
 Re: Странный пример задачки по комбинаторике
Сообщение24.03.2016, 12:49 
Заслуженный участник
Аватара пользователя


18/09/14
4962
gris в сообщении #1108779 писал(а):
У меня такая интерпретация: Переплётчик хочет подарить подруге книжку в красиво сделанном переплёте. Варинтов книг 12, вариантов переплёта 3. Вариантов подарка 36.

Вы хороший адвокат. Нашли оправдание неверному решению :D
Но всё-таки исходная цитата звучит вполне чётко:
Цитата:
Пример. Переплетчик должен переплести 12 различных книг в красный, зеленый и коричневые переплеты. Сколькими способами он может это сделать?

Решение. Имеется 12 книг и 3 цвета, значит по правилу произведения возможно 12*3=36 вариантов переплета.

Он должен переплести не одну книгу, а 12 различных книг.
Поэтому приведённое там решение неверно. А ТС совершенно прав:
Denis Russkih в сообщении #1108766 писал(а):
должно быть $3^{12} = 531441$.

 Профиль  
                  
 
 Re: Странный пример задачки по комбинаторике
Сообщение24.03.2016, 13:13 
Заслуженный участник
Аватара пользователя


01/09/13
4648
iou в сообщении #1108771 писал(а):
Так ведь книги все одинаковые.

Если все книги одинаковые (тождественные), то ответ снова не такой - задача тогда эквивалентна делению отрезка на три, и ответ будет $13\cdot7$ :-)

 Профиль  
                  
 
 Re: Странный пример задачки по комбинаторике
Сообщение24.03.2016, 14:39 


08/05/08
600
Если почитать тему перед этой задачей там, то примерно это и есть правильный ответ:
gris в сообщении #1108779 писал(а):
У меня такая интерпретация: Переплётчик хочет подарить подруге книжку в красиво сделанном переплёте. Вариантов книг 12, вариантов переплёта 3. Вариантов подарка 36.

 Профиль  
                  
 
 Re: Странный пример задачки по комбинаторике
Сообщение24.03.2016, 14:46 
Заслуженный участник
Аватара пользователя


18/09/14
4962
ET в сообщении #1108795 писал(а):
Если почитать тему перед этой задачей там, то примерно это и есть правильный ответ:

Прочитал. Ничего нового не обнаружил. Ответ неправильный - при той формулировке задачи, которая в действительности дана.

 Профиль  
                  
 
 Re: Странный пример задачки по комбинаторике
Сообщение24.03.2016, 15:36 
Заслуженный участник


27/04/09
28128
Если хочется решать вопрос голосованием, я присоединюсь к голосам о недвусмысленности формулировки задачи. Читается однозначно — а если что-то приписать, можно будет добиться только нульзначного чтения (противоречия в условии).

 Профиль  
                  
 
 Re: Странный пример задачки по комбинаторике
Сообщение24.03.2016, 16:53 


08/05/08
600
Mihr в сообщении #1108796 писал(а):
ET в сообщении #1108795 писал(а):
Если почитать тему перед этой задачей там, то примерно это и есть правильный ответ:

Прочитал. Ничего нового не обнаружил. Ответ неправильный - при той формулировке задачи, которая в действительности дана.

Ответ при той формулировка, разумеется, неправильный. Правильна интерпретация gris

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


13/08/08
14494
Всё же ТС это и предположил.
Denis Russkih в сообщении #1108823 писал(а):
Мне кажется, так могло бы быть только в том случае, если бы переплётчику надо было переплести одну из 12 книг.

 Профиль  
                  
 
 Re: Странный пример задачки по комбинаторике
Сообщение24.03.2016, 18:24 
Аватара пользователя


05/01/13

3968
iou в сообщении #1108771 писал(а):
"Комбинаторика" Виленкин Н.Я.

Благодарю за совет, обязательно посмотрю. :)

iou в сообщении #1108771 писал(а):
Так ведь книги все одинаковые. Есть $12$ книг, $3$ цвета: берем $1$ книгу, её либо в красный, либо в зеленый, либо в коричневый, вторую и все последующие аналогично, итого $12\cdot3=36$, то есть если мы вначале $3$ книги покрасим в красный или в конце - всё равно.

Как уже сказали выше, книги различные, о чём говорится в условии открытым текстом. :)

Но давайте предположим, что они одинаковые. Я всё равно не понимаю, как Вы получаете $12\cdot3=36$ вариантов. :)

Мне вот лично кажется, что для случая одинаковых книг уместнее будет следующая формула с той страницы:

Цитата:
Сочетаниями из n элементов по m элементов называются комбинации, составленные из данных n элементов по m элементов, которые различаются хотя бы одним элементом (отличие сочетаний от размещений в том, что в сочетаниях не учитывается порядок элементов).
[...]
Число сочетаний c повторениями (n элементов, взятых по m, где элементы в наборе могут повторяться) вычисляется по формуле:
${\widetilde{C}}_n^m = \dfrac{(n + m - 1)!}{m! (n-1)!}$

В самом деле, у нас ведь есть 3 элемента (3 возможных цвета), взятые 12 раз (с повторениями), причём порядок следования не важен (поскольку мы рассматриваем одинаковые книги). Как по мне, для этого случая данная формула — самое оно, разве нет? :)

Получается, что количество возможных вариантов в данном случае равно
$\dfrac{(3 + 12 - 1)!}{12! \cdot (3 - 1)!} = \dfrac{14!}{12! \cdot 2!} = 91$

Или я не прав? :) Если так, то в чём моя ошибка?


Aritaborian в сообщении #1108775 писал(а):
После объяснения, данного iou, стало понятно, как можно его получить?

Нет, не понятно, см. мои рассуждения выше. Прошу пояснить.

Aritaborian в сообщении #1108775 писал(а):
Ф. А. Новиков. Дискретная математика. "Питер", 2011. Гл. 5. "Комбинаторика".

Спасибо, а 2013 год подойдёт?


Geen в сообщении #1108789 писал(а):
iou в сообщении #1108771 писал(а):
Так ведь книги все одинаковые.

Если все книги одинаковые (тождественные), то ответ снова не такой - задача тогда эквивалентна делению отрезка на три, и ответ будет $13\cdot7$ :-)

Очень интересно! :) Как я смотрю, для случая одинаковых книг Вы получили тот же ответ, что и у меня чуть выше, ведь $13 \cdot 7 = 91$. Но пришли к этому ответу явно каким-то другим путём. :) Можно узнать подробнее, как Вы рассуждали?

 Профиль  
                  
 
 Re: Странный пример задачки по комбинаторике
Сообщение24.03.2016, 19:56 
Аватара пользователя


29/04/13
8013
Богородский
Вроде бы уже всё объяснили и не раз:

Mihr в сообщении #1108785 писал(а):
Он должен переплести не одну книгу, а 12 различных книг.
Поэтому приведённое там решение неверно. А ТС совершенно прав:
Denis Russkih в сообщении #1108766 писал(а):
должно быть $3^{12} = 531441$.

Чтобы убедиться, что для исходной формулировки это верный ответ, мне, например, проще представить 12-значное число в троичной системе счисления. Сколько таких чисел? Правильно: $3^{12}$.

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


23/07/05
17975
Москва
iou в сообщении #1108771 писал(а):
Так ведь книги все одинаковые. Есть $12$ книг, $3$ цвета: берем $1$ книгу, её либо в красный, либо в зеленый, либо в коричневый, вторую и все последующие аналогично, итого $12\cdot3=36$, то есть если мы вначале $3$ книги покрасим в красный или в конце - всё равно.
А книга - "Комбинаторика" Виленкин Н.Я.
А где у Виленкина такая задача и с таким решением?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 38 ]  На страницу 1, 2, 3  След.

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



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

Сейчас этот форум просматривают: genk, YandexBot [bot]


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

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