Нещо като тетрис

[kamenf]

#	#	#	#		#	#	#
						#
#	#
#	#			#	#
					#	#
			#
			#
			#	#

Условията:

• Поле, квадратно, 8х8, като показаното по-горе, но празно.
• Произволен брой от всички възможни завъртяни и огледални варианти на изобразените в примерното поле цветни блокчета (нещо като тетрис блокчетата)
• Блокчетата не падат като при тетрис, а могат да се поставят на произволно свободно място в полето (всяко квадратче на блокче да е на незаето от друго блокче поле)

Целта:
Да се заемат с блокчета възможно най-малко квадрати от полето без да е възможно да се постави повече кое да е от наличните блокчета.

Варианти, предполагам, има доста. Давайте своите и да видим кой до къде може да го докара.
За по-напреднали: колко е възможният най-малък брой?

[klingonoid]

.....

[kamenf]

Супер! А по-добре може ли?

[Yasen6275]

	#	#	#			#
		#		#		#	#
#	#		#	#	#	#
	#		#	#		#
	#		#	#		#
	#	#	#	#		#	#
#	#		#		#
	#			#	#	#

Ако под по-добре разбираш с по-малко парчета, може би да, с едно по-малко. Всяка междина трябва да е с размер 3 квадратчета или по малка за да не може да се сложи нещо в нея. Колкото са по-близки до този размер междините, толкова по ефективно се използва пространството. Пр мен има 4 с размер единица които теоретично биха могли да станат на 2 (3,1 или 2,2) но не го виждам как.

ПП Държа да получа наградата за най-красиво подреждане. В краен случай за най-симетрично.

ППП 8 парчета *4 квадратчета = 32 заети => че има 32 свободни или 10 междини по 3 и една по 2

// Някакъв брутфорс с по 4 запълнени и 4 празни на ред и колона и някакви допълнителни условия за съседство?

/// След няколко часа драскане по една камара листа съм почти убеден, че няма как да стане с 8 парчета.

[ql^2/8]

И аз мисля, че 9 е минималния брой. Това са 36 запълнени и 28 незапълнени,
което ще рече поне 10 бели дупки, повечето от които по 3 квадратчета.
Ето моите кандидати в конкурса за симетрия:
tet3.jpg tet1.jpg
Проверих коя фигура сама може да се изпълни задачата с 9 парчета.
Оказаха се две: едната е показана на втората картинка горе, ако се замени
средното квадратче със стълбичката, а другата е по-долу:
tet2.jpg

[kamenf]

4x4 - може:

	#
#	#		#
#		#	#
		#

4x8 - може:

		#	#	#
	#		#		#	#	#
#	#	#		#		#
			#	#	#

Какво му е на 8х8?

[Yasen6275]

4x4 - 16 квадратчета - 12 гранични - 3/4 > 0.5
4х8 - 32 квадратчета - 20 гранични - 5/8 > 0.5
8х8 - 64 квадратчета - 28 гранични - 7/16 > 0.5

Ако ми остане време утре ще тествам редицата 5х5, 6х6, 7х7.

//в тея размерности липсата на кратност на броя квадратчета (елемент/общ) е голям проблем.

[kamenf]

Ясене, 28 са граничните. Не че подобрява отношението...
Аз, обаче, не мога да видя в този факт достатъчно условие за невъзможност. А може и да изпускам нещо което за мен не е очевидно.
Някой ще опита ли да даде неоспоримо доказателство? В едната или в другата посока...

[Yasen6275]

Ясене, 28 са граничните. Не че подобрява отношението...
Аз, обаче, не мога да видя в този факт достатъчно условие за невъзможност. А може и да изпускам нещо което за мен не е очевидно.
Някой ще опита ли да даде неоспоримо доказателство? В едната или в другата посока...

Оправено. На мен ми се струваше че 0.5 е граничната стойност.

Идеята ми е че с нарастване на размера на големия квадрат нараства броя на квадратчета които трябва да се оградят от 4 страни, а не от 3. Другото което усложнява задачата при увеличаването на страна на големия квадрат/правоъгълник е необходимостта да запълниш едно от "изгодните" квадратчета. Тоест слагаш ограничител там където го има вече.

Бе най-просто казано, ако големя квадрат ти има периодично гранично условие (~безкрайна площ), с 50% покритие не можеш да минеш.

// Само да си посмял да попиташ колко близко до 0.5 можем да стигнем и ....

[Bibi]

Понеже имам начална идея, а нямам време да я доразвия, някой иска ли да я споделя тук?

[Yasen6275]

Понеже имам начална идея, а нямам време да я доразвия, някой иска ли да я споделя тук?

Ади ди ди. Не бъди скръндза

[Bibi]

Ок.
Първо - за който не се е сетил, най-лесно ми се вижда човек вместо да рисува, да си вземе една истинска шахматна дъска. Да си маркира по нея с копчета/бобчета/мидички/пулове от някоя игра. Или още по-добре да вземе един лист хартия, да го сложи върху дъската за да го разчертае на квадрати, като се води по нея и да си изреже фигурки от 5-те модела. Няма нужда от огледални, понеже фигурките могат да се обръщат при нужда. Освен това вярвам, че от пръчковидните и квадратните няма да се ползват много бройки.

Самата идея е да се концентрираме върху дупките, а не върху тетрисчетата.
Най-изгодните дупки са от 3 кутийки. От тях може да имаме пръчковидна тройка или L.
Пръчката има 8 съседни квадратчета, които трябва да се покриват с фигура, а L има само 7, така че L е по-изгоден.
Ако един L се разположи в ъгъл, тези 7 намаляват на само 3 - останалите 4 се спестяват.

Ако има решение с 8 фигури, дупките ще са на обща площ 32.
Това в най-добрия случай означава 10 тройни и една двойна.
Около тях трябва да се покрият между 76-86 съседни квадрата (като някои са преброени по два пъти).
По ръбове и ъгли можем да спестим max 24 от тях, така че остават 52 до 86 квадрата за покриване.
И оттук трябва да можем някак да сметнем, че това няма как да стане само с 8 фигурки.

[Yasen6275]

Ти мислиш за дупките, аз с какво да ги запълвам. Какво да се прави, физиологични особености.

Това с броя съседни квадратчета ми харесва като идея. Ще взема да я открадна и да я приложа в моите разсъждения.

От тетрисчетата пръчката има 10 съседа, L-9 и останалите по 8.
Друго важно "свойство" на тетрисчетата е броя ъгловите съседи които могат да имат. Това ни дава възможност да "ограждаме" дупките по-ефективно според мен.
При пръчката и квадрата са 4, L- 5 и при станалите по 6.

// Май трябва да обединим подходите си и да говорим за "единични граници" и максимално ефективното им използване.

/// Камене ако решим за 8х8 ще ни мъчиш ли за 12х12? Или първо 12х8?

//// Това топологична задача ли е?

///// За произволна размерност на големия квадрат имаме 4 квадратчета с 2 единични граници(ег), 4х(n-2) с 3 ег и (n-2)² с 4 ег.
Дупките могат да бъдат с размер 1, 2 и 3 квадратчета.
Както се подразбира от по-горния ред, единична дупка може да има 2,3 или 4 ег, в зависимост от мястото си.
Двойна, в зависимост от мястото си и ориентацията, 3-6 ег.
Пръчковидната 3-ка, 4;5;7;8 ег.
Огънатата 3-ка, 4;6;7;8 ег.

[Bibi]

Огънатата 3-ка, ако е на ръб има 5 съседа. А максимумът й е 7.

[Yasen6275]

Аналогични разсъждения за тетрисчетата:
Пръчка - 5;6;9;10 ег.
L - 4;6;8;9;10 ег.
стълба - 7-10 ег.
т - 6-10 ег.
квадрат - 4;6;8 ег.

Броя на ег в един голям квадрат е 4*n²- 4*n=4*n(n-1) 4*2+4*3*(n-2)+4*4*(n² - 2n+4) =4*(2+3n-6+4n² -8n+16)=4*(4n²-5n+12) 4(n² - n + 4). За n=8 това са 224.

Десет 3-ни и една 2-на дупка унищожават 42 от тях. 8 тетрисчета унищожават от 48 до 64. (свързаността на елементите)

Остават 118-134 ег.

Делим на 2(двойното преброяване на всяка ег) и остават 59-67.

За дупките това означава 6 ег средно за всяка.
За тетрисчетата - 7-9 ег средно за за всяко.

- - - - - - - - - -

Биби аз броя граничните чертички, не съседните квадратчета.