2018-12-13 Сколько различных значений можно получить, расставляя всеми возможными способами скобки в выражении 2 : 3 : 5 : 7 : 11 : 13 : 17 : 19 : 23 : 29?
При любой расстановке скобок данное выражение можно представить в виде дроби. Тогда, так как все данные числа — простые, результат вычислений будет однозначно определяется тем, куда «попало» каждое из этих чисел: в числитель или в знаменатель. Очевидно, что независимо от расстановки скобок, число 2 попадает в числитель, а число 3 — в знаменатель. Каждое из следующих чисел может «попасть» как в числитель, так и в знаменатель, например, при такой расстановке скобок 2 : (3 : 5) $\cdots$ число 5 окажется в числителе дроби, а если скобки поставить так (2 : 3) : 5 $\cdots$ — в знаменателе.
Докажем, что существуют расстановки скобок, при которых каждое из чисел 5, 7, 11, 13, 17, 19, 23, 29 «попадает» как в числитель, так и в знаменатель, независимо от расположения остальных чисел. Для этого, например, разобьем все данные числа, начиная с числа 3, на группы следующим образом: каждая группа начинается с числа, которое должно «попасть» в знаменатель, и может содержать еще несколько (в том числе, и ноль) чисел, идущих следом за ним, которые все должны «попасть» в числитель. Эти группы заключаем в скобки и больше нигде скобок не ставим. Тогда первое число каждой группы попадет в знаменатель, так как на него непосредственно делится двойка, а остальные числа группы «попадут» в числитель, так как на них делится первое число из этой группы, «попавшее» в знаменатель.
Таким образом, количество чисел, которые могут являться значением данного выражения при всех возможных расстановках скобок, равно $2^ <8>= 256$.
Эту задачу можно обобщить для любого количества чисел, причем они не обязательно должны быть простыми. Расставляя всеми возможными способами скобки в выражении $a_ <1>: a_ <2>: \cdots : a_$, где каждые два числа взаимно просты, можно получить $2^$ различных значения. Ответ: 256.
Источник
Сколькими способами можно расставить скобки
Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.
Добро пожаловать!
Получили 2 · 3 = 6.
v08 17 2009. 17:23 C. Комбинаторика Этот же ответ можно было получить так: на первое место может сесть три человека, тогда на второе — оставшиеся два; всего получается 2 · 3 = 6 способов.
Аналогично действуем и при решении исходной задачи: на первое место может сесть пять человек, на второе — четыре, на третье — три, и на четвертое — два. Итого получаем 5 · 4 · 3 · 2 = 120.
б) В этом пункте совершенно аналогично получаем 5 · 4 · 3 · 2 · 1 = = 120.
в) Первый человек может сесть на любое из шести мест, второй — на любое из оставшихся пяти, третий — на любое из оставшихся четырех, четвертый — на любое из оставшихся трех, и, наконец, пятый — на любое из оставшихся двух. Всего получаем 6 · 5 · 4 · 3 · 2 = вариантов рассадки.
г) Аналогично находим ответ: 2520 способов.
Задача. Семь учеников «В» класса решили вместе покататься:
а) на аттракционе «поезд», состоящем из семи одноместных вагончиков;
б) на карусели, у которой ровно семь мест;
в) на «поезде» из десяти вагончиков;
г) на карусели, у которой ровно десять мест.
Сколькими способами они смогут это сделать Вопросы в пунктах а) и в) по существу такие же, как и в предыду щей задаче.
Пункты б) и г) отличается от пунктов а) и в) тем, что карусель — это как бы поезд, замкнутый в кольцо. Поэтому для того, чтобы получить правильные ответы в пунктах б) и г), надо ответы в пунктах а) и в) поделить на число мест. Действительно, ведь если мы будем «склеивать» карусель с уже сидящими в кабинках школьниками из поезда с сидящими в вагонах школьниками, то каждая карусель будет получаться из ровно семи рассадок школьников по поезду. Так, например, следующие рассадки школьников в поезде:
Задача. Сколькими способами можно пройти из левого нижнего угла квадрата: а) 2 2; б) 3 3; в*) 5 5, двигаясь только вверх или вправо по сторонам клеток v08 17 2009. 17:23 C. Комбинаторика Решение. Решать задачу будем следующим образом: будем писать рядом с узлом решетки число, равное числу способов попасть из этой точки в правый верхний угол. Рядом с точками, лежащими на правой или верхней стороне квадрата, мы сразу можем написать единицы, потому что из каждой из них можно пройти в правый верхний угол, очевидно, единственным способом. А далее будем действовать так:
если у нас есть такая точка, что правее и выше от нее лежат точки, рядом с которыми уже написаны числа, то рядом с этой точкой мы пишем сумму чисел, стоящих справа и сверху. Вопрос на засыпку:
почему именно сумму и почему именно этих чисел Как сумма этих чисел связана с числом способов пройти в правый верхний угол В итоге рано или поздно мы расставим числа рядом со всеми узлами решетки. В частности, рядом с левым нижним углом. Это и будет ответ.
Задача. Сколькими способами можно представить числа 5, 10, в виде суммы: а) двух; б) трех натуральных чисел Решение. Заметим, что условие задачи можно понимать по-разному.
Вопрос в том, считаются ли, например, разложения 3 = 2 + 1 и 3 = = 1 + 2 одинаковыми. Разберем оба случая на примере разбиения числа в сумму трех натуральных чисел.
В. Разложения, отличающиеся перестановкой слагаемых, считаются одинаковыми.
Выпишем все способы разложения десяти в сумму трех слагаемых:
Заметим, что для того, чтобы выписать все тройки чисел, дающих в сумме, достаточно выписать лишь те наборы чисел, в которых каждое следующее не меньше предыдущего (что мы и сделали). Например, набор (7, 2, 1) у нас представлен как (1, 2, 7). В этом месте возникает вопрос, почему мы выписали все разложения. Для ответа достаточно внимательно посмотреть на способ перечисления.
Ответ. Число раскладывается в сумму двух натуральных чисел двумя способами, а в сумму трех — двумя способами. Число раскладывается в сумму двух натуральных чисел пятью способами, а в сумму трех — восемью способами. Число раскладывается в сумму двух натуральных чисел десятью способами, а в сумму трех — тридцатью тремя способами.
v08 17 2009. 17:23 C. Комбинаторика В. Разложения, отличающиеся перестановкой слагаемых, считаются разными.
Тогда наша задача будет эквивалентна следующей: перед нами лежат в ряд десять палочек; сколькими способами между ними можно поставить две перегородки так, чтобы и слева и справа от каждой перегородки лежало по палочке.
А задачу с палочками решить совсем не трудно. Всего у нас есть девять мест, куда мы можем ставить перегородки. Поэтому первую перегородку мы можем поставить на девять мест, а вторую — на оставшиеся восемь. Но при этом мы каждый расклад посчитаем по два раза (перегородки-то одинаковые). Поэтому ответ: (9 · 8)/2 = 36.
Задача. Сколькими способами можно расставить скобки в выражении a + b — c · d Условие этой задачи при первом прочтении не вполне понятно.
Вопрос вот в чем: нас интересуют произвольные расстановки скобок или обладающие какими-то разумными свойствами Например, устроит ли нас такая расстановка скобок: (((a + b — c · d))) Ясно, что если мы будем расставлять скобки произвольно, то получим бесконечно много вариантов. Поэтому возможное разумное прочтение условия такое:
Будем считать две расстановки скобок в выражении a + b — c · d одинаковыми, если при подстановке в них любого набора чисел (a, b, c, d) получается одно и то же число. Сколько существует различных (в этом смысле) расстановок скобок Решение. Расставить скобки — это то же самое, что определить порядок выполнения действий. В каком порядке выполнять сложение и вычитание неважно, остается решить, в какой момент выполнять умножение. Получаются выражения:
(a + b — c · d), a + (b — c) · d, (a + b — c) · d.
Остается убедиться, что при некоторых значениях a, b, c и d все эти выражения принимают попарно различные значения. Для этого подойдут практически любые значения переменных, например, a = 3, b = 2, c = 1, d = 0.
Задача. а) Докажите, что подмножеств в множестве столько же, сколько отображений этого множества в множество <0, 1>. б) Докажите, что это число равно числу последовательностей нулей и единиц длины пять.
v08 17 2009. 17:23 C. Комбинаторика Решение. Каждому подмножеству M множества A = мы можем естественным образом сопоставить отображение f из множества A в множество <0, 1>по следующему правилу: элемент x A отображается в 1 (то есть f (x) = 1), если x лежит в M, и в 0, если не лежит. Нетрудно заметить (хотя это надо формально и аккуратно проверить), что мы построили биекцию.
В пункте б) действуем аналогично. То есть строим биекцию из множества всех подмножеств множества A = в множество последовательностей из нулей и единиц. Например, подмножеству M = мы сопоставим последовательность (1, 0, 1, 0, 1); подмножеству M = сопоставим (0, 1, 1, 0, 0); подмножеству M = сопоставим (1, 0, 0, 1, 1) и так далее. А именно, занумеруем элементы множества, после чего любому подмножеству поставим в соответствие последовательность, у которой на каждом месте стоит 1, если этот элемент принадлежит подмножеству, и 0, если нет.
Задача *. Сколько существует различных наборов бусинок, из которых можно составить ровно два различных ожерелья Во-первых, очень важно разобраться в том, какие наборы считаются различными, а какие — нет. Например, наборы <синий, синий, красный>и <оранжевый, зеленый, зеленый>считаются одинаковы- ми, а наборы <красный, синий, зеленый>и <голубой, желтый, голу бой>— различными. Почему Во-вторых, полезно порисовать всевозможные наборы из небольшого числа бусинок и попытаться найти какие-то закономерности.
Решение. Во-первых, наборы бусинок не упорядочены, то есть наборы <синий, синий, красный>и <синий, красный, синий>одинаковы.
Во-вторых, наборы, получающиеся друг из друга переименованием цветов, также считаются одинаковыми.
Докажем сначала, что в искомом наборе не может быть слишком много различных цветов, а именно, не может быть более трех различных цветов. Допустим, нашелся набор, содержащий бусинки четырех различных цветов (назовем их красный, желтый, зеленый, синий), из которого можно составить только два различных ожерелья. Рассмотрим следующие ожерелья:
v08 17 2009. 17:23 C. Комбинаторика Здесь «К» означает все бусинки красного цвета, «З» — синего и т. д.
Видно, что эти ожерелья различны. Следовательно, в искомом наборе не более трех различных цветов. Если все бусинки одноцветны, то можно составить только одно ожерелье. Итак, в искомом наборе бусинок может встречаться или два, или три цвета. Дальше задача является явным перебором. Приведем его для случая двух цветов.
Если бусинок каждого цвета хотя бы три, то можно составить такие три различных ожерелья: (все красные, все синие), (красные кроме одной, синяя, красная, остальные синие), (красные кроме двух, синяя, красная, синяя, красная, остальные синие).
Следовательно, бусинок какого-то цвета (допустим, красного) не больше двух. Если в наборе ровно одна красная бусинка, то из этого набора можно составить только одно ожерелье. Таким образом, в искомом наборе ровно две красные бусинки и сколько-то синих.
Заметим, что различные ожерелья отличаются только числом синих бусинок между красными. Теперь уже несложно видеть, что ровно два ожерелья получится, если синих бусинок будет две или три.
Случай наборов из трех цветов разбирается аналогично.
Ответ. Две красных и две синих бусинки; две красных и три синих бусинки; две красных, одна синяя и одна желтая бусинка; три крас ных, одна синяя и одна желтая бусинка.
Задача *. В городе Энск номера автобусных билетов четырехзначные. Жители этого города считают, что билеты, у которых сумма первых двух цифр равна сумме последних двух цифр, счастливые.
Сколько счастливых билетов в Энске Указание. Здесь надо отдельно посчитать число счастливых билетов, у которых сумма первых двух цифр равна нулю. Затем те, у которых эта сумма будет равна единице. И так далее до случая, когда сумма будет равна 18 = 9 + 9. Затем найденные числа сложить. Заметим, что мы уже решали похожую задачу, когда разбивали разные числа в сумму двух.
Задача *. Сколькими способами можно раскрасить колесо обозрения: а) с 7 кабинками в 3 цвета; б) с 10 кабинками в 2 цвета При раскраске не обязательно использовать все цвета.
Решение. а) Зафиксируем сначала колесо и раскрасим его. Это можно сделать 37 способами. Теперь посчитаем, сколько раз мы учли каждую раскраску вращающегося колеса. Любая раскраска, которая не v08 17 2009. 17:23 C. Комбинаторика переходит в себя ни при каком вращении колеса, посчитана 7 раз.
Поскольку число 7 — простое, в себя при вращении колеса переходят только одноцветные раскраски. Итак, все раскраски, кроме трех, посчитаны по раз, а эти три — по одному разу. Отсюда легко находим 37 — число раскрасок + 3.
б) Будем действовать аналогично предыдущему пункту. При этом возникнет новая трудность: не только одноцветные раскраски переходят в себя при повороте. Посчитаем сначала (кроме одноцветных), сколько раскрасок переходят в себя при хоть каком-нибудь повороте.
При повороте на 1, 3, 7 и 9 в себя переходят только одноцветные раскраски. При повороте на 2, 4, 6 и 8 в себя переходят еще и раскраски, в которых цвета чередуются (у зафиксированной карусели есть две такие неодноцветные раскраски). При повороте на 5 в себя переходят симметричные раскраски (кроме одноцветных, их 25 — 2 = 30). Следовательно, по 10 раз мы посчитали 210 — 2 — 2 — 30 = 990 раскрасок.
Итак, общее число раскрасок вращающегося колеса равно + 30 + + + 2 = 99 + 6 + 1 + 2 = 108.
5 Далеким обобщением этого метода подсчета является лемма Берн сайда из листочка «Теория групп ».
Задача. Кто-то режет правильный: а) шестиугольник; б*) семиугольник; в*) восьмиугольник на треугольники, проводя разрезы по непересекающимся диагоналям. Сколько разных наборов треугольников может получиться Решение. а) Разрезания шестиугольника мы можем разбить на два класса: те, в которых есть разрез по главной диагонали, и те, в которых его нет. Заметим, что если шестиугольник разрезан по главной диагонали, то как бы мы ни разрезали получившиеся четырехугольники (трапеции), мы будем получать один и тот же набор треугольников.
Если же разреза по главной диагонали нет, то это означает, что мы можем лишь отрезать маленькие треугольнички от шестиугольника, и в этом случае также можем получить лишь один набор треугольников в итоге (см. рис. а).
б) Ответ: два набора (см. рис. б).
в) Ответ: четыре набора (см. рис. в).
v08 17 2009. 17:23 C. Комбинаторика а) б) в) Задача. Сколько существует различных игральных кубиков (на гранях кубика расставлены числа от до ) Это хорошее упражнение на идею «факторизации»: нужно сначала вычислить число элементов большего множества объектов, а потом разделить это число на число повторений.
К концу листка до такого плана обычно догадывается каждый, но его реализация связана с некоторыми техническими трудностями.
Поэтому не стоит требовать полностью формального решения от всех школьников — вполне достаточно понимания того, что происходит.
Решение. Итак, нас интересует число способов наклеить на грани кубика цифры от 1 до 6, при этом кубики с наклеенными цифрами считаются одинаковыми, если их можно совместить так, чтобы цифры на гранях совпали.
Пусть сначала кубик неподвижно лежит на столе. Число способов наклеить на него цифры от 1 до 6 есть количество способов рассадить 6 человек (наклейки) по 6 местам (грани), т. е. (см. задачу ) 6! = 720.
Осталось понять, сколько из получившихся 720 кубиков можно совместить так, чтобы наклейки совпали. Другими словами, пусть все эти 720 кубиков лежат на столе в том положении, в каком на них были наклеены цифры; если разрешить какой-то из кубиков катать по столу, сколько из имеющихся кубиков мы сможем получить v08 17 2009. 17:23 C. Комбинаторика Ясно, что это число равно числу способов повернуть кубик (числу симметрий куба). Эти способы уже нетрудно подсчитать: при повороте верхняя грань куба может оказаться в одном из 6 положений (сверху, снизу, слева, справа, спереди, сзади), каждому из которых соответствует ровно 4 поворота (действительно, после того, как место одной из граней куба зафиксировано, единственное, что мы можем делать, — вращать его вокруг проходящей через эту грань оси). То есть всего способов 6 · 4 = 24.
Значит, на нашем столе каждый игральный кубик встречается по 24 раза. Соответственно, число различных игральных кубиков равно 720 : 24 = 30.
v08 17 2009. 17:23 C. Подстановки. Ходим по циклу листок 1 / октябрь Это первый листок из серии, в которой изучаются сначала подстановки, а потом и абстрактные группы.
Большинство задач представляют собой несложные упражения на понимание того, что такое произведение подстановок. Содержательные вопросы про подстановки отложены до листка «Подстановки » (и, частично, листков по теории групп). Стоит, однако, отметить две важные задачи: задачу, в которой (как будет видно позже) доказывается, что подстановки образуют группу, и (дополнительную) задачу, что-то объясняющую про то, как могут быть устроены перестановки.
Определение. Подстановкой из n элементов называется биективное отображение из множества <1, 2, …, n>в себя. Запись вида i i2…in, j1 j2… jn где i1, i2, …, in — различные элементы множества <1, 2, …, n>и j1, j2, …, jn — различные элементы множества <1, 2, …, n>, обозначает подстановку a, для которой a(ik) = jk при всех k <1, 2, …, n>.
Множество подстановок из n элементов обозначается Sn. Подстанов ку можно графически изобразить следующим образом. Расположим на плоскости элементы множества <1, 2, …, n>и для каждого i проведем стрелку из элемента i в элемент a(i). То, что получилось, называется графом подстановки.
Проясним несколько моментов, которые могут вызвать трудности после прочтения определения. Несмотря на данное «формальное» определение, подстановка — это очень наглядный объект. При решении задач этого листка следует обязательно «поиграть» с подстановками, проверяя утверждения для небольших n, в том числе, сделав несколько фишек с номерами, и переставляя их.
