uwdanny

To 大山

   

对了,就是这么简单
当是老师上课就是举的这个例子,请2个同学上台表演
结果是,分配的一方以拿出2枚硬币成交.急得俺在下面喊,"ONE ENOUGH".

That's also Question 1 on my first assignment when I took Game Theory course. ^oo^

For this question, I agree with the answer ( 97, 0, 1, 0, 2 ) or ( 97,0,1,2,0 ). The key point is to ensure the satisfaction from #4 or #5, since #3 will agree anyways.

uwdanny

To rat, do we know whether the unbalanced individual weights less or more than the others? Just to make sure everything's absolutely clear.

uwdanny

Here's an attemp using enumeration-related knowledge.

Label 12 balls as

001, 112, 200,
010, 120, 201,
011, 121, 202,
012, 122, 220

I did this because there're 3^3 = 27 possible lables. We first need to eliminate 000, 111, 222, these 3 labels are useless; now there remains 27-3=24 labels. Since it is a circular list, we divide by 2 to eliminate the ordering. ( ie. 100 is same as 122 but with bit-flip, 1 -- 1, 0 --- 2 )

Now, we rename these labels as follows,

    A   001
    B   010
    C   011
    D   012
    E   112
    F   120
    G   121
    H   122
    I   200
    J   201
    K   202
    L   220

Notice that each digit has 4 "0"s, 4 "1"s and 4 "2's. Now we can start the 3 weighings.

First weigh: Weigh ABCD against IJKL, that is, weigh shots with first digit 0 against those with first digit 2. If Weight(ABCD) less than Weight(IJKL), we mark 0; else if Weight(ABCD) greater than Weight(IJKL), we mark down 2, else, (the different one will have first digit 1), we mark down 1

Second weigh: Weight AIJK against FGHL, that is, weigh shots with second digit 0 against those with second digit 2. If Weight(AIJK) less than Weight(FGHL), we mark 0; else if Weight(AIJK) greater than Weight(FGHL), we mark down 2, else, (the different one will have second digit 1), we mark down 1

Third weigh: similar to first, second weight, focus on the 3rd digit of the labels.

My claim is that, if we let x, y, z represent the numbers we mark down from weight 1, 2, 3 respectively, then the ball labelled xyz is the different one, which is lighter than the rest.

In the case if xyz doesn't appear on my labelling list, you could do a bit-flip operation, the label obtained after bit-flip is guaranteed to be on my labelled list, and that individual will be heavier than the rest.

Done. ^oo^

uwdanny

To "Big Mt.", I think my solution makes more mathematical sense and easier to prove.

^oo^