Число внутренних стенок.
От: Pushkin Россия www.linkbit.com
Дата: 03.04.03 06:15
Оценка:
У меня явно не хватает кнопок, чтобы оценить задачу КонстантинаА о Лабиринтах
Автор: KonstantinA
Дата: 11.02.03
. Помимо того, что она сама весьма занимательна, я уже сбился со счёта, какую новую задачу она порождает. (Если кого наш PolyminoLab подзадолбал, можете дальше не читать )

На бумаге в клеточку написуем прямоугольник AxB. Какова может быть максимальная длина (в клетках) внутренних стенок, при котором область останется связной (из любой клетки можно попасть в любую другую)?


Нужна формула и более-менее убедительное доказательство. Мне кажется, у меня есть и то и другое.
Re: Число внутренних стенок.
От: Chorkov Россия  
Дата: 03.04.03 06:35
Оценка: 91 (5)
Здравствуйте, Pushkin, Вы писали:

P>

P>На бумаге в клеточку написуем прямоугольник AxB. Какова может быть максимальная длина (в клетках) внутренних стенок, при котором область останется связной (из любой клетки можно попасть в любую другую)?


Нуу,.. сегодня что-то совсем просто ...

Число внутренних границ между клетками A(B-1)+B(A-1)=2AB-A-B,
Число границ между клетками, которые должны остаться незакрытими,
найдем из следующих соображений: представим что клетки — вершины
графа ( AB вершин ). Тогда чтобы его связать надо AB-1 связей —
это число границ, которые должны остаться не перегороженными.

Следивательно число перегородок: A(B-1)+B(A-1)-(AB-1)=AB-A-B+1=(A-1)(B-1).

Пример решения:

+-----+
|* * *|
|     |
|*|*|*|
|     |
|*|*|*|
+-----+
Re[2]: Блин, даже добавить нечего :)
От: Pushkin Россия www.linkbit.com
Дата: 03.04.03 06:41
Оценка:
Здравствуйте, Chorkov

Re: Число внутренних стенок.
От: mrhru Россия  
Дата: 03.04.03 06:45
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>У меня явно не хватает кнопок, чтобы оценить задачу КонстантинаА о Лабиринтах
Автор: KonstantinA
Дата: 11.02.03
.


Чем смог — помог.

P>

P>На бумаге в клеточку написуем прямоугольник AxB. Какова может быть максимальная длина (в клетках) внутренних стенок, при котором область останется связной (из любой клетки можно попасть в любую другую)?


P>Нужна формула и более-менее убедительное доказательство. Мне кажется, у меня есть и то и другое.


И мне кажется, что у меня есть и то и другое, а также кажется что и у тебя тоже есть и то и другое.
Следовательно, у меня кажущихся вещей в два раза больше.

1) Верхняя оценка.
Для связности лабиринта необходимо, чтобы каждая его клетка 
имела не менее 2 открытых граней. Кроме того, у двух клеток 
допустимо наличие только по одной открытой грани - в них 
путь начинается и заканчивается. А так же, каждая внутрення
стенка принадлежит двум клеткам. Тогда 

  Lmax = (2АВ - 2(А + В) + 2) / 2 = АВ - (А + В) + 1

2) Такие лабиринты существуют, например

+-----------+
|           |
|---------- |
|           |
| ----------|
|           |
|---------- |
|           |
+-----------|
Евгений
Re[2]: Число внутренних стенок.
От: Pushkin Россия www.linkbit.com
Дата: 03.04.03 06:51
Оценка:
Здравствуйте, mrhru, Вы писали:

M>Чем смог — помог.




M>1) Верхняя оценка.

M>Для связности лабиринта необходимо, чтобы каждая его клетка
M>имела не менее 2 открытых граней. Кроме того, у двух клеток
M>допустимо наличие только по одной открытой грани — в них
M>путь начинается и заканчивается.

Вполне допустимы лабиринты, где более двух тупиков. Тем не менее мне кажется это нормальным путём, просто рассуждения надо провести поаккуратнее... Но гениально простое решение от Chorkov делает их ненужными.
Re[3]: Число внутренних стенок.
От: mrhru Россия  
Дата: 03.04.03 06:57
Оценка:
Здравствуйте, Pushkin, Вы писали:

M>>1) Верхняя оценка.

M>>Для связности лабиринта необходимо, чтобы каждая его клетка
M>>имела не менее 2 открытых граней. Кроме того, у двух клеток
M>>допустимо наличие только по одной открытой грани — в них
M>>путь начинается и заканчивается.

P>Вполне допустимы лабиринты, где более двух тупиков. Тем не менее мне кажется это нормальным путём, просто рассуждения надо провести поаккуратнее...


Согласен.

P>Но гениально простое решение от Chorkov делает их ненужными.


Совершенно согласен.
Евгений
Re[3]: Хотя...
От: Pushkin Россия www.linkbit.com
Дата: 03.04.03 06:59
Оценка:
P>Здравствуйте, Chorkov

...клетки — вершины графа ( AB вершин ). Тогда чтобы его связать надо AB-1 связей


Вот это неплохо бы доказать для полного счастья
Re[4]: Хотя...
От: mrhru Россия  
Дата: 03.04.03 07:11
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>

P>...клетки — вершины графа ( AB вершин ). Тогда чтобы его связать надо AB-1 связей


P>Вот это неплохо бы доказать для полного счастья


Что именно доказать?
То, что дерево — это связный граф без циклов, т.е. у дерева число связей минимально?
Или то, что в дереве с N вершинами N-1 связь, что доказывается по индукции?
Евгений
Re[5]: Хотя...
От: Pushkin Россия www.linkbit.com
Дата: 03.04.03 07:19
Оценка:
Здравствуйте, mrhru, Вы писали:

M>Или то, что в дереве с N вершинами N-1 связь, что доказывается по индукции?


Имелось в виду утверждение: для того, чтобы граф с N вершинами был связным в нём должно быть как минимум N-1 связь. Оно не так очевидно, как кажется — разговоров о цепочках маловато будет. Но ты уже произнёс ключевое слово "индукция", поэтому считай, что я успокоился
Re[6]: Хотя...
От: MichaelP  
Дата: 03.04.03 07:51
Оценка: 14 (2)
Здравствуйте, Pushkin, Вы писали:

P>Имелось в виду утверждение: для того, чтобы граф с N вершинами был связным в нём должно быть как минимум N-1 связь. Оно не так очевидно, как кажется — разговоров о цепочках маловато будет. Но ты уже произнёс ключевое слово "индукция", поэтому считай, что я успокоился


Могу успокоить и без индукции:

Предположим есть граф. Если мы сольем две вешины соединенные ребром, то получим граф с тем же числом связных компонент. При этом число вершин уменьшится на 1, а ребер, как минимум на 1. Очевидно, что такую операцию мы можем продолжать до "схлопывания" графа в точки, соответствующие связным компонентам. Отсюда — количество ребер в графе, как минимум N-S, где S число связных компонент.
Re: Число внутренних стенок.
От: MichaelP  
Дата: 03.04.03 08:20
Оценка: 2 (1)
Здравствуйте, Pushkin, Вы писали:

Опять же навеяло
P>

P>На бумаге в клеточку написуем прямоугольник AxB. Назовем "комнатой" прямоугольник со сторонами >=2 не содержащий внутри себя стенок. Какова может быть минимальная длина (в клетках) внутренних стенок, при котором прямоугольник не содержит "комнат"?


Нужна формула и более-менее убедительное доказательство. Мне кажется, у меня есть и то и другое. (© Pushkin)
Re[7]: Хотя...
От: Pushkin Россия www.linkbit.com
Дата: 03.04.03 08:30
Оценка:
Здравствуйте, MichaelP, Вы писали:

MP>Предположим есть граф. Если мы сольем две вешины соединенные ребром, то получим граф с тем же числом связных компонент. При этом число вершин уменьшится на 1, а ребер, как минимум на 1. Очевидно, что такую операцию мы можем продолжать до "схлопывания" графа в точки, соответствующие связным компонентам. Отсюда — количество ребер в графе, как минимум N-S, где S число связных компонент.




PS
IT опять что-то нахимичил с оценками, так что приходится обходиться значками
Re[2]: Число внутренних стенок.
От: mrhru Россия  
Дата: 03.04.03 09:04
Оценка:
Здравствуйте, MichaelP, Вы писали:

MP>Опять же навеяло

P>>

P>>На бумаге в клеточку написуем прямоугольник AxB. Назовем "комнатой" прямоугольник со сторонами >=2 не содержащий внутри себя стенок. Какова может быть минимальная длина (в клетках) внутренних стенок, при котором прямоугольник не содержит "комнат"?


MP>Нужна формула и более-менее убедительное доказательство. Мне кажется, у меня есть и то и другое. (© Pushkin)


И мне кажется, что у меня есть и то и другое, а также кажется что и у тебя тоже есть и то и другое.
Следовательно, у меня кажущихся вещей в два раза больше. (© не помню)

1)   Если в лабиринте нет комнат 2х2, то нет и комнат больших размеров.
1.5) Необходимо так поставить стенки, чтобы любая комната была разрушена.
2)   В лабиринте АхВ без внутренних стенок - возможных комнат 2х2 - (А - 1) * (В - 1)
3)   Установкой одной стенки мы можем разрушить не более двух комнат
4)   Итого стенок требуется не менее
     Lmin = (А - 1) * (В - 1) / 2

Например, для лабиринта 3х3:
+-----+
|* * *|
|     |
|*|*|*|
|     |
|* * *|
+-----+
Евгений
Re[3]: Число внутренних стенок.
От: MichaelP  
Дата: 03.04.03 09:15
Оценка:
Здравствуйте, mrhru, Вы писали:

M>
M>1)   Если в лабиринте нет комнат 2х2, то нет и комнат больших размеров.
M>1.5) Необходимо так поставить стенки, чтобы любая комната была разрушена.
M>2)   В лабиринте АхВ без внутренних стенок - возможных комнат 2х2 - (А - 1) * (В - 1)
M>3)   Установкой одной стенки мы можем разрушить не более двух комнат
M>4)   Итого стенок требуется не менее
M>     Lmin = (А - 1) * (В - 1) / 2

M>Например, для лабиринта 3х3:
M>+-----+
M>|* * *|
M>|     |
M>|*|*|*|
M>|     |
M>|* * *|
M>+-----+
M>


А 4х4?
Re[4]: Число внутренних стенок.
От: Pushkin Россия www.linkbit.com
Дата: 03.04.03 10:53
Оценка: 2 (1)
Здравствуйте, MichaelP, Вы писали:

MP>А 4х4?


Ну просто округляй в большую сторону и всё.
mrhru совершенно прав — одной стенкой убиваем две соседние (частично перекрывающиеся) комнаты. Если нарисовать сетку из (A-1)x(B-1) точек, где каждая символизирует комнату, а связь их перекрытие, то надо просто убирать последовательно пары связанных комнат. Не видо, что бы нам могло препятствовать это делать, если только в самом конце одна комната останется, так её отдельно покоцать.

Итак ответ (A-1)*(B-1)/2 с округлением вверх.
Для 4х4 это будет 3*3/2=5

* * * *
  -
* * *|*
  -
* * *|*
  -
* * * *
Re[4]: Число внутренних стенок.
От: mrhru Россия  
Дата: 03.04.03 11:03
Оценка: 22 (2)
Здравствуйте, MichaelP, Вы писали:

MP>Здравствуйте, mrhru, Вы писали:


M>>
M>>1)   Если в лабиринте нет комнат 2х2, то нет и комнат больших размеров.
M>>1.5) Необходимо так поставить стенки, чтобы любая комната была разрушена.
M>>2)   В лабиринте АхВ без внутренних стенок - возможных комнат 2х2 - (А - 1) * (В - 1)
M>>3)   Установкой одной стенки мы можем разрушить не более двух комнат
M>>4)   Итого стенок требуется не менее
M>>     Lmin = (А - 1) * (В - 1) / 2

M>>Например, для лабиринта 3х3:
M>>+-----+
M>>|* * *|
M>>|     |
M>>|*|*|*|
M>>|     |
M>>|* * *|
M>>+-----+
M>>


MP>А 4х4?


Мдя.

Немного по другому (в свете модных нынче графов )
Необходимо устранить в исходном графе все циклы длины 4.
Например, для комнаты 5х5, граф будет в виде,
+-+-+-+
| | | |
+-+-+-+
| | | |
+-+-+-+
| | | |
+-+-+-+
| | | |
+-+-+-+

где + это центры комнат.

Разрывы всех циклов длиной 4 — это замощение этого клетчатого поля домино.
Если количество клеток нечетно (когда (А — 1) * (В — 1) нечётно), необходимо
добавлять ещё одну стенку, поэтому
 Lmin = floor((А - 1) * (В - 1) / 2)
Евгений
Re[5]: Число внутренних стенок.
От: mrhru Россия  
Дата: 03.04.03 11:11
Оценка:
Здравствуйте, Pushkin, Вы писали:

MP>>А 4х4?


P>Ну просто округляй в большую сторону и всё.


Упс. Опоздал с ответом.

P>Итак ответ (A-1)*(B-1)/2 с округлением вверх.


Евгений
Re[5]: Число внутренних стенок.
От: MichaelP  
Дата: 03.04.03 11:16
Оценка:
Здравствуйте, mrhru, Вы писали:


M>Немного по другому (в свете модных нынче графов )

M>Необходимо устранить в исходном графе все циклы длины 4.
M>Например, для комнаты 5х5, граф будет в виде,
M>
M>+-+-+-+
M>| | | |
M>+-+-+-+
M>| | | |
M>+-+-+-+
M>| | | |
M>+-+-+-+
M>| | | |
M>+-+-+-+
M>

M>где + это центры комнат.

M>Разрывы всех циклов длиной 4 — это замощение этого клетчатого поля домино.

M>Если количество клеток нечетно (когда (А — 1) * (В — 1) нечётно), необходимо
M>добавлять ещё одну стенку, поэтому
M>
M> Lmin = floor((А - 1) * (В - 1) / 2)
M>


С вестибулярным аппаратом немного не в порядке (пол с потолком перепутал)
А так решение лучше чем мое
Re[6]: Число внутренних стенок.
От: mrhru Россия  
Дата: 03.04.03 11:24
Оценка:
Здравствуйте, MichaelP, Вы писали:

M>>
M>> Lmin = floor((А - 1) * (В - 1) / 2)
M>>


MP>С вестибулярным аппаратом немного не в порядке (пол с потолком перепутал)



При выборе одного из двух, если к тому же известен правильный выбор, вероятность неправильного выбора больше, чем, скажем, выбор 1 из 10.
Евгений
Re[6]: Offtopic
От: MichaelP  
Дата: 03.04.03 11:24
Оценка:
Здравствуйте, MichaelP, Вы писали:

MP>С вестибулярным аппаратом немного не в порядке (пол с потолком перепутал)


Всегда путал сталактиты со сталагмитами, пока добрые люди не научили простому правилу:

StalaGmite — Ground
StalaCtite — Ceil

Это откуда они растут.
Re: Число внутренних стенок.
От: Аноним  
Дата: 04.04.03 08:29
Оценка:
Здравствуйте, Pushkin,

Если размер клеточки а удовлетворяет единственному условию а > 0 ,
то их колличество может быть не ограничено никаким целым числом, т.е. бесконечно.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.