Given n > 1 items and a two pan balance scale with no weights, determine the lightest and the heaviest items in $\lceil 3n/2 \rceil − 2$ weighings. I tried splitting down the middle and picking one side over the other given some condition, but I'm not able to properly define the conditions.
$\begingroup$
$\endgroup$
5
-
$\begingroup$ Welcome to Puzzling.SE! This looks like a puzzle you copied from somewhere. Can you please cite the source of this puzzle? $\endgroup$– Wais KamalCommented Oct 22, 2018 at 6:30
-
$\begingroup$ I'm actually writing this from a puzzle they gave in class. I tried to find other online sources that have this problem, and there are similar ones, but I couldn't find this exact one. If you find a source, I'd be happy to refer it. $\endgroup$– user53357Commented Oct 22, 2018 at 6:32
-
$\begingroup$ This is not allowed here. You must have permission to post this puzzle here. It is unfair to post a competition puzzle and get answers. Put in another way this is cheating. $\endgroup$– Wais KamalCommented Oct 22, 2018 at 6:36
-
$\begingroup$ This is not from a competition or any such thing, it's just an interesting puzzle to solve and it's general knowledge. Not like it's a competition problem in which case it would be jepordizing everyone equally... $\endgroup$– user53357Commented Oct 22, 2018 at 6:38
-
2$\begingroup$ Those brackets look like they should be the ceiling function instead. (You cannot order three weights in 2.5 weighings.) $\endgroup$– BassCommented Oct 22, 2018 at 8:34
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
A simple way to find the heaviest object is to compare two object keep only the heaviest and repeat until you compared all object.
Problem of this method : $n-1$ comparison needed for the heaviest (and as much for the lightest).
However to meet your bound only a small improvement is needed.
Hint 1:
Divide and conquer
Hint 2:
Be clever when dividing
Hint 3:
$n/2$ comparison is clever enough ;)
Hint 4:
$$3n/2-2 = n/2+(n/2-1)+(n/2-1)$$
-
$\begingroup$ Hmmm, I was thinking something along the lines of dividing in the middle, and then comparing one element on the left and one on the right. Then, for the next comparison, whichever side had the smaller element, traverse one down on that side and take that element for the new comparison, but keep the same element as last time for the other side since it's the largest element seen so far. Is this the right idea? $\endgroup$– user53357Commented Oct 22, 2018 at 8:39