tag:blogger.com,1999:blog-4115025577315673827.post7476822447312710715..comments2020-05-20T14:21:54.596+05:30Comments on CSE Blog - quant, math, computer science puzzles: Puzzle: Working ComputerPratik Poddarhttp://www.blogger.com/profile/11577606981573330954noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-4115025577315673827.post-82272584834587188912014-06-23T09:28:49.509+05:302014-06-23T09:28:49.509+05:30"Fix one of them" - Its not allowed!"Fix one of them" - Its not allowed!<br />Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-80298735420569646682014-01-05T19:51:36.143+05:302014-01-05T19:51:36.143+05:30Say, total m computers are there. Fix one of them ...Say, total m computers are there. Fix one of them (say, the m-th one). Ask each computer 1,2,3,4,........m (so, we ask the fixed computer too : this is allowed since the question mentions that any computer can tell about any computer} about this fixed computer.. Say k say 'fine' and m-1-k say 'damaged'. Thus we get two groups of computers: G1={all computers which say m-th one is fine} and G2= {all computers which say m-th one is damaged}. Then those computers are fine which belong to the group having more members (since, less than half are damaged)... i guess this worksAnonymoushttps://www.blogger.com/profile/09402444319712118726noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-81971362740552112852009-08-26T16:27:14.481+05:302009-08-26T16:27:14.481+05:30@jaadu...
great solution...
seems correct to me.....@jaadu...<br />great solution...<br /><br />seems correct to me.... :)Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-85372137653398918352009-08-24T08:30:01.752+05:302009-08-24T08:30:01.752+05:30here is a solution in which in N-1 computers we wo...here is a solution in which in N-1 computers we would be able to find a working computer.<br />we will try to find a chain of computer (i1,i2,i3....im) such that each ij is queried about i(j+1) and answer is correct.Note that if such chain contains a working computer then last computer in the chain would be working.so query computer 1 about 2.If answer is yes query computer 2 about 3.continue till answer is correct.suppose at some point computer i when queried about computer j says wrong,in that case remove computer i and j from the chain,and continue query process by querying predecessor of i about successor of j.here note that when we remove computer i and j from the chain at-least one of them must be faulty.here for each computer accept the first one we are querying once.hence N-1 comparison in worst case.think about the best case using this algorithm.Unknownhttps://www.blogger.com/profile/17923995765018410791noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-21456333164694936682009-08-23T21:03:52.696+05:302009-08-23T21:03:52.696+05:30@Jaadu...
I am not able to prove that this is mini...@Jaadu...<br />I am not able to prove that this is minimum.. All I am claiming is that I can always get a solution in 2n checks.. <br /><br />Can someone suggest a better solution? or a proof that this is the best solution..?Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-69230103700155267262009-08-23T18:11:52.377+05:302009-08-23T18:11:52.377+05:30Isme yeh kahan prove hua ki 2k is the minimum numb...Isme yeh kahan prove hua ki 2k is the minimum number of query required,Unknownhttps://www.blogger.com/profile/17923995765018410791noreply@blogger.com