Andrew1000000 Aug 31 2011 at 20:17

Прямоугольники из спичек

1 min

1.7K

Entertaining tasks

+12

Comments 28

pfactum Aug 31 2011 at 20:33

Попробую. 150.

Levsha100 Aug 31 2011 at 21:43

135?

Levsha100 Aug 31 2011 at 21:44

Ой, извините, таки 150.

Andrew1000000 Aug 31 2011 at 20:35

У меня тоже получился такой ответ.
Может кто-то найдёт лучшее решение или докажет, что это невозможно :)

binba Aug 31 2011 at 20:36

Много

toomturum Aug 31 2011 at 20:44

imm.io/8I8C

Andrew1000000 Aug 31 2011 at 20:45

1 прямоугольник всё-таки остался…

LeshaL Aug 31 2011 at 21:04

В эту картинку много спичек можно вернуть
— в третий снизу ряд — все кроме крайних
— в пятый снизу ряд — аналогично
итд

Ну и конечно убрать одну спичку из внешнего

Andrew1000000 Aug 31 2011 at 20:46

Тоже 150 получилось.

Garrett Aug 31 2011 at 21:31

А если так?
imm.io/8Ied
получилось что надо убрать 100 спичек

binba Aug 31 2011 at 21:33

На оставшуюся, наверное, сотню прямоугольников вам плевать?)

Garrett Aug 31 2011 at 21:34

Так прямоугольников то и нету, одни г образные, или вы всё же имеете ввиду замкнутые контуры?

Sing Aug 31 2011 at 23:14

Судя по всему, в задании имелось ввиду именно замкнутые контуры. Ибо иначе ответ — ни одной, так как там нет прямоугольников изначально — одни квадраты.

Sing Aug 31 2011 at 23:25

Ой. Позор. Квадрат это прямоугольник. Всех с 1 сентября.

Sing Aug 31 2011 at 23:21

А также, у вас один большой прямоугольник (весь рисунок), 25 прямоугольников 3 х 2 спички. Ну а потом идут уже многочисленные комбинации.

altair4eg Aug 31 2011 at 21:33

140

altair4eg Aug 31 2011 at 22:07

125

Andrew1000000 Aug 31 2011 at 22:34

Поздравляю. Я и сам не знал, что решение можно так улучшить.
Подумал, что 150 предел, так как тогда получается максимальное остовное дерево, т. е. граф без циклов. А ведь циклы вполне могут быть, главное чтобы они не были прямоугольниками :)

hollow Aug 31 2011 at 22:43

не много не понял ваше решение и почему оно верное(? могу быть не прав) 1х1х1х1 спичка = квадрат, т.е. можно отделаться более меньшим кол-вом спичек, как например в варианте выше на 140.

link0ln Aug 31 2011 at 22:15

Раньше занимался темой изготовления домашних вайфай антенн(панельных), и вот сразу как-то вспомнилось, глядя на различные варианты расположения спичек )))

halyavin Aug 31 2011 at 22:21

Оптимум будет если разбить прямоугольник на угловые тримино так, чтобы не было подпрямоугольников разбитых на тримино. Это легко можно сделать для прямоугольников 2^n*2 x 2^n*3. Но как это сделать для 10x15 или 2000x3000 мне пока не понятно.

CAJAX Aug 31 2011 at 22:47

100 спичек вроде бы

CAJAX Aug 31 2011 at 22:48

А. уже понял, что неправильно. Куча прямоугольников осталась.

Denai Aug 31 2011 at 22:53

k.min.us/jU7nxeK6zWFUy.png
Оно?

Denai Aug 31 2011 at 22:55

А не, затупил, не обращайте внимания

Yan169 Sep 1 2011 at 00:09

115

Yan169 Sep 1 2011 at 00:25

108

Yan169 Sep 1 2011 at 02:48

Ещё можно оптимизировать до 105. Для такой схемы формула для поля n*m клеток, где m делится на 3, будет (m/3)*(2n+1). Т.е. для 2000x3000 получится 4001000. Думаю, это минимум.