S/O 面試 - 推理遊戲 brain teasers (答案posted)

最近喜歡找brain teasers來玩, 看到一些很不錯的. 在這跟大家分享.
看到有一題跟之前的面試post裡相似的問題, 但是難度更高. 原來大公司如Google或投資銀行也問過面試的程序員.  我花了些時間才找到方法, 再去看其他答案後發現我的方法有些不同. 可見我是沒程序員的思考啊!
大家試試看, 說不定有一天面試時用得上.

如果有十二枚波子, 十一枚的重量一樣, 其中一枚的不同 (可以是較輕或重). 你如何用平衡秤三次來找出不同重量的一枚? 不同的一枚是較輕或較重?

已經知道答案的板友請不要回答.

Edit : to add the need to find whether the unusual one is lighter or heavier.

Update: pg.1&2已有答案. 想玩的不要scroll down

本篇文章已被 Pearltea 於 Aug 23 2015, 16:43 編輯過

[很喜歡這種貼，謝謝分享]

我會選擇用two-split.

12->6,6
6->3,3

當然最後較難，想了一想，就1,1; 不同就知道了。[故意說亂些少，但應該明白的XD]

另外一問：有多少個solution?

two-split的方法: 如果已知道不同的一枚是較輕或較重才會有用. 所以分6:6的話, 還未知道不同的一枚是在那一邊.

two-split的方法: 如果已知道不同的一枚是較輕或較重才會有用. 所以分6:6的話, 還未知道不同的一枚是在那一邊.

謝提醒，我再想想

trial 2:

12->4,4,4; pick any two groups

I think it should be case by case (two cases; equal or unequal)

the trivial one should be easier: if equal

then pick 3 marbles from the remaining group, pick any one marble from the 8 marbles as standard

then 2 - 2 (with standard, WLOG)

1. if equal, then the remaining (unused) one; make a lift with standard and we can know whether it is lighter or heavier than others;

2. if unequal, see the inbalance; assume left side is lighter (WLOG, again)

then one on the left is lighter; or the one on the right (not standard) is heavier;

try 1-1 on the left; I think the remaining solution for this case should be trivial.


[拋磚引玉，will explain the remaining cases; if the explanation above is not wrong XD]

本篇文章已被 XxEDxX 於 Aug 23 2015, 11:03 編輯過

two-split的方法: 如果已知道不同的一枚是較輕或較重才會有用. 所以分6:6的話, 還未知道不同的一枚是在那一邊.

謝提醒，我再想想

好。

原題加了：不同的一枚是較輕或較重?

這樣就會減少不同的方式。我第一次看到的version只找不同的一枚所以我的方法有些少出入

trial 2:

12->4,4,4; pick any two groups

I think it should be case by case (two cases; equal or unequal)

the trivial one should be easier: if equal

then pick 3 from the remaining group, pick any one marble from the 8 marbles as standard

then 2 - 2 (with standard, WLOG)

1. if equal, then the remaining (unused) one; make a lift with standard and we can know whether it is lighter or heavier than others;

2. if unequal, see the inbalance; assume left side is lighter (WLOG, again)

then one on the left is lighter; or the one on the right (not standard) is heavier;

try 1-1 on the left; I think the remaining solution for this case should be trivial.


[拋磚引玉，will explain the remaining cases; if the explanation above is not wrong XD]

請繼續

[trial 2: cont]

if after the first lift, unequal;

then mark the marbles as 1,2,3,4;5,6,7,8 (remaining as 9,10,11,12) [just for simpler explanation...]

WLOG, assume left is lighter;

then 3,4,9:1,2,5 (put 6,7,8 aside, will deal with them later)

case by case again:

if balance, then try 6,7,8 similar as the last step before;

if not balance, then...

@if the left is still lighter: then one of 3 or 4 is lighter; lift them and find the spy;

@if the right is lighter: then one of 1 or 2 is lighter; lift them and find the spy;


[please correct me for any mistakes...]

I didn't read ED's solution

If mine is redundant , just tell me n ignore this
So here we go.

Mark 1-12 in sequence

1st :
1234 vs 5678
Two possible result ,
same weight (go to A)or difference ( go to B ),

2nd-A :
9,10 vs 11,12 and follow with 3rd : 9,11 vs 10,12

2nd-B:
1256vs 3478 and follow with 3rd : 1357 vs 2468

That's it.

I just read ur solution.

I assumed u r right
Soooooooooo, Sry for my poor comprehension.


I don't really get the following .


(i)
1st : 1234 vs 5678 , result : equal .
2nd : 39 vs 10,11 , result : 10,11 lighter.

Now either 9 is heavier or 10,11 is lighter.
With one more trial now ,from ur solution , I can't tell excatly which ball is lighter/heavier .

(ii)
1st : 1234 vs 5678 , result : not equal
2nd : 349 vs 125 , result : equal

Now, with one more trial ....
Once again I can't excatly tell

Please advise.

I have thought around your solution.

If according to your solution we have three times (left:heavier), can you tell me which marble is different? And, is it lighter or heavier than others?

I think your answer looks simpler, but it seems unable to cover all possibilities.

I just read ur solution.

I assumed u r right
Soooooooooo, Sry for my poor comprehension.


I don't really get the following .


(i)
1st : 1234 vs 5678 , result : equal .
2nd : 39 vs 10,11 , result : 10,11 lighter.

Now either 9 is heavier or 10,11 is lighter.
With one more trial now ,from ur solution , I can't tell excatly which ball is lighter/heavier .

(ii)
1st : 1234 vs 5678 , result : not equal
2nd : 349 vs 125 , result : equal

Now, with one more trial ....
Once again I can't excatly tell

Please advise.

Maybe I write my solution unclearly, so that you seem to misunderstand my solution.

Let me answer your cases one by one.

***

For your case 1:

I wrote: "the trivial one should be easier: if equal

then pick 3 from the remaining group, pick any one marble from the 8 marbles as standard"

So, if 1234:5678 is equal,

then

You wrote: "2nd : 39 vs 10,11 , result : 10,11 lighter." is not my solution.

***

For your case 2:

You wrote: "1st : 1234 vs 5678 , result : not equal
2nd : 349 vs 125 , result : equal

Now, with one more trial ....
Once again I can't excatly tell"

You can't exactly tell, since you have one more trial

Then we have 6,7,8 left, with one more trial. Please see my Part 1, last step.

That's it.


Thanks for your reply.

"pick 3 from the remaining group"

For this I mean pick 3 marbles. Sorry for any possible misinterpretation.

Edit: I will insert the word "marbles" in my previous answer.

本篇文章已被 XxEDxX 於 Aug 23 2015, 11:02 編輯過

I have thought around your solution.

If according to your solution we have three times (left:heavier), can you tell me which marble is different? And, is it lighter or heavier than others?

I think your answer looks simpler, but it seems unable to cover all possibilities.

For simpler argument,

After your first step, if it is unequal, then you have 8 marbles to be considered.

2-step bisection method is not enough to pick the different one and determine whether it is lighter or heavier.

You need one more step, so you totally need 4 steps for your solution.

Haha i was just too confident wif my 2mins answer ,
To a point that I couldn't wait for pearltea's confirmation n google'd da answer.

I guess both of us didnt hit the bell yet.
( damn my arrogant , no more chance for me ;p)

Gdluck ED, enjoy the fun of getting closer to the answer.

Maybe urs can be an alternative answer,
But my poor comprehension seems still can't get me to the agree-side with ya solution.

本篇文章已被 Caesar 於 Aug 23 2015, 11:07 編輯過

Then please tell me where did I miss the point, thanks.

You can directly point it out.

Then please tell me where did I miss the point, thanks.

You can directly point it out.

Hey relax.

As I said I'm sorry for my poor comprehension.

No offence it's truly my fault. I honestly mean it.

If u said I get u wrong ,
I guess I basically can't understand ur solution, then how could I point it out ?

From the so-called model answer I read, it's totally difference with both of us .
As I said maybe urs can be an alternative answer, so dun be mad, it's just my comprehension fails.

Then please tell me where did I miss the point, thanks.

You can directly point it out.

Hey relax.

As I said I'm sorry for my poor comprehension.

No offence it's truly my fault. I honestly mean it.

If u said I get u wrong ,
I guess I basically can't understand ur solution, then how could I point it out ?

From the so-called model answer I read, it's totally difference with both of us .
As I said maybe urs can be an alternative answer, so dun be mad, it's just my comprehension fails.

Haha, don't get me wrong. I didn't get mad. Relax, probably I have to insert some evilgrins!!

For your case 1, if you read my solution again, I said "pick 3 marbles from the remaining group". I hope you get what I mean, or I hope what I edit can make you understand my point better.

For your case 2, you have one more step. It is enough for picking the different one from the 3 marbles left.

Hey I'm dumb. ( yea sry)

For my case (ii) ,
I can't point it out really.

1st : 1234 vs 5678 , result : not equal
2nd : 349 vs 125 , result : equal

Now ,we all know 678 is the defective group now .

Please advise a detailed solution on how to figure out which one is a lighter/heavier with a final trial.
This is my question 2 hours ago, and I still can't point it out.

Oh please , I know I'm dumb.

本篇文章已被 Caesar 於 Aug 23 2015, 11:32 編輯過

what is your unequal in the first step?

It can give you some idea for the third step bro