ONLY 8 STEPS MAX, AND NEARLY ALWAYS 7

The trick here is to use intersecting sets for the weighing process.

Weigh two groups of 33. As usual, two possibilities, that they weight the same or they differ.

Let’s look at the case where they differ.

In that case, you know the odd one out is one of these 66 pumpkins.

Choose 16 from each of the two groups of 33, and weigh that combined set of 32.

If it is equal in average pumpkin weight to either of the original groups of 33, then you know that it doesn’t contain the odd one out (because 32 with the odd pumpkin can’t have the same average weight as 33 with the odd pumpkin).

At this stage you have divided your 66 into four sets of

• a 16,
• b 17,
• c 16,
• d 17

You know the weight of a + b, and of c+d from the first two weighings. You now know the weight of of a + c by your third weighing, and (by subtraction) you also know the weight of b + d.

Also, if b+d is equal in average pumpkin weight to either of the original 33, you know the odd one out isn’t in it, by the same kind of reasoning as before - a group of 34 with the odd pumpkin can’t have the same average weight as a group of 33 with it.

So that’s only three weighings so far.

Here let’s just write [math]=_{p}[/math] to mean “equal in average pumpkin weight ”.

So then, if a+ c [math]=_{p}[/math] a+b. then the pumpkin is in d

If a + c [math]=_{p}[/math] c + d then the pumpkin is in b

If b+d[math] [/math][math]=_{p} [/math]a+b the pumpkin is in c

and if b + d [math]=_{p} [/math] c + d the pumpkin is in a

So after three weighings you are down to a set of 17 in the worst case, and at this point you also know the weight of a standard pumpkin, so you know if it is heavier or lighter than normal.

Now weigh 8 of those 17, and in the worst case it’s in the remaining 9

weigh 4, in worst case it’s in remaining 5

weigh 2, in worst case in remaining 3

weigh one of those and worst case, remaining 2

weigh one of those and you’ve got it.

So that’s 8 weighings in total though most often you’ll manage in 7.

What though if it the first two groups of 33 weigh the same?

Well in that case,after two weighings, you know it is in the final group of 34 but you don’t know if it is heavier or lighter. But you know the weight of a standard pumpkin from your first two measurements.

So now weigh 17 of the ones left. Either it weighs the same as 17 standard pumkips, so it’s in the remaining 17 or it is different. Either way, as before we are down to 17 pumpkins after three weighings.

Rest as before.

So, my answer is that you can always do it in 8.

Fastest solution with this method

If you get down to 16 in three weighings you will get there in 4 more steps. You then weigh 8, 4, 2 and 1 and you’ve got it.

It’s the same at any point along the process, even if you get down to 5 pumpkins and find it is in 2 of them instead of 3, or you are down to 3 and when you weigh one of those it turns out to be the odd pumpkin..

So, nearly always you get there in 7 weighings, but if you are unlucky, then it takes 8.

PROBABILITY OF GETTING THERE IN 7 STEPS WITH THIS METHOD

The easiest way to get the answer is to work out the probability of taking 8 steps.

It will take 8 steps if first of all it is in any of the four groups of 17 after three weighings.

Then in each group of 17 it has to be in the 2 left over after you weigh 8, 4, 2 and then 1 of them.

So that makes a total of 8 worst case pumpkin positions so the probability of it taking 8 steps is 8% and you are 92% certain of finding it with 7 weighings.

(Thanks to comments for putting me right on the number of pumpkins, and this is Dave Buchfuhrer’s suggestion for an easier way to find the probabilities)

Is this optimal or is there any solution that can find it in at most 8 steps with a higher than 92% chance of finding it in 7 steps, using any method?

UPDATE: OPTIMAL SOLUTION OF 7 STEPS GUARANTEED, 6 STEPS IN 28% OF THE TIME

Dave Buchfuhrer has used the same approach of intersecting steps, in an ingenious way and got it right down to 7 steps maximum and often times 6 steps, and proved that it is optimal. See Dave Buchfuhrer's answer to I have 99 pumpkins that all weigh the same and 1 weighs different, what is the minimum number of uses of a digital scale to locate the odd pumpkin?