Author Topic: ZT: 寻找魔法豌豆  (Read 36724 times)

fzy

  • Hero Member
  • *****
  • Posts: 520
ZT: 寻找魔法豌豆
« on: 三月 27, 2006, 02:30:53 pm »
小仙女Cinderella有n个袋子,每个袋子里有无限的豌豆。n-1个袋子里的豌豆是正常的,每粒重一克;有一个特殊袋子里的豌豆是魔法豌豆,每个重两克。每次Cinderella可以用每个袋子里取出若干豌豆,然后放在一起称称有多重。她的秤最多称量100克的东西,即使Cinderella选出的豌豆总重大于100克,称量的结果将仍然是100克。用10次称量,最多可以在多少个袋子中找到那个装魔法豆子的袋子?

 
 

packman

  • Full Member
  • ***
  • Posts: 226
Re: ZT: 寻找魔法豌豆
« Reply #1 on: 三月 27, 2006, 03:59:31 pm »
I think the lower bound is bigger than that:

Take 1 bean  from each bag, 1st time you can weigh 99 bags.
if they are equal to 99 grams, weigh the next 99 bags.... and so on.

To find a special bag among 99 bags, you need 4 rounds (52 + 26 + 13 + 13 = 104 )

So the lower boundary is at least 99*6 + 104 = 698 bags.
« Last Edit: 三月 27, 2006, 04:08:53 pm by packman »
简单==完美

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
Re: ZT: 寻找魔法豌豆
« Reply #2 on: 三月 27, 2006, 04:04:30 pm »
We can put 99 bags for the first 4 weighs, 96 for the 5th weigh, 72 for the 6th weigh, 48 for the 7th weigh, 24 for the 8th weigh, 18 for the 9th weigh, 12 for the 10th weigh, this gives us a total of 666. This is just my current thinking, someone may come up with a bigger number. I will think more about this later. Just to put a lower bound here. 666 (devil's number).

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
Re: ZT: 寻找魔法豌豆
« Reply #3 on: 三月 27, 2006, 04:07:21 pm »
Quote
I think the lower bound is bigger than that

As soon as I post it, I realized that and deleted my earlier post and made a new one. But my new one comes out at the same time as yours (yours is probably several minutes earlier, while I was typing my message). I see our idea is the same, but different numbers. I am sure you cannot put 13 bags in the last weigh, thus, your number is definitely wrong. :)  I will think about it more.
« Last Edit: 三月 27, 2006, 04:12:57 pm by 万精油 »

packman

  • Full Member
  • ***
  • Posts: 226
Re: ZT: 寻找魔法豌豆
« Reply #4 on: 三月 27, 2006, 04:16:28 pm »
Why can't? :?

[ I am sure you cannot put 13 bags in the last weigh, thus, your number is definitely wrong. :)  I will think about it more.
简单==完美

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
Re: ZT: 寻找魔法豌豆
« Reply #5 on: 三月 27, 2006, 04:27:56 pm »
Quote
Why can't?


Suppose nothing wrong in the first 9 weighs, your last weigh of 13 bags will need 91 beans. Which only gives you a window of 9, and you cannot differentiate the last five bags (9,10,11,12,13).

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
Re: ZT: 寻找魔法豌豆
« Reply #6 on: 三月 27, 2006, 04:29:38 pm »
After some more detailed thinking, my new lower bound is 99*7+78+26+12=809. Would love to see a higher number.

packman

  • Full Member
  • ***
  • Posts: 226
Re: ZT: 寻找魔法豌豆
« Reply #7 on: 三月 27, 2006, 04:57:12 pm »
I see why you cannot weigh 13 beans in the last round.
But somehow I think your new high number is too high. Can you explain the last two rounds?
I think it would be 12+12+24+48+96+99*5 = 591

After some more detailed thinking, my new lower bound is 99*7+78+26+12=809. Would love to see a higher number.
« Last Edit: 三月 27, 2006, 04:59:56 pm by packman »
简单==完美

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
Re: ZT: 寻找魔法豌豆
« Reply #8 on: 三月 27, 2006, 05:02:09 pm »
Quote
But somehow I think your new high number is too high.

On the countary, I just realized it can go even higher. I am leaving my office right now, will type more when I got home. (i.e. tonight).

idiot94

  • Sr. Member
  • ****
  • Posts: 484
Re: ZT: 寻找魔法豌豆
« Reply #9 on: 三月 27, 2006, 05:09:42 pm »
leaving office at 5? ... envy .. :)
In general, the men of lower intelligence won out. Afraid of of their own shortcomings ... they boldly moved into action. Their enemies, ...  thought there was no need to take by action what they could win by their brains. Thucydides, History

idiot94

  • Sr. Member
  • ****
  • Posts: 484
Re: ZT: 寻找魔法豌豆
« Reply #10 on: 三月 27, 2006, 05:21:14 pm »
my current number is 7*99+124=817.
First 7 round 99, then the last pile is 50+50+24 (put 50+24*2) --- the next pile will be 50. Put 13+13*2+11*3, final pile will be 13. Put 1+..+12 (leave 1 out).
In general, the men of lower intelligence won out. Afraid of of their own shortcomings ... they boldly moved into action. Their enemies, ...  thought there was no need to take by action what they could win by their brains. Thucydides, History

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
Re: ZT: 寻找魔法豌豆
« Reply #11 on: 三月 27, 2006, 09:00:05 pm »
Quote
my current number is 7*99+124=817.

Same idea, my number is 819.

First 7 weigh are 99 each.

The 8th weigh we can deal with 70 (43 1s and 27 2s)

The 9th weigh we can deal with 43 (13 1s, 13 2s, 13 3s and 4 4s)

The last weigh is 13 (1 to 12 each and leave one out)

This gives us a total of 7*99+70+43+13 = 819.

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
Re: ZT: 寻找魔法豌豆
« Reply #12 on: 三月 27, 2006, 09:07:11 pm »
Let me explain my numbers:

If there are 13 bags, and one of them is magic, then, we can put n beans from the nth bag from the first 12 bags, this gives us total of 78. Whatever over weight will tell us the magic bag. If the weigh is exactly 78, then we know the 13th bag is the magic.

Now that we know we can handle 13 bags, in the next to the last weigh, we can have 13 1s,  13 2s, 13 3s and 4 4s, if the magic bag is among them, this weigh will restrict it to 13 bags.

Now that we know we can handle 43 bags with two weighs, in the third to the last weigh, we can have 43 1s, and 27 2s (total of 97 beans).

The rest of them is easy, 99 beans each round.

万精油

  • Administrator
  • Hero Member
  • *****
  • Posts: 1831
Re: ZT: 寻找魔法豌豆
« Reply #13 on: 三月 28, 2006, 08:43:52 am »
Since we can also use leave one out strategy in the second to last round, we can actually handle 44 instead of 43, this means we can get 71 in the third to the last round (44 1s and 27 2s). Thus, the total is 820.

820!

May be the problem should ask for 4 round instead of 10 round, because 7 99 is just too much.
« Last Edit: 三月 28, 2006, 08:45:50 am by 万精油 »

fzy

  • Hero Member
  • *****
  • Posts: 520
Re: ZT: 寻找魔法豌豆
« Reply #14 on: 三月 28, 2006, 10:08:12 am »
You all have the right strategy, now just need to fine tune it a little more.