easier and harder?

Question

There have been a number of these questions out here, so I just wanted to give people a chance to get some points.

Easier: If you have n scales (balances) and can use each once. And you have a bunch of rocks that look the same but one has a piece of gold in it and weighs more. What is the maximum number of rocks you can have and still find the gold in n weighs?

Harder: If you don't know if the gold weighs more or less, what is the maximum number of rocks that you can have and still be able to find the gold in n weighs?

And I want proof that these are the maximums.

School isn't out for me!!!!!!

I will give some lower bounds. If you have 3 scales, you can find the gold from 20 pieces of rocks (if you know the gold is heavier), and 10 pieces (if you don't know which is heavier).

You may be able to do more rocks with 3 scales, but I don't want to give you the answer . .

Pascal, I believe your "hardier" equation is wrong:

If there is 1 scale, you can only have 1 nut (yours suggests you can have 2 nuts).

If there are 2 scales, you can only (I believe) have 3 nuts, yours gives 5.

And I think you can only have 12 for 3 scales, not 14.

Answer 1

Easier: 3^n. The reason is that whatever scheme you use for determining which rocks to put on the scale, the only information you have about the gold is a sequence of n weighings. Thus, to positively identify the gold, you must have each possible sequence of weighings consistent with at most 1 rock containing the gold. Now, each rock must be assigned to some sequence of results based on how the scales will react if that rock contains the gold under your weighing scheme, and you cannot assign R rocks to S sequences without assigning more than one rock to the same sequence unless R≤S. Thus the maximum number of rocks you can distinctly identify is the maximun number of distinct sequences of results you can get from n scales. Each weighing can only give you one of three results - the scale tips to the left, the scale tips to the right, or the scale balances. This gives you a maximum of 3^n different sequences of results. Thus you can identify the gold in at most 3^n different rocks. Q.E.D.

Harder: (3^n+1)/2. Again you must assign rocks to sequences, but in this case, all but one rock must be assigned to at least two distinct sequences. The reason for this is as follows: Suppose the rock containing the gold is on the scale. Then if the gold is lighter, the scale will tip one way, and if the gold is heavier, the scale will tip the other. Thus, unless the rock's position depends in some way on its weight, both the sequence containing the scale tipping to the right on that weighing and the scale tipping to the left on that weighing are consistent with that rock containing the gold - thus, the number of sequences that a rock is consistent with is multiplied by two every time a rock is weighed with no information (explicit or implicit) about the gold's weight. Since prior to the first time the rock containing the gold is weighed, there can be no information on the gold's weight, this must happen at least once, provided that the rock containing the gold is weighed at least once. If the rock containing the gold is never weighed, it will yeild the sequence {0,0,0...} (where 0 means the scale balances). There is only one such sequence, and only one rock can be assigned to it, thus every rock except one must be assigned two sequences, and that rock still must be assigned one sequence. Therefore, if r is the number of rocks, 2(r-1) + 1 ≤ 3^n. Thus the maximum number of rocks that can be distinguished is (3^n+1)/2. Q.E.D.

Answer 2

It depends on the chain on which the scale hangs.

Answer 3

gold weights thousands of pounds and takes alot of strangth to hold.

Answer 4

School's OUT FOR SUMMER!!!!!!!!!!!!!!!