матрица из окон дома, сколько сигналов можно закодировать

[Whitaker]

Здравствуйте! Может кто-нибудь помочь с этой задачкой? Честно говоря, я даже условие не понял(т.е. как и где расположены окна и чего требуется) и не понял какие сигналы считаются одинаковыми.

Окна дома, обращенные к морю, расположены в узлах прямоугольной сетки с m горизонталями (этажами) и n вертикалями. Сколько сигналов можно передать находящемуся в море кораблю, освещая некоторые из окон дома, если в темноте нельзя различить положение освещенных окон относительно дома?

[MrDindows]

Whitaker в сообщении #465243 писал(а):

как и где расположены окна и чего требуется) и не понял какие сигналы считаются одинаковыми.

Окна расположены...как таблица $m$ на $n$. Одинаковыми считаются одинаковые "фигуры", например, если у нас горят два соседних окна внизу по центру или же два соседних окна вверху справа - это одна и та же фигура, один и тот же сигнал.

[ewert]

Whitaker в сообщении #465243 писал(а):

если в темноте нельзя различить положение освещенных окон относительно дома?

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

[Whitaker]

MrDindows в сообщении #465256 писал(а):

Whitaker в сообщении #465243 писал(а):

как и где расположены окна и чего требуется) и не понял какие сигналы считаются одинаковыми.

Окна расположены...как таблица $m$ на $n$. Одинаковыми считаются одинаковые "фигуры", например, если у нас горят два соседних окна внизу по центру или же два соседних окна вверху справа - это одна и та же фигура, один и тот же сигнал.

Других как бы "эквивалентных" ему нет да больше? Только одна? Или еще есть ?
Если есть, то напишите пожалуйста хотя бы некоторые. Задача мне до сих пор неясна.

[MrDindows]

Whitaker в сообщении #465269 писал(а):

MrDindows в сообщении #465256 писал(а):

Whitaker в сообщении #465243 писал(а):

как и где расположены окна и чего требуется) и не понял какие сигналы считаются одинаковыми.

Окна расположены...как таблица $m$ на $n$. Одинаковыми считаются одинаковые "фигуры", например, если у нас горят два соседних окна внизу по центру или же два соседних окна вверху справа - это одна и та же фигура, один и тот же сигнал.

Других как бы "эквивалентных" ему нет да больше? Только одна? Или еще есть ?
Если есть, то напишите пожалуйста хотя бы некоторые. Задача мне до сих пор неясна.

Что вы имеете ввиду под словом эквивалентные в кавычках? Давайте у нас будут просто одинаковые сигналы и разные. Про них я вам написал.

-- Пн июл 04, 2011 23:23:43 --

И очевидно что расстояние между окнами мы можем различить, да и об этом чётко написано в условии: не возможно различить положение окон относительно дома, значит относительно других светящихся окон положение можно различить.

[Dan B-Yallay]

Можно c кораблем договориться, что например, самое правое нижнее окно горит всегда. Тогда максимально возможное число сигналов будет $2^{mn-1}$.
При дополнительных договоренностях можно выжать еще какое-то число сигналов. Например, правое нижнее окно горит почти всегда, а если не горит, то будет огорожено горящими как буквой Г:

$$ \begin{matrix}X & \ldots & X & X \\ \cdot & \cdot & \cdot & \cdot \\ X & \ldots & \square & \square \\ X & \ldots & \square & \blacksquare \end{matrix} \hspace{60pt} \Rightarrow \hspace{20pt} 2^{mn-1}+ 2^{mn-4}$$

Наверное можно и это улучшить.

[PAV]

Вообще-то нетрудно понять, что всегда должно гореть хотя бы одно окно в левом столбце и хотя бы одно в нижней строке.

[TOTAL]

В прямоугольной клетчатой доске X на Y покрасили некоторые клетки так, что в правом и левом столбцах есть покрашенная клетка, также в нижней и верхней строках есть покрашеная клетка. Надо найти количество таких раскрасок. Затем просуммировать по всех прямоугольникам, вмещающимся в заданный в условии прямоугольник.

[PAV]

TOTAL

зачем требовать одновременно правый и левый столбец? а также верхнюю и нижнюю строчку?

Достаточно чего-то одного.

Вообще-то ответ задачи должен быть $2^{nm}-2^{(n-1)m}-2^{(m-1)n}+2^{(n-1)(m-1)}$

(здесь не посчитан случай, когда ни одно окно не горит; из условия задачи не вполне ясно, считается ли это за "сигнал"; по здравому смыслу вроде как нет, но если да - тогда его надо еще добавить)

[TOTAL]

PAV в сообщении #465343 писал(а):

зачем требовать одновременно правый и левый столбец? а также верхнюю и нижнюю строчку?

Чтобы задать сигнал определенных габаритов.

Например, для $n=m=2$
1 сигнал с габаритами 1 на 1
1 сигнал с габаритами 1 на 2
1 сигнал с габаритами 2 на 1
7 сигналов с габаритами 2 на 2

[PAV]

Это слишком сложное решение исходной задачи. Считать отдельно количество сигналов заданных габаритов совершенно излишне.

[TOTAL]

PAV в сообщении #465350 писал(а):

Это слишком сложное решение исходной задачи. Считать отдельно количество сигналов заданных габаритов совершенно излишне.

Да, теперь вижу, что $\left[2^{n-1} \cdot 2^{m-1} + (2^{n-1}-1) \cdot (2^{m-1}-1) \right] \cdot 2^{(n-1)(m-1)}$