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

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

Вопрос о целых точках на треугольнике, получается, стоит так: при каких целых система:

имеет решения , удовлетворяющие условиям выше.

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

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

Проецируем треугольник на — получается треугольник на плоскости с вершинами Внутрь него точки попадут такие:

Решаем систему, состоящую из двух первых уравнений:

Получаем следующие решения:

Полученные значения подставляются в третье уравнение , и если оказывается целым — точка найдена. После подстановки получается выражение:

то есть должна быть чётной. Из кандидатов подойдут только .

Плюс точки на сторонах, и всего точек на треугольнике

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

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

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

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

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

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

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

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

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

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

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

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

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

Теперь берём пару отрезков. Пусть это отрезки с концами и считаем В каком случае они пересекается? В том, когда Учитывая, что могут быть любой парой, замечаем следующее: общее количество пересечений отрезков равно количеству случаев, когда в перестановке большее число стоит раньше меньшего (не обязательно по соседству). Как сказали бы старшие товарищи, число пересечений равно числу инверсий в перестановке. Так и будем говорить дальше.

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

Как посчитать число перестановок с заданным количеством инверсий? Подойдём к задаче индуктивно. В фигурных скобках будем указывать различные перестановки, а в квадратных перечислим количества перестановок, имеющих соответственно инверсий.

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

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

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

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

Посмотрим, какие числа получались в квадратных скобках. Напишем эти последовательности одну под другой:

Здесь в строке (нумерация начинается с ) приводятся числа для равные количеству перестановок из чисел с инверсиями.

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

Действительно, — количество перестановок из (n-1) чисел, в которых уже есть инверсий. В них мы вынуждены поставить новое на последнее место ( инверсий). Раз мы ставим на единственно возможное место, количество перестановок не изменится.

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

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

Заметим, что так как не бывает перестановок с отрицательным числом инверсий, как и не может быть перестановок со слишком большим (больше чем ) количеством инверсий.

Итак, имеем следующий способ построения коллекции

Первая строчка:

По строчке ползёт «окно» шириной Попавшие в «окно» числа складываются и выписываются в следующую (2-ю) строку:

Вторая строка:

По ней будет ползти окно шириной Сложение попавших в окно чисел даст третью строку:

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

Выпишем (без нулей) первые строк нашей коллекции и выберем в ней нужное нам

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

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

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

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

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

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

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

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

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

Всего в -угольнике

диагоналей. Разобьем стороны на пар параллельных сторон. Несложно заметить, что если зафиксировать какую-то пару ( вершины), то оставшиеся вершины можно соединить попарно диагоналями, параллельными этой паре. Их всего будет Значит, диагоналей, параллельных какой-то стороне А непараллельных

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

1) Одноцветные раскраски – их всего . (Каждый поворот на переводит их в себя)

2) Разноцветные раскраски с противоположными секторами одинакового цвета – их , по числу способов выбора пары цветов из семи. (Каждый поворот на переводит такие раскраски в себя)

3) Прочие раскраски, не переходящие в себя ни при каком повороте.

Из общего числа , каждая раскраска первого типа считается раз, раскраска второго типа - по раза, и раскраска третьего типа - по раза. Отсюда можно найти число способов раскраски третьего типа. Это

Тогда общее число способов раскраски, с учётом отождествлений, получается как сумма .

Так как число делится на 5, то на 9-м месте может стоять только пятёрка. После этого нужно на оставшиеся 8 мест распределить 8 цифр: 3 семёрки, 3 тройки, пятерку и двойку. Всего перестановок будет 8!, но так как есть повторяющиеся цифры, то ответ будет:

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

Пусть шары — это саквояжи. Перегородки между ними — разбиение саквояжей по цветам. Рассмотрим случаи:

В первом случае в покупку входят саквояжи всех четырех цветов. Тогда поставим между шарами перегородки: число шаров, лежащих слева от первой перегородки, равно числу саквояжей первого цвета; число шаров, лежащих между первой и второй — второму и т.д. Мест для перегородок поэтому в этом случае получаем способов.

Во втором случае в покупке присутствуют саквояжи трёх из четырех цветов. Выбрать их способа. Ставим перегородки на мест — способов. Итого в этом случае получаем способов.

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

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

Суммируя способы во всех случаях, получаем

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

Старуха Шапокляк может взять школьную тетрадку в клетку и отметить там ряд из клеток. Затем в произвольных разных клетках этого ряда она ставит крестики. Передав этот листок продавцу, она ставит условие: число клеток, лежащее слева от первого крестика, равно числу саквояжей первого цвета; число клеток, лежащих между первым и вторым крестиком, равно числу саквояжей второго цвета, число клеток, лежащее правее третьего крестика, равно числу саквояжей -ого цвета. При этом, если левее первого крестика, между какими-либо двумя крестиками, или правее -го крестика нет клеток, значит, в покупке не будет саквояжей соответствующего цвета.

Тем самым число вариантов покупки равно числу способов расстановки крестика на различных позициях, то есть равно

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

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

Пусть в таблице строк и столбцов, а клетка, получившая одинаковые номера, расположена в строке с номером и в столбце с номером Тогда, если считать по строкам, в этой клетке стоит число а если считать по столбцам, то это Следовательно, что равносильно

Если или то номера Пети и Васи совпадут во всех клетках. Значит, и Пусть тогда где Получаем Поэтому так как аналогично с Следовательно, количество клеток, получивших одинаковые номера, равно

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

Если треуогльник прямоугольный с гипотенузой , то по т.Пифагора

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

Если гипотенузой является сторона , то аналогично получаем соотношение , что возможно только в следующих случаях:

для каждого из которых есть троек , т.е. всего способов.

Если гипотенузой является сторона , то получаем соотношение . Аналогично предыдущему, находим способов.

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

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

Итак, у Саши на одно вороство уходит цикла, поскольку за те секунд, что он ворует и прячет шарик, Маша успевает найти три шара и начать вешать третий из них. Аналогично Паше требуется циклов. Воровать каждый из них может в любой из циклов, не считая первого, тогда Саша украдёт не более шаров, а Паша — не более . В итоге шаров останется как минимум .

Остаётся привести пример. Пусть Саша ворует шары в начале циклов, а Паша — в начале циклов. Нетрудно видеть, что разнциа между номерами циклов соответствует скорости ребят.

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

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

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

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

(a) Пусть Ваня сможет за конечное количество ходов добиться Вначале

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

Иначе Таня вынуждена сделать или и опять-таки Ваня выигрывает.

(b) Стратегия Тани — держать коэффициент при равным 10 или 11.

В этом случае значение многочлена будет не кратно трем и, следовательно, не равно нулю.

Действительно, многочлены

не кратны трем при любом целом

При остаток от деления на три равен 2; при остаток от деления на три составляет 1 и 2, соответственно; при остаток от деления на три составляет 2 и 1, соответственно.