Олимпиадные задачи из источника «параграф 3. Индукция в геометрии и комбинаторике» для 2-8 класса

Любую ли сумму из целого числа рублей больше семи, можно уплатить без сдачи денежными купюрами по 3 и 5 рублей?

Сколько существует (невырожденных) треугольников периметра 100 с целыми длинами сторон?

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

Клетки шахматной доски100×100 раскрашены в 4 цвета так, что в любом квадрате 2×2 все клетки разного цвета. Докажите, что угловые клетки раскрашены в разные цвета.

На плоскости проведены<i>n</i>окружностей так, что любые две из них пересекаются в паре точек, и никакие три не проходят через одну точку. На сколько частей делят плоскость эти окружности?

На сколько частей делят плоскость <i>n</i> прямых <i>общего положения</i>, то есть таких, что никакие две не параллельны и никакие три не проходят через одну точку?

<b>Гениальные математики.</b>а) Каждому из двух гениальных математиков сообщили по натуральному числу, причем им известно, что эти числа отличаются на единицу. Они поочередно спрашивают друг друга: "Известно ли тебе мое число?" Докажите, что рано или поздно кто-то из них ответит "да". Сколько вопросов они зададут друг другу? (Математики предполагаются правдивыми и бессмертными.) б) Как изменится число заданных вопросов, если с самого начала известно, что данные числа не превосходят 1000?

Докажите, что правильный треугольник можно разрезать на<i>n</i>правильных треугольников для любого<i>n</i>, начиная с шести.

Докажите, что квадрат можно разрезать на<i>n</i>квадратов для любого<i>n</i>, начиная с шести.

  а) Головоломка "Ханойская башня" представляет собой восемь дисков, нанизанных в порядке уменьшения размеров на один из трёх колышков. Требуется переместить всю башню на другой колышек, перенося каждый раз только один диск и не помещая больший диск на меньший. Докажите, что головоломка имеет решение. Какой способ будет оптимальным (по числу перекладываний дисков)?   б) Занумеруем колышки числами 1, 2, 3. Требуется переместить диски с 1-го колышка на 3-й. Сколько понадобится перекладываний, если прямое перемещение диска с 1-го колышка на 3-й и с 3-го на 1-й запрещено (каждое перекладывание должно производиться через 2-й колышек)?   в) Сколько понадобится перекладываний, если в условии пункта а) добавить дополнительное требование: первый (самый маленький) диск нельзя класть на 2-...

Из квадрата клетчатой бумаги размером16×16 вырезали одну клетку. Докажите, что полученную фигуру можно разрезать на "уголки'' из трех клеток.

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

Было семь ящиков. В некоторые из них положили еще по семь ящиков (не вложенных друг в друга) и т. д. В итоге стало 10 непустых ящиков.

Сколько всего стало ящиков?