Problem 1154. Identify the heavier bag

Created by HARISANKAR PS

Solve Later

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?

Solve

Solution Stats

144 Solutions
56 Solvers

Last Solution submitted on Nov 12, 2024

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

Show comments

Problem Recent Solvers56

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 Solvers56

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 Solvers56

Suggested Problems

More from this Author5

Problem Tags

Community Treasure Hunt

Players