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

[pfactum]

Попробую. 150.

[Levsha100]

135?

[Levsha100]

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

[Andrew1000000]

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

[binba]

Много

[toomturum]

imm.io/8I8C

[Andrew1000000]

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

[LeshaL]

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

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

[Andrew1000000]

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

[Garrett]

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

[binba]

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

[Garrett]

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

[Sing]

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

[Sing]

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

[Sing]

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

[altair4eg]

140

[altair4eg]

125

[Andrew1000000]

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

[hollow]

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

[link0ln]

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

[halyavin]

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

[CAJAX]

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

[CAJAX]

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

[Denai]

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

[Denai]

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

[Yan169]

115

[Yan169]

108

[Yan169]

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