5
$\begingroup$

You are stuck in a room with 100 floor tiles, and a magic button which you can carry with you. There are three types of tiles: real, fake and nopey. There are at most 49 fake tiles, and there is at least one real tile. To give a clue on the types of some tiles, you can stand on one tile and press the magic button, then stand on another tile and press the magic button again. That counts as one move. Moves are not subdivided up further.

After that, the following will happen.

  1. If the first tile is real, you will hear a beep if the second tile is fake, else nothing.
  2. If the first tile is fake, you will hear either a beep or nothing randomly, with a 50% chance of either, no matter what the second tile is.
  3. If the first tile is nopey, you will hear nothing, no matter what the second tile is.

Your goal is to find a tile that is not fake. If you find one, you can jump on that tile three times. If it is not fake, you can leave the room. But if it is fake, you will be stuck in the room forever.

Question: How can you successfully find a non-fake tile (real or nopey), in as few moves as possible?

$\endgroup$
3
  • $\begingroup$ Are you looking for worst case behavior of the fakes(I believe that has no successful strategy) or for minimal statistical average? (assuming 50% beep chance of fakes?) $\endgroup$
    – Retudin
    Commented Jun 8 at 8:29
  • $\begingroup$ What happens if you jump three times on a fake tile? Can that be used as part of the strategy or is jumping on a tile three times completely irrelevant to the puzzle? $\endgroup$ Commented Jun 8 at 9:58
  • $\begingroup$ I've addressed this in my answer, but I think the inconsistency of the fake tile beeping takes away from the question more than it adds. A formulation where a fake-tile-first pair always behaves consistently is a bit more interesting, since it removes any "just try it a bunch of times" based strategy. $\endgroup$
    – kagami
    Commented Jun 13 at 16:41

1 Answer 1

7
$\begingroup$

I'll say that tile A "beeps" tile B if stepping on A first and then B produces a beep.

If we need to be perfectly confident that our choice is safe:

We must pick a target tile, and test it as the second tile with every other tile as the first. We then go back and retest every tile that dinged our target tile 12 times or until it doesn't ding. If it never flips to not dinging, we select a new target tile and repeat the process. We expect to find a target which was not dinged at least once by any other tile and can be certain that it is safe in an average of ~101 moves if there is one fake to ~230 moves if there are 49 fakes and 1 true. There are some minor tactical considerations, such as noting any fake tile and not revisiting it, but that doesn't affect the average case much. If we try every single target without success, we can go back and try dinging pair more times. Note that there is always a non-zero possibility that a fake tile behaves consistently within finite moves, so this doesn't guarantee we escape in finite moves.

If we need a strategy to escape with perfect confidence guaranteed to be achieved within finite moves:

It is impossible. If we are very, very unlucky, each pair with a fake tile first will behave exactly as it does the first time it was tested. We will then end up with a set of cliques as defined below. If we get a set that behave indistinguishably from one another as shown, then any algorithm that would identify one as the "true+nopey" clique would do the same for the fake+nopey cliques. Thus there is no guarantee we can escape in finite moves.

We define a "clique" of tiles as a set that has the following three properties:

1. No tile within the clique beeps any other tile in the clique

2. Every tile in the clique beeps either all or none of the tiles outside the clique

3. Contains 51 or more tiles

A clique is guaranteed to exist since the the set of nopey + true tiles satisfies all three conditions. If there is only one clique, then we would jump on any tile in it and escape.

There could also be cliques composed of Fake + Nopey, in which case the intersection of all cliques will be composed of nopeys if there are any tiles in that intersection. If so, we pick any tile in the intersection and escape.

But we can end up with a set of cliques where the intersection of all cliques is empty. I conjecture that in any such situation, there is no guaranteed escape as long as our bad luck holds, but below is an example with three cliques for which this is definitely the case.

The below figure has one true+nopey and two fake+nopeys cliques, where the behavior of each with respect to the others is indistinguishable. The fakes are divided into two types: sleeper fakes that behave like nopeys (they don't ding anyone) and imposter fakes that ding every tile outside of their clique.

enter image description here

For some example numbers that work, if |T| = |I_1| = |I_2| = 1; |N_0| = |S_1| = |S_2| = 12; and |N_1| = |N_2| = |S_12| = 20, we observe that each clique follows all the rules and appears to be identical in every way. We're short one tile, but we can randomly add one to N_0, S_1, or S_2, without it helping us out in any way. In such an arrangement we can never have better than a 2^-x chance of escaping in x moves.

Finally, we note that there is a better strategy than above in the case where we MUST make an attempt within finite N moves, and seek to minimize the possibility of error:

We simply pick a pair randomly and test it over and over until we hit some threshold of acceptable error, switching to a different pair if we observe inconsistent behavior. We then jump on the first of the pair that we've observed no inconsistency in. We'll expect to have begun testing a true/nopey first on move 4 on average, so we'll have something like a 2^-(N-5) chance of failure, which is much lower than the chance of the first strategy failing.

$\endgroup$
2
  • 1
    $\begingroup$ The parts of this answer should be reversed, as only the one without any error possible really answer the question. The other part (with acceptable minimal error) is a nice add to the discussion, but not an answer to this question, IMHO. $\endgroup$ Commented Jun 11 at 6:23
  • $\begingroup$ Agreed and edited, together with some back-of-the-envelope move estimates. Exact numbers would rely on some additional info about the distribution of the number of true and fake tiles. I think 12 attempts is optimal, but not 100% on that. $\endgroup$
    – kagami
    Commented Jun 11 at 12:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.