Как из нескольких чисел выявить нестандартные
Учитесь решать задачи по комбинаторике? На самом начальном этапе нужно изучить основные формулы комбинаторики: сочетания, размещения, перестановки (смотрите подробнее ниже) и научиться их применять для решения задач.
Как выбрать формулу комбинаторики?
Мы подготовили для вас наглядную схему с примерами решений по каждой формуле комбинаторики:
- алгоритм выбора формулы (сочетания, перестановки, размещения с повторениями и без),
- рекомендации по изучению комбинаторики,
- 6 задач с решениями и комментариями на каждую формулу.
Перестановки
Пусть имеется $n$ различных объектов.
Будем переставлять их всеми возможными способами (число объектов остается неизменными, меняется только их порядок). Получившиеся комбинации называются перестановками, а их число равно
$$P_n=n!=1\cdot 2\cdot 3 \cdot . \cdot (n-1) \cdot n$$
Символ $n!$ называется факториалом и обозначает произведение всех целых чисел от $1$ до $n$. По определению, считают, что $0!=1, 1!=1$.
Пример всех перестановок из $n=3$ объектов (различных фигур) — на картинке справа. Согласно формуле, их должно быть ровно $P_3=3!=1\cdot 2\cdot 3 =6$, так и получается.
С ростом числа объектов количество перестановок очень быстро растет и изображать их наглядно становится затруднительно. Например, число перестановок из 10 предметов — уже 3628800 (больше 3 миллионов!).
Размещения
Пусть имеется $n$ различных объектов.
Будем выбирать из них $m$ объектов и переставлять всеми возможными способами между собой (то есть меняется и состав выбранных объектов, и их порядок). Получившиеся комбинации называются размещениями из $n$ объектов по $m$, а их число равно
Пример всех размещений из $n=3$ объектов (различных фигур) по $m=2$ — на картинке справа. Согласно формуле, их должно быть ровно $A_3^2=3\cdot (3-2+1)=3\cdot 2 =6$.
Сочетания
Пусть имеется $n$ различных объектов.
Будем выбирать из них $m$ объектов все возможными способами (то есть меняется состав выбранных объектов, но порядок не важен). Получившиеся комбинации называются сочетаниями из $n$ объектов по $m$, а их число равно
Пример всех сочетаний из $n=3$ объектов (различных фигур) по $m=2$ — на картинке справа. Согласно формуле, их должно быть ровно $C_3^2=\frac =3$. Ясно, что сочетаний всегда меньше чем размещений (так как при размещениях порядок важен, а для сочетаний — нет), причем именно в $m!$ раз, то есть верна формула связи:
Интересное и простое из комбинаторики. Функция Эйлера
Прежде всего хочу сказать, мне всего 14 лет. Я надеюсь, что информация, которой поделюсь, будет для кого-то интересна.
Речь пойдет о некоторых задачах комбинаторики.
Сколько вариантов расставить n предметов?
Способ №1
Способ №2
Допустим, нам нужно узнать, сколько вариантов в расстановке 10 предметов. Умножаем: 1x2x3..x10
Получим: 10! = 3628800
Как из n предметов выбрать k предметов?
Способ №1
Допустим, вы — организатор лотереи. Из 10 участников вам нужно выбрать 2 победителя. Вы можете узнать количество способов сделать это.
Так же как и в случае с факториалом, можно посчитать вручную. Выбирать n предметов, пока не иссякнут все варианты.
Цитирую: но есть способ, который по своей простоте опережает приведенный ранее способ.
Способ №2
Высчитывается по формуле:
Итак, сколько же способов из 10 участников выбрать 2 победителя?
Ответ вполне себе простой —
Числа Фибоначчи
Стоит отдать должное человеку, который «придумал» эти числа. Леонардо Пизанский. Думаю достаточно, чтобы Вы запомнили имя этого великого человека.
Приступим. Числа Фибоначчи применяются в Теории Чисел. Если сказать честно, я знаю не слишком много об этих числах.
Числа Фибоначчи — это последовательность чисел, в котором каждое последующее числовое значение равно сумме двух предыдущих. Первые два числа Фибоначии — единицы. Соответственно, 3-е число = 2.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946.
Еще раз повторюсь — я знаю не слишком много об этих числах. Если я еще не слишком вас утомил/отпугнул/надоел — идем дальше.
Функция Эйлера
В этом пункте я попытаюсь выложить все, что знаю об этом. Я потратил достаточно времени и сил, чтобы изучить эту, между прочим абсолютно простою вещь.
По правде говоря, я очень горжусь тем, что такой человек как Леонард Эйлер жил в России.
К делу. Есть три разных способа посчитать функцию Эйлера. На выбор одного из способов влияют некоторые факторы.
Функция Эйлера обозначается (читать как фи от n).
Способ №1
Увы, но этот способ применять следует для высчитывания функции простых чисел.
Например, функция Эйлера для 3 =
Способ №2
Данный способ следует применять если число можно представить как степень какого-то числа. Например, 9 — это
Посчитаем функцию для 9.
Способ №3
Если число нельзя представить как степень, но можно представить как два множителя — этот способ нам и нужен.
Тут немного сложнее. Нужно разложить число на два множителя, посчитать функцию для каждого из множителей и полученные результаты перемножить.
Также хочу отметить, что если число можно представить и как степень и как два множителя, то в преимуществе всегда степень какого-то числа (о как, в рифму).
Таким образом получаем:
Правила комбинаторики в задаче B6
Решая задачи по теории вероятностей, мы постоянно используем одну и ту же формулу, которая одновременно является классическим определением вероятности:
где k — число благоприятных исходов, n — общее число исходов (см. «Тест по теории вероятностей»).
И эта формула прекрасно работает до тех пор, пока задачи были легкими, а числа, стоящие в числителе и знаменателе — очевидными.
Однако последние пробные экзамены показали, что в настоящем ЕГЭ по математике могут встречаться значительно более сложные конструкции. Отыскание значений становится проблематичным. В таком случае на помощь приходит комбинаторика. Ее законы работают там, где искомые значения не выводятся непосредственно из текста задачи.
В сегодняшнем уроке не будет строгих формулировок и длинных теорем — они слишком сложны и, к тому же, совершенно бесполезны для решения настоящих задач B6. Вместо этого мы рассмотрим простые правила и разберем конкретные задачи, которые действительно встречаются на ЕГЭ. Итак, поехали!
Число сочетаний и факториалы
Пусть имеется n объектов (карандашей, конфет, бутылок водки — чего угодно), из которых требуется выбрать различных объектов. Тогда количество вариантов такого выбора называется элементов Это число обозначается и считается по специальной формуле.
Обозначение:
Выражение n ! читается как «эн-факториал» и обозначает произведение всех натуральных чисел включительно:
Кроме того, в математике по определению считают, подобный бред редко, но все же встречается в задачах по теории вероятностей.
Что дает нам эта формула? На самом деле, без нее не решается практически ни одна серьезная задача.
К сожалению, в школе совершенно не умеют работать с факториалами. Кроме того, в формуле числа сочетаний очень легко запутаться: где стоит и что обозначает Поэтому для начала просто запомните: меньшее число всегда стоит сверху — точно так же, как и в формуле определения вероятности (вероятность никогда не бывает больше единицы).
Для лучшего понимания разберем несколько простейших комбинаторных задач:
Задача. У бармена есть 6 сортов зеленого чая. Для проведения чайной церемонии требуется подать зеленый чай ровно 3 различных сортов. Сколькими способами бармен может выполнить заказ?
Тут все просто: есть n = 6 сортов, из которых надо выбрать сорта. Число сочетаний можно найти по формуле:
Задача. В группе из 20 студентов надо выбрать 2 представителей для выступления на конференции. Сколькими способами можно это сделать?
Опять же, всего у нас есть n = 20 студентов, а выбрать надо студента. Находим число сочетаний:
Обратите внимание: красным цветом отмечены множители, входящие в разные факториалы. Эти множители можно безболезненно сократить и тем самым значительно уменьшить общий объем вычислений.
Задача. На склад завезли 17 серверов с различными дефектами, которые стоят в 2 раза дешевле нормальных серверов. Директор купил в школу 14 таких серверов, а сэкономленные деньги своровал и купил дочке шубу из меха соболя за 200 000 рублей. Сколькими способами директор может выбрать бракованные серверы?
В задаче довольно много лишних данных, которые могут сбить с толку. Наиболее важные факты: всего есть серверов, а директору надо серверов. Считаем число сочетаний:
Красным цветом снова обозначены множители, которые сокращаются. Итого, получилось 680 комбинаций. В общем, директору есть из чего выбрать.
Как видите, число сочетаний из n по k считается достаточно просто. Проблема в том, что многие школьники никогда не работали с факториалами. Для них это новый и незнакомый математический объект, и для его освоения требуется некоторая тренировка.
Хорошая новость состоит в том, что во многих задачах формулы оказывается вполне достаточно для нахождения ответа. Но есть и плохая новость: в тех редких случаях, когда нужны дополнительные правила, решение задачи резко усложняется. Эти правила мы сейчас и рассмотрим.
Закон умножения
в комбинаторике: число сочетаний (способов, комбинаций) в независимых наборах умножается.
Другими словами, пусть имеется A способов выполнить одно действие выполнить другое действие. Путь также эти действия независимы, т.е. никак не связаны между собой. Тогда можно найти число способов выполнить первое и второе действие по формуле:
Задача. У Пети есть 4 монеты по 1 рублю и 2 монеты по 10 рублей. Петя, не глядя, достал из кармана 1 монету номиналом 1 рубль и еще 1 монету номиналом 10 рублей, чтобы купить сигарету за 11 рублей у бабули в подземном переходе. Сколькими способами он может выбрать эти монеты?
Итак, сначала Петя достает монету имеющихся монет номиналом 1 рубль. Число способов сделать это равно
Затем Петя снова лезет в карман и достает монету имеющихся монет номиналом 10 рублей. Здесь число сочетаний равно
Поскольку эти действия независимы, общее число вариантов равно
Задача. В корзине лежат 8 белых шаров и 12 черных. Сколькими способами можно достать из этой корзины 2 белых шара и 2 черных?
Всего в корзине белых шаров, из которых надо выбрать шара. Это можно сделать различными способами.
Кроме того, в корзине имеется черных шаров, из которых надо выбрать опять же шара. Число способов сделать это равно
Поскольку выбор белого шара и выбор черного — события независимые, общее число комбинаций считается по закону умножения: Как видим, вариантов может быть довольно много.
Закон умножения показывает, сколькими способами можно выполнить сложное действие, которое состоит из двух и более простых — при условии, что все они независимы.
Именно этой формулы многим не хватило для решения задачи B6 на пробном ЕГЭ по математике. Разумеется, существуют и другие методы решения, в которых комбинаторика не используется — и мы обязательно рассмотрим их ближе к настоящему экзамену. Однако ни один из них не сравнится по надежности и лаконичности с теми приемами, которые мы сейчас изучаем.
Закон сложения
Если закон умножения оперирует «изолированными» событиями, которые не зависят друг от друга, то в законе сложения все наоборот. Здесь рассматриваются взаимоисключающие события, которые никогда не случаются одновременно.
Например, «Петя вынул из кармана 1 монету» и «Петя не вынул из кармана ни одной монеты» — это взаимоисключающие события, поскольку вынуть одну монету и при этом не вынуть ни одной невозможно.
Аналогично, события «Выбранный наугад шар — белый» и «Выбранный наугад шар — черный» также являются взаимоисключающими.
в комбинаторике: если два взаимоисключающих действия можно выполнить способами соответственно, то эти события можно объединить. При этом возникнет новое событие, которое можно выполнить способами.
Другими словами, при объединении взаимоисключающих действий (событий, вариантов) число их комбинаций складывается.
Можно сказать, что закон сложения — это логическое «ИЛИ» в комбинаторике, когда нас устраивает любой из взаимоисключающих вариантов. И наоборот, закон умножения — это логическое «И», при котором нас интересует одновременное выполнение и первого, и второго действия.
Задача. В корзине лежат 9 черных шаров и 7 красных. Мальчик достает 2 шара одинакового цвета. Сколькими способами он может это сделать?
Если шары одинакового цвета, то вариантов немного: оба они либо черные, либо красные. Очевидно, что эти варианты — взаимоисключающие.
В первом случае мальчику предстоит выбирать черных шара имеющихся. Число способов сделать это равно
Аналогично, во втором случае выбираем красных шара возможных. Число способов равно
Осталось найти общее количество способов. Поскольку варианты с черными и красными шарами — взаимоисключающие, по закону сложения имеем:
Задача. В ларьке продаются 15 роз и 18 тюльпанов. Ученик хочет купить 3 цветка для своей одноклассницы, причем все цветы должны быть одинаковыми. Сколькими способами он может составить такой букет?
По условию, все цветы должны быть одинаковыми. Значит, будем покупать либо 3 розы, либо 3 тюльпана. В любом случае,
В случае с розами придется выбирать вариантов, поэтому число сочетаний равно Для тюльпанов же а число сочетаний —
Поскольку розы и тюльпаны — это взаимоисключающие варианты, работаем по закону сложения. Получаем общее число вариантов Это и есть ответ.
Дополнительные условия и ограничения
Очень часто в тексте задачи присутствуют дополнительные условия, накладывающие существенные ограничения на интересующие нас сочетания. Сравните два предложения:
- Имеется набор из 5 ручек разных цветов. Сколькими способами можно выбрать 3 ручки для обводки чертежа?
- Имеется набор из 5 ручек разных цветов. Сколькими способами можно выбрать 3 ручки для обводки чертежа, если среди них обязательно должен быть красный цвет?
Чувствуете разницу? В первом случае мы вправе брать любые цвета, какие нам нравятся — дополнительных ограничений нет. Во втором случае все сложнее, поскольку мы обязаны выбрать ручку красного цвета (предполагается, что она есть в исходном наборе).
Очевидно, что любые ограничения резко сокращают итоговое количество вариантов. Ну и как в этом случае найти число сочетаний? Просто запомните следующее правило:
Пусть имеется набор элементов, среди которых надо выбрать При введении дополнительных ограничений числа уменьшаются на одинаковую величину.
Другими словами, если из 5 ручек надо выбрать 3, при этом одна из них должна быть красной, то выбирать придется элементов элемента. Таким образом, вместо надо считать
Теперь посмотрим, как это правило работает на конкретных примерах:
Задача. В группе из 20 студентов, среди которых 2 отличника, надо выбрать 4 человека для участия в конференции. Сколькими способами можно выбрать этих четверых, если отличники обязательно должны попасть на конференцию?
Итак, есть группа студентов. Но выбрать надо из них. Если бы не было дополнительных ограничений, то количество вариантов равнялось числу сочетаний
Однако нам поставили дополнительное условие: 2 отличника должны быть среди этих четырех. Таким образом, согласно приведенному выше правилу, мы уменьшаем числа на 2. Имеем:
Задача. У Пети в кармане есть 8 монет, из которых 6 монет по рублю и 2 монеты по 10 рублей. Петя перекладывает какие-то три монеты в другой карман. Сколькими способами Петя может это сделать, если известно, что обе монеты по 10 рублей оказались в другом кармане?
Итак, есть монет. Петя перекладывает монеты, из которых 2 — десятирублевые. Получается, что из 3 монет, которые будут переложены, 2 уже зафиксированы, поэтому числа надо уменьшить на 2. Имеем:
В обоих примерах я намеренно пропустил детали работы с факториалами — попробуйте выполнить все расчеты самостоятельно. Разумеется, для этих задач существуют и другие способы решения. Например, с помощью закона умножения. В любом случае, ответ будет один и тот же.
В заключение отмечу, что в первой задаче мы получили 153 варианта — это намного меньше, чем исходные вариантов. Аналогично, 3 монеты из 8 можно переложить способами, что значительно больше 6 способов, которые мы получили в последней задаче.
Эти примеры наглядно демонстрируют, что введение любых ограничений значительно сокращает нашу «свободу выбора».
Как из нескольких чисел выявить нестандартные
.
Рассмотрим задачу о числе сочетаний с повторениями: имеется по r одинаковых предметов каждого из n различных типов; сколькими способами можно выбрать m (
) из этих (n*r) предметов?
.
.
.
«Самое большое простое число 2 32582657 -1. И я с гордостью утверждаю, что запомнил все его цифры… в двоичной форме».
Карл Померанс
Как из нескольких чисел выявить нестандартные
.
Рассмотрим задачу о числе сочетаний с повторениями: имеется по r одинаковых предметов каждого из n различных типов; сколькими способами можно выбрать m () из этих (n*r) предметов?
.
.
.
«Самое большое простое число 2 32582657 -1. И я с гордостью утверждаю, что запомнил все его цифры… в двоичной форме».
Карл Померанс
Крутейшие задачи на комбинаторику
Подобрали для вас самые интересные задачи на комбинаторику — когда решение кроется в том, как мы сочетаем, группируем и комбинируем данные. Очень приятные задачки для крутых разработчиков и очень полезные — для начинающих.
Все эти задачки мы уже загадывали вам в 2019 году, пора их собрать в одном месте для удобства и кайфа.
Задача про тысячу пробирок
Представьте, что вы работаете в лаборатории, которая ищет средство от смертельной болезни. Вам на испытание пришла партия из 1 000 пробирок с лекарством, которое нужно опробовать на людях. Проверка санкционирована Минздравом, у вас имеются все лицензии, но есть проблема. Вы узнаёте, что одну пробирку перепутали и по ошибке отправили вместо лекарства ядовитый реактив. Внешне он ничем не отличается от медикамента.
Вам нужно как можно скорее передать пробирки в больницы для запуска клинического теста, но отправлять отравленную пробирку нельзя: погибнут люди. Тесты всех пробирок займут месяцы, это очень долго. Но у вас есть лабораторные мыши. Вы знаете, что лекарство безвредно для них, но даже капля яда убьёт мышь за сутки. У вас 10 мышей, а пробирок — 1 000.
Как вычислить пробирку с ядом как можно быстрее? За какое время можно гарантированно найти пробирку с ядом?
Самопроверка. Прежде чем узнать решение, ответьте на такие вопросы:
- Рационально ли выбирать какие-то отдельные бутылки из общей массы или нужно протестировать всё?
- Есть ли в условии задачи лимит по количеству введённого лекарства?
- Обязаны ли мы тестировать одну мышь только одной пробиркой? Можно ли использовать одно животное несколько раз или дать ему лекарства из нескольких пробирок?
Сначала кажется, что решить задачу нереально — мышей в 100 раз меньше, чем пробирок. Значит, нам нужно как-то научиться быстро сокращать количество элементов, которые нужно проверить.
Мы знаем, что даже капля яда убьёт мышь за сутки. Значит, если мы смешаем эту каплю с настоящим лекарством, яд тоже сработает. Воспользуемся этим так:
Разделим все пробирки на равные группы — по 100 пробирок в каждой.
В каждой группе возьмём по капле из каждой пробирки и смешаем их. Получим 10 смесей, одна из которых отравлена, и дадим каждой мыши свою смесь. Через сутки мы увидим, какой грызун погиб, и поймём, где конкретно был яд.
Теперь у нас осталось 100 пробирок и девять мышей. Видите, мы за сутки сократили количество пробирок в 10 раз. Будем использовать этот же приём и дальше: делить сосуды на равные группы и делать смеси. На второй день разделим 100 пробирок на девять групп:
Восемь групп по 11 пробирок и одна группа из 12 пробирок.
Как видите, на совсем равные части поделить не получилось, но это не критично — задача всё равно решается. Теперь даём смеси мышам и через сутки смотрим, какое животное погибнет на этот раз.
Предположим самый сложный случай — яд был в смеси из 12 пробирок. У нас остаётся восемь мышей и 12 пробирок. Их тоже делим на восемь групп:
Четыре группы по две пробирки и четыре группы по одной пробирке.
Снова даём вещество мышам и через сутки смотрим на результат. Если погибла особь, которая пила только из одной пробирки, — то она и была отравлена, а значит, мы нашли яд за три дня. Если эта мышь дегустировала смесь из двух сосудов, то на следующий день мы берём эти две пробирки, две мыши из тех, что остались, и обеим даём попробовать своё лекарство. Через сутки узнаем, где был яд.
В итоге за три или за четыре дня мы точно сможем сказать, какая пробирка в партии была перепутана.
Ответ: максимум за четыре дня мы найдём яд.
Сторож и фонарик
Сторож проверял инвентарь и заметил, что у него не работает фонарик. Он пошарил в тумбочке и вытащил 8 батареек. Насколько он помнил, половина из них — свежие, потому что он совсем недавно покупал в магазине батарейки по акции. А вот ещё четыре точно разряжены: сторож планировал их утилизировать, но оказалось, что сделать это в России не так просто. В общем, теперь сторожу нужно вставить батарейки в фонарик, чтобы проверить, какие из них ещё не разряжены.
Чтобы фонарик заработал, в него должны быть вставлены две заряженные батарейки. Сколько максимально пар батареек нужно перебрать сторожу, чтобы фонарик точно заработал?
Назовём каждую батарейку отдельной буквой — А, Б, В, Г, Д, Е, Ж, З. Это позволит нам не перепутать батарейки, когда мы будем менять их местами.
Теперь разобьём батарейки на пары и проверим в фонарике каждую из них:
(А Б) (В Г) (Д Е) (Ж З) — это четыре первые пары.
Если фонарик заработал на какой-то из них — отлично, мы нашли нужную пару.
Если лампочка так и не загорелась, значит, в каждой паре у нас оказалась одна хорошая батарейка и одна плохая. Давайте подумаем, почему.
Если бы в одной паре было две нерабочие батарейки, то на остальные три пары приходилось бы две нерабочие и четыре рабочие батарейки. Неизбежно одна из пар подобралась бы с двумя рабочими батарейками.
Следовательно, раз ни одна из пар не включила фонарь, в любой из них есть одна рабочая и одна нерабочая батарейка.
Теперь возьмём любые две пары — например (А Б) и (В Г) — и поменяем в них первые батарейки местами. Получим:
(В Б) и (А Г) — в этот момент мы проверили уже шесть пар.
Если фонарик не заработал и после этой перестановки, значит, мы поменяли местами одинаковые батарейки: хорошую заменили на хорошую или плохую — на плохую. Выходит, нужно взять вторую батарейку из первой пары и поменять её с первой батарейкой из второй пары:
Берём пару (В Б), достаём оттуда вторую батарейку Б и ставим её на первое место в паре (А Г), получаем (Б Г) — это седьмая пара.
Если фонарик загорелся, значит, второй мы поставили хорошую батарейку. Если фонарик всё ещё не светит, получается, в этой паре у нас две плохих батарейки, а две хороших остались в другой — (В А). Ставим их в фонарик, и готово!
Получается, что нам понадобится проверить максимум 7 пар.
Как надевают носки настоящие программисты
Представьте, что вы затеяли переезд, сложили все вещи по ящикам и коробкам и отвезли их в новое место. В новом доме пока что беспорядок: коробки лежат друг на друге, что-то свалено в углу и до некоторых ящиков сложно добраться. В одном из таких ящиков вперемешку лежат носки разного цвета: пять синих, шесть жёлтых, семь красных и восемь чёрных. Так уж получилось.
Вам нужно выйти на улицу в носках одинакового цвета, но из-за беспорядка сложно достать сам ящик — можно вытаскивать оттуда только по одному предмету. В ящике щель, в которую вы можете засунуть руку, но не можете увидеть, за каким носком потянулись.
Вопрос: сколько максимально нужно достать носков из ящика, чтобы получить пару одинакового цвета? А что, если требуется взять с собой запасной комплект и он тоже должен быть одного цвета?
Для одной пары
Давайте возьмём самый неудачный случай и каждый раз будем вытаскивать носок нового цвета. Например, мы сначала вытягиваем жёлтый носок, затем красный, потом синий и чёрный. Получилось четыре экземпляра без пары, в них на улицу не уйдёшь.
А теперь какой бы носок мы ни вытащили следующим, его цвет в любом случае совпадёт с тем, что у нас уже есть в руках. Например, пятым оказался жёлтый — а он у нас уже есть. Всё, пара готова, мы направляемся к выходу, и для этого нам потребовалось вытащить максимально пять носков. Это было легко.
Для двух пар
Две пары могут быть разного цвета — давайте это учтём при решении.
В первой части мы нашли комплект за пять попыток. В итоге у нас есть одна пара жёлтых носков и три одиноких носка: синий, красный и чёрный. Давайте подберём пару к ним.
Снова рассмотрим вариант, когда всё идёт не так быстро, как бы нам хотелось. Допустим, шестой носок, который мы вытащили, — опять жёлтый. Теперь у нас снова четыре предмета разного цвета, как в первом примере. Поэтому мы уже знаем, что любой следующий носок даст нам пару, а значит, для двух пар понадобится максимально семь попыток.
Угон, криминал и логика
В одном городе ограбили магазин, и дело поручили инспектору — бывшему программисту. Он опросил трёх свидетелей преступления и выяснил, что преступники скрылись на машине. Но все три свидетеля говорили разные вещи:
- Первый утверждал, что это были синие «Жигули».
- Второй — что это чёрная «Волга».
- Третий вообще сказал, что это был «Мерседес», но точно не синий.
Инспектору показалось подозрительным такое несоответствие в показаниях, поэтому он проверил свидетелей на старом детекторе лжи. Но детектор был настолько старый, что лишь показал, что каждый из свидетелей соврал про марку или цвет. Все думали, что найти машину не получится, но инспектор смог вычислить автомобиль преступников.
Как он это сделал?
На удивление, эта задача решается простым алгоритмом с элементами перебора: берём высказывание первого свидетеля, предполагаем, что первая часть верная, а вторая — нет. После этого проверяем, насколько это совпадает с остальными условиями задачи и высказываниями других свидетелей.
1-й вариант: допустим, первый свидетель сказал правду про цвет, но наврал про марку. Получается, что цвет машины — синий, и это точно не «Жигули».
Тогда второй свидетель, который сказал про чёрную «Волгу», наврал про цвет, а это значит, что про марку он сказал правду. Получается, что машина была — синяя «Волга».
Теперь проверим показания третьего свидетеля. Он тоже один раз сказал правду, но его ответ был — «точно не синий „Мерседес“». Выходит, что он наврал и про цвет, и про марку, а по условиям задачи такого не может быть: каждый хоть раз сказал правду.
Получается, что первый свидетель наврал про цвет, а значит, про марку он сказал правду. Проверим это.
2-й вариант: допустим, первый свидетель сказал правду про марку — «Жигули», но наврал про цвет. Получается, что у нас есть «Жигули» точно не синего цвета.
Второй свидетель сказал, что это была чёрная «Волга», но мы уже поняли, что это были «Жигули», а значит, второй наврал про марку и сказал правду про цвет. А цвет у второго свидетеля — чёрный. Получились чёрные «Жигули». Проверим показания третьего.
Третий свидетель сказал, что это был «точно не синий „Мерседес“», но мы-то уже знаем про «Жигули», поэтому третий с маркой тоже наврал. А про цвет он как раз сказал правду: не синий — это тоже может быть чёрный.
Всё сходится: преступники уехали на чёрных «Жигулях». Хотя лучше бы на «Мерседесе».
Кто держит зебру? (задача Джейсона Стэйтема)
В пацанских пабликах пишут так: Джейсон Стэйтем использовал эту задачу, чтобы находить людей, способных мыслить логически на одном с ним уровне. Возможно, это был Альберт Эйнштейн. Но даже если это не он, задача всё равно чертовски интересная.
Задача звучит так:
- На улице стоят пять домов.
- Англичанин живёт в красном доме.
- У испанца есть собака.
- В зелёном доме пьют кофе.
- Украинец пьёт чай.
- Зелёный дом стоит сразу справа от белого дома.
- Тот, кто майнит Bitcoin, разводит улиток.
- В жёлтом доме майнят Ethereum.
- В центральном доме пьют молоко.
- Норвежец живёт в первом доме.
- Сосед того, кто майнит Stellar, держит лису.
- В доме по соседству с тем, в котором держат лошадь, майнят Ethereum.
- Тот, кто майнит IOTA, пьёт апельсиновый сок.
- Японец майнит Monero.
- Норвежец живёт рядом с синим домом.
В целях ясности следует добавить, что каждый из пяти домов окрашен в свой цвет, а их жители — разных национальностей, владеют разными животными, пьют разные напитки и майнят разные криптовалюты. Ещё одно замечание: в утверждении 6 «справа» означает справа относительно вас.
Вопрос: кто пьёт воду, а кто держит зебру?
Чтобы не было спорных моментов, добавим следующее:
- дома расположены в ряд, друг за другом;
- один из жильцов точно пьёт воду, и кто-то из жильцов точно держит зебру.
Суть решения сводится к следующему: мы шаг за шагом будем брать данные из условий, чтобы найти неизвестные пока значения, а все результаты вписывать в такую таблицу:
| Дом | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| Цвет | жёлтый | синий | ? | ? | ? |
| Национальность | норвежец | ? | ? | ? | ? |
| Напиток | вода | ? | ? | ? | ? |
| Криптовалюта | Ethereum | ? | ? | ? | ? |
| Животное | ? | ? | ? | ? | ? |
Затем мы будем брать новые результаты, смотреть, как их можно совместить с условиями, также занесём в таблицу и станем так делать до тех пор, пока не заполним все ячейки.
Разбираемся с первым домом
В п. 10 явно сказано, что норвежец живёт в первом доме, а если добавить сюда п. 15 (норвежец живёт рядом с синим домом), то становится понятно, что второй дом — синий.
Теперь разберёмся с цветом первого дома. Мы уже знаем, что рядом с первым домом стоит синий дом, а значит это единственный дом, который стоит рядом с первым. Из пункта 6 (зелёный дом стоит сразу справа от белого дома) следует, что первый дом не может быть зелёным или белым — зелёный и белый должны стоять рядом, а у нас рядом с первым домом стоит синий. Остаются красный или жёлтый. Но в красном доме живёт англичанин — так написано в п. 2, поэтому остаётся только жёлтый. Первый дом — жёлтый.
Смотрим, что говорят нам условия задачи про жёлтый дом:
п. 8 — в жёлтом доме майнят Ethereum;
п. 12 — в доме по соседству с тем, в котором держат лошадь, майнят Ethereum.
Но у нас рядом с домом, где майнят Ethereum, стоит только второй дом, поэтому лошадь держат во втором доме.
Переходим к напиткам. Мы уже знаем, что в первом жёлтом доме живёт норвежец, который майнит Ethereum. Вот как это влияет на условия:
- Норвежец не пьёт чай, потому что это делает украинец в п. 5.
- Норвежец не пьёт кофе, потому что по п. 4 кофе пьют в зелёном доме.
- Норвежец также не пьёт молоко, потому что в п. 9 написано, что в центральном доме пьют молоко. Но так как первый дом — не центральный, то и молоко в первом доме не пьют.
- Норвежец не пьёт апельсиновый сок, потому что согласно п. 13 апельсиновый сок пьёт тот, кто майнит IOTA.
Поэтому единственное, что остаётся пить норвежцу, — это вода. Отлично, мы нашли ответ на первый вопрос. Не забудем занести всю найденную информацию в таблицу:
| Дом | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| Цвет | жёлтый | синий | ? | ? | ? |
| Национальность | норвежец | ? | ? | ? | ? |
| Напиток | вода | ? | молоко | ? | ? |
| Криптовалюта | Ethereum | ? | ? | ? | ? |
| Животное | ? | лошадь | ? | ? | ? |
Всё о втором доме
Начнём с криптовалюты.
Мы точно знаем, что это не Ethereum, потому что её майнит норвежец в первом доме. А ещё, раз у жильца синего дома есть лошадь, то он точно не майнит Bitcoin — в п. 7 написано, что тот, кто майнит Bitcoin, разводит улиток. Давайте поработаем с предположениями и проверим, насколько верное каждое из них.
Допустим, что во втором доме майнят IOTA. По п. 13 (тот, кто майнит IOTA, пьёт апельсиновый сок) жилец пьёт апельсиновый сок, а это значит, что тут живёт не украинец, потому что он пьёт чай (п. 5). Это также не англичанин, который живёт в красном доме (п. 2), и не испанец, потому что по п. 3 у испанца есть собака. Японец тоже тут жить не может, потому что по п. 14 японец майнит Monero, а не IOTA. Норвежец же, напомним, живёт в первом доме. Получается, что во втором доме никто не живёт, а такого не может быть, следовательно, наше предположение, что во втором доме майнят IOTA, неверное.
Идём дальше и предположим, что во втором доме майнят Monero, а значит, из п. 14 видно, что тут живёт японец (японец майнит Monero). Поэтому во втором доме не пьют чай, потому что чай пьёт украинец (п. 5), не пьют кофе, потому что кофе пьют в зелёном доме (п. 4). А ещё здесь не пьют молоко — молоко пьют в третьем доме (п. 9), и не пьют апельсиновый сок, потому что сок пьёт любитель IOTA (п. 13). А раз вода уже занята норвежцем, то получается, что во втором доме ничего не пьют. Такого не может быть, а значит, наше предположение, что во втором доме майнят Monero, неверное. Мы выяснили, что там не майнят Ethereum, Bitcoin, IOTA и Monero. Остаётся только Stellar — её и майнят во втором доме.
Давайте выясним национальность, зная название криптовалюты. Это не англичанин, который живёт в красном доме (п. 2), и не испанец с собакой (п. 3), потому что во втором доме держат лошадь. Ещё это не японец, который майнит Monero (п. 14), и не норвежец из первого дома. Получается, что во втором доме живёт украинец, а согласно п. 5 украинец пьёт чай.
Занесём новые данные в таблицу:
| Дом | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| Цвет | жёлтый | синий | ? | ? | ? |
| Национальность | норвежец | украинец | ? | ? | ? |
| Напиток | вода | чай | молоко | ? | ? |
| Криптовалюта | Ethereum | Stellar | ? | ? | ? |
| Животное | ? | лошадь | ? | ? | ? |
Где живёт лиса
Исходя из п. 11 (сосед того, кто майнит Stellar, держит лису), мы понимаем, что раз Stellar майнят во втором доме, то лиса живёт или в первом, или в третьем доме.
Допустим, что лиса — в третьем доме. Теперь делаем внезапный поворот и зададимся вопросом: а что тогда пьёт человек из п. 7, который разводит улиток и майнит Bitcoin? Он не пьёт сок, потому что сок пьёт любитель IOTA (п. 13), и молоко — его пьют в третьем доме, где, как мы предполагаем, держат лису. Вода и чай уже заняты на предыдущих этапах. Остаётся только кофе, который пьют в зелёном доме (п. 4).
А раз так, то получается, что в зелёном доме живёт человек, который разводит улиток, майнит Bitcoin и пьёт кофе. Он точно не норвежец или украинец — мы это выяснили раньше. И это точно не англичанин, который живёт в красном доме (п. 2), не испанец, у которого собака (п. 3), и не японец, который майнит Monero (п. 14). Мы исключили все национальности, а такого не может быть, поэтому наше исходное предположение о том, что лиса живёт в третьем доме — неверное.
Получается, что лиса живёт в первом доме. Добавим это в табличку:
| Дом | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| Цвет | жёлтый | синий | ? | ? | ? |
| Национальность | норвежец | украинец | ? | ? | ? |
| Напиток | вода | чай | молоко | ? | ? |
| Криптовалюта | Ethereum | Stellar | ? | ? | ? |
| Животное | лиса | лошадь | ? | ? | ? |
Третий дом
У нас осталось два свободных напитка — кофе и апельсиновый сок, которые пьют в четвёртом и пятом доме.
Тот, кто майнит Bitcoin и разводит улиток, не живёт в доме, где пьют сок, потому что его пьёт любитель IOTA (п. 13). Значит, делаем предположение, что любитель улиток живёт в доме, где пьют кофе, а по п. 4 кофе пьют в зелёном доме. А мы только что разобрали в разделе про лису именно ту ситуацию, когда жилец зелёного дома разводит улиток и пьёт кофе. Тогда мы пришли к выводу, что это невозможно, а значит, любитель улиток не может пить кофе или сок, поэтому он не живёт в четвёртом или пятом доме.
Получается, что любитель улиток, который майнит Bitcoin, живёт в третьем доме.
| Дом | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| Цвет | жёлтый | синий | ? | ? | ? |
| Национальность | норвежец | украинец | ? | ? | ? |
| Напиток | вода | чай | молоко | ? | ? |
| Криптовалюта | Ethereum | Stellar | BitCoin | ? | ? |
| Животное | лиса | лошадь | улитки | ? | ? |
Четвёртый и пятый дома
В зелёном доме пьют кофе (п. 4), а любитель IOTA пьёт сок (п. 13), поэтому он не может жить в зелёном доме. Получается, что в зелёном доме майнят Monero, а раз так, то это — японец (п. 14).
Это означает, что в оставшемся доме пьют сок и майнят IOTA, и дом этот на 3-м или на 4-м месте (по п. 6 — зелёный дом стоит сразу справа от белого дома). Допустим, в третьем доме живёт испанец, у которого должна быть собака (п. 3), но в таблице в третьем доме уже есть улитки, а значит, испанец с собакой живёт в четвёртом доме, и как раз именно он пьёт сок и майнит IOTA.
Третий дом методом исключения остаётся англичанину, а это значит, что третий дом — красный (п. 2). Получается, что у испанца белый дом.
Запишем всё в таблицу:
| Дом | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| Цвет | жёлтый | синий | красный | белый | зелёный |
| Национальность | норвежец | украинец | англичанин | испанец | японец |
| Напиток | вода | чай | молоко | сок | кофе |
| Криптовалюта | Ethereum | Stellar | BitCoin | IOTA | Monero |
| Животное | лиса | лошадь | улитки | собака | ? |
Зебра
У нас осталась одна незаполненная клетка в таблице, которая тоже методом исключения достаётся зебре.
Теперь мы можем ответить на вопросы по задаче: воду пьёт норвежец, а зебру держит японец.
Правила комбинаторики в задаче B6
Решая задачи по теории вероятностей, мы постоянно используем одну и ту же формулу, которая одновременно является классическим определением вероятности:
где k — число благоприятных исходов, n — общее число исходов (см. «Тест по теории вероятностей»).
И эта формула прекрасно работает до тех пор, пока задачи были легкими, а числа, стоящие в числителе и знаменателе — очевидными.
Однако последние пробные экзамены показали, что в настоящем ЕГЭ по математике могут встречаться значительно более сложные конструкции. Отыскание значений становится проблематичным. В таком случае на помощь приходит комбинаторика. Ее законы работают там, где искомые значения не выводятся непосредственно из текста задачи.
В сегодняшнем уроке не будет строгих формулировок и длинных теорем — они слишком сложны и, к тому же, совершенно бесполезны для решения настоящих задач B6. Вместо этого мы рассмотрим простые правила и разберем конкретные задачи, которые действительно встречаются на ЕГЭ. Итак, поехали!
Число сочетаний и факториалы
Пусть имеется n объектов (карандашей, конфет, бутылок водки — чего угодно), из которых требуется выбрать различных объектов. Тогда количество вариантов такого выбора называется элементов Это число обозначается и считается по специальной формуле.
Обозначение:
Выражение n ! читается как «эн-факториал» и обозначает произведение всех натуральных чисел включительно:
Кроме того, в математике по определению считают, подобный бред редко, но все же встречается в задачах по теории вероятностей.
Что дает нам эта формула? На самом деле, без нее не решается практически ни одна серьезная задача.
К сожалению, в школе совершенно не умеют работать с факториалами. Кроме того, в формуле числа сочетаний очень легко запутаться: где стоит и что обозначает Поэтому для начала просто запомните: меньшее число всегда стоит сверху — точно так же, как и в формуле определения вероятности (вероятность никогда не бывает больше единицы).
Для лучшего понимания разберем несколько простейших комбинаторных задач:
Задача. У бармена есть 6 сортов зеленого чая. Для проведения чайной церемонии требуется подать зеленый чай ровно 3 различных сортов. Сколькими способами бармен может выполнить заказ?
Тут все просто: есть n = 6 сортов, из которых надо выбрать сорта. Число сочетаний можно найти по формуле:
Задача. В группе из 20 студентов надо выбрать 2 представителей для выступления на конференции. Сколькими способами можно это сделать?
Опять же, всего у нас есть n = 20 студентов, а выбрать надо студента. Находим число сочетаний:
Обратите внимание: красным цветом отмечены множители, входящие в разные факториалы. Эти множители можно безболезненно сократить и тем самым значительно уменьшить общий объем вычислений.
Задача. На склад завезли 17 серверов с различными дефектами, которые стоят в 2 раза дешевле нормальных серверов. Директор купил в школу 14 таких серверов, а сэкономленные деньги своровал и купил дочке шубу из меха соболя за 200 000 рублей. Сколькими способами директор может выбрать бракованные серверы?
В задаче довольно много лишних данных, которые могут сбить с толку. Наиболее важные факты: всего есть серверов, а директору надо серверов. Считаем число сочетаний:
Красным цветом снова обозначены множители, которые сокращаются. Итого, получилось 680 комбинаций. В общем, директору есть из чего выбрать.
Как видите, число сочетаний из n по k считается достаточно просто. Проблема в том, что многие школьники никогда не работали с факториалами. Для них это новый и незнакомый математический объект, и для его освоения требуется некоторая тренировка.
Хорошая новость состоит в том, что во многих задачах формулы оказывается вполне достаточно для нахождения ответа. Но есть и плохая новость: в тех редких случаях, когда нужны дополнительные правила, решение задачи резко усложняется. Эти правила мы сейчас и рассмотрим.
Закон умножения
в комбинаторике: число сочетаний (способов, комбинаций) в независимых наборах умножается.
Другими словами, пусть имеется A способов выполнить одно действие выполнить другое действие. Путь также эти действия независимы, т.е. никак не связаны между собой. Тогда можно найти число способов выполнить первое и второе действие по формуле:
Задача. У Пети есть 4 монеты по 1 рублю и 2 монеты по 10 рублей. Петя, не глядя, достал из кармана 1 монету номиналом 1 рубль и еще 1 монету номиналом 10 рублей, чтобы купить сигарету за 11 рублей у бабули в подземном переходе. Сколькими способами он может выбрать эти монеты?
Итак, сначала Петя достает монету имеющихся монет номиналом 1 рубль. Число способов сделать это равно
Затем Петя снова лезет в карман и достает монету имеющихся монет номиналом 10 рублей. Здесь число сочетаний равно
Поскольку эти действия независимы, общее число вариантов равно
Задача. В корзине лежат 8 белых шаров и 12 черных. Сколькими способами можно достать из этой корзины 2 белых шара и 2 черных?
Всего в корзине белых шаров, из которых надо выбрать шара. Это можно сделать различными способами.
Кроме того, в корзине имеется черных шаров, из которых надо выбрать опять же шара. Число способов сделать это равно
Поскольку выбор белого шара и выбор черного — события независимые, общее число комбинаций считается по закону умножения: Как видим, вариантов может быть довольно много.
Закон умножения показывает, сколькими способами можно выполнить сложное действие, которое состоит из двух и более простых — при условии, что все они независимы.
Именно этой формулы многим не хватило для решения задачи B6 на пробном ЕГЭ по математике. Разумеется, существуют и другие методы решения, в которых комбинаторика не используется — и мы обязательно рассмотрим их ближе к настоящему экзамену. Однако ни один из них не сравнится по надежности и лаконичности с теми приемами, которые мы сейчас изучаем.
Закон сложения
Если закон умножения оперирует «изолированными» событиями, которые не зависят друг от друга, то в законе сложения все наоборот. Здесь рассматриваются взаимоисключающие события, которые никогда не случаются одновременно.
Например, «Петя вынул из кармана 1 монету» и «Петя не вынул из кармана ни одной монеты» — это взаимоисключающие события, поскольку вынуть одну монету и при этом не вынуть ни одной невозможно.
Аналогично, события «Выбранный наугад шар — белый» и «Выбранный наугад шар — черный» также являются взаимоисключающими.
в комбинаторике: если два взаимоисключающих действия можно выполнить способами соответственно, то эти события можно объединить. При этом возникнет новое событие, которое можно выполнить способами.
Другими словами, при объединении взаимоисключающих действий (событий, вариантов) число их комбинаций складывается.
Можно сказать, что закон сложения — это логическое «ИЛИ» в комбинаторике, когда нас устраивает любой из взаимоисключающих вариантов. И наоборот, закон умножения — это логическое «И», при котором нас интересует одновременное выполнение и первого, и второго действия.
Задача. В корзине лежат 9 черных шаров и 7 красных. Мальчик достает 2 шара одинакового цвета. Сколькими способами он может это сделать?
Если шары одинакового цвета, то вариантов немного: оба они либо черные, либо красные. Очевидно, что эти варианты — взаимоисключающие.
В первом случае мальчику предстоит выбирать черных шара имеющихся. Число способов сделать это равно
Аналогично, во втором случае выбираем красных шара возможных. Число способов равно
Осталось найти общее количество способов. Поскольку варианты с черными и красными шарами — взаимоисключающие, по закону сложения имеем:
Задача. В ларьке продаются 15 роз и 18 тюльпанов. Ученик хочет купить 3 цветка для своей одноклассницы, причем все цветы должны быть одинаковыми. Сколькими способами он может составить такой букет?
По условию, все цветы должны быть одинаковыми. Значит, будем покупать либо 3 розы, либо 3 тюльпана. В любом случае,
В случае с розами придется выбирать вариантов, поэтому число сочетаний равно Для тюльпанов же а число сочетаний —
Поскольку розы и тюльпаны — это взаимоисключающие варианты, работаем по закону сложения. Получаем общее число вариантов Это и есть ответ.
Дополнительные условия и ограничения
Очень часто в тексте задачи присутствуют дополнительные условия, накладывающие существенные ограничения на интересующие нас сочетания. Сравните два предложения:
- Имеется набор из 5 ручек разных цветов. Сколькими способами можно выбрать 3 ручки для обводки чертежа?
- Имеется набор из 5 ручек разных цветов. Сколькими способами можно выбрать 3 ручки для обводки чертежа, если среди них обязательно должен быть красный цвет?
Чувствуете разницу? В первом случае мы вправе брать любые цвета, какие нам нравятся — дополнительных ограничений нет. Во втором случае все сложнее, поскольку мы обязаны выбрать ручку красного цвета (предполагается, что она есть в исходном наборе).
Очевидно, что любые ограничения резко сокращают итоговое количество вариантов. Ну и как в этом случае найти число сочетаний? Просто запомните следующее правило:
Пусть имеется набор элементов, среди которых надо выбрать При введении дополнительных ограничений числа уменьшаются на одинаковую величину.
Другими словами, если из 5 ручек надо выбрать 3, при этом одна из них должна быть красной, то выбирать придется элементов элемента. Таким образом, вместо надо считать
Теперь посмотрим, как это правило работает на конкретных примерах:
Задача. В группе из 20 студентов, среди которых 2 отличника, надо выбрать 4 человека для участия в конференции. Сколькими способами можно выбрать этих четверых, если отличники обязательно должны попасть на конференцию?
Итак, есть группа студентов. Но выбрать надо из них. Если бы не было дополнительных ограничений, то количество вариантов равнялось числу сочетаний
Однако нам поставили дополнительное условие: 2 отличника должны быть среди этих четырех. Таким образом, согласно приведенному выше правилу, мы уменьшаем числа на 2. Имеем:
Задача. У Пети в кармане есть 8 монет, из которых 6 монет по рублю и 2 монеты по 10 рублей. Петя перекладывает какие-то три монеты в другой карман. Сколькими способами Петя может это сделать, если известно, что обе монеты по 10 рублей оказались в другом кармане?
Итак, есть монет. Петя перекладывает монеты, из которых 2 — десятирублевые. Получается, что из 3 монет, которые будут переложены, 2 уже зафиксированы, поэтому числа надо уменьшить на 2. Имеем:
В обоих примерах я намеренно пропустил детали работы с факториалами — попробуйте выполнить все расчеты самостоятельно. Разумеется, для этих задач существуют и другие способы решения. Например, с помощью закона умножения. В любом случае, ответ будет один и тот же.
В заключение отмечу, что в первой задаче мы получили 153 варианта — это намного меньше, чем исходные вариантов. Аналогично, 3 монеты из 8 можно переложить способами, что значительно больше 6 способов, которые мы получили в последней задаче.
Эти примеры наглядно демонстрируют, что введение любых ограничений значительно сокращает нашу «свободу выбора».
Интересное и простое из комбинаторики. Функция Эйлера
Прежде всего хочу сказать, мне всего 14 лет. Я надеюсь, что информация, которой поделюсь, будет для кого-то интересна.
Речь пойдет о некоторых задачах комбинаторики.
Сколько вариантов расставить n предметов?
Способ №1
Способ №2
Допустим, нам нужно узнать, сколько вариантов в расстановке 10 предметов. Умножаем: 1x2x3..x10
Получим: 10! = 3628800
Как из n предметов выбрать k предметов?
Способ №1
Допустим, вы — организатор лотереи. Из 10 участников вам нужно выбрать 2 победителя. Вы можете узнать количество способов сделать это.
Так же как и в случае с факториалом, можно посчитать вручную. Выбирать n предметов, пока не иссякнут все варианты.
Цитирую: но есть способ, который по своей простоте опережает приведенный ранее способ.
Способ №2
Высчитывается по формуле:
Итак, сколько же способов из 10 участников выбрать 2 победителя?
Ответ вполне себе простой —
Числа Фибоначчи
Стоит отдать должное человеку, который «придумал» эти числа. Леонардо Пизанский. Думаю достаточно, чтобы Вы запомнили имя этого великого человека.
Приступим. Числа Фибоначчи применяются в Теории Чисел. Если сказать честно, я знаю не слишком много об этих числах.
Числа Фибоначчи — это последовательность чисел, в котором каждое последующее числовое значение равно сумме двух предыдущих. Первые два числа Фибоначии — единицы. Соответственно, 3-е число = 2.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946.
Еще раз повторюсь — я знаю не слишком много об этих числах. Если я еще не слишком вас утомил/отпугнул/надоел — идем дальше.
Функция Эйлера
В этом пункте я попытаюсь выложить все, что знаю об этом. Я потратил достаточно времени и сил, чтобы изучить эту, между прочим абсолютно простою вещь.
По правде говоря, я очень горжусь тем, что такой человек как Леонард Эйлер жил в России.
К делу. Есть три разных способа посчитать функцию Эйлера. На выбор одного из способов влияют некоторые факторы.
Функция Эйлера обозначается (читать как фи от n).
Способ №1
Увы, но этот способ применять следует для высчитывания функции простых чисел.
Например, функция Эйлера для 3 =
Способ №2
Данный способ следует применять если число можно представить как степень какого-то числа. Например, 9 — это
Посчитаем функцию для 9.
Способ №3
Если число нельзя представить как степень, но можно представить как два множителя — этот способ нам и нужен.
Тут немного сложнее. Нужно разложить число на два множителя, посчитать функцию для каждого из множителей и полученные результаты перемножить.
Также хочу отметить, что если число можно представить и как степень и как два множителя, то в преимуществе всегда степень какого-то числа (о как, в рифму).
Как из нескольких чисел выявить нестандартные
.
Рассмотрим задачу о числе сочетаний с повторениями: имеется по r одинаковых предметов каждого из n различных типов; сколькими способами можно выбрать m () из этих (n*r) предметов?
.
.
.
«Самое большое простое число 2 32582657 -1. И я с гордостью утверждаю, что запомнил все его цифры… в двоичной форме».
Карл Померанс
Виды нестандартных задач, способы их решения
В данной презентации собраны основые виды нестандартных задач, изучаемых в начальной школе и рассмотрены способы их решения.
Просмотр содержимого документа
«Виды нестандартных задач, способы их решения»
Эффективное решение нестандартных творческих задач
для младших школьников
Знание только тогда знание, когда оно приобретено усилиями твоей мысли, а не памяти.
Развитие творческих способностей – важнейшая задача начального образования, ведь этот процесс пронизывает все этапы развития личности ребёнка, пробуждает инициативу и самостоятельность принимаемых решений, привычку к свободному самовыражению, уверенность в себе.
Творчество – это всегда новое, неизведанное, непредсказуемое, увлекательное и захватывающее.
Одним из средств развития интеллектуальных и творческих способностей младших школьников является решение нестандартных задач.
« Нестандартные задачи – это такие задачи, для которых в курсе математики не имеется общих правил и положений, определяющих точную программу их решения»,- писал Л.М.Фридман.
Нестандартная задача – это задача, алгоритм решения которой учащимся неизвестен, то есть учащиеся не знают заранее ни способов решения, ни того, на какой учебный материал опирается решение.
Понятие «нестандартная задача» является относительным.
Одна и та же задача может быть стандартной или нестандартной, в зависимости от того, знакомы ли учащиеся со способами решения задач такого типа.
При решении занимательных задач преследуются следующие цели:
- формирование и развитие мыслительных операций: анализа, синтеза, сравнения, аналогии, обобщения и т.д.;
- развитие и тренинг мышления вообще и творческого в частности;
- поддержание интереса к предмету, к учебной деятельности;
- развитие качеств творческой личности (познавательная активность, упорство в достижении цели, самостоятельность, усидчивость);
- подготовка учащихся к творческой деятельности (творческое усвоение знаний, способов действий, умение переносить знания и способы действий в незнакомые ситуации и видеть новые функции объекта)
Помогая ученику, учитель должен оказать ему внутреннюю помощь, т.е. ограничиться такими подсказками, которые могли бы рождаться в сознании самого ученика, и избегать внешней помощи, т.е. давать куски решения, которые не связаны с сознанием ученика.
Три заповеди учителя (по Д. Пойа):
1.Старайся научить своих учеников догадываться.
2.Старайся научить своих учеников доказывать.
3.Пользуйся наводящими указаниями, но не старайся навязывать своего мнения насильно.
Нестандартные задачи по математике, используемые в начальной школе, условно можно разделить на следующие группы :
- задачи на взвешивание
- задачи на переливание;
- задачи, решаемые с «конца»;
- задачи на установление взаимно-однозначного соответствия между множествами;
- задачи о лжецах;
- задачи о переправах;
- задачи, решаемые с помощью логических выводов и т.д.
Методы реш ения:
- алгебраический;
- арифметический;
- графический;
- практический;
- метод предположения;
- метод перебора
Способы решения логических задач:
- способ рассуждений;
- способ составления таблиц;
- способ построения графов;
- способ бильярда;
- способ кругов Эйлера
Приёмы работы над задачей
1. Изучение условия задачи.
2. Выдвижение идеи(плана) задачи.
3. Поиск аналогии, сравнительные чертежи.
4. Разбиение задачи на подзадачи.
5. Решение одной задачи несколькими способами.
6. Приём разбора готового решения.
Эффективность обучения младших школьников решению нестандартных задач зависит от нескольких условий :
1. Задачи следует вводить в процесс обучения в определенной системе с постепенным нарастанием сложности, так как непосильная задача мало повлияет на развитие учащихся.
2. Необходимо предоставлять ученикам максимальную самостоятельность в поиске решения задач, давать возможность пройти до конца по неверному пути, убедиться в ошибке, вернуться к началу и искать другой, верный путь решения.
3. Нужно помочь учащимся осознать некоторые способы, приемы, общие подходы к решению нестандартных арифметических задач.
На первом этапе учащиеся должны:
- усвоить процесс решения любой задачи(читаю задачу, выделяю, что известно и что надо узнать);
- познакомиться с приемами работы над задачей(видами наглядной интерпретации, поиска решения, проверки решения задачи и др.)
На втором этапе учащиеся применяют ранее сформулированные общие приемы в ходе самостоятельного поиска решения конкретных задач.
При поиске решения незнакомой задачи полезно сделать чертеж (рисунок), т.к. именно он может быть способом решения задачи.
Памятка
Если тебе трудно решить задачу, то попробуй:
— сделать к задаче рисунок или чертеж (подумай, может быть нужно сделать на них дополнительные построения или изменить чертеж в процессе решения задачи);
— ввести вспомогательный элемент (часть);
— использовать для решения задачи способ подбора;
— переформулировать задачу другими словами, чтобы она стала более понятной и знакомой;
— разделить условие или вопрос задачи на части и решить ее по частям;
— начать решение задачи с «конца»
на взвешивание
и переливание
Задачи на взвешивание – достаточно распространенный вид математических задач. В таких задачах от решающего требуется локализовать отличающийся от остальных предмет по весу за ограниченное число взвешиваний.
Поиск решения в этом случае осуществляется путем операций сравнения, правда, не только одиночных элементов, но и групп элементов между собой.
Задача №1
Из девяти монет одна фальшивая: она легче остальных.
Как за два взвешивания на чашечных весах без гирь определить, какая именно монета фальшивая?
Решение:
- Разобьём монеты на 3 кучки по 3 монеты.
- Первое взвешивание: положим по 3 монеты на каждую чашку весов.
Возможны два варианта:
- Равновесие.
Тогда на весах только настоящие монеты, а фальшивая среди тех монет, которые не взвешивались.
2 . Одна из кучек легче.
Значит в ней фальшивая монета.
- Второе взвешивание:теперь требуется найти фальшивую среди трёх монет ( по методу первого взвешивания).
Задача №2
В мешке 24 кг гвоздей. Как, имея только чашечные весы без гирь, отмерить 9 кг гвоздей?
Решение:
Основная доступная операция – деление некоторого (произвольного) количества гвоздей на две равные по весу кучки.