superprismatic 11 Posted May 3, 2011 Report Share Posted May 3, 2011 Suppose you see before you 10 identical-looking blocks. No two of these blocks weigh the same. Your task is to sort the blocks according to weight using the fewest number of weighings. You get to chose which scale you would like to use for all the weighings. The scales are labeled S2, S3, S4, S5, S6, S7, S8, and S9. Once you choose a scale, you must use it exclusively. If you choose scale SN (where N is between 2 and 9 inclusive), then it will only weigh a subset containing precisely N blocks. The scale will then sort the N blocks according to weight and report this weight- ordering to you. What value of N will allow you to determine the weight-ordering of all 10 blocks in the fewest number of weighings? Quote Link to post Share on other sites

0 Guest Posted May 3, 2011 Report Share Posted May 3, 2011 s7 s8 or s9 Quote Link to post Share on other sites

0 superprismatic 11 Posted May 3, 2011 Author Report Share Posted May 3, 2011 s7 s8 or s9 Please explain. Quote Link to post Share on other sites

0 Guest Posted May 3, 2011 Report Share Posted May 3, 2011 pertand all the blocks are labled 1-10 with S7 weigh 1-7. then weigh 8-10 with the four heaviest blocks of 1-7 lets pertend 4-7.If 8 9 or 10 are the lightest out of those seven weigh 1 2 and 3 with the lightest four from 4-7 then you should have enough information to put them in order for S8 and S9 it is pretty much the same thing Quote Link to post Share on other sites

0 Guest Posted May 3, 2011 Report Share Posted May 3, 2011 sorry it should say 4-10 insted of 4-7 Quote Link to post Share on other sites

0 Guest Posted May 3, 2011 Report Share Posted May 3, 2011 the second time not the first Quote Link to post Share on other sites

0 Guest Posted May 4, 2011 Report Share Posted May 4, 2011 S9 In first go, I'd weigh any 9 weights. Let's say they are arranged in order W1 through W9 post weighing (W1 is lightest, W9 is heaviest). Now, I can remove W1 and put the unknown weight W instead, in weighing number 2. If it is more than any other weight on the scale then no further weighing is required, else I'd remove W9 and put W1 again to get the correct order in third weighing. So, weighing required are minimum 2 and maximum 3. Quote Link to post Share on other sites

0 bushindo 14 Posted May 4, 2011 Report Share Posted May 4, 2011 (edited) Suppose you see before you 10 identical-looking blocks. No two of these blocks weigh the same. Your task is to sort the blocks according to weight using the fewest number of weighings. You get to chose which scale you would like to use for all the weighings. The scales are labeled S2, S3, S4, S5, S6, S7, S8, and S9. Once you choose a scale, you must use it exclusively. If you choose scale SN (where N is between 2 and 9 inclusive), then it will only weigh a subset containing precisely N blocks. The scale will then sort the N blocks according to weight and report this weight- ordering to you. What value of N will allow you to determine the weight-ordering of all 10 blocks in the fewest number of weighings? Maybe i'm missing something somewhere... S9 will result in the fewest weighings. Notice that S9 can duplicate the functionality of any SN, where N<9. For instance, suppose we want to use S9 to weigh 7 objects. Simply put the 7 desired objects on S9 along with 2 other objects (let's call them placeholders), and then discard the rank of the 2 placeholders in the final ranking. So, if S_i for some i < 9 results in the fewest number of weighings, then S9 can duplicate the function of S_i and hence possesses that property too. Edited May 4, 2011 by bushindo Quote Link to post Share on other sites

0 Guest Posted May 4, 2011 Report Share Posted May 4, 2011 Maybe i'm missing something somewhere... S9 will result in the fewest weighings. Notice that S9 can duplicate the functionality of any SN, where N<9. For instance, suppose we want to use S9 to weigh 7 objects. Simply put the 7 desired objects on S9 along with 2 other objects (let's call them placeholders), and then discard the rank of the 2 placeholders in the final ranking. So, if S_i for some i < 9 results in the fewest number of weighings, then S9 can duplicate the function of S_i and hence possesses that property too. However, if the assumption is that you are not able to determine the previous order of the block, once the scale rearranges them; then this kind of rank discarding wont be feasible. Quote Link to post Share on other sites

0 Guest Posted May 4, 2011 Report Share Posted May 4, 2011 its s8 scale and minimum weighings is 3 weigh 1 first weigh 8 then remove the first 1(asuming the first has highest weight) and add one more brick. weigh 2 again remove the first 1 and add one more brick weigh 3 remove the last 2 bricks maintaining the order and add those first 2 bricks done!!! the bricks after 3 weigh add it to the remaining 2 bricks all arranged in descending order Quote Link to post Share on other sites

0 Guest Posted May 4, 2011 Report Share Posted May 4, 2011 opps sry... its s9 no of weighings is 3 (with 8 its 4) weigh 1 first weigh 9 weigh 2 then remove the first 1(asuming the first has highest weight) and add one more brick. weigh 3 remove the last 1 and add first brick removed from weigh 2 done!!! the bricks after 3 weigh add it to the remaining last 1 brick all arranged in descending order Quote Link to post Share on other sites

0 superprismatic 11 Posted May 4, 2011 Author Report Share Posted May 4, 2011 Maybe i'm missing something somewhere... S9 will result in the fewest weighings. Notice that S9 can duplicate the functionality of any SN, where N<9. For instance, suppose we want to use S9 to weigh 7 objects. Simply put the 7 desired objects on S9 along with 2 other objects (let's call them placeholders), and then discard the rank of the 2 placeholders in the final ranking. So, if S_i for some i < 9 results in the fewest number of weighings, then S9 can duplicate the function of S_i and hence possesses that property too. Your response is what I was trying to elicit with this question. I didn't ask for the actual weighing scheme, although that's what I got in most cases. I don't suppose this was a very good problem when responses start with a "Am I missing something?" prelude. That's the way the ball bounces! I didn't successfully hide the underlying simple principle here. Quote Link to post Share on other sites

0 Guest Posted May 4, 2011 Report Share Posted May 4, 2011 However, if the assumption is that you are not able to determine the previous order of the block, once the scale rearranges them; then this kind of rank discarding wont be feasible. A place holder is distinguishable from a block, regardless of original order. It is a placeholder not a block afterall. You are simply padding the itemcount so you can use the larger scale. Regardless: If you can't distinguish the blocks by any means other than their weight, then the minimum number of weights is 3. You need a scale that integrate the remaining blocks ® after the first weighing into a fully sorted order. So your scale must be able to handle R + W/2 + 1. So the remaining blocks must be less than half the number of weighed blocks for any weighing: R < W/2. The three scales that fit this are S7,S8,S9. If then use KlueMaster's pattern then: weigh, split off lightest then weigh the remainder with ordered. Then re-weigh the split-off lightest with lightest of the reweighed, append the heavy ordered R_{2}, and your done. Quote Link to post Share on other sites

0 Guest Posted May 5, 2011 Report Share Posted May 5, 2011 S6, S7, S8 or S9 to Quote Link to post Share on other sites

0 Guest Posted May 5, 2011 Report Share Posted May 5, 2011 (edited) S6, S7, S8 or S9 to establish the order of the blocks in the minimum of 3 weighings, though S9 may be considered the best to use, as it may be easier to deduce the order of the weights. The steps for a procedure for weighing N blocks with S7, S8 and S9 may be: (1) Weigh N blocks. (2) Weigh the remaining (10 - N) blocks + (N - (10 - N)) heaviest of step 1. If the order can not yet be deduced, (3) Weigh N blocks that are the lightest. The order of the blocks should now be known (deducible). A procedure for weighing N blocks with S6 requires a different approach, one such procedure may be: (1) Weigh 6 blocks. (2) Weigh the remaining 4 blocks + the heaviest and third heaviest of step 1. If the order can yet be deduced, deduce the blocks that must be weighed against each other to find the order, then (3) Weigh the blocks that must be weighed against each other in order to find the order. The order of the blocks should now be known (deducible) Using S2, S3, S4, or S5 would require more than 3 weighings to be certain of having the correct order of weights of the ten blocks. Edited May 5, 2011 by Dej Mar Quote Link to post Share on other sites

## Question

## superprismatic 11

Suppose you see before you 10 identical-looking

blocks. No two of these blocks weigh the same.

Your task is to sort the blocks according to

weight using the fewest number of weighings.

You get to chose which scale you would like to

use for all the weighings. The scales are

labeled S2, S3, S4, S5, S6, S7, S8, and S9.

Once you choose a scale, you must use it

exclusively. If you choose scale SN (where

N is between 2 and 9 inclusive), then it will

only weigh a subset containing precisely N

blocks. The scale will then sort the N blocks

according to weight and report this weight-

ordering to you. What value of N will allow

you to determine the weight-ordering of all

10 blocks in the fewest number of weighings?

## Link to post

## Share on other sites

## 14 answers to this question

## Recommended Posts

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.