Problem 1154. Identify the heavier bag

Created by HARISANKAR PS

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?><w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>There are N=2^n bags of rice looking alike, N-1 of which have equal weight and one is slightly heavier. The weighing balance is of unlimited capacity. Using the balance, the minimum number of weighing required to identify the heavier bag is?</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Solve

Solution Stats

99 Solutions
45 Solvers

Last Solution submitted on Jul 24, 2021

Last 200 Solutions

Problem Comments

4 Comments

4 Comments

Show 1 older comment

@bmtran (Bryant Tran) on 31 Dec 2012

I think it only takes 5 weighings when N=128. Am I incorrect?

Alfonso Nieto-Castanon on 31 Dec 2012

agree 5 weighing for N=128 (worst case scenario you reduce to 43 15 5 2 1 after each consecutive weighing)

trekker on 2 Jan 2013

the last test case provided by the author is wrong: should be 5 since log(128)/log(3) < 5.

Rafael S.T. Vieira on 2 Sep 2020

The problem is that the author do not specify an strategy. And as mentioned, dividing by 3 yields a better strategy than 6 weightings for 128. But, my guess is that the author counted the number of divisions instead of the number of weightings 128->[42 42 43] -> [14 14 14; 14 14 15]->[5 5 4; 5 5 5]->[2 2 0; 2 2 1]->[1;2]->1.

Solution Comments

Solution 183475

1 Comment

1 Comment

Dan on 8 Jan 2013

Correct the test suite

Problem Recent Solvers45

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 1154. Identify the heavier bag

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers45

Suggested Problems

More from this Author5

Problem Tags

Community Treasure Hunt

Problem 1154. Identify the heavier bag

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers45

Suggested Problems

More from this Author5

Problem Tags

Community Treasure Hunt

Players