Задача про ссылки на «Кивипедии»

Условие

На «Кивипедии» есть несколько статей. В каждой статье имеется хотя бы одна ссылка на другую статью, а также на каждую статью «Кивипедии» ведёт ссылка с хотя бы одной другой статьи, но никакие две статьи не ссылаются друг на друга. Кроме того, известно, что со страницы «Киви (фрукт)», переходя по ссылкам, невозможно дойти до страницы «Киви (птица)». Редакторы хотят добавить ровно одну ссылку в ровно одну статью так, чтобы с каждой статьи, переходя по ссылкам, можно было добраться до любой другой (после этого две статьи могут ссылаться друг на друга). Оказалось, что это получится сделать N способами. Каким числам НЕ может равняться N? Выберите все подходящие варианты.

Варианты: 30, 31, 32, 33, 34, 35, 36, 37, 38, 39.

3 попытки

Если не получается
Как начисляется опыт
  • Разбор условия — +10
  • Мини-задача: сам — +20, пропуск — 0
  • Верный ответ — +30
  • На ответ — 3 попытки
  • В мини-задаче — 3 попытки
  • «Проверь себя» — ★ и +30 за задачу

Где начало новой стрелки

Назовём нижней группой статьи, в которые можно прийти из любой статьи, а верхней — статьи, из которых можно прийти в любую. Новая ссылка из статьи X в статью Y подходит. В какой группе статья X — в верхней или в нижней?

Сколько способов

Пусть в нижней группе 4 статьи, а в верхней — 6. Сколькими способами можно добавить подходящую ссылку?

Сколько статей в группе

Какое наименьшее число статей может быть в нижней группе (если подходящая ссылка есть)?

Пример

Пример: вверху 5 статей ссылаются друг на друга по кругу, внизу 7 статей тоже по кругу, и есть одна ссылка сверху вниз. Сколько всего ссылок в этом примере (до добавления новой)?

Сколько чисел не подходит

Сколько чисел из списка 30, 31, …, 39 не может равняться N?

    Сначала попробуй решить сам

    1

    Шаг 1 · разбираем условие

    Что дано и что нужно найти

    2:11

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

    • «На „Кивипедии“ есть несколько статей. В каждой статье имеется хотя бы одна ссылка на другую статью…»

      Нарисуем статьи кружками, а ссылки — стрелками. Из каждого кружка выходит хотя бы одна стрелка.

    • «…на каждую статью „Кивипедии“ ведёт ссылка с хотя бы одной другой статьи…»

      В каждый кружок входит хотя бы одна стрелка.

    • «…но никакие две статьи не ссылаются друг на друга.»

      Между двумя кружками нет пары стрелок «туда и обратно» — стрелка может быть только одна.

    • «…со страницы „Киви (фрукт)“, переходя по ссылкам, невозможно дойти до страницы „Киви (птица)“.»

      Ходить можно только по стрелкам, в их сторону. От кружка «Фрукт» до кружка «Птица» такого пути нет.

    • «Редакторы хотят добавить ровно одну ссылку в ровно одну статью так, чтобы с каждой статьи, переходя по ссылкам, можно было добраться до любой другой (после этого две статьи могут ссылаться друг на друга).»

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

    • «Оказалось, что это получится сделать N способами.»

      N — число подходящих новых стрелок. Стрелку определяет, откуда она идёт и куда.

    • «Каким числам НЕ может равняться N? Выберите все подходящие варианты.»

      Варианты — числа 30, 31, …, 39. Отметить нужно те, которыми N быть не может.

    ПФптицафрукт
    Пример, который подходит под условие: 8 статей, П — «Киви (птица)», Ф — «Киви (фрукт)». От Ф до П по стрелкам не дойти.

    Задача: найти среди чисел 30, 31, …, 39 все, которыми N быть не может.

    Разборы — 99 ₽ в месяц

    Оформить

    Сначала реши основную задачу

    3 задачи без подсказок

    Условие то же, варианты другие.

    Условие во всех трёх задачах

    На «Кивипедии» есть несколько статей. В каждой статье имеется хотя бы одна ссылка на другую статью, а также на каждую статью «Кивипедии» ведёт ссылка с хотя бы одной другой статьи, но никакие две статьи не ссылаются друг на друга. Кроме того, известно, что со страницы «Киви (фрукт)», переходя по ссылкам, невозможно дойти до страницы «Киви (птица)». Редакторы хотят добавить ровно одну ссылку в ровно одну статью так, чтобы с каждой статьи, переходя по ссылкам, можно было добраться до любой другой (после этого две статьи могут ссылаться друг на друга). Оказалось, что это получится сделать N способами. Каким числам НЕ может равняться N? Выберите все подходящие варианты.