Помогите решить задачки на логику

lerabva

CRIMINAL CUPBEARERS. An evil king has 1000 bottles of wine. A neighboring queen plots to kill the bad king, and sends a servant to poison the wine. The king's guards catch the servant after he has only poisoned one bottle. The guards don't know which bottle was poisoned, but they do know that the poison is so potent that even if it was diluted 1,000,000 times, it would still be fatal. Furthermore, the effects of the poison take one month to surface. The king decides he will get some of his prisoners in his vast dungeons to drink the wine. Rather than using 1000 prisoners each assigned to a particular bottle, this king knows that he needs to murder no more than 10 prisoners to figure out what bottle is poisoned, and will still be able to drink the rest of the wine in 5 weeks time. How does he pull this off?
2. CIRCULAR JAIL CELL. There is a circular jail with 100 cells numbered 1-100. Each cell has an inmate and the door is locked. One night the jailor gets drunk and starts running around the jail in circles. In his first round he opens each door. In his second round he visits every 2nd door (2,4,6---) and shuts the door. In the 3rd round he visits every 3rd door (3 ,6,9---) and if the door is shut he opens it, if it is open he shuts it. This continues for 100 rounds (i.e. 4,8,12 ---; 5 ,10,15 ---; ---; 49,98 etc.) and exhausted the jailor falls down. How many prisoners found their doors open after 100 rounds?
3. 100 PRISONERS AND A LIGHT BULB
100 prisoners are imprisoned in solitary cells. Each cell is windowless and soundproof. There's a central living room with one light bulb; the bulb is initially off. No prisoner can see the light bulb from his or her own cell. Each day, the warden picks a prisoner equally at random, and that prisoner visits the central living room; at the end of the day the prisoner is returned to his cell. While in the living room, the prisoner can toggle the bulb if he or she wishes. Also, the prisoner has the option of asserting the claim that all 100 prisoners have been to the living room. If this assertion is false (that is, some prisoners still haven't been to the living room all 100 prisoners will be shot for their stupidity. However, if it is indeed true, all prisoners are set free and inducted into MENSA, since the world can always use more smart people. Thus, the assertion should only be made if the prisoner is 100% certain of its validity.
Before this whole procedure begins, the prisoners are allowed to get together in the courtyard to discuss a plan. What is the optimal plan they can agree on, so that eventually, someone will make a correct assertion?
Note 1: ( 1/8/2003 3:51PM Update) What is meant by optimal? If your solution is optimal, it means you can prove that no other algorithm can produce a lower average running time. This is usually very hard to do though, and I would be surprised if anyone ever sends me such a proof. So the best we can do in the meantime is try to beat the best average running time we know of. The number to beat so far is around 3500 days. So BEFORE YOU E-MAIL ME YOUR SOLUTION, check its average time to see if beats the 4000 day ballpark. If you get a number around 27-28 years, then you've found the solution most people who solve the puzzle come up with. However, it's not optimal.
Note 2: (1/8/2003 3:49PM Update) How to compute average running time? The preferred method is to do a probabilistic analysis using pencil and paper. But if you haven't learned about stuff like that, a much simpler way is to just program your solution and run it maybe 100 times, recording how many days elapsed in each invocation. Afterwards you should have an array of 100 numbers. Now take the average of all them, and you'll have an empirical average which is close to the theoretical one.
Note 3: (11/7/2002 7:35AM Update) The problem statement used to say "The prisoners are allowed to get together one night to discuss a plan." In the forum, quite a few people mentioned the clever solution of simply having the planning meeting in the central living room, and then asserting that everyone has been there on the first day of the random selection process. To assure that this problem is not so easily defeated, I have stipulated that the meeting happen in the courtyard.
Note 4: Does anyone know where this riddle originated? I got it from a friend who got it from another friend who doesn't know where it comes from.

kliM

Если у числа четное число делителей (включая 1 и само число то клетка с этим номером будет закрыта, в противном случае - открыта. Нечетное число делителей только у квадратов, значит открыты будут комнаты с номерами 1, 4, 9, ... 81, 100, т.е. 10 штук

kliM

пусть для простоты у нас 1024=2^10 бутылок, занумеруем их от 0 до 1023 и запишем в двоичной системе. Номера будут 10-значными.
Возьмем 10 смертников, для кажного сготовим "коктейль": Для i-го смертника (i=1...10) смешаем вина из бутылок, i-я цифра в номере которых равна нулю, бутылок таких у каждого будет 512. Даем выпить. Через месяц смотрим кто помер, кто нет. Результат 0 - помер, 1 - нет записываем в виде 10-значного двоичного числа. Получаем номер ядовитой бутылки, спаиваем ее ассасину. В худшем случае (если отравлена нулевая бутылка) помрет 10 зеков.

lerabva

Спасибо тебе большое.
народ, а кто-нибудь может на счёт третей задачки что-то знает?
привожу её ещё раз , а то её не видно за другими:)
3. 100 PRISONERS AND A LIGHT BULB
100 prisoners are imprisoned in solitary cells. Each cell is windowless and soundproof. There's a central living room with one light bulb; the bulb is initially off. No prisoner can see the light bulb from his or her own cell. Each day, the warden picks a prisoner equally at random, and that prisoner visits the central living room; at the end of the day the prisoner is returned to his cell. While in the living room, the prisoner can toggle the bulb if he or she wishes. Also, the prisoner has the option of asserting the claim that all 100 prisoners have been to the living room. If this assertion is false (that is, some prisoners still haven't been to the living room all 100 prisoners will be shot for their stupidity. However, if it is indeed true, all prisoners are set free and inducted into MENSA, since the world can always use more smart people. Thus, the assertion should only be made if the prisoner is 100% certain of its validity.
Before this whole procedure begins, the prisoners are allowed to get together in the courtyard to discuss a plan. What is the optimal plan they can agree on, so that eventually, someone will make a correct assertion?
Note 1: ( 1/8/2003 3:51PM Update) What is meant by optimal? If your solution is optimal, it means you can prove that no other algorithm can produce a lower average running time. This is usually very hard to do though, and I would be surprised if anyone ever sends me such a proof. So the best we can do in the meantime is try to beat the best average running time we know of. The number to beat so far is around 3500 days. So BEFORE YOU E-MAIL ME YOUR SOLUTION, check its average time to see if beats the 4000 day ballpark. If you get a number around 27-28 years, then you've found the solution most people who solve the puzzle come up with. However, it's not optimal.
Note 2: (1/8/2003 3:49PM Update) How to compute average running time? The preferred method is to do a probabilistic analysis using pencil and paper. But if you haven't learned about stuff like that, a much simpler way is to just program your solution and run it maybe 100 times, recording how many days elapsed in each invocation. Afterwards you should have an array of 100 numbers. Now take the average of all them, and you'll have an empirical average which is close to the theoretical one.
Note 3: (11/7/2002 7:35AM Update) The problem statement used to say "The prisoners are allowed to get together one night to discuss a plan." In the forum, quite a few people mentioned the clever solution of simply having the planning meeting in the central living room, and then asserting that everyone has been there on the first day of the random selection process. To assure that this problem is not so easily defeated, I have stipulated that the meeting happen in the courtyard.
Note 4: Does anyone know where this riddle originated? I got it from a friend who got it from another friend who doesn't know where it comes from.
Оставить комментарий
Имя или ник:
Комментарий: