Зайци и салати от моркови

[MitkoS]

При такова разпределение, колко чинии изхвърляме ако умрат X1,X2,Y1,Y2,Z1,Z2 ?
Би трябвало да изхвърлим 8.13 = 104 ==> остават 896

По мои предишни сметки (с тази задача интензивно се занимавах около шест (!!!) седмици преди да я публикувам тук), с паралелепипедчето, лесно се стига до 898 чинии. По едно време даже си мислех, че става и за 899 чинии, но вече не съм съвсем убеден в това.

Между другото Очо, горещо ти препоръчвам да попрегледаш старите задачи от този раздел - има далеч-далеч по-интересни неща от тези зайци. Пък и някое ново оригинално решение за тия зайци може да се появи от старите задачи.

[Очо]

А, не. Благодаря за предложението, но и тази ми стига. Иначе се страхувам, че ще започна да си режа морковите на равностранни триъгълници и да ги подреждам по степените на двойката в чинията.. Разбирам, че вече ти омръзна да ми четеш недогледаните предложения (ще гледам да не пиша повече...)и да ми показваш грешките, но сам човек трудно си ги намира.. Задачата изглежда лесна, ама хич не е.

[tonych]

4з. 5з. 6з. 3з.
25ч. 25ч. 1з.

25ч. 25ч. 2з.

заец 1 и заец 2 си хапват хоризонтално , а 5 и 6 вертикално 3 и 4 за разнообразие по диагонал
ако една чиния в квадрата е отровна и ако са две чинии отровни
1,4,5 1,3,4,5,6
2,3,5 2,3,4,5,6
2,4,6 1,2,3,4,5
1,3,6 1,2,3,4,6
1,2,3,5,6
1,2,4,5,6
всички тези зайци се жертват в името на салатата в най -добрия случай 3, а в най-лошия 6 за останалите 900 салати зайците се комбинират спрямо горната схема по следния начин:
345678
5678910
125678
1278910
123478
1234910
1256910
3456910
3478910
въпросът е заслужава ли си да загубим 6(3) заека за да спасим 950 наядени салати?




пп: снощи май съм бил замаян нещо нещата не са такива каквито изглеждат на пръв поглед.....в крайна сметка реших да спася 990 салати гарантирано, а с голяма вероятност 992
но пълно щастие няма губя от 1 до 10 заека


пп2:тъй като няма друга задача ще си позволя един допълнителен въпрос.(ако Миткос няма нищо напротив)
С колко най - малко зайци можем да спасим всичките 998 салати?

[MitkoS]

Интересно предложение, но има грешка - броят на умрелите зайци може да бъде 3, 4, 5, 6

При 3 и 4 всичко е наред - лесно отделяме 975, 950, 925, или точно 900 неотровни.
Но при 5 и 6, нещата категорично не стават.

Ще покажа как изглеждат нещата например при 4 умрели зайци, тъй като ми е най-лесно.
Съгласно предложението, делим първоначално на 10 групи по 100 чинии, и после всяко от тези 100 делим още един път на 4 по 25. И съответно опитването от страна на зайците е по предложената таблица в предишния пост.

a) 123456
b) 345678
c) 5678910
d) 125678
e) 1278910
f) 123478
g) 1234910
h) 1256910
i) 3456910
j) 3478910

Какво става, ако например умрат зайци с номера 1, 3, 6, 9
Трябва да отделим всички групи от по 25 чинии, от които три от умрелите зайци са опитвали.
Имаме група от която са опитвали (1,3,6) - тази група е в a)
Имаме група от която са опитвали (1,3,9) - тази група е в g)
Имаме група от която са опитвали (1,6,9) - тази група е в h)
Имаме група от която са опитвали (3,6,9) - тази група е в i)
Т.е., трябва да отделим 4 по 25 (=100) като потенциално отровни (защото, ако отровните две чинии са в които и да е две различни групи от посочените четири групи, то ще умрат точно тези четири заека)

Но при 5 или 6 умрели заека, вече трябва да отделим много повече потенциално отровни групи от по 25. Мързи ме да го разписвам в детайли, тъй като има разни подварианти и е трудно за обясняване, но така или иначе, предполагам, че вече става ясно защо трябва да отделим повече от 4 по 25. Най-лесно се вижда за случая когато умрат 1,3,5,7,9

[Bibi]

Сега аз съвсем се обърках
Защо отделяме цялата група А, щом заек 2 е жив?

[MitkoS]

Не отделяме цялата група A.
Група А се сътои от 100 чинии разделени на четири подгрупи A1, A2, A3, A4
Умрелите зайци <1,3,6> са опитвали "едновременно" точно от една от тези четири подгрупи и отделяме само нея от цялото А.

В предишния пост написах:
...
Имаме група от която са опитвали (1,3,6) - тази група е в a)
Имаме група от която са опитвали (1,3,9) - тази група е в g)
Имаме група от която са опитвали (1,6,9) - тази група е в h)
Имаме група от която са опитвали (3,6,9) - тази група е в i) ...

При сегашните доуточнения, текста трябва да се промени така:
Имаме такава подгрупа в a) от която са опитвали <1,3,6>
Имаме такава подгрупа в g) от която са опитвали <1,3,9>
Имаме такава подгрупа в h) от която са опитвали <1,6,9>
Имаме такава подгрупа в i) от която са опитвали <3,6,9>

ПП.
tonych е виновен за недоразуменията, защото него пръв го е домързяло да опише нещата както трябва

[tonych]

може би трябва да ги напиша всичките защото при мен в група h и група i умират съответно 1 6 и 10 и 3 6 10
важна е и подредбата в самата група ще проверя по внимателно снощи ги нацелих на прима виста


пп:ами домързя ме признавам виноват съм

сега ще я разпиша цялата за да се анализира по - лесно

[MitkoS]

В конкретния случай, важното е дали в h има подгрупа от която са опитвали и трите заека <1,6,9>
Ако няма такава, то аз не съм разбрал за какво става дума.
Ама така като гледам - има

[tonych]

х=25
4563
хх 1
хх 2

6785
хх 3
хх 4

89107
хх 5
хх 6

19102
хх 7
хх 8

1342
хх 9
хх 10

3784
хх 1
хх 2

59106
хх 3
хх 4

19102
хх 5
хх 6

3564
хх 7
хх 8

3784
хх 9
хх 10

може да има една разместена набрах ги директо от листа
sorry за дългата колона..... мисля че ако има дублиране чрез разместване може да се избегне
пп: Миткос разбрах къде бъркам 13589 ако умрат незнаем дали са били 135 189 589 359 и т.н
присъединявам се към хората които ще кажат че задчата е тудна , но не и нерешима скоро ще я разбием сега вече имам поглед върху нещата

[MitkoS]

Добре,
ако при конкретната наредба умрат 2,3,5,8,9, то имаме 5 на брой подгрупи за изхвърляне:
в a) - <2,3,5>
в b) - <3,5,8>
в c) - <5,8,9>
в d) - <2,8,9>
в g) - <3,5,9>
Защото може например двете отровни чинии да са:
- в съответните подгрупи в a) и d) (==> ще умрат точно тия пет заека)
- в съответните подгрупи в b) и d) (==> ще умрат точно тия пет заека)
- в съответните подгрупи в a) и c) (==> ще умрат точно тия пет заека)
- в съответните подгрупи в d) и g) (==> ще умрат точно тия пет заека)
Т.е., ако двете отровни чинии са например в подгрупите a) и d), то резултата е че ще умрат зайците 2,3,5,8,9
Но ние трябва да изхвърлим и тези от b) c) g) защото и при тях можем да получим същия резултат - и няма как да знаем че отровните чинии са точно в a) и d) защото ние виждаме само резултата от умрели зайци.

5 x 25=125

х=25
4563
хх 1
Xх 2

6785
хX 3
хх 4

89107
Xх 5
хх 6

19102
хх 7
Xх 8

1342
хх 9
хх 10

3784
хх 1
хх 2

59106
Xх 3
хх 4

19102
хх 5
хх 6

3564
хх 7
хх 8

3784
хх 9
хх 10

[Bibi]

Според моите сметки можем да гарантираме 896 чинии от 1000.
И вероятно мога да ви убедя, че повече от това не можем да постигнем.

По начина, по който Митко реши задачата за 2000.
Пак същите клетки, но сега в половината от тях ще сложим по 12 салати, а в останалите 40 клетки ще сложим по 13.
В най-лошия случай губим 8 от по-пълните комплекти, което прави 104 чинии.

[MitkoS]

Доколкото си спомням, този резултат от 896 неотровни чинии може да се постигне и с пълно комбиниране от тройни комбинации.

А с парелепипеда може и повече от 896 - клетките които са с по 13 чинии, се подреждат по такъв начин вътре в паралелепипеда, че сечението на кои и да е шест пласта (два по X, два по Y, два по Z) никога да не съдържа само клетки от по 13 чинии, а гарантирано да има поне две от по 12, с което се постигат 898 неотровни чинии. Сега не си спомням в детайли как точно ги наредих тогава тия клетки от по 13 чинии, но мога да се поразтърся в разни стари тефтери с драсканици.
Нещо повече - в един момент си мислех, че става и за 899 ... ама за 899 не си спомням категорично става ли или не става.

[Bibi]

Тази задача сама по себе си ми се вижда интересна.
И аз опитвах да направя подобна "фина настройка", но при положение, че гоним толкова голяма плътност от 50% за тези 13-ки, ми се видя изгубена кауза.
Прилича ми на задачата за разполагане на царици по шахматното поле. Само дето тук са топове, дъската е тримерна, а те имат право да бият най-много един друг топ.
Моля те, потърси тефтерите, защото за сега не успявам да го наглася.
А моите разсъждения са от съвсем друго естество и довечера ще ги напиша, за да обменим идеи.

[MitkoS]

Не си намерих тефтерите, но определено си мисля, че надценяваш сложността на „задачата с топовете” – говоря за случая в сечението да има най-малко две кубчета с по 12 чинии, с което си гарантираме резултат от 898 неотровни чинии.

Ето едно елементарно разсъждение:
Нека да вземем един от пластовете – няма значение по коя координата е и дали е 5x4 или 4x4 – нека за удобство да е 4x4. Ако тоя пласт ще участва в сечението, то в него ще има четири единични кубчета които са от това сечение и те „образуват правоъгълник” в смисъл, че техните координати са <x,y>, <x+x1,y>, <x,y+y1>, <x+x1,y+y1>.
Ако успеем така да наредим кубчетата в пласта, че който и да е такъв правоъгълник (в пласта) винаги да има поне една клетка с 12 чинии, то задачата е решена – можем спокойно да приложим същата наредба и в останалите пластове по тая координата, защото които и два пласта да участват в сечението по тази координата, то техните (при това "еднакви") правоъгълници ни дават общо две кубчета с 12 чинии. (Казвам „еднакви”, в смисъл че координатите на правоъгълника в единия пласт са <x,y,z1>, <x+x1,y,z1>, <x,y+y1,z1>, <x+x1,y+y1,z1>, а в другия са <x,y,z2>, <x+x1,y,z2>, <x,y+y1,z2>, <x+x1,y+y1,z2>).
А такива нареждания в пласта - колкото си искаш ( с „1” съм означил единично кубче с 13 чинии, а с „0” – единично кубче с 12 чинии):
0101
1010
0011
1100
Или пък
1010
0101
1100
0011
И т.н. (И всякаквите му там симетрии и ротации или пък рокадо на колони или рокадо на редове)

Дали ще дублираме пластовете по тая координата, или ще ползваме някоя разновидност все пак за да не са еднакви - все тая, съответните правоъгълници от тия два пласта, ще ни дадат най-малко две от нужните ни клетки с 12 чинии.

[Bibi]

Обещах да си опиша наблюденията и разсъжденията.

1. Имаме три числа - общ брой чинии, брой отровни и брой зайчета.
Най-важното от тях е броят отровни салати.
При една отровена задачата е много по-лесна.
Следващо по важност е не общият брой чинии, а броят зайци.
Това може лесно да се съобрази от факта, че като групираме (все едно смесваме) по 25 чинии, те стават неразличими една от друга. Дали ще започнем с 2000, или с 1200, или с 4000, решението ще е еднакво, само групите ще са с друг брой чинии.
(Единствената съществена разлика идва когато решаваме задача за 80 чинии вместо 2000, защото тогава всяка група ще е от само една чиния и няма да имаме двусмислието което получаваме сега - дали в откритата отровна група е имало само една или там са били и двете лоши чинии.)

2. Зачудих се защо Митко работи с тримерен куб, а не примерно с двумерен (т.е. правоъгълник) или 4-мерен...
Първо - мисля, че мога да докажа, че всяко решение би могло да се онагледи с помощта на някакъв (ако трябва дори 17-мерен) куб.

Какво показаха сметките ми с 10 зайци:
- 2-мерен е горе долу добре (изхвърляме 1/9);
- 3-мерен е още по-добре (само 1/10);
- при 4, 5, 6-мерен... нещата се влошават все повече и повече.

По тази причина считам, че някой тримерен модел ще е идеалното решение за 10 заека, без значение общо колко са чиниите.
Числото 10 може да се разбие на 3 събираеми по много начини, но най-хомогеният от тях (Митковия 4+3+3) дава максимума спасени чинии.

Направих още малко сметки само за сравнение (навсякъде смятам само случая с твърдо 2 отровни чинии):
- при 12 заека ни трябва 4-мерен модел.
- при 10 видяхме, че добрият модел е тримерен.
- при 8 заека най-доброто решение е двумерното (квадрат).
- при малки бройки зайци (примерно 4) работи едномерния - при който делим на 5 комплекта, всеки заек лапа само от един, нищо не се кръстосва.
- при 1 заек задачата не може да се реши. В смисъл, че ако той умре, каквото и да сме му дали да яде, няма да сме в състояние да посочим дори една-едничка неотровна салата.

По задачата за топовете ще помисля по-натам.