Регистрирайте сеРегистрирайте се

Задача 14


 
   Форум за математика Форуми -> Задача на седмицата
Предишната тема :: Следващата тема  
Автор Съобщение
Pinetop Smith
Фен на форума


Регистриран на: 12 May 2007
Мнения: 961
Местожителство: Хасково
Репутация: 153.6Репутация: 153.6
гласове: 87

МнениеПуснато на: Mon Nov 10, 2008 3:56 pm    Заглавие: Задача 14

Имам 10 опитни зайчета и 1000 чинии с попара. В две от чиниите попарата е отровна. След един час трябва да нахраним група хора(като отровата действа точно 59 минута след като е поета).
а) Можем ли да нахраним 450 човека, като сме сигурни, че няма да отровим никой от тях?
б) Колко най-много човека можем да нахраним?

allier
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Реклама







Пуснато на:     Заглавие: Реклама

Върнете се в началото
dim
Напреднал


Регистриран на: 28 Jul 2008
Мнения: 324

Репутация: 45.7Репутация: 45.7Репутация: 45.7Репутация: 45.7Репутация: 45.7
гласове: 21

МнениеПуснато на: Mon Nov 10, 2008 4:28 pm    Заглавие:

а) Ами ако нахраним 452-ма човека със сигурност поне 450 ще останат живи Smile

Надали така се решава задачата. Аз не разбирам много и условието. Колко попара може да изяде най-много един заек? Може ли да разпределим всичката попара на 10 места? От колко попари най-много може да яде един заек за 1 мин?

Извинявам се предварително за абсурдните въпроси Smile

ПП: Интересна задача
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
dgs
Редовен


Регистриран на: 23 Jun 2008
Мнения: 228

Репутация: 25Репутация: 25Репутация: 25
гласове: 13

МнениеПуснато на: Tue Nov 11, 2008 12:25 am    Заглавие:

Има нещо смущаващо в така поставеното условие:
(1). От една страна би трябвало условието да предполага да може всяко от зайчетата да опита от "много" чинийки за тази една минута.
(2). От друга страна, ако това в (1) наистина е така, то има тривиално решение с което можем да нахраним 800 човека - делим паничките на 10 групи по 100 панички и всяко зайче за една минута опитва от всичките 100 панички в една единствена група. Две от тях ще умрат, но останалите живи осем зайчета, ще ни гарантират 800 неотровни панички.

И според мен, е необходимо да има доуточния по условието.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
allier
Начинаещ


Регистриран на: 14 Aug 2008
Мнения: 65

Репутация: 14.4
гласове: 6

МнениеПуснато на: Tue Nov 11, 2008 2:58 am    Заглавие:

Izvinqvam se che pak ne pisha na kirilica no prosto nqmam v momenta.

Shte dam malko doutochnenie. Purvo, i az ne znam kolko e otgovora za dve otrovni popari, za 499 znam primer, obache. Vtoro, vremeto kakto e zadadeno v uslovieto ne e vajno - edinstvenoto koeto ni kazva to e che tryabva vednaga da reshim kak da razpredelim poparata na zaicite t.e. ne mojem da izchakame zaek da umre za da testvame nanovo. Eto naprimer za 3 zaeka A,B,C i 7 popari P1,P2,...,P7 i samo edna otrovna (v zadachata ima tochno 2 otrovni, ne edna):

P1 -> A
P2 -> B
P3 -> C
P4 -> A & B
P5 -> A & C
P6 -> B & C
P7 -> A & B & C

Tui kato samo edna popara v tozi sluchai e otrovna po tova koi zaici sa umreli mojem da vustanovim otrovnata popara. Naprimer, ako umrat A i C, to poparata e 5-ta.

Problemut s tova kodirane v sluchaya na dve otrovni popari e che ne mojem da opredelim koi sa tochno te i saotvetno poluchavame che prekaleno mnogo ot poparite tryabva da sa potencialno otrovni.

Nadqvam se tova utochnenie da pomogne.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
allier
Начинаещ


Регистриран на: 14 Aug 2008
Мнения: 65

Репутация: 14.4
гласове: 6

МнениеПуснато на: Tue Nov 11, 2008 3:04 am    Заглавие:

Pak sum se oburkal neshto - vmesto 450 schitaite 900 t.e. v a) se pita mojem li da nahranim 900 choveka. Kakto e otbelyazal choveka, 800 popari mogat da se garantirat po nachina po koito toi e pokazal. Vuprosut e dali mojem s podhodqshto kodirane na poparite da garantirame poveche neotrovni.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
dim
Напреднал


Регистриран на: 28 Jul 2008
Мнения: 324

Репутация: 45.7Репутация: 45.7Репутация: 45.7Репутация: 45.7Репутация: 45.7
гласове: 21

МнениеПуснато на: Tue Nov 11, 2008 1:56 pm    Заглавие:

Ами ако наредим чиниите в кръг (1000-ъгълник), разпределим 10-те заяка по върховете му равномерно (10-ъгълник) и пуснем всеки заек да яде в радиус от върха на който седи 75 чинии. На базата на тази постановка и пресичането на радиусите на зайците, лесно се определя в кои 50 чини има отрова, а отровите са 2. Проста трябва да изчкаме да видим кои зайци ще умрат. Така че няма проблем да нахраним 900 човека.

Ако зайците се паднат в подходящите интервали, т. е. умрат само 2 заека, тогава използвайки постановката можем да заключим, че ще нахраним 1000-2.48=904 човека.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
allier
Начинаещ


Регистриран на: 14 Aug 2008
Мнения: 65

Репутация: 14.4
гласове: 6

МнениеПуснато на: Tue Nov 11, 2008 3:16 pm    Заглавие:

Za 900 ima primer, da. No tova koeto si napisal kato primer ne go razbrah neshto. Moje bi shtoto pri mene e 5 sutrinta :)
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
dim
Напреднал


Регистриран на: 28 Jul 2008
Мнения: 324

Репутация: 45.7Репутация: 45.7Репутация: 45.7Репутация: 45.7Репутация: 45.7
гласове: 21

МнениеПуснато на: Tue Nov 11, 2008 3:55 pm    Заглавие:

Постановката е акто на картинката. В средата на всяка от 10-те окръжности има по един заек, а по голямата окръйност са разпределени равномерно чиниите. Всеки заек яде в радиус 75 чинии, т. е. яде от 150 чинии. Така разбиваме 1000-те чинии на 20 части по 50 чинии. Кто знаем умрелите зайци винаги можем да кажем кои 50 чинии са заразени. Примерно ако умре заек N2, ще знаем, че неговата петдесятка е заразена. Ако умрат зайци N4 и N5, ще знаем, че петдесятката м/у тях е заразена. Ама като гледам сега май системата издиша при три поредни мъртви зайци...


Zaici.jpg
 Description:
 Големина на файла:  35.06 KB
 Видяна:  2734 пъти(s)

Zaici.jpg


Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
martosss
VIP Gold


Регистриран на: 17 Mar 2007
Мнения: 3937
Местожителство: Somewhere over the rainbow
Репутация: 424.2Репутация: 424.2
гласове: 213

МнениеПуснато на: Tue Nov 11, 2008 4:20 pm    Заглавие:

ОК, ето още един въпрос, който като че ли ще е с отрицателен отговор, но все пак съм длъжен да го задам:
Имаме 1 минута да нахраним 10 заека с 1000 купички попара, тоест по 100 купички на заек

Да кажем, че сме много организирани и освен това имаме точен часовник, който отчита точния момент, в който всеки заек е опитал от съответната купичка, може ли да засечем кога всеки заек приема попара и да гледаме след 59 мин и х секунди ТОЧНО кога ще умре заека, при което да се ориентираме коя точно е заразената купичка?

В този случай лош късмет би било ако двете заразени купички са при 1 и същ заек и първата е заразена, тогава след като умре точно на 59-тата минута няма да знаем коя друга купичка от останалите 99 от неговия дял е заразена Crying or Very sad Но предполагам че с малко комбинации на зайците би могло това да се избегне Wink

Въпроса остава - може ли да точно да се следи в коя секунда е умрял заек?
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Baronov
Напреднал


Регистриран на: 05 Jun 2008
Мнения: 316

Репутация: 55.4
гласове: 39

МнениеПуснато на: Tue Nov 11, 2008 4:31 pm    Заглавие:

HE.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
dgs
Редовен


Регистриран на: 23 Jun 2008
Мнения: 228

Репутация: 25Репутация: 25Репутация: 25
гласове: 13

МнениеПуснато на: Thu Nov 13, 2008 8:20 pm    Заглавие:

Стигам до следните отговори на въпросите в задачата:

а) Можем ли да нахраним 900 човека, като сме сигурни, че няма да отровим никой от тях?
Отговор: НЕ

б) Колко най-много човека можем да нахраним?
Отговор: 889

По-надолу, повърхностно съм обяснил как съм стигнал до тези отговори. Ако трябва, ще дам допълнителни обяснения в отделен пост.
А това са два полезни линка за комбинаторика. В тях са описани и означенията които ползвам по-долу.
http://www.math10.com/bg/algebra/kombinatorika.html
http://bg.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BC%D0%B1%D0%B8%D0%BD%D0%B0%D1%82%D0%BE%D1%80%D0%B8%D0%BA%D0%B0

Разгледал съм (на хартия) всички варианти на комбинации (и с повторения, и без повторения) на 10 елемента от 2-ри до 5-ти клас. Допълнително давах различни "тежести" към комбинациите от различните класове.
Няма смисъл да се разглеждат комбинациите от по-висок k-ти клас (k>5) - полезната информация за малкото подслучаи с оцелели живи зайчета е много малко и се налага да изхвърляме много панички, тъй като не можем да твърдим, че не са отровни.

По моите сметки, най-висок резултат се постига, при комбинации от 2-ри клас с повторения:
[tex]C_{10^{1}} + C_{10^{2}}[/tex]
т.е., от зайчетата правим възможните "единични" и двойни комбинации
[tex]C_{10^{1}} = 10[/tex]
[tex]C_{10^{2}} = 45[/tex]
[tex]C_{10^{1}} + C_{10^{2}} = 55[/tex]

Отделно, делим чиниите на групи от по 18 и 19 чинии по следния начин:
[tex]1000 = 10.19 + 45.18[/tex]
Зайчетата от десетте "единични" комбинации опитват от 10-те групи по 19 панички
Зайчетата от 45-те двойни комбинации опитват от 45-те групи по 18 панички
(По-нагоре споменах "тежести" - имах предвид именно това, че групите не са с еднакъв брой панички)

Има три възможни случая:

Случай 1. Умират 4 зайчета
Трябва да изхвърлим групите които съответстват на двойните комбинации от тези четири зайчета.
Общия брой на тези групи е
[tex]C_{4^{2}} = 6[/tex]
т.е., изхвърляме [tex]6.18 = 108[/tex] панички, като сме сигурни, че в останалите 892 няма отрова

Случай 2. Умират 3 зайчета
Трябва да изхвърлим групите които съответстват на двойните комбинации от тези три зайчета, а също и групите които съответстват на "единичните" комбинации на тези три зайчета.
[tex]C_{3^{2}} + C_{3^{1}} = 3 + 3 = 6[/tex]
т.е., изхвърляме [tex]3.18 + 3.19 = 111[/tex] панички, като сме сигурни, че в останалите 889 няма отрова

Случай 3. Умират 2 зайчета
Трябва да изхвърлим групите които съответстват на "единичните" комбинации на тези две зайчета, а същи и двойната комбинация от тия две умрели зайчета.
[tex]C_{2^{1}} + C_{2^{2}} = 2 + 1 = 3[/tex]
т.е., изхвърляме [tex]2.19 + 1.18 = 56[/tex] панички, като сме сигурни, че в останалите 944 няма отрова

Най-големия възможен брой с изхвърлени панички е в Случай 2 и затова не можем да твърдим, че при този метод - комбинации от 2-ри клас с повторения - можем да нахраним повече от 889 човека.

!?! Разбира се, може и да съм объркал някъде в разсъжденията и сметките
!?! Или пък да съм пропуснал някой вариант с по-висок клас комбинации, при който сметката за 900 човека ще излезе
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
dgs
Редовен


Регистриран на: 23 Jun 2008
Мнения: 228

Репутация: 25Репутация: 25Репутация: 25
гласове: 13

МнениеПуснато на: Tue Nov 18, 2008 9:41 am    Заглавие:

Laughing Докарах ги до 892.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
allier
Начинаещ


Регистриран на: 14 Aug 2008
Мнения: 65

Репутация: 14.4
гласове: 6

МнениеПуснато на: Tue Nov 18, 2008 10:53 am    Заглавие:

Davai oshte malko Razz - pone oshte 10-tina dobavi.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
dgs
Редовен


Регистриран на: 23 Jun 2008
Мнения: 228

Репутация: 25Репутация: 25Репутация: 25
гласове: 13

МнениеПуснато на: Tue Nov 18, 2008 11:18 am    Заглавие:

Аз ще давам, ама ти сигурен ли си, че няма още някакво объркване в условието ? И съответно си сигурен, че резултата от 900 е постижим ?

Извинявай, че ти задавам такъв въпрос, ама (ми) се налага.
От всичко прочетено до момента в тази задача, ми се струва че тази задача е неправилно обощение на друга задача.

Да не би например да се разчита, че ако разделим чиниите на две групи от по 500, то и в двете групи ще има по една отровна. Но това не е вярно - и двете отровни могат да останат в едната група от 500 чинии. Ако беше вярно, резултата щеше да е около 960.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
allier
Начинаещ


Регистриран на: 14 Aug 2008
Мнения: 65

Репутация: 14.4
гласове: 6

МнениеПуснато на: Tue Nov 18, 2008 11:22 am    Заглавие:

Ne, oburkvane nqma. No kato gledam si na prav put taka che si modificirai malko primera. Drugoto koeto oshte ne sme napravili po zadachata e dokazatelstvo koeto da limitira broya na sigurnite popari - tuk veche ne znam tochno kak da se podhodi.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
dgs
Редовен


Регистриран на: 23 Jun 2008
Мнения: 228

Репутация: 25Репутация: 25Репутация: 25
гласове: 13

МнениеПуснато на: Fri Nov 21, 2008 6:58 pm    Заглавие:

Laughing Докарах го до 896
Всички комбинации от 1-ви до 3-ти клас като съответните "тежести" са:
1000 = 120.5 + 45.5 + 10.13 + 1.45 , като от последните 45 чинии никой заек не опитва
Ако умрат 3 заека, изхвърляме 104 чинии, ако умрат четири заека, изхвърляме 102, във всички останали случаи (0, 1, 2, 5, 6 умрели зайци) изхвърляме под 100 или точно 100

ПП
allier написа:

Eto naprimer za 3 zaeka A,B,C i 7 popari P1,P2,...,P7 i samo edna otrovna

Примера с трите заека и едната отровна чиния става и за 8 попари

ПП2
Продължавам да си мисля, че има някакво объркване някъде по условието ... и няма (верен) пример за 900 ... или пък има някаква допълнителна логическа уловка - например, обединяваме чиниите по две в нови по-големи 500 чинии.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
nepoznat
Начинаещ


Регистриран на: 21 Nov 2008
Мнения: 11
Местожителство: Dimitrovgrad
Репутация: 3.6Репутация: 3.6Репутация: 3.6

МнениеПуснато на: Sat Nov 22, 2008 7:49 pm    Заглавие:

и аз ги докарах до 892
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
dgs
Редовен


Регистриран на: 23 Jun 2008
Мнения: 228

Репутация: 25Репутация: 25Репутация: 25
гласове: 13

МнениеПуснато на: Sun Nov 23, 2008 5:44 pm    Заглавие:

Very Happy
Разгледах един друг подход с непълно комбиниране, чрез който пак стигам до 896.
Обаче тук при този подход ми се струва, че има още какво да се оптимизира.

Накратко:
- разглеждаме паралелепипед със страни 5 x 4 x 4,
- представяме си, как паралелепипеда се състои от 5 пласта по x-координатата и от 4 пласта по y-координатата и от 4 пласта по z-координатата. И са се получили единични кубчета, които са сечения на точно по един x-пласт, един y-пласт и един z-пласт
- единичните кубчета вътре в паралелепипеда са общо 80 на брой
- разпределяме всичките 1000 чинии вътре в кубчетата, като в 60 кубчета имаме по 12 чинии, а останалите 20 кубчета имаме по 14 чинии. Тия 20 кубчета умишлено сме разположили на в 4-тия z-пласт, който се състои от 20 единични кубчета.
- пускаме 4 зайчета да опитат от всички чинии от първите 4 пласта по x-координатата, по 5-тия x-пласт не пускаме зайче
- пускаме други 3 зайчета да опитат от всички чинии от първите 3 пласта по y-координатата, по 4-тия y-пласт не пускаме зайче
- пускаме останалите 3 зайчета да опитат от всички чинии от първите 3 пласта по z-координатата, по 4-тия z-пласт не пускаме зайче

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

Накрая ще забележим, че трябва да изхвърлим най много 8 единични кубчета.
А от тези 8 единични кубчета, най-много 4 са с по 14 чинии
т.е. максималния брой изхвърлени чинии е
4.12 + 4.14 = 48 + 56 = 104

// Може да се оптимизира до 5.12 + 3.14 = 60 + 42 = 102
За целта, 20-те групи от по 14 чинии не ги държим в един z-пласт, ами ги разхвърляме равномерно между пластовете. Има как да стане оптимизацията до 102.

Другото, което се набива в очи, е че при този метод изхвърляме 1/10 от групите, но за съжаление, броя на групите е такъв, че не можем да разпределим 1000 чинии по равно във всичките групи. Ако можехме, то веднага получавахме 900.
И още нещо което се набива в очи - при този метод, в конретното разделяне на зайчетата на 3 непресичащи се множества (10=4+3+3) постигаме завидно отношение на (изхвърлени групи)/(общ брой групи) = 1/10. При всяко друго разделяне на три непресичащи се множества това отношение е по-голямо от 1/10. По-голямо е от 1/10 и когато разделим на 2, 4 или 5 непресичащи се множества (тогава паралелепипеда е 2-мерен, 4-мерен и 5-мерен, съответно изхвърляме 2^2, 2^4 и 2^5 на брой групи). По-голямо е и при повече на брой непресичащи се множества

И така, засега при мен окончателния резултат е 898 гарантирано неотровни чинии

ДОБАВЕНО:
Това с паралелепипеда директно решава видоизменената задача:
"Дадени са 2000 чинии (две от които са отровни). Да се отделят 1800"
Защото 2000 се дели на 80.
(на картинката, десетте заека са номерирани x1, x2, x3, x4, y1, y2, y3, z1, z2, z3)

Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Покажи мнения от преди:   
   Форум за математика Форуми -> Задача на седмицата Часовете са според зоната GMT + 2 Часа
Страница 1 от 1

 
Идете на:  
Не Можете да пускате нови теми
Не Можете да отговаряте на темите
Не Можете да променяте съобщенията си
Не Можете да изтривате съобщенията си
Не Можете да гласувате в анкети
You cannot attach files in this forum
Може да сваляте файлове от този форум
Copyright © 2005-2020 math10.com.