Maybe I am misunderstanding but the question says NONE of the labels are correct right? If so, I was thinking of it this way. If you press coke, it can only be random or Pepsi (.25?), if you press Pepsi, it can only be coke or random (.75?), if you press random it can only be coke or Pepsi (.5) (oddly this is still random 50/50 :) ). So the optimal on first try would be to press Pepsi?

You press random and taste, lets say it comes out pepsi. This means that this button has to be the pepsi button because if it was the random button then the label would be correct, like you mentioned. This settles the pepsi button.

Regarding the other two buttons, one is random and the other is coke but their labels are pepsi and coke, giving us only two possible (order-independent) states which I'll illustrate with the format drink(label)/drink(label):

Coke(Pepsi)/Random(coke)

Coke(Coke)/Random(Pepsi)

The second case is invalid because it would require for the coke label to be correct, leaving only one possible case: the button labeled pepsi would have to give out coke.

Both methods are fine.

Let's say you press the Random button first. If it is actually the Coke button, you get a Coke, and you can stop. Otherwise it's actually the Pepsi button, then you press the Pepsi button since that is actually the Coke button. So you get a Coke in one or two button presses.

Basically there are only two permutations of buttons possible, because all other permutations are disqualified by the "not the same as before" rule. Since the goal is specifically to get a Coke in the fewest button presses, you just have to not start with the Coke button since that is the least likely to produce a Coke.

And if that first press fails, the Pepsi label must be the Random button, so you should press the button with the Random label as it is guaranteed to be the Coke button.

This was actually my first-glance answer. Consider that the Pepsi label can't possibly be the Pepsi button, but the other two can.

No, you an apply more reasoning to it up front. If "none of them are correct" then you press 'surprise' first, and you either get the drink you wanted that time, or on your next guess.

If the labels are all incorrect, you would want to start with the one labelled with the drink you don't want. This would give you an initial chance of 75% of getting the drink you do want (.5 + .25). If you don't get it on the first press, then you would press the one labelled "random", as this would 100% be the drink that you do want.

I worked this out for the version of the problem on the linked pages but I must have misread the one posted here.

In Monty Hall Game you improve your odds to be 2/3, not 1/2. If you think the staying door wins 1/3 of the time and the switching door 2/3, where is the car located in the 1/6 missing?