P и Q – подмножества множества выражений вида  (a₁, a₂, ..., a_n),  где a_i – натуральные числа, не превосходящие данного натурального числа k (таких выражений всего kⁿ). Для каждого элемента  (p₁, ..., p_n)  множества P и каждого элемента  (q₁, ..., q_n)  множества Q существует хотя бы один такой номер m, что  p_m = q_m.  Докажите, что хотя бы одно из множеств P и Q состоит не более чем из k^n–1 элементов для
  а)  k = 2  и любого натурального n;
  б)  n = 2  и любого натурального  k > 1;
  в) произвольного натурального n и произвольного натурального  k > 1.

   Решение

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

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

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

Решение

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

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

Решение

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

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

Решение

P и Q – подмножества множества выражений вида  (a₁, a₂, ..., a_n),  где a_i – натуральные числа, не превосходящие данного натурального числа k (таких выражений всего kⁿ). Для каждого элемента  (p₁, ..., p_n)  множества P и каждого элемента  (q₁, ..., q_n)  множества Q существует хотя бы один такой номер m, что  p_m = q_m.  Докажите, что хотя бы одно из множеств P и Q состоит не более чем из k^n–1 элементов для
  а)  k = 2  и любого натурального n;
  б)  n = 2  и любого натурального  k > 1;
  в) произвольного натурального n и произвольного натурального  k > 1.

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

Решение

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

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

Решение

---

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