Тема Физтех и вступительные по математике в МФТИ

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

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела физтех и вступительные по математике в мфти

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 41#31510Максимум баллов за задание: 7

Найдите количество прямоугольников со сторонами, параллельными осям координат, таких, что точка $(14;22)$ содержится внутри (но не на границе) каждого из них, абсциссы вершин являются натуральными числами меньше $29$ , а ординаты — натуральны и меньше, чем $31$ .

Источники: Физтех-2013, 11 (см. fizteh2013.ru)

Подсказки к задаче

Подсказка 1

Прямоугольник задаётся четырьмя прямыми. Каким условиям должны удовлетворять эти прямые, чтобы точка (14, 22) была внутри? А чтобы при этом выполнялись ограничения на абциссу и ординату?

Подсказка 2

0 < a < 14 < b < 29, 0 < c < 22 < d < 31, где a,b — абсциссы вертикальных границ фигуры, c, d — ординаты горизонтальных границ прямоугольника! Сколько вариантов у нас есть для a? А для b?

Показать ответ и решение

Прямоугольник можно задать 4 прямыми вида $x= a$ , $x= b$ , $y = c$ , $y = d$ . Пусть не умаляя общности $a< b$ и $c< d$ . По условию $0 <a <14< b< 29$ и $0<c <22< d< 31$ . Отсюда для $a$ у нас 13 вариантов, для $b$ у нас $28 − 14= 14$ вариантов, для $c$ у нас 21 вариант и для $d$ у нас $30− 22= 8$ вариантов.

Получаем ответ $13⋅14 ⋅21⋅8 =30576$ .

Ответ:

$30576$

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 42#34170Максимум баллов за задание: 7

Число 84605 написали семь раз подряд, при этом получилось 35-значное число

84605846058460584605846058460584605.

Из этого 35-значного числа требуется вычеркнуть две цифры так, чтобы полученное после вычёркивания 33-значное число делилось на 15. Сколькими способами это можно сделать?

Источники: Физтех-2013, 11.5

Подсказки к задаче

Подсказка 1

Рассмотрите отдельно делимость этого числа на 5 и на 3. В каком случае число не будет делиться на 5?

Подсказка 2

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

Подсказка 3

Если вычеркнем 2 единички или нолик с двоечкой, то нам число подойдет. Посчитаем кол-во способов выбрать 2 единички, отдельно - выбрать нолик с двоечкой, а дальше остался лишь счёт.

Показать ответ и решение

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

Если в числе заменить все цифры 8 и 5 на 2, цифры 4 на 1, а цифры 6 на 0, то остаток от деления числа на 3 не изменится (остаток от деления числа на 3 равен остатку от деления суммы цифр этого числа на 3). Таким образом, нужно узнать, сколькими способами можно вычеркнуть две цифры из числа $X = 21002210022100221002210022100221002$ так, чтобы полученное число делилось на 3. Сумма цифр числа $X$ равна 35. Чтобы после вычёркивания сумма цифр делилась на 3, мы можем вычеркнуть либо 1) две единицы, либо 2) двойку и ноль. Количество способов вычеркнуть две единицы равно $2 C 7 = 21$ ; количество способов вычеркнуть один ноль и одну двойку равно $1 1 C14⋅C14 = 14⋅14 =196$

Две последние цифры вычёркивать нельзя, поэтому получаем $196+ 21− 1= 216$ способов.

Ответ: 216

Ошибка.
Попробуйте повторить позже

Задача 43#101216Максимум баллов за задание: 7

При каком наибольшем натуральном значении $n$ число $n!+ 5n +52$ является точным квадратом?

Подсказки к задаче

Подсказка 1

Как можно выявлять точные квадраты?

Подсказка 2

Попробуйте посмотреть на остатки.

Подсказка 3

Например, 5n всегда делится на 5. А что тогда можно сказать про n! ?

Подсказка 4

Если n ≥ 5, то остаток при делении на 5 выражения будет равен 2, но ни один точный квадрат не даёт такой остаток по модулю 5. Осталось рассмотреть n < 5.

Показать ответ и решение

Заметим, что при $n≥ 5$ $n!$ делится на 5. Отсюда

n!+5n+ 52≡ 2 (mod 5)

Рассмотрим таблицу остатков квадратов по модулю 5:


$x$	$x2$

$0$	$0$

$1$	$1$

$2$	$4$

$3$	$4$

$4$	$1$

Из таблицы видно, что квадрат не может давать остаток 2 по модулю 5, а, значит, при $n≥ 5$ число $n!+ 5n +52$ не является квадратом. Осталось рассмотреть $n <5.$

При $n =4 :n!+ 5n+ 52 =24+ 20+ 52 =96$ — не квадрат.

При $n =3 :n!+ 5n+ 52 =6 +15+ 52= 73$ — не квадрат.

При $2 n =2 :n!+ 5n+ 52 =2 +10+ 52= 64 =8$ — квадрат.

Итак, наибольшее натуральное значение $n,$ при котором число $n!+5n +52$ является точным квадратом, равно 2.

Ответ:

Ошибка.
Попробуйте повторить позже

Задача 44#34657Максимум баллов за задание: 7

Последнюю цифру шестизначного числа переставили в начало (например из числа $123456$ получится $612345$ ), и полученное шестизначное число вычли из исходного числа. Какие числа из промежутка $[618222;618252]$ могли получиться в результате вычитания?

Источники: Физтех-2012, 11.5 (см. olymp.mipt.ru)

Подсказки к задаче

Подсказка 1

Вводим число в виде abcdef (с чертой). Сделав операцию из условия, получится fabcde. Если наблюдается повторение, то почему бы не сделать замену?

Подсказка 2

Да, первые 5 знаков составляют повторяющееся число, пусть оно (т.е. abcde) будет х, тогда имеем дело с цифрой f и 5-значным х. Реализуем условие через эти натуральные переменные.

Подсказка 3

Заметим, что 9х - 99999f лежит в предложенном отрезке, при этом f ≠ 0 (почему?). Тогда количество возможных ответов моментально сокращается.

Показать ответ и решение

Пусть $ABCDEF$ — данное шестизначное число. Обозначим пятизначное число $ABCDE$ через $x.$ Тогда $ABCDEF − FABCDE = (10x+ F)− (100000F +x)= 9x− 99999F.$ Таким образом, полученная разность делится на $9.$ Из промежутка $[618252;618222]$ на $9$ делятся числа $618228,618237,618246.$

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

$9x − 99999F = 618228$

$9x − 99999F = 618237$

$9x − 99999F = 618246$

имеет целочисленное решение, где $x$ — пятизначное число, а $F$ — однозначное число, не равное нулю. Для этого достаточно в каждом из уравнений подставить $F = 1$ и убедиться, что получающееся значение $x$ является пятизначным целым числом.

Действительно, первому уравнению удовлетворяет пара $x= 79803,F = 1;$ второму — пара $x= 79804,F = 1;$ третьему — пара $x =79805,F =1.$ Значит, если в качестве исходных чисел взять $798031,798041,798051,$ то в результате перестановки и вычитания мы получим числа $61828,618237,618246.$

Ответ:

$618228,618237,618246$

Ошибка.
Попробуйте повторить позже

Задача 45#67080Максимум баллов за задание: 7

Сколькими способами можно выложить в ряд три красных, четыре синих и пять зелёных шаров так, чтобы никакие два синих шара не лежали рядом?

Подсказки к задаче

Подсказка 1

У нас есть условие на синие шары, поэтому давайте их пока трогать не будем. Сколько есть способов разложить в ряд 3 красных и 5 зеленых шаров?

Подсказка 2

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

Подсказка 3

Да, надо просто располагать синие шары между красными и зелеными, а еще можно положить их в конец или начало исходного ряда! Сколько способов есть это сделать?

Подсказка 4

Конечно, число сочетаний из 9 по 4.

Показать ответ и решение

Сначала разложим красные и зелёные шары. Для этого, не умаляя общности, надо выбрать $3$ места из $8$ для красных шаров. Между ними (а также слева и справа) остаётся $9$ мест, куда можно ставить синие шары. Из этих мест надо выбрать четыре. Итого $3 4 C8 ⋅C 9 = 7056.$

Ответ:

$7056$

Ошибка.
Попробуйте повторить позже

Задача 46#39645Максимум баллов за задание: 7

$19$ депутатов Городского Собрания выбирают Председателя из $5$ кандидатов. Каждый голосует ровно за одного из них. После голосования составляется протокол заседания, в котором указывается лишь количество голосов за каждого кандидата (без указания, кто за кого проголосовал). Сколько различных протоколов может получиться?

Источники: Физтех-2011, отборочный тур, 9 (см. fizteh2013.ru)

Подсказки к задаче

Подсказка 1

Попробуем перевести задачу на язык шаров и перегородок. В конце концов в протоколе у нас будет пять значений – количество голосов за каждого кандидата. И нам нужно найти количество таких протоколов. Хм... Какое тогда уравнение можно составить, чтобы в дальнейшем применить идею шаров и перегородок?

Подсказка 2

Верно, если за 1, 2, 3, 4 и 5 кандидата проголосуют соответственно a, b, c, d и e депутатов, то их сумма будет равна 19. И того, учитывая ограничения на количество голосов(проголосовавших депутатов) нам нужно найти количество таких пятёрок. Тогда с точки зрения шаров и перегородок, что нам нужно сделать?

Подсказка 3

Да, нам нужно расставить 4 перегородки в какое-то количество мест. Поймём теперь в какое. Надо не забыть, что перегородки могут стоять в начале и в конце(когда за кандидата никто не проголосовал, например) и рядом между собой(тогда за кандидата между ними 0 голосов). Итого у нас получается всего элементов 23 – это 20 мест для одной перегородки между шарами и по краям, но у нас ещё есть 3 перегородки, которые могут стоять рядом с нашими позициями, то есть ещё дополнительных 3 места.

Показать ответ и решение

Количество различных протоколов соответствует количеству различных упорядоченных пятёрок $(x ,x ,x ,x,x ) 1 2 3 4 5$ , таких что $x1+ x2+ x3+x4+ x5 = 19$ с учётом того, что у нас есть ограничения $x1 ≤ 19,x2 ≤ 19,x3 ≤ 19,x4 ≤19,x5 ≤19.$

Такая задача эквивалентна тому, чтобы расставить $4$ перегородки между $19$ шариками, причем перегородки могут стоять в начале, в конце или на одной и той же позиции (так как голосов каждого вида может быть любое количество от $0$ до $19$ , то есть ограничения на количество голосов, кроме уравнения - связки, у нас нет). Количество элементов в каждой из получившихся пяти группах между перегородками (возможно, каких-то пустых) это и будут значения $x1,x2,x3,x4,x5.$

Итак, у нас есть $23$ элемента - $19$ шариков и $4$ перегородки. Количество различных (!) их перестановок равно $4 C 23.$

Ответ:

$8855$

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 47#70308Максимум баллов за задание: 7

26 солдат выстроены в одну шеренгу. Сколько существует различных способов выбрать 11 из них так, что никакие двое из них не стоят рядом?

Источники: Физтех - 2011, 10 класс

Подсказки к задаче

Подсказка 1

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

Подсказка 2

Получаем, что перегородки не могут стоять рядом, но могут стоять в начале и в конце. Тогда первую перегородку можно поставить на любое из 16 мест, вторую — на любое из 15 мест и т.д. Уверены, что вы знаете, как посчитать количество способов выставить 11 перегородок!

Показать ответ и решение

Используем метод шаров и перегородок. Шары — не выбранные солдаты, а перегородки — выбранные. При этом перегородки не могут стоять рядом, но могут стоять в начале и конце. Подсчитаем количество способов: первую перегородку между $15$ шарами ставим на любое из $16$ мест, вторую на оставшиеся $15$ мест и так далее, последнюю перегородку ставим на одно из $6$ мест. Так как порядок выбора мест не важен, число способов:

16 ⋅15⋅14⋅...⋅6 -----11!------=4368

Ответ: 4368

Ошибка.
Попробуйте повторить позже

Задача 48#70326Максимум баллов за задание: 7

Целые числа $m$ и $n$ таковы, что

4m+ 5n= mn − 9

Найдите, какое наибольшее значение может принимать $m$ .

Подсказки к задаче

Подсказка 1

Когда мы видим выражение вида a * mn + b * n + c * m + d, то первым делом нам нужно попробовать его разложить на скобки, добавив некоторую константу к обеим частям уравнения. Попробуйте это сделать, ведь с множителями удобнее работать чем с слагаемыми!

Подсказка 2

Получится (m-5)(n-4)=29. Много ли целых чисел могут давать в произведении 29?

Показать ответ и решение

Первое решение. Постараемся разложить на скобки:

mn − 4m− 5n− 9= 0

mn− 4m − 5n+ 20= 29

(m − 5)(n − 4)= 29

В правой части простое число, поэтому в левой части целые числа в скобках могут равняться только 1 и 29, либо -1 и -29. Наибольшее значение $m$ достигается при $m − 5 =29 ⇐⇒ m = 34.$

______________________________________________________________________________________________________________________________________________________

Второе решение. Запишем равенство в виде

m = 9+-5n =5+ -29- ≤5+ 29= 34 n− 4 n − 4

Равенство реализуется при $n =5.$

Ответ: 34