21
$\begingroup$

This is the follow up question to my previous question

You wake up and find yourself in a very strange room with a single door. You find a note on the ground surrounded by lots of cards:

There are 66 green and 66 blue door cards on the ground. If you put one blue and one green card into the slots next to the door, the door will open. If you insert two cards of the same color, you will lose a life! I won't tell you how many lives you have, but you will die if you lose all of them!

For most people, this could be completed easily. Unfortunately, you cannot distinguish the color of the cards because you are fully colorblind! Whoever put you there probably knows this. They undoubtedly gave you just enough lives for you to be certain you can get out - if you play their game optimally.

This time you need to put two green cards into the slot to open the door instead of one green and one blue.

so

How many tries do you need to guarantee you open the door?

$\endgroup$
1
  • $\begingroup$ I assume we get the cards back if we fail, right? $\endgroup$
    – Moacir
    Commented Jun 12, 2019 at 13:51

5 Answers 5

26
$\begingroup$

It can be done in

69 attempts at most (slight optimisation of athin's answer, but probably still not optimal)

Solution

First, number all the cards 1 to 132. Then compare 1-2, 3-4, etc. up to 125-126 (63 attempts in total). If none of them worked, each of the 63 tested pairs should contain at least 1 blue, so there are at least 63 blues in cards 1-126. That means that the remaining cards 127-132 should contain at most 3 blues and at least 3 greens.
Now, split the remaining 6 cards into 2 groups {127,128,129} and {130,131,132}. At least one of the groups should contain 2 greens (since there are at least 3 greens in 127-132). Now, just test all combinations inside the groups (127-128, 127-129, 128-129, 130-131, 130-132 and 131-132 - 6 attempts in total). At least one of them should work, since one of the group contains at least 2 greens.
Grand total: 63+6=69 attempts

$\endgroup$
3
  • 2
    $\begingroup$ well done, this is a bit more complicated answer than mine but it seems right to me :) $\endgroup$
    – Oray
    Commented Jun 11, 2019 at 10:58
  • $\begingroup$ Can you prove that this 69 is optimal ? $\endgroup$ Commented Mar 30, 2021 at 19:50
  • $\begingroup$ @HemantAgarwal There is another answer which proves that 69 is the lower bound. Since it's achievable, it must be optimal. $\endgroup$
    – trolley813
    Commented Mar 30, 2021 at 19:54
17
$\begingroup$

Also not sure whether this is optimal but I can do this in

$70$ tries.

First,

Make $66$ pairs from all cards and put each pair one by one.

In the worst case,

All pairs are not two greens. The only possible thing is that each pair is green-blue.

Finally,

Pick any two pairs. Try all $4$ possibilities by taking one card from the first pair and one from another pair. Therefore we need $66 + 4 = 70$ tries.

$\endgroup$
7
  • $\begingroup$ this is not optimal, but upvoted. $\endgroup$
    – Oray
    Commented Jun 11, 2019 at 10:34
  • 2
    $\begingroup$ You don't need +4 since you already tried one of the combos in the first round. Therefore 69 maximum tries. $\endgroup$
    – Paul Evans
    Commented Jun 12, 2019 at 14:56
  • 1
    $\begingroup$ @PaulEvans we still need +4 as actually there are 6 combinations and 2 are already tried, cmiiw. $\endgroup$
    – athin
    Commented Jun 12, 2019 at 15:43
  • 1
    $\begingroup$ Two of those combinations are right, since you have green + blue combinations, so 3 is enough, 66+(4<wrong combinations>-2<already tested>+1<right answer>)=69 $\endgroup$
    – Montolide
    Commented Jun 12, 2019 at 19:32
  • 2
    $\begingroup$ @Montolide Whoopsie, we need green-green to solve this puzzle instead of blue-green $\endgroup$
    – athin
    Commented Jun 12, 2019 at 21:53
15
$\begingroup$

I can prove a lower bound of

$69$ tries.

The first step is to notice that the question is equivalent to

finding an $132$-node graph $G$ with no independent set of size $\ge 66$.

The reason is:

1. If we have the graph $G$, then for each edge $(x,y)$ in $G$, we put the $x$-th and $y$-th card into the slot. If we failed then no edge has two green cards as its endpoint, so $66$ green cards induce an independent set of $G$.

and

2. If we have a strategy to win the game, then the strategy must be nonadaptive, since we don't gain any information from each failure to choose two green cards. That is, the strategy of each step is already determined before the game gets played. If the $i$-th step is to test card $a_i$ and card $b_i$, we insert edge $(a_i,b_i)$ into $G$. If $G$ has a size-$66$ independent set, our strategy would be invalid when this set of cards are green.

Then we observe

$G$ must contain an odd cycle. Because otherwise $G$ is a bipartite graph which always have an independent set of size $\ge \frac{132}{2}=66$.

and

If $G$ has $C$ connected components, then $G$ has at least $133-C$ edges. For an arbitrary graph $G'$, if it has $C'$ components and $V'$ vertices, then it has at least $V'-C'$ edges, so we infer that $G$ has at least $132-C$ edges. However as we demonstrated above, $G$ has a cycle, and deleting an edge from that cycle doesn't change the number of its components. So we conclude $G$ has $\ge (132-C)+1$ edges.

So there are a few cases. If

$C\ge 66$, then we can take any vertex from a component to form an independent set of size $C$. This is invalid;

If

$C\le 64$, then $G$ has $\ge 133-64=69$ edges;

If

$C=65$, then every component must be a clique: if some component is not a clique, we can take two vertices from it and one vertex from every other component and still form an independent set (of size $C+1$). Now let $a_1,a_2,\dots,a_{65}$ be the number of vertices in each component, then $\sum_{i=1}^{65}a_i=132$ and the number of edges is $E=\sum_{i=1}^{65}\frac{a_i(a_i-1)}{2}$. Even if we allow $a_i$'s be real numbers (instead of integers), the minimum of $E$ is reached when each $a_i=a=132/65$, and $E=65\cdot \frac{a(a-1)}{2}\approx 68.03$. Therefore $69$ edges are needed in this case. (We note that this corresponds to @trolley813's answer, and optimal integer solution is that each $a_i$ is $2$ except two of them are $3$.)

$\endgroup$
4
$\begingroup$

A completely sideways answer - but possibly only one try...

Here you need to cheat a little, and cause yourself some sort of injury to get some blood - smear some of that blood on one card, and then another - keep doing this until you find two that have different shades.

(see other answers for how many of them you may need to check, however if you keep one card and swap the other every time then that's 66 tries - every single card of one colour, and a single card of the other).

The red "filter" cannot restore invisible (to you) colour, but it can hide some of the colour that's already there, so allowing you to see a difference in shade between the two different coloured cards.

Of course, the fiendish person setting this trap may have already thought of this and ensured they used specific pigments that don't work with this filtering - but they might not want to reuse this trap if they come in and find it looks like a scene from a horror movie...

$\endgroup$
1
$\begingroup$

Not sure if this is optimal, but:

Take a set of 3 cards. Try the 3 combinations of pairs of cards (3 tries). If they all fail, at least 2 cards must be blue. Discard all 3.

Then worst case, after

33 sets of 3, you've discarded all the blue cards

So you're guaranteed to find two green on your

100th attempt

$\endgroup$
1
  • 3
    $\begingroup$ Then it doesn't work!! Thanks for pointing pointing that out $\endgroup$
    – Mohirl
    Commented Jun 11, 2019 at 10:11

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