ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Фильтр
Сложность с по   Класс с по  
Выбрана 1 задача
Версия для печати
Убрать все задачи

P и Q – подмножества множества выражений вида  (a1, a2, ..., an),  где ai – натуральные числа, не превосходящие данного натурального числа k (таких выражений всего kn). Для каждого элемента  (p1, ..., pn)  множества P и каждого элемента  (q1, ..., qn)  множества Q существует хотя бы один такой номер m, что  pm = qm.  Докажите, что хотя бы одно из множеств P и Q состоит не более чем из kn–1 элементов для
  а)  k = 2  и любого натурального n;
  б)  n = 2  и любого натурального  k > 1;
  в) произвольного натурального n и произвольного натурального  k > 1.

   Решение

Задачи

Страница: << 68 69 70 71 72 73 74 >> [Всего задач: 1006]      



Задача 65883

Темы:   [ Классическая комбинаторика (прочее) ]
[ Процессы и операции ]
[ Мощность множества. Взаимно-однозначные отображения ]
Сложность: 5
Классы: 9,10,11

Автор: Петров Ф.

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

Прислать комментарий     Решение

Задача 66584

Темы:   [ Ориентированные графы ]
[ Индукция ]
[ Теория алгоритмов (прочее) ]
Сложность: 5
Классы: 8,9,10,11

В некотором государстве 32 города, каждые два из которых соединены дорогой с односторонним движением. Министр путей сообщения, тайный злодей, решил так организовать движение, что, покинув любой город, в него нельзя будет вернуться. Для этого он каждый день, начиная с 1 июня 2021 года, может менять направление движения на одной из дорог. Докажите, что он сможет добиться своего к 2022 году (то есть за 214 дней).
Прислать комментарий     Решение


Задача 66880

Темы:   [ Теория графов (прочее) ]
[ Теория игр (прочее) ]
Сложность: 5
Классы: 8,9,10,11

За каждым из двух круглых столиков сидит по $n$ гномов. Каждый дружит только со своими соседями по столику слева и справа. Добрый волшебник хочет рассадить гномов за один круглый стол так, чтобы каждые два соседних гнома дружили между собой. Он имеет возможность подружить $2n$ пар гномов (гномы в паре могут быть как с одного столика, так и с разных), но после этого злой волшебник поссорит между собой $n$ пар гномов из этих $2n$ пар. При каких $n$ добрый волшебник может добиться желаемого, как бы ни действовал злой волшебник?
Прислать комментарий     Решение


Задача 73685

Темы:   [ Задачи с ограничениями ]
[ Целочисленные решетки ]
[ Индукция (прочее) ]
[ Объединение, пересечение и разность множеств ]
Сложность: 5
Классы: 10,11

P и Q – подмножества множества выражений вида  (a1, a2, ..., an),  где ai – натуральные числа, не превосходящие данного натурального числа k (таких выражений всего kn). Для каждого элемента  (p1, ..., pn)  множества P и каждого элемента  (q1, ..., qn)  множества Q существует хотя бы один такой номер m, что  pm = qm.  Докажите, что хотя бы одно из множеств P и Q состоит не более чем из kn–1 элементов для
  а)  k = 2  и любого натурального n;
  б)  n = 2  и любого натурального  k > 1;
  в) произвольного натурального n и произвольного натурального  k > 1.

Прислать комментарий     Решение

Задача 73773

Темы:   [ Треугольник Паскаля и бином Ньютона ]
[ Бином Ньютона ]
[ Индукция (прочее) ]
[ Делимость чисел. Общие свойства ]
[ Рекуррентные соотношения (прочее) ]
Сложность: 5
Классы: 9,10,11

Автор: Шлейфер Р.

Для любого натурального числа n сумма     делится на 2n–1. Докажите это.

Прислать комментарий     Решение

Страница: << 68 69 70 71 72 73 74 >> [Всего задач: 1006]      



© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .