Перебор случаев

Рассмотрим два случая.

1) Пусть делится на 5 (на отрезке имеется таких значений ). Для каждого такого значения подходят те и только те значения , при которых сумма остатков от деления на 7 и на 7 равна 0 или 7, т. е. подходит одно из каждых семи последовательных значений . Итого, для каждого значения получаем по 100 вариантов.

2) Пусть не делится на 5 (на отрезке имеется таких значений ). Для каждого такого подходят те и только те значения , кратные 5, при которых сумма остатков от деления на 7 и на 7 равна 0 или 7, т. е. подходит одно из каждых последовательных значений . Итого, для каждого значения получаем по 20 вариантов.

Суммируем количество пар: .

Возьмем какое-нибудь число Тогда возможны два варианта:

1. Если то и

2. Предположим Тогда Иначе
(а) Если
(b) Если
И так как то

Таким образом, для любого либо либо есть три различных числа таких, что

При этом любая функция с таким свойством подходит. Тогда найдем число функций с необходимым свойством.

1. Нет ни одной тройки элементов, что Значит, для всех чисел верно Такая функция одна.

2. Есть одна тройка элементов, что Выбрать тройку можно способами. При этом есть два способа задать функцию в тройке. Итого функций.

3. Есть две тройки элементов, что Выбрать первую тройку можно способами, остальные три элемента образуют вторую тройку. Но варианты, в которых выбрали в первую тройку и выбрали все кроме одинаковые. То есть способов разбить элементы на две тройки. При этом в каждой тройке есть два способа задать функцию. Итого функций.

Всего число функций равно

Начнём считать с вратарей. Место вратаря может занять только вратарь, поэтому у нас всегда всего 2 способа выбрать его.

Дальше рассмотрим три случая по количеству универсалов на месте защитников:

1. Среди выбранных защитников нет универсалов. Значит, количество так выбрать двух защитников в команду равно

На место нападающих в этом случае мы можем поставить либо нападающих, либо универсалов, следовательно, способов

Следовательно, вариантов команд в этом случае

2. Среди выбранных защитников один универсал. Значит, количество так выбрать двух защитников в команду равно

На место нападающих в этом случае мы можем поставить либо нападающих, либо оставшихся универсалов, следовательно, способов

Следовательно, вариантов команд в этом случае

3. Среди выбранных защитников оба являются универсалами. Значит, количество так выбрать двух защитников в команду равно

На место нападающих в этом случае мы можем поставить либо нападающих, либо оставшегося универсала, следовательно, способов

Следовательно, вариантов команд в этом случае

В итоге способов выбрать команду равно

Любой рассадке вечером можно сопоставить рассадку, в которой белка, сидевшая на дереве с номером (нумерация по часовой стрелке), сидит на дереве по модулю 6 (то есть просто белку переместили на противоположное место). Нетрудно видеть, что это противоположное место является либо тем местом, на котором белка сидела утром, либо соседним с ним. Значит, можно решить задачу, в которой каждая белка либо осталась на своём месте, либо перешла на соседнее.

Пусть изначально белки сидели в порядке . Рассмотрим случаи:

Все остаются на своих местах. Тогда есть только один случай ().

Если перемещается вправо на место , у есть два варианта действий. может переместиться влево(на место ) или переместиться вправо на место .

Рассмотрим движение по кругу. Если перемещается на место , то единственный способ для — переход к , переход к , переход к и переход к , в результате чего достигается . Каждый бельчонок может также двигаться влево(). Таким образом, тут два случая.

Некоторые бельчата из соседних пар , , меняются местами, оставаясь в той же паре. Если перемещается на место , перемещается на место . может остаться на месте, или переместиться на , может остаться на месте, или переместиться на . Это даёт случаев, но бельчата не могут все оставаться на месте, поскольку мы уже посчитали такую возможность в случае , и, следовательно, здесь случаев. Кроме этого, могут быть пары что даёт еще случаев.

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

Всего случаев .

Посчитаем сначала общее количество способов распределить дни без учёта условия. Заметим, что нам нужно выбрать 4 голодных дня, остальные сразу станут обжорными. Значит, их количество

Теперь посчитаем способы, которые нам не подходят под условия, чтобы вычесть их. Понятно, чтобы не выполнялось условие задачи нужно иметь хотя бы 3 голодных дня подряд, но, т.к. голодных дней всего 4 возможно два варианта:

1) У нас 3 голодных дня подряд и 1 голодный, не стоящий с ними рядом. Будем воспринимать эти 3 дня как 1, назовём его большой голодный день, т.е. теперь у нас будет 8 дней и мы распределяем большой голодный день и голодный день так, чтобы они не стояли рядом. Если большой голодный стоит первым или последним, то у обычного есть 6 вариантов, в иных случаях у него их 5. В итоге

2) У нас 4 голодных дня подряд. Количество таких способов равно количеству способов выбрать место для первого голодного дня, оно равно 7.

В итоге количество способов распределения, подходящих под условия равно

Заметим, что из любых трёх целых чисел найдётся несколько из них, сумма которых кратна трём. (Ведь не может быть числа, кратного трём, и не могут быть одновременно числа с остатками и , а чисел одного остатка не более двух).

А значит, при этом из условия нас интересуют В рассматриваемом множестве чисел по чисел, дающих остатки и при делении на

Тогда для подходят любые три числа с одинаковыми остатками, их Для любая пара чисел с ненулевыми остатками, то есть пар чисел с одинаковыми остатками и с разными.

Итого чисел.

Пусть на первом месте стоит число Заметим, что если то числа стоят в нашей перестановке в порядке убывания (если двигаться слева направо). Действительно, по условию левее числа должно стоять левее или то есть левее или то есть и т. д. Аналогично при числа стоят в порядке возрастания, так как левее должно быть левее — число и т. д. Следовательно, любая из рассматриваемых перестановок однозначно задаётся набором мест, занимаемых числами (таких мест может вообще не быть, если то есть для перестановки Количество этих наборов равно количеству подмножеств множества из элемента — всех мест, кроме первого, то есть По числу элементов подмножества однозначно определяется число стоящее на первом месте.

Если первый мальчик достал карточку с номером , то, чтобы сумма на карточках была 46, второй мальчик должен достать карточку с номером Значит, достаточно рассмотреть все возможные варианты для первого мальчика, так как карточка, которую должен достать второй мальчик, определяется однозначно. А если существует вариант, что второй мальчик достал карточку с номером а первый — с номером и такой случай ещё не рассмотрен, то это значит, что изначально мы рассмотрели не все возможные варианты для первого.

Пусть первый мальчик достал карточку а второй — В задаче может принимать любое значение от 1 до 31, но нужно проверить, для любого ли такого значения у второго мальчика найдётся карточка с номером Если первый достал 1, то второй должен был выбрать карточку но карточки с номером 45 нет, так как самый большой номер — 31. Тогда самая маленькая карточка, которую может использовать первый, — это Значит, для любой карточки с номером от 15 до 31 второй мальчик может положить свою карточку с таким номером, чтобы в сумме получилось 46. Карточек с номерами от 15 до 31 — 17 штук.

Следовательно, существует 17 способов, чтобы мальчики достали по одной карточке так, чтобы сумма на них была ровно 46.

Посмотрим, чему может равнять сумма выбранных чисел. По условию она делится на 6. Первые три числа, делящиеся на 6, — это 6, 12 и 18. Следующие числа уже не меньше 24, а выписанные на доску числа не больше 10, то есть их сумма всяко не больше 20, то есть меньше 24. Значит, сумма может принимать всего три значения: 6, 12 и 18. Рассмотрим все три случая по-отдельности.

Случай 1. Посчитаем, сколькими способами можно выбрать два числа с суммой 6. Подходят пары (1, 5) и (2, 4), а других пар нет — ведь одно из чисел в паре обязательно не превосходит 3, две из таких пар мы выписали, а выбрать две тройки мы не можем. Значит, в этом случае получилось 2 пары.

Случай 2. Посчитаем, сколькими способами можно выбрать два числа с суммой 12. Подходят пары (2, 10), (3, 9), (4, 8), (5, 7). Других нет, так как одно из чисел не превосходит 6, при этом пары (1, 11) и (6, 6) из выписанных на доску чисел составить нельзя, а все остальные мы привели. Итак, в этом случае получилось 4 пары.

Случай 3. Посчитаем, сколькими способами можно выбрать два числа с суммой 18. Числа, меньшие 8, в пару брать нельзя, так как иначе второе число из пары будет не меньше 11. А из 8, 9 и 10 можно составить только одну пару — (8, 10). Значит, в этом случае получилась всего 1 пара.

Все полученные количества способов необходимо сложить, так как мы разбирали три различных варианта суммы, а подходит любой из этих вариантов. Итого получаем возможных пар для выбора Елизаветы Павловны.

Например, подходит число 180: в самом деле, .

Рассмотрим первые 28 дней месяца. Так как эти даты идут друг за другом, то среди них каждый день недели встречается по 4 раза. Остались 29-е, 30-е и 31-е число месяца, значит, ровно 3 дня недели в этом месяце встречаются по 5 раз, и эти 3 дня идут подряд. По условию известно, что среди этих трех подряд идущих дней нет ни среды, ни воскресенья. Тогда среди этих дней не может быть еще и понедельника со вторником. Значит, 3 дня, которые встречаются в месяце по 5 раз, это четверг, пятница и суббота. При этом 29-е число должно быть четвергом. Но 15-е число по сравнению с 29-м — это ровно две недели назад, значит, 15-е число — тоже четверг.

Рассмотрим все три случая, из какой деревни могли быть звонившие.

Случай 1. Пусть звонили из Правдино. В таком случае исходя из первой фразы получается, что пожар в Правдино, но второй же фразой утверждается, что он в Переменово. Такого быть не может, значит, этот случай невозможен.

Случай 2. Пусть звонили из Лгуново. В таком случае из первой фразы можно сделать вывод, что пожар не в Лгуново, а из второй фразы — что пожар не в Переменово. Значит, в этом случае единственным вариантом, где может быть пожар, является деревня Правдино.

Случай 3. Пусть звонили из Переменска. Но в таком случае первая и вторая фразы утверждают одно и то же, что пожар в Переменске. Это невозможно, так как ее жители чередуют правду и ложь, значит, этот случай также отпадает.

Таким образом, в результате полного перебора всех случаев мы выяснили, что единственным возможным является вариант, когда пожар случился в деревне Правдино, туда и надо ехать.

Нас интересуют только однозначные, двухзначные и трехзначные числа. Давайте сделаем их всех трехзначными дописав в начале нули. На делимость на 4 влияют только 2 последние цифры, поэтому на первом месте может стоять любая цифра, кроме и . Наше число делиться на 2, поэтому третья цифра должна быть четной. Пусть на втором месте , на третьем . Для у нас есть варианты 0, 2, 6, 8. Если или , то может быть только 1. Если или , то может быть равно 0, 2, 6, 8. Итого для пары и всего вариантов и тогда для всего числа вариантов, но среди этих вариантов есть случай 000. Он нам не подходит, так как число должно быть натуральным.

Чтобы число было кубом, нужно, чтобы степень каждого числа делилась на 3. Если мы возьмем одну карточку со степенью 2 и одну со степенью 3, то они в произведении будут кубом только, если изначальные степени были кубами. Значит в этом случае у нас варианта.

Если на обеих карточках степени 2, то нужно посмотреть на остаток этих степеней при делении на 3. Степени могут давать остатки 1 и 2 или 0 и 0. В первом случае у нас получится вариантов, во втором случае у нас получится варианта (делим на 2, потому что каждая пара посчитана дважды). Аналогично со степенями 3.

Разложим на множители:

Тогда в НОКе тройка появилась именно из . В не могут быть другие простые множители, кроме 2, 3 и 5, причем двойка может входить в в степени (то есть 5 вариантов), тройка входит ровно в первой степени, пятерка может входить в степени (то есть 3 варианта), так как иначе НОК будет явно больше. Тогда всего вариантов числа .

Первое решение.

В числе всего цифра. Если мы хотим посчитать числа только с четными цифрами, то на первом месте может стоять или . Если число начинается с , то такое число среди необходимым нам только одно. Здесь число может начинаться на 0, так как нам нужны не только -значные числа, а число, например, можно представить, как . Тогда всего чисел с четными цифрами будет . Это верно, поскольку с одной стороны на каждом месте, кроме первого, может стоять любая четная цифра, но таким образом у нас получится и число, состоящее только из 0, поэтому мы вычитаем 1, а с другой стороны тут мы забыли про число , которое нужно добавить. Итого чисел.

Так же посчитать числа с нечетными цифрами нельзя, поскольку среди них нуля уже нет. Давайте посчитаем только -значные числа с нечетными цифрами. Тогда их будет , так как на всех местах, кроме первого, может быть любая из 5 нечетных цифр, а на первом месте не может быть только . Отсюда уже понятно, что чисел с нечетными цифрами больше. Посчитаем, сколько меньших чисел с нечетными цифрами. Понятно, что однозначных чисел у нас 5, двухзначных — , трехзначных — , , 20-значных — . Поэтому разница между количеством чисел с нечетными цифрами и количеством чисел с четными цифрами будет равна

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

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение.

Давайте посмотрим, как превратить число с четными цифрами в число с нечетными цифрами. Можно прибавить 1 ко всем цифрам. Тогда заметим, что все нужные нам числа с четными цифрами в нужные нам числа с нечетными цифрами (кроме ), то есть часть чисел мы разбили на пары, где одно число с нечетными цифрами, а другое с четными цифрами, и в этих парах есть все числа с четными цифрами, кроме . Давайте посмотрим, есть ли у нас числа с нечетными цифрами, которые не участвуют в парах. Заметим, что у каждого числа с четными цифрами первая цифра хотя бы (здесь мы считает настоящие числа и они не могут начинаться с нуля), а значит у числа в паре с ними первая цифра хотя бы , поэтому вне пар у нас остались все числа с нечетными цифрами, у которых первая цифра . -значных чисел с нечетными цифрами, у которых первая цифра 1 ровно . Тогда разница между количеством чисел с нечетными цифрами и количеством чисел с четными цифрами будет равна

(-1 из-за )

Всего у нас есть по чисел, дающих каждый из остатков при делении на . Квадраты чисел дают остатки по модулю , мы хотим выбрать такие два из них, что их сумма будет . Отсюда возможны два случая:

а) числа оба кратны

б) одно из чисел дает остаток или (и квадрат даст остаток ), а другое — или при делении на (то есть квадрат даст ).

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

Давайте разобъём треугольники на три группы, которые будем последовательно красить (см. картинку ниже). Общее количество способов покрасить треугольники из первой группы — При этом существует три типа их раскраски, которые мы далее рассмотрим по отдельности: когда они все одинакового цвета, когда они все покрашены в разные цвета, и когда два треугольника покрашены в один цвет, а оставшийся — в третий.

Вариант 1 (треугольники покрашены в один цвет): таких раскрасок ровно три штуки — по одной на каждый цвет. При этом, любой треугольник из второй группы можно покрасить одним из двух способов — ведь оба его соседа покрашены в один и тот же цвет. Итого, способов покрасить треугольники второй группы: . Аналогично, угловые треугольники из третьей группы тоже можно покрасить 8 способами. Итого, раскрасок первого типа: .

Вариант 2 (треугольники покрашены в разные цвета): таких раскрасок шесть штук — вначале нужно выбрать цвет для верхнего треугольника, потом покрасить правый в один из двух оставшихся цветов, и последний треугольник докрасить в оставшийся цвет. Цвет каждого треугольника из второй группы восстанавливается однозначно — ведь у них два соседа разных цветов. Раскрасить же угловые треугольники снова можно 8 способами. Итого, раскрасок второго типа: .

Вариант 3 (два треугольника одного цвета, и третий — другого): это все оставшиеся способы покрасить треугольники из первой группы, а значит, их количество . Теперь у одного треугольника второй группы два одноцветных соседа, а у двух других — два разноцветных соседа. Значит, их можно покрасить способами. С угловыми же треугольниками всё также, как в предыдущих случаях — 8 способов раскраски. Итого, раскрасок третьего типа: .

Наконец, осталось сложить эти три количества и получить ответ: .

Первое решение.

Три точки из данных можно выбрать способами.

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

Значит, всего есть треугольник.

Второе решение.

Выбрать по одной точке на каждой стороне можно способами.

Выбрать две точки на одной стороне и одну точку на другой можно способами.

Значит, всего есть треугольник.

Приведенное в условии правило перестановки букв, или перестановку, будем обозначать греческой буквой Перестановку можно интерпретировать как отображение множества цифр в себя. Например, тот факт, что первая буква перешла на третье место, можно записать как а также изобразить стрелочкой из 1 в 3:

Видно, что если бы мы перестановку применяли многократно, то буквы на 2-й и 6-й позициях постоянно менялись бы местами, а буквы на позициях 1, 3, 4, 5 переставлялись бы по циклу. Поэтому перестановка может символически быть записана в виде произведения циклов:

Запись отражает цикловую структуру перестановки показывая, что в ней один цикл длины 4 и один цикл длины 2.

Посмотрим теперь более детально на то, что произойдет, если по правилу переставить буквы еще раз. Так 1 при первом применении правила перешла в 3: а при повторном применении 3 перешла в 4: Значит, в результате двойной перестановки 1 переходит в 4. Будем это записывать как или же Поэтому правило двойной перестановки букв, представляющее собой квадрат перестановки выглядит так:

Заметим, что после повторной перестановки 2 и 6 вернутся на свои места, то есть цикл распадется на два тривиальных цикла и а цикл превратится в два цикла и Таким образом, при повторном применении перестановки циклы четной длины распадаются на два цикла, длины каждый. Несложно проверить, что при этом циклы нечетной длины сохраняются. Справедливо утверждение.

Утверждение. Перестановка представляет собой полный квадрат в том и только том случае, когда в ее представлении в виде произведения непересекающихся циклов может быть сколько угодно и какие угодно циклы нечётной длины, в то время как циклов одной и той же чётной длины должно быть чётное число.

Рассмотрим первую комбинацию уеqwrt из пункта а). Она получена из qwerty перестановкой которая представляет собой цикл длины 6. Поскольку циклов четной длины здесь нечетное количество (всего один), то, согласно утверждению, такая комбинация двойной перестановкой букв получиться не могла. Аналогично исследуются и остальные комбинации в пункте а).

Проведем подсчет общего числа перестановок, являющихся полными квадратами. Их цикловые структуры могут быть следующие:

• Это перестановка, оставляющая все на своих местах (тождественная перестановка). Она единственна.
• Мы должны выбрать 5 элементов из шести, чтобы составить цикл дины 5. Это можно сделать 6-ю способами. Из пяти элементов цикл длины 5 можно организовать способами (действительно, организуем цикл из пяти элементов элемент может перейти в любой из четырех (т.к. в себя нельзя), элемент переходит в один из оставшихся трех и т.д. В итоге получаем способов). Таким образом, здесь перестановок.
• Выбрать два элемента из шести для первого цикла длины 2 можно способами. Для второго цикла длины 2 есть способа. Итого От порядка следования циклов результат не зависит, поэтому 90 еще следует разделить на два. Всего 45 перестановок с такой структурой.
• Здесь мы 6 элементов десятью способами разбиваем на две тройки и из каждой тройки получаем по 2 цикла. Всего 40 перестановок.
• Здесь мы двадцатью способами выбираем тройку и из каждой тройки получаем по 2 цикла. Всего 40 перестановок.

В итоге, имеется перестановок длины 6, представляющих собой полный квадрат.