Different weights

Logic Level 3

Suppose that there are infinitely many stones, such that for each positive integer, there are infinitely many stones having that weight in grams.

Using his hands, Dan can distinguish between two stones if their weight difference is 4 or more grams, but is unable to determine their exact weight difference.

Does there exist an integer $m$ , such that Dan can find 2 stones whose weight difference is exactly $m$ grams? If yes, what is the minimum value of $m$ ?

Note: Assume that in a finite amount of time, Dan can compare every possible pair of stones.

Yes, 0 Yes, 1 Yes, 2 Yes, 3 Yes, 4 Yes, 5 No, this can't be done for any given exact weight difference

1 solution

Sahil Bansal
Jun 13, 2017

First suppose the person chooses a stone weighing x gram. Now he selects many other stones which seems to be same as this one. This would consist of all stones weighing x-3 to x+3 grams. Now from this new group person choose pairs of stones and checks whether he is able to distinguish between them or not. When he is able to distinguish between them, he places stone with greater weight and lesser weight separately. Now the stones with lesser weight would consist of weights x-3,x-2 and x-1, and greater weight x+1,x+2, and x+3.Now in next step he takes out those stones from one group which can be distinguished from all the stones in the other group. This would consist of stones weighing x-3 if taken from group with lesser weight and x+3 if taken from the other. Hence all such stones can be separated out.

I am not quite sure what you are saying.

Suppose that the stones all have integer weights 1, 2, 3. I pick a stone, which happens to have a weight of 2. I find stones which seem the same, which is all of them. I check every pair of stones, and I'm unable to distinguish any of them. What do I do with those that are of "apparent same weight"?

How can I tell which stones have weights of 1, 2, 3? I think we cannot do that with individual comparisons.

Calvin Lin Staff - 3 years, 12 months ago

We don't have to pick a stone of given weight but we have to pick two stones with given weight difference. So for my above solution to be applicable, we can start with some stone having higher weight.

Sahil Bansal - 3 years, 12 months ago

Alright, once again, supposed that the stones all have integer weights 1, 2, and 3. Can you explain how your solution proceeds?

Or perhaps I am misunderstanding your question. Do you mean to say that there are infinitely many stones of each integer weight? I interpreted it as there are infinitely many stones, each of which have integer weights, but we are not guaranteed that there is a stone of a given weight (like 4, 5, 6, ...).

Calvin Lin Staff - 3 years, 12 months ago

@Calvin Lin – In this question,I mean to say that there are infinitely many stones of all integer weights.

Sahil Bansal - 3 years, 12 months ago

@Sahil Bansal – K, I've rephrased the question. Can you check that it agrees with what you want?

However, my concern still stands. When you say "First suppose the person chooses a stone weighing x gram. Now he selects many other stones which seem to be same as this one.", there is no guarantee that he will find at least one stone of weight x-3, at least one stone of weight x-2, etc. After finitely many tries, he might unluckily only pick out stones of weight $x$ . We might be able to get around this by allowing for "(uncountably) infinitely many comparisons can be done in a finite amount of time", and make him check every stone against the original one. Some clarity about this would help the problem.

(Also, you would want to ensure that $x \geq 4$ , but that's easily dealt with.)

Calvin Lin Staff - 3 years, 12 months ago

@Calvin Lin – Ok,the question has the same meaning. That problem can be somewhat cleared if we state in the question that the number of stones for given weight are finite in number which is known to person,so that he knows when to stop the comparison. Also ,I have changed my solution accordingly.

Sahil Bansal - 3 years, 12 months ago

@Sahil Bansal – Making the number of stones for a given weight finite would not really help. For example, he might unluckily only compare with the infinitely many stones that weight x+5 or more. Ultimately, he has to be able to compare every pair of stones (in a finite amount of time).

Note: For completeness, in your solution, you are missing out what to do with those stones that cannot be compared. You should mention that these stones all have weight $x$ , and hence he can find 2 stones that have a weight difference of 0.

Calvin Lin Staff - 3 years, 12 months ago

@Calvin Lin – Actually, I didn't think of this.

Sahil Bansal - 3 years, 12 months ago

Different weights

1 solution

0 pending reports