Пожалуйста, используйте IE6/7/8 с плагином MathPlayer, Firefox с установленными математическими шрифтами или Opera 9.5 и выше.
| Работодателям и кадровым агентствам: Размещение вакансий | 26.03.2008 03:07 | |
| Правила и принципы форума «Высшая математика» | 28.10.2009 15:17 | |
| Открыта свободная публикация вакансий для математиков | 26.09.2019 16:34 |
01.03.2013 21:22
Дата регистрации:
10 лет назад
помогите решить задачи! ( комбинаторика)
1. Поезду, в котором находится m пассажиров, предстоит сделать n остановок.
а) Сколькими способами могут выйти пассажиры на этих остановках?
б) Решите ту же задачу, если учитывается лишь количество пассажиров, вышедших на каждой остановке.
2. На полке стоит 12 книг. Сколькими способами можно выбрать 5 книг, никакие две из которых не стоят рядом?
ТуРиСТ НаМБеР ВаН. ЛОДКА ДЛЯ ПУТЕШЕСТВИЙ И ПОКАТУШЕК. PHOENIX 560 КАЮТА. СЕМЬЯ и ДЕТИ Оценят.
3. На каждом борту лодки должно сидеть по 4 человека. Сколькими способами можно выбрать команду для этой лодки, причем десять человек хотят сидеть на левом борту лодки, двенадцать-на правом, а девяти безразлично где сидеть?
4. Сколькими способами можно расположить в 9 лузах 7 белых и 2 черных шара? Часть луз может быть пустой,а лузы считаются различными.
01.03.2013 21:32
Дата регистрации:
14 лет назад
Посты: 13 190
Деточка, здесь не принято говорить иносказательно.
Сначала объясните, что вы понимаете под словами «помогите решить задачи».
Вот я могу помочь старушке поднести сумку, могу помочь электрику, подержав лестницу. на которую он влез, чтобы поменять лампочку.
Но как «помочь решить задачи» — я не понимаю. «Решать»- это некий физиологический акт, а как помочь в совершении физиологического акта — я не понимаю. Вы же не просите :»помогите сходить по нужде», или «помогите выспаться», помогите скушать обед», видимо, тут вы догадываетесь, что нужно стараться самостоятельно.
Так КАКОГО ЛЕШЕГО вы все заладили «помогите решить задачи».
01.03.2013 22:38
Дата регистрации:
10 лет назад
«помогите решить задачу»
Мне знакомы эти слова! Ведь это Вы в прошлый раз ( примерно две недели назад ) говорили тоже самое! Только формулировка была иначе : «Объясните что значит «помогите решить задачу»». И в конце было вроде «решить за вас эти задачи и выложить здесь?».Вы повторились и я повторюсь: Я не прошу вас решать эти задачи за меня — я прошу всего лишь подтолкнуть на их решение. Если не хотите не надо!
Вас никто не заставляет!!
Редактировалось 1 раз(а). Последний 01.03.2013 22:38.
01.03.2013 22:43
Дата регистрации:
10 лет назад
«помогите решить задачу»
В следующий раз я буду просить не помогите решить, а подтолкните на решение задачи
01.03.2013 23:15
Дата регистрации:
Задачи на комбинаторику #9
10 лет назад
Посты: 1 972
А что Вы уже сделали?
Попытайтесь выписать несколько стандартных формул и посмотреть, не подходят ли они сюда.
1а). Представьте, что Вы пассажир. Сколько у Вас вариантов действий? А у всех вместе?
1б) Случай немного сложнее, но тоже разобран в учебниках по комбинаторике. Например, можете считать остановки «ящиками», а пассажиров — «шарами».
3. Переберите разные варианты. По числу людей «третьего типа».
4. Это задача 1б) для черных шаров и белых шаров отдельно. (если считать, что одноцветные шары неразличимы). Получите два числа и перемножьте.
дважды два — не всегда 5
01.03.2013 23:34
Дата регистрации:
14 лет назад
Посты: 13 190
Так здесь нельзя 2подтолкнуть».
Каждая из этих задач решается описанием правильного физического (математического) «процесса», позволяющего корректно перечислить ровно по одному разу все возможные варианты и пересчитать их.
Такие способы («процессы») пересчета давно придуманы и описаны в учебниках по комбинаторике.
Например, в отличной книге Виленкина «Комбинаторика».
Иное «подталкивание» к решению, кроме как изложение самого решения, здесь вряд ли возможно.
получается, что вы хотите, чтобы вас подтолкнули к чтению учебников? А самостоятельно догадаться, что перед решением задач нужно читать учебники, вы не в состоянии?
02.03.2013 00:56
Дата регистрации:
10 лет назад
Посты: 1 972
в задаче 2
Можно «приклеить» к каждой выбранной книге соседнюю справа. Если таковая есть (2 варианта).
дважды два — не всегда 5
02.03.2013 06:43
Дата регистрации:
12 лет назад
В сущности уважаемая Provincialka Вам уже дала все необходимые подсказки (см. ее пост «А что Вы уже сделали?»). Я лишь конкретизирую некоторые моменты на простом языке:
1.
а) Количество способов Вам сойти с поезда ровно такое же, как и для любого другого пассажира, причем предполагается, что то на какой остановке сойдет один пассажир не зависит от остановки на которой сойдет или сошел другой. Вспомните о правиле произведения.
б) задача равносильна отысканию количества способов представления числа $m$ в виде суммы $n$ слагаемых с учетом порядка их следования. Формула проста, известна и стара. Посмотрите в литературе, или в сети.
2.
Как ни парадоксально, но на эту задачу гораздо проще смотреть в общем виде. Если $f(n,k)$ — количество способов выбрать $k$ книг из $n$ , стоящих на полке, так, что никакие две из них не стоят рядом, то выполняется соотношение
$f(n,k)=f(n-1,k)+f(n-2,k-1)$ ,
которое, кстати, сразу дает очень простую реализацию подсчета на ЭВМ через рекурсию. Раскачивая аналитически это соотношение можно вывести явный вид $f(n,k)=C_^k+C_^$ , где $C_p^q$ — количество сочетаний без повторений из $p$ элементов по $q$ , причем полагаем $C_p^q=0$ при $q>p$ . Если возникнут затруднения с выводом, то можете просто доказать ответ при помощи мат. индукции или, подставив в соотношение $n=12$ и $k=5$ , руками обсчитать рекурсию. Так или иначе, обоснование приведенного соотношения и вывод (либо доказательство) из него (с его помощью) ответа в общем или частном виде предоставляется Вам.
3.
Задача стандартная, как и требуемые рассуждения. Пара $(m;n)$ интерпретируется как $m$ безразличных людей сели на левый борт, а $n$ на правый. Из условия задачи, если
Цитата
На каждом борту лодки должно сидеть по 4 человека
то если на левом борту $m$ безразличных человек, то на него также должны сесть и $4-m$ жаждущих левого борта. Аналогично и с правым бортом $n+(4-n)$ . Вот пример рассуждений для конкретной пары $(3;2)$ , т.е. $m=3$ и $n=2$ :
1) количество способов выбрать 3-х безразличных из всех имеющихся и посадить на левый борт равно $C_9^3$
2) на левом борту после 1) оказалось $3$ человека, а должно быть $4$ , поэтому остаток $4-3$ мы добиваем жаждущими левого борта и по правилу произведения получаем $C_9^3cdotC_^$
3) Левый борт укомплектован после 1) и 2), переходим к правому борту (помня как выглядит левый!). Для правого борта выбираем $2$ безразличных человека, причем $3$ безразличных уже сидят на левом борту, поэтому у нас их осталось лишь $9-3=6$ . Откуда получаем $C_9^3cdotC_^cdotC_^$
4) На правом борту после 3) оказалось $2$ человека, а должно быть $4$ , поэтому остаток $4-2$ мы добиваем жаждущими правого борта и получаем $C_9^3cdotC_^cdotC_^cdotC_^$
Т.о. паре $(3;2)$ соответствует количество способов
$C_9^3cdotC_^cdotC_^cdotC_^=C_9^3cdotC_^cdotC_^cdotC_^$ . Проводите аналогичные рассуждения со всеми остальными парами $(m;n)$ при $m,n=0,1,ldots,4$ и суммируйте все полученные количества.
4.
Здесь мне уже нечего добавить к ответу уважаемой Provincialk-и. Если Вы нашли формулу для 1.б), то сразу перешагнете и эту задачу.
P.S. Ваши ответы можете выложить здесь для проверки участниками форума.
Редактировалось 2 раз(а). Последний 02.03.2013 17:10.
Источник: www.mathforum.ru
На каждом борту лодки должно сидеть по 4 человека сколькими способами можно выбрать команду
Задача 30747
Условие
На каждом борту лодки должно сидеть по четыре человека. Сколькими способами можно выбрать команду для этой лодки, если есть 31 кандидат, причём десять человек хотят сидеть на левом борту лодки, двенадцать – на правом, а девяти безразлично где сидеть?
Ответ
Источники и прецеденты использования
| книга | |
| Автор | Генкин С.А., Итенберг И.В., Фомин Д.В. |
| Год издания | 1994 |
| Название | Ленинградские математические кружки |
| Издательство | Киров: «АСА» |
| Издание | 1 |
| глава | |
| Номер | 11 |
| Название | Комбинаторика-2 |
| Тема | Классическая комбинаторика |
| задача | |
| Номер | 061 |
Проект осуществляется при поддержке и .
Источник: problems.ru
Перестановки из n элементов
Определение 3. Перестановкой из n элементов называется любой упорядоченный набор этих элементов.
Пример 7a. Всевозможными перестановками множества, состоящего из трех элементов являются: (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3), (3, 2, 1), (3, 1, 2).
Число различных перестановок из n элементов обозначается Pn и вычисляется по формуле Pn=n!.
Пример 8.Сколькими способами семь книг разных авторов можно расставить на полке в один ряд?
Решение:эта задача о числе перестановок семи разных книг. Имеется P7=7!=1*2*3*4*5*6*7=5040 способов осуществить расстановку книг.
Обсуждение.Мы видим, что число возможных комбинаций можно посчитать по разным правилам (перестановки, сочетания, размещения) причем результат получится различный, т.к. принцип подсчета и сами формулы отличаются. Внимательно посмотрев на определения, можно заметить, что результат зависит от нескольких факторов одновременно.
Во-первых, от того, из какого количества элементов мы можем комбинировать их наборы (насколько велика генеральная совокупность элементов).
Во-вторых, результат зависит от того, какой величины наборы элементов нам нужны.
И последнее, важно знать, является ли для нас существенным порядок элементов в наборе. Поясним последний фактор на следующем примере.
Пример.На родительском собрании присутствует 20 человек. Сколько существует различных вариантов состава родительского комитета, если в него должны войти 5 человек?
Решение:В этом примере нас не интересует порядок фамилий в списке комитета. Если в результате в его составе окажутся одни и те же люди, то по смыслу для нас это один и тот же вариант. Поэтому мы можем воспользоваться формулой для подсчета числасочетанийиз 20 элементов по 5.
Иначе будут обстоять дела, если каждый член комитета изначально отвечает за определенное направление работы. Тогда при одном и том же списочном составе комитета, внутри него возможно 5! вариантовперестановок, которые имеют значение. Количество разных (и по составу, и по сфере ответственности) вариантов определяется в этом случае числом размещений из 20 элементов по 5.
Условие
В столовой предложено на выбор 6 блюд. Каждый день Вася берет некоторый набор блюд (возможно, не берет ни одного блюда), причем этот набор блюд должен быть отличен от всех наборов, которые он брал в предыдущие дни. Какое наибольшее количество дней Вася сможет питаться по таким правилам и какое количество блюд он в среднем при этом будет съедать за день?
Подсказка
Каждому набору блюд можно сопоставить противоположный набор, состоящий в точности из тех блюд, которых нет в исходном наборе.
Решение
Количество дней равно, очевидно, количеству различных наборов из 6 блюд. Для каждого блюда есть две возможности – быть выбранным или невыбранным. Поэтому количество дней равно 2 6 .
Каждому набору блюд можно сопоставить противоположный набор, состоящий в точности из тех блюд, которых нет в исходном наборе. Вместе в исходном и в противоположном наборе – 6 блюд, значит, в среднем приходится по 3 блюда на набор. Поскольку все 64 набора разбиваются на пары противоположных, то в среднем за эти 64 дня Вася съедал 3 блюда.
64 дня, в среднем 3 блюда в день.
Варианты задачи 1
| Вариант | Условие задачи |
| Сколькими способами можно разбить 14 человек на пары? | |
| Сколько существует десятизначных чисел, в записи которых имеется хотя бы две одинаковые цифры? | |
| Сколько существует четырёхзначных номеров (от 0001 до 9999), у которых сумма двух первых цифр равна сумме двух последних цифр? | |
| Сколькими способами можно расселить 15 гостей в четырех комнатах, если требуется, чтобы ни одна из комнат не осталась пустой? | |
| Поезду, в котором находится m пассажиров, предстоит сделать n остановок. а) Сколькими способами могут выйти пассажиры на этих остановках? б) Решите ту же задачу, если учитывается лишь количество пассажиров, вышедших на каждой остановке. | |
| а) Найдите сумму всех трехзначных чисел, которые можно записать с помощью цифр 1, 2, 3, 4 (цифры могут повторяться). б) Найдите сумму всех семизначных чисел, которые можно получить всевозможными перестановками цифр 1, . 7. | |
| Параллелограмм пересекается двумя рядами прямых, параллельных его сторонам; каждый ряд состоит из m прямых. Сколько параллелограммов можно выделить в образовавшейся сетке? | |
| На окружности отмечено десять точек. Сколько существует незамкнутых несамопересекающихся девятизвенных ломаных с вершинами в этих точках? | |
| Пассажир оставил вещи в автоматической камере хранения, а когда пришел получать вещи, выяснилось, что он забыл номер. Он только помнит, что в номере были числа 23 и 37. Чтобы открыть камеру, нужно правильно набрать пятизначный номер. Каково наименьшее количество номеров нужно перебрать, чтобы наверняка открыть камеру? | |
| Сколькими способами из полной колоды (52 карты) можно выбрать а) 4 карты разных мастей и достоинств? б) 6 карт так, чтобы среди них были представители всех четырех мастей? |
Условие
В Монголии имеются в обращении монеты в 3 и 5 тугриков. Входной билет в центральный парк стоит 4 тугрика. Как-то раз перед открытием в кассу парка выстроилась очередь из 200 посетителей. У каждого из них, а также у кассира есть ровно 22 тугрика. Докажите, что все посетители смогут купить билет в порядке очереди.
Решение
Набрать 22 тугрика монетами по 3 и 5 тугриков можно единственным способом: две монеты по 5 тугриков и четыре монеты по 3 тугрика. Укажем, как должен действовать кассир. У первого посетителя он просит три монеты по 3 тугрика и дает ему сдачу монетой в 5 тугриков. У второго посетителя кассир просит две монеты по 5 тугриков и дает ему слачу двумя монетами по 3 тугрика.
После этого у кассира монет каждого типа стало на одну больше. Продолжая действовать таким же образом, он сможет обслужить любое количество посетителей.
Варианты задачи 2
| Вариант | Условие задачи |
| а) Сколькими способами можно разбить 15 человек на три команды по 5 человек в каждой? б) Сколькими способами можно выбрать из 15 человек две команды по 5 человек в каждой? | |
| Переплетчик должен переплести 12 одинаковых книг в красный, зеленый или синий переплеты. Сколькими способами он может это сделать? | |
| В почтовом отделении продаются открытки 10 видов. Сколькими способами можно купить в нем а) 12 открыток; б) 8 открыток; в) 8 различных открыток? | |
| Сколькими способами 3 человека могут разделить между собой 6 одинаковых яблок, один апельсин, одну сливу и один мандарин? | |
| Сколькими способами 4 черных шара, 4 белых шара и 4 синих шара можно разложить в 6 различных ящиков? | |
| Сколькими способами можно разделить на команды по 6 человек для игры в волейбол группу: а) из 12; б) из 24 спортсменов? | |
| При игре в преферанс каждому из трех игроков раздают по 10 карт, а две карты кладут в прикуп. Сколько различных раскладов возможно в этой игре? (Считаются возможные раздачи без учета того, что каждые 10 карт достаются конкретному игроку.) | |
| Сколькими способами можно составить букет из 17 цветков, если в продаже имеются гвоздики, розы, гладиолусы, ирисы, тюльпаны и васильки? | |
| Нарисуйте все лестницы из 4 кирпичей в порядке убывания, начиная с самой крутой (4, 0, 0, 0), и заканчивая самой пологой (1, 1, 1, 1). | |
| Завод выпускает погремушки в виде кольца с надетыми на него 3 красными и 7 синими шариками. Сколько различных погремушек может быть выпущено? (Две погремушки считаются одинаковыми, если одна из них может быть получена из другой только передвижением шариков по кольцу и переворачиванием.) |
Условие
На лотерейном билете требуется отметить 8 клеточек из 64. Какова вероятность того, что после розыгрыша,
в котором также будет выбрано 8 каких-то клеток из 64 (все такие возможности равновероятны), окажется, что угаданы
а) ровно 4 клетки? б) ровно 5 клеток? в) все 8 клеток?
Решение
8 клеток из 64 могут быть выбраны способами. Следовательно, вероятность того, что выпадет какой-то один определенный способ, равна Число случаев, в которых оказались угаданными ровно k клеток равно числу способов, при которых выбираются k клеток
из 8 отмеченных и 8 – k клеток из 56 неотмеченных, то есть Таким образом, вероятность угадать ровно k клеток равна
Ответ
Варианты задачи 3
| Вариант | Условие задачи |
| Сколькими способами можно разбить 10 человек на две баскетбольные команды по 5 человек в каждой? | |
| Сколько существует шестизначных чисел, у которых по три четных и нечетных цифры? | |
| 30 человек голосуют по 5 предложениям. Сколькими способами могут распределиться голоса, если каждый голосует только за одно предложение и учитывается лишь количество голосов, поданных за каждое предложение? | |
| Сколькими способами можно выложить в ряд 5 красных, 5 синих и 5 зеленых шаров так, чтобы никакие два синих шара не лежали рядом? | |
| На каждом борту лодки должно сидеть по 4 человека. Сколькими способами можно выбрать команду для этой лодки, если есть 31 кандидат, причем десять человек хотят сидеть на левом борту лодки, двенадцать – на правом, а девяти безразлично где сидеть? | |
| На полке стоит 12 книг. Сколькими способами можно выбрать из них 5 книг, никакие две из которых не стоят рядом? | |
| Имеется 20 человек – 10 юношей и 10 девушек. Сколько существует способов составить компанию, в которой было бы одинаковое число юношей и девушек? | |
| Международная комиссия состоит из 9 человек. Материалы комиссии хранятся в сейфе. Сколько замков должен иметь сейф, сколько ключей для них нужно изготовить и как их разделить между членами комиссии, чтобы доступ к сейфу был возможен тогда и только тогда, когда соберутся не менее 6 членов комиссии? | |
| В кооперативе из 11 человек имеется партячейка. На каждом собрании ячейки происходит либо приём одного члена в партию, либо исключение из партии одного человека. В партячейке не может быть меньше трёх человек. Возвращаться к какому-либо из прежних составов партячейки запрещено уставом. Может ли к какому-то моменту оказаться, что все варианты состава ячейки реализованы? | |
| На прямой отмечено 10 точек, а на параллельной ей прямой – 11 точек. Сколько существует а) треугольников; б) четырехугольников с вершинами в этих точках? |
Источник: mykonspekts.ru