Question

Помогите пожалуйста, буду очень очень сильно благодарна! Чтобы выйти из пещеры, Али-бабе нужно или сказать волшебное слово или решить головоломку. Волшебное слово он забыл, поэтому придется решать головоломку. Она такова: Есть полоска из 110 клеток, расположенных в два ряда. Нужно положить в некоторые из клеточек по камню (в каждой клеточке может быть либо один либо ноль камней) так, чтобы ровно у половины камней был сосед из другого длинного ряда. Если ему удастся так расположить максимально возможное количество камней, дверь откроется. Помогите Али-бабе, подскажите, каково это максимальное количество камней. Комментарий. Если в полоске 10 клеток (см. рисунок), то максимальное количество камней, которое можно расположить таким образом, равно четырем. На рисунке показано, как положить четыре камня, чтобы ровно у половины (у камня 1 и камня 3) был сосед из другого длинного ряда.

Answer 1

Пусть пару имеют 2n камней, тогда без пары тоже 2n камней. Каждая пара и каждый непарный камень занимают один столбец, поэтому всего будет занято n + 2n = 3n столбцов.

Всего доступно столбцов 110/2 = 55, поэтому 3n ≤ 55, n ≤ 18.

Максимальному n = 18 соответствует максимальное количество камней 4n =  72.

Answer 2

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

Для начала рассмотрим случай, когда n четное. Разместим камни во всех клетках первого ряда. Поскольку во втором ряду тоже n/2 клеток, и каждая из них имеет соседа из первого ряда, мы можем разместить ровно n/2 камней во втором ряду.

Теперь рассмотрим случай, когда n нечетное. Разместим камни во всех клетках первого ряда, кроме средней клетки (номер (n+1)/2). В этом случае у нас будет (n-1)/2 камней в первом ряду. Во втором ряду у нас также будет (n-1)/2 клеток, и каждая из них будет иметь соседа из первого ряда.

Таким образом, максимальное количество камней, которое можно разместить, равно n/2 для четного n и (n-1)/2 для нечетного n. В случае с полоской из 110 клеток, где n=110, мы получим:

Максимальное количество камней = 110/2 = 55.

Таким образом, Али-баба может разместить максимально 55 камней таким образом, чтобы ровно у половины из них был сосед из другого длинного ряда.