I clarified a particular behavior of Lucy (it was not entirely clear before that she would not cooperate with Alice in any way). In simpler terms, Lucy's goal is the complete opposite of Alice's.

I think there are already too many views and changing this may make things a little confusing. I changed a majority of "she" into Alice instead. P.s: I was following the same notation as found in Satlzer's book when he is talking about distributed systems (Lucy or other extensions of Lucifer acts as an adversary for Alice). I will keep this in mind for future questions.

That's a necessary condition, but not sufficient. In addition to the condition, we also want the strategy to minimize the expected number of balls taken. So, if we use Yao's principle, $E[\text{performance}]$ would be the expected number of balls taken, subject to the condition you mentioned.

But $k$ is not equal to the expected number of boxes opened, right? I mean, if Lucy decides to distribute the balls uniformly, then even if we set $k = n$ (which means, we open every box), then the expected number of boxes opened would be $O(1)$. The main difficulty I've encountered while trying to solve this problem is to find a distribution that guarantees that the expected number of boxes opened by Alice is large conditioned that Alice would like to succeed with probability at least $1/n$.

It was supposed to be an upper bound, not exactly. I've fixed that.

Note: I changed the terminology. Instead of boxes containing balls, now we have $2n$ balls, $n$ are colored red. I don't think the solution of this form is a nash equilibrium. If Lucy paints the balls completely at random, then the expected number of balls Alice take would be $O(1)$ (sum of geometric series with parameter $1 / 2$). On the other hand, if Lucy know Alice takes $\log_2 n$ items at random, then instead of painting the balls arbitrarily, she would paint the last $n$ balls instead. I think this implies that the expectation and $k$ may be different.