Вывод формул для сетки с элементами.

[kthxbye]

Имеем сетку, площадью S со сторонами a, b (нечетные), разделенную на единичные квадраты, которые принимают значение: клетки с дробью (x), точкой (y) и пустая клетка (z). Условия расположения: к x должны примыкать 4 y по горизонтали и вертикали, но не по диагонали; x не могут примыкать друг к другу по диагонали; оставшиеся промежутки занимают z; для любой сетки параметры x, y максимальны.

Вывести формулы зависимости x, y, z от a, b и S соот.-но.

[arseniiv]

И что вы на пути к этому уже сделали?

[kthxbye]

Собственно, вывел рабочие формулы путем построения сеток малых размеров:

$a = 2n + 1, b = 2m + 1, x = n(m+1) + m(n+1), y = mn, z = m + n + mn + 1;$

Меня интересует какими еще способами их можно вывести.

[arseniiv]

Можно, например, индукцией доказать, что для бо́льших размеров всё так же.

Кстати, требование

kthxbye в сообщении #795061 писал(а):

для любой сетки параметры x, y максимальны

неоднозначно.

Вы уверены, что формулы верны? Для доски $3\times3$ можно напридумывать много вариантов, но $(x,y,z)=(4,1,4)$ никак у меня не получается. Как он у вас выглядел?

kthxbye в сообщении #795061 писал(а):

Условия расположения: к x должны примыкать 4 y по горизонтали и вертикали

Могут ли $x$-клетки быть на краях сетки?

(И ещё штрих.)

kthxbye в сообщении #795061 писал(а):

клетки с дробью (x), точкой (y) и пустая клетка (z)

Коли уж вы не представили никаких картинок, зачем было описывать их так? Написали бы «клетки трёх типов: $x, y, z$». Или хотя бы среднее «фиолетовые, жёлто-зелёные и цвета морской волны» — это хотя бы можно неоднозначно представить.

[kthxbye]

arseniiv в сообщении #795071 писал(а):

Могут ли $x$-клетки быть на краях сетки?

Нет, не могут. В первых и последних рядах и столбцах чередуются z и y.

arseniiv в сообщении #795071 писал(а):

неоднозначно.

Почему же? В квадрате 3х3 мы можем разместить максимум 1 кл. х, к которой примыкают 4 кл. у. Тогда $z = 4$.

arseniiv в сообщении #795071 писал(а):

Написали бы «клетки трёх типов: $x, y, z$».

В оригинале это /, . и пустая. Заменять можно любыми параметрами, или даже цветами, какими душе угодно.

[arseniiv]

kthxbye в сообщении #795078 писал(а):

Почему же? В квадрате 3х3 мы можем разместить максимум 1 кл. х, к которой примыкают 4 кл. у. Тогда $z = 4$.

Для этого квадрата других вариантов, исходя из уточнения о том, что клетки $x$ не могут быть на краю, и так нет. Так что этот размер ничего показательного не даёт, кроме того, что, значит, формулы записаны точно неправильно: вы описали вариант $(x,y,z) = (1,4,4)$, а по формулам

kthxbye в сообщении #795067 писал(а):

$a = 2n + 1, b = 2m + 1, x = n(m+1) + m(n+1), y = mn, z = m + n + mn + 1;$

выходит $(4,1,4)$. Надеюсь, они просто перепутаны.

Пока мне кажется, что для любого размера есть всегда только один вариант размещения.

-- Вс дек 01, 2013 21:02:47 --

Или, если уж говорить об оптимизации, то только числа $x$.

[kthxbye]

arseniiv в сообщении #795081 писал(а):

Надеюсь, они просто перепутаны.

Да, пардон. $x = mn, y =n(m+1) + m(n+1), z = m + n + mn + 1.$

arseniiv в сообщении #795081 писал(а):

Пока мне кажется, что для любого размера есть всегда только один вариант размещения.

Это действительно так. Если все клетки по периметру грубо назовем кольцом, то в итоге в сетке чередуются два кольца - z и y; x и y.

arseniiv в сообщении #795081 писал(а):

Или, если уж говорить об оптимизации, то только числа $x$.

Есть другие вариации задачи, которые я не указал. Например, если примыкание кл. х по диагонали допустимо, то количество кл. y будет уже несколько другим.

[arseniiv]

Так вот, если оптимизируется $x$, то кажется, что $2\times2$-периодическая структура — единственное решение. Из-за правил фактически в сетку погружаются не отдельные клетки $x,y,z$, а блоки

$$\begin{bmatrix} z & y & z \\ y & x & y \\ z & y & z \end{bmatrix},$$

которые могут перекрываться. Вам надо только показать, что большее, чем $mn$, количество таких блоков сетка $(2m+1)\times(2n+1)$ не выдержит.

А с другими правилами и задача уже другая. Не всегда можно по решению одной задачи построить решение похожей.

-- Вс дек 01, 2013 21:18:39 --

arseniiv в сообщении #795086 писал(а):

Вам надо только показать, что большее, чем $mn$, количество таких блоков сетка $(2m+1)\times(2n+1)$ не выдержит.

И индукция по $(m,n)$ тут должна быть замечательно уместной.

-- Вс дек 01, 2013 21:21:28 --

kthxbye в сообщении #795084 писал(а):

Например, если примыкание кл. х по диагонали допустимо, то количество кл. y будет уже несколько другим.

Просто если, например, максимизировать только количество клеток $y$, мы получим очевидное $(x,y,z) = (0,ab,0)$ — раз нет $x$-клеток, мы не стеснены правилами, которые касаются только их окружения. Если $ax + by\to\max$, можно получить тоже разное. И порядок на парах $(x,y)$ задать можно по-разному, так что надо точно указывать точно, когда что максимизируется.

[kthxbye]

arseniiv в сообщении #795086 писал(а):

Просто если, например, максимизировать только количество клеток $y$, мы получим очевидное $(x,y,z) = (0,ab,0)$ — раз нет $x$-клеток, мы не стеснены правилами, которые касаются только их окружения. Если $ax + by\to\max$, можно получить тоже разное. И порядок на парах $(x,y)$ задать можно по-разному, так что надо точно указывать точно, когда что максимизируется.

Я, к своему стыду, ничего не понял из вышесказанного и индукцией решать задачи не умею.

arseniiv в сообщении #795086 писал(а):

А с другими правилами и задача уже другая. Не всегда можно по решению одной задачи построить решение похожей.

К слову, там $x = 2n(n - 1) + 1, y = 2n(n + 1), z = 4n.$

[arseniiv]

Индукция — это, скорее, технический приём, чтобы уже найденный ответ формально обосновать. Вот у вас есть $1=mn$ блок для $(m,n)=1$. Теперь представьте, что для произвольных $(m,n)$ у вас имеется $k$ блоков, и докажите, например, что для $(m,n+1)$ блоков должно быть ровно $k+m$. (Если $k = mn$, то $k + m = m(n+1)$.) Тогда, если учесть, что для $(n,m)$ блоков столько же, сколько для $(m,n)$, можно индукцией показать, что для $(m,n)$ всегда $mn$ блоков. (Коряво как-то написал.)