Комбинаторика, теорвер и теория чисел на Физтехе

Результат броска кубиков можно описать набором из 70 чисел от 1 до 6. Рассмотрим какой-либо такой набор. Если каждое из чисел набора заменить с на , получим новый набор, состоящий из чисел от 1 до 6. При этом если сумма чисел в исходном наборе была , то она станет равной То есть каждому набору с суммой мы можем поставить в соответствие набор с суммой

Так как , то количество наборов с суммой больше 350 равно количеству наборов с суммой меньше 140. Отметим также, что все наборы равновероятны. Значит, вероятность выбросить больше 350 равна вероятности выбросить меньше 140. Но вероятность выбросить не больше 140 очков выходит больше выше рассмотренных, так как добавляются способы, в которых сумма составляет ровно 140 очков. Поэтому больше вероятность того, что сумма не превосходит 140.

Разложим на множители. Значит, искомые числа могут состоять из следующих цифр:

1) три двойки, две пятёрки, одна семёрка и две единицы,

2) четвёрка, двойка, две пятёрки, одна семёрка и три единицы,

3) восьмёрка, две пятёрки, одна семёрка и четыре единицы.

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

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

В третьем случае выбрать места для единиц можно способами, далее для двух пятёрок способа, оставшиеся восьмёрку и семёрку ставим двумя способами. Всего получается вариантов.

Итого вариантов.

Результат броска кубиков можно описать набором из 70 чисел от 1 до 6. Рассмотрим какой-либо такой набор. Если каждое из чисел набора заменить с на , получим новый набор, состоящий из чисел от 1 до 6. При этом если сумма чисел в исходном наборе была , то она станет равной То есть каждому набору с суммой мы можем поставить в соответствие набор с суммой

Так как , то количество наборов с суммой больше 350 равно количеству наборов с суммой меньше 140. Отметим также, что все наборы равновероятны. Значит, вероятность выбросить больше 350 равна вероятности выбросить меньше 140. Но вероятность выбросить не больше 140 очков выходит больше выше рассмотренных, так как добавляются способы, в которых сумма составляет ровно 140 очков. Поэтому больше вероятность того, что сумма не превосходит 140.

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

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

Давайте подумаем, какие есть варианты для остатков трёх карточек, чтобы их сумма делилась на либо все три числа должны давать разные остатки (способов выбрать так карточки так как выбрать карточку с остатком — способа, способов выбрать карточку с остатком — и способов выбрать карточку с остатком — ), либо все три остатка (тогда способов либо все три остатка 1 (тогда способов либо все три остатка (тогда способов Итого всего

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

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

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

Сумма трёх чисел может делиться на в следующих случаях.

1.

Все три числа дают одинаковые остатки от деления на Есть способов выбрать числа из множества и по способов выбрать числа из множеств и В сумме получаем способов.

2.

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

В сумме выходит способов.

Данные числа, расположенные в порядке возрастания, образуют арифметическую прогрессию с разностью 3. Следовательно, остатки от деления на 5 у этих чисел чередуются. Действительно, если какое-то из этих чисел делится на 5, то есть имеет вид , где , то следующее за ним число есть — и оно даёт остаток 3 от деления на 5 — далее , дающее остаток 1 от деления на 5, затем — , дающее остаток 4 от деления на 5 , затем , дающее остаток 4 от деления на 5; наконец, следующим является , которое снова делится на 5, после чего порядок остатков по чисел на 5 идут в порядке

Среди данных нам 100 чисел есть по 20 чисел, дающих остатки от деления на 5.

Сумма двух чисел может делиться на 5 в следующих случаях.

1) Оба числа делятся на 5. Всего карточек с такими числами 20 , и нужно выбрать 2 из них — есть способов.

сделать это.

2) Одно из чисел даёт остаток 1 от деления на 5 — тогда второе должно давать остаток 4 от деления на 5. Эту пару чисел можно выбрать способами.

3) Одно из чисел даёт остаток 2 от деления на 5 — тогда второе даёт остаток 3 , и, аналогично второму случаю, получаем 400 способов выорать 2 числа. В итоге выходит 990 способов.

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

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

Получаем ответ .

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

Треугольники делятся на два типа

• Катеты параллельны осям. Тогда один из них соединяет точки с одинаковой абсциссой, а второй лежит на какой-то прямой. Выберем эту абсциссу способами, а затем прямую и саму точку способами (сначала прямую, а затем точку из оставшихся на ней). В итоге способов.
• Ни один из катетов не лежит на прямых, поэтому там лежит гипотенуза (ведь на какой-то прямой лежат две вершины треугольника), откуда высота к ней имеет длину . Она же является корнем из произведения проекций катетов, то есть их произведение равно — длины проекций являются натуральными числами, потому их значения могут быть только такими. Если это и , то, выбирая прямую, затем порядок двух различных отрезков проекций на прямой, а затем абсциссу высоты, получаем способа (поскольку мы не можем брать ближайших точек с одной стороны прямой, а с другой одну, чтобы наши проекции “влезли”). Если же это и , то сначала выбираем прямую, порядок выбирать не нужно, поскольку отрезки равны, а точку выберем способами, поскольку с каждой стороны прямой нельзя брать по точек. В итоге способа.

В качестве ответа имеем .

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

Рассмотрим два возможных случая:

• Гипотенуза треугольника лежит на одной из прямых, а вершина прямого угла - на второй прямой. Пусть - данный треугольник с прямым углом при вершине - его высота, опущенная на гипотенузу. Из пропорциональности отрезков прямоугольного треугольника получаем, что , т.e. . Поскольку и - целые числа, то возможны следующие случаи: и и .

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

  Во втором и третьем случаях длина гипотенузы равна 26, и её можно расположить способами. Для каждого положения гипотенузы существует два способа размещения вершины - получаем способов.

• Один из катетов треугольника (назовём его ) перпендикулярен данным прямым, а второй катет лежит на одной из данных прямых. Тогда положение катета можно выбрать 200 способами. Для каждого варианта расположения катета вершину можно расположить 398 способами (подходят все точки кроме уже выбранных и ) - всего выходит способов.

Итого получаем способов.

Доказано, какие три вида прямоугольных треугольников возможны — 2 балла.

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

Произведён подсчёт количества треугольников одного вида — 1 балл.

Произведён подсчёт количества треугольников двух видов — 2 балла.

Произведён подсчёт количества треугольников трёх видов — 4 балла.

Ошибка в  при подсчёте количества треугольников — снять 1 балл от общей суммы.

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

Верный ответ в развёрнутой форме — баллы не снимаются.

Будем называть парной карточкой к данной такую карточку, что их сумма кратна , а видом карточки — её последние две цифры. Рассмотрим несколько случаев

• Номер на карточке кратен , то есть заканчивается на или . Карточек каждого вида ровно по , а парная карточка к каждой из них заканчивается на те же самые две цифры. То есть для обоих видов мы получим по способов взять две парные карточки с такими последними цифрами. Всего .
• Номер карточки заканчивается на , при этом он не больше . В силу второго ограничения таких карточек тоже по каждого вида. Легко видеть, что в пару им идут виды , по одному на каждый, то есть для каждой выбранной карточки подойдёт карточка парного вида. Итак, выбираем вид способами, затем его представителя и пару ему также , итого .
• Остались карточки с номерами . Для каждой из них есть по парной, то есть получаем способов.

Складывая по всем случаям, получаем способов.

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

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

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

Номер на карточке оканчивается на число от до (таких карточек ). Для каждой из них пару можно выбрать способами (если число оканчивается на то подойдёт любая карточка с числом, оканчивающимся на если число оканчивается на — любая карточка с числом, оканчивающимся на и т.д.). Таким образом, получаем вариантов.

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

Итого выходит способов.

Проведем через 2 вершины и центр квадрата прямые, параллельные осям, как на картинке.

Заметим, что выделенные на картинке цветом треугольники равны по двум углам и стороне. Значит, если одна вершина с координатами , то следующая , затем по аналогичным соображениям следующая вершина и последняя . Тогда из условия, что все координаты неотрицательные получаем, что числа неотрицательны. Отсюда и . Значит, для значения у нас вариант и для значения у нас вариант, но если , то не получится квадрат. Итого: вариантов для пар , но заметим, что в квадрате изначальную вершину можно выбрать четырьмя способами. Значит, четырём парам значений и соответствует один квадрат. Таким образом, квадратов .

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

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

В качестве ответа имеем .

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

Сначала проигнорируем то, что 0 не может быть первым. Тогда для каждого разряда сумма различных цифр в нём , при фиксированной цифре на любой позиции число способов поставить остальные — , откуда сумма таких чисел равна . Затем поставим 0 на первое место, а остальные 4 цифры образуют 4-хзначное число, для всех вариантов которого аналогично сумма будет . С учётом того, что всего чисел , имеем:

Восстанавливаем цифры, начиная с последней. Так как число должно делиться на оно должно оканчиваться на или — всего варианта. Делимость на зависит от суммы цифр — значит, мы можем ставить любые цифры на место звёздочек, кроме последней (считая с конца) звёздочки. Значит, для – пропусков у нас есть по вариантов, на месте — варианта. Теперь посчитаем, сколькими способами мы можем восстановить первую звёздочку. Если на данный момент сумма цифра имеет остаток то на месте пропуска мы можем поставить или Если же сумма цифр даёт остаток — или если — или Значит, на месте первой звёздочки у нас всегда будет ровно варианта восстановить цифру. Итого получаем способа расставить цифры.

Рассмотрим все диагонали (или стороны) и разобьем их на группы параллельных. Такие группы бывают 2 видов: те, которые содержат диаметр и те, которые не содержат. Первых групп всего 11 (количество различных диагоналей, проходящих через центр) и в каждой из них по 10 диагоналей. Вторых групп тоже 11, но в каждой из них по 9 диагоналей (см. рис).

Для того, чтобы выбрать выпуклый четырёхугольник, у которого есть хотя бы одна пара параллельных сторон, нужно выбрать две параллельные диагонали (или стороны) и составить из них трапецию. Так мы получим четырехугольников. Осталось проверить, что они различны. На самом деле если наш четырехугольник имеет две пары параллельных прямых (вписанный параллелограмм — это прямоугольник), то он был посчитан два раза. Значит, из этого числа нужно вычесть количество прямоугольников. Выбрать прямоугольник можно таким способом. Сначала выберем 2 его соседние вершины. Это можно сделать способами, так как соседние вершины не могут быть противоположными, а затем однозначно определим оставшиеся 2 вершины, так как диагональ прямоугольника должна проходить через центр окружности. Так, каждый прямоугольник мы посчитаем раз и поэтому всего прямоугольников .

Получаем ответ .

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

• кратно . Тогда делится на . Отсюда . В итоге получаем случаи .
• кратно , откуда , откуда кратно 3. Снова получаем два случая , откуда .

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

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

Разложив делимое и делитель на множители, получаем условие . Значит, одно из чисел или делится на 89 . Рассмотрим два случая.

a) , т.е. . Тогда получаем . Первый множитель делится на 5 при , а второй — при , откуда получаем, что .

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

Итак, условию задачи удовлетворяют числа, дающие остатки при делении на 445, то есть подходят каждые 4 из 445 подряд идущих чисел. Так как , получаем чисел.

_________________________________________________________________________________________________________________________________________________________________________________

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

. . Числа 5 и 89 простые, поэтому существует 4 случая:

Для каждого такого случая существует ровно одно решение по модулю (по КТО), так как если бы существовала и для, например, третьего случая, то и значит, и делится на 445, то есть .

Отсюда все числа от 1 до 445000 разбиваются на группы по 445 в каждой, из которых есть ровно 4 решения.

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

Распределим между разрядами “единичек”, так как на первом разряде точно стоит хотя бы одна “единичка”. Ставим перегородки между шарами. Так как порядок выбора мест не важен, число способов:

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

Если в числе заменить все цифры и на , цифры на а цифры на то остаток от деления числа на не изменится (остаток от деления числа на равен остатку от деления суммы цифр этого числа на ). Нужно узнать, сколькими способами можно вычеркнуть две цифры из числа так, чтобы полученное число делилось на . Сумма цифр числа равна . Чтобы после вычёркивания сумма цифр делилась на , мы можем вычеркнуть либо а) две единицы, либо б) двойку и ноль.

а) Количество способов вычеркнуть две единицы равно

б) Количество способов вычеркнуть один ноль и одну двойку равно

Но в пункте (б) мы подсчитали способ, при котором вычеркнуты последние две цифры. Такого допускать нельзя, чтобы не нарушить делимость на . Этот способ нужно вычесть. Так что в итоге получаем способов.