Есть 3 вида краски: красный, белый и синий. Необходимо покрасить ступеньки лестницы разными цветами, не разрешается комбинация из одинаковых цветов: КК, СС или ББ. Ступенек ровно 12. Существуют такие ограничения: синяя ступенька не должна иметь соседей одинакого цвета, то есть разрешаются такие варианты: КСБ или БСК, нельзя: КСК или БСБ, а также нельзя красить крайние ступеньки синей краской. Сколькими разными способами можно покрасить ступеньки лестницы? Пытаемся решить, но решение получается громоздким, и возможно, ошибочным. Заранее благодарю за помощь и подсказки!

задан 25 Окт 23:49

10|600 символов нужно символов осталось
2

Для начала окрасим в синий цвет какие-то ступеньки. Мы при этом выбираем подмножество (возможно, пустое), в котором нет соседних элементов. Найти число способов это сделать -- известная задача, где ответом являются числа Фибоначчи. То есть f(1)=2, f(2)=3, f(3)=5, ... и так далее. Здесь будет f(12)=377. Но надо исключить те варианты, когда крайние ступеньки синие. При этом 1-я и 12-я синие, 2-я и 11-я -- не синие, а остальные -- какие угодно по цвету, без синих соседей. Это f(8)=55 способов, их надо вычесть. Итого 322 способа выбора синих ступенек.

Легко понять, что если мы пропустим все синие цвета и рассмотрим остальные, то там Б и К везде будут чередоваться. Это значит, что каждый из 322 способов выбора синих ступенек, двумя способами продолжается до раскраски в три цвета. Итого 644 способа.

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

ссылка

отвечен 26 Окт 1:06

1

Интересно, что задача эквивалента замощению полосы из 11 клеток доминошками размером в 1 или 2. А это число наверное легко найти?

(26 Окт 1:38) abc
1

@abc: я не знаю, почему эквивалентна, но если мы полоску покрываем плитками из 1 или 2 клеток, то там тоже числа Фибоначчи возникают.

(26 Окт 1:48) falcao
1

у меня другой ответ получился $%2F_{12}=2\cdot89=178$% проверил вручную для лестницы из n=4 получилось $%2F_{4}=2*3=6$%.

(26 Окт 2:48) abc
1

@abc: там хотя и числа Фибоначчи, но номера сдвинуты. Это надо учитывать.

Для n=4 есть такие способы: БКБК, КБКБ, СБКБ, СКБК, КСБК, БСКБ, КБСК, БКСБ, КБКС, БКБС, СКСБ, СБСК, КСБС, БСКС. Их не 6, а 14, то есть 2(f(n)-f(n-4)), где f(0)=1, f(1)=2, f(2)=3, f(3)=5, f(4)=8 и т.д.

P.S. Я сейчас перечитал условие, и заметил, что его можно понять двояко. Я понял так, что обе сразу синие ступеньки нельзя красить синим. Если же никоторую нельзя, то ответом будет 2f(n-2). Но тогда это 2*144=288.

(26 Окт 3:06) falcao

Спасибо за подробное решение задачи! Надо будет почитать о числах Фибоначчи и связи этих чисел с комбинаторикой. А правильный ответ 288, если крайние ступеньки не красить в синий цвет?

(26 Окт 22:04) milib

@milib: да, если ни одна из крайних ступенек не синяя, то раскрашиваются n-2 клетки кроме крайних, где синих соседей нет. Тогда получается f(n-2), а потом умножаем на 2 с учётом раскраски того, что останется, в два цвета.

О числах Ф. достаточно знать только рекуррентную формулу. Пусть есть m клеток. Если первая синяя, то вторая не синяя, и остальное раскрашиваем f(m-2) способами. Если первая не синяя, то f(m-1) для остальной части. Отсюда f(m)=f(m-1)+f(m-2), а больше тут никакой теории нет.

(26 Окт 23:22) falcao
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,005
×4

задан
25 Окт 23:49

показан
72 раза

обновлен
27 Окт 19:46

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru