Ttdfjt

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?

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

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.

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 frac1322=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

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

If

$Cle 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^65a_i=132$ and the number of edges is $E=sum_i=1^65fraca_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=65cdot fraca(a-1)2approx 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$.)

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...

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

The lower bound should be

This solution was for v1 problem. I wrote this one by mistake. Ill try the v2 problem.