7
$\begingroup$

The Great Houdini is performing again! A guy from the audience arbitrarily chooses $52$ cards from a huge stack. He shuffles the cards and announces to Houdini that there are $a$ spades, $b$ hearts, $c$ clubs and $d$ diamonds. Houdini now has to guess the suits in the deck one by one. After every guess, the guy from the audience reveals the current card and everybody (including Houdini) sees the correct suit.

Houdini's strategy: At any moment in time, Houdini knows the numbers of remaining suits in the deck. Houdini always guesses a suit that occurs the highest number of times (ties are broken arbitrarily).

Question: What is the smallest possible number of correct guesses under Houdini's strategy (over all possible values of $a,b,c,d$)?

Improve this question
$\endgroup$

4 Answers 4

Reset to default
12
$\begingroup$

The smallest possible of correct guesses is max(a, b, c, d): every other suit could come up first and he would guess the most likely one over and over until nothing was left but those, and then he would get all the rest correct.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Just adding this to complete your answer. By the pigeon-hole principle, the smallest number of guesses is therefore 52/4 = 13 and occurs when a=b=c=d. Any other distribution would result in a higher max(a,b,c,d). $\endgroup$
    – Lawrence
    Commented Mar 12, 2015 at 10:00
  • $\begingroup$ @Lawrence - Indeed. I figured that was obvious. $\endgroup$
    – Rex Kerr
    Commented Mar 12, 2015 at 12:18
1
$\begingroup$

I think the answer is :

13

Because ;

There is 52 cards in one deck a+b+c+d=52 and worst possible outcome is that if houdini lock on some card suit and it does not decrease then our lock never change until there are just these cards... and tie breakers is arbitrarily , that means we can assume there worst things happens and all of cards are 13a-13b-13c-13d and we lock on b, and arbitrarily we always go with b in ties.

Improve this answer
$\endgroup$
0
1
$\begingroup$

I think the answer is

14 13

Because:

He will always guess the suit that occurs the highest number of times, so if we want him to fail that suit can never come up.

For example if we have 14 A, 13 B, 13 C, 12 D he will always guess A.

In worst case scenario, A never comes up, so he will deplete all the other ones and then correctly guess the last suit that remains.

But it is 13 because that is the lowest number that is simultaneously equal to or higher than other suits. Meaning we have conditions:

a >= b
a >= c
a >= d
a + b + c + d = 52

EDIT: I googled definition of 'arbitrarily' and changed my answer.

Improve this answer
$\endgroup$
1
$\begingroup$

I'd like to complement the other answers by a more formal explanation.

The answers rely on the fact that the correct guesses will be at least max(a,b,c,d). Why is it so?

If you consider the progression of max(a,b,c,d) over the game, you can see that it decreases by 1 every time the last of the highest occuring suits is revealed.
(i.e. when there is only one suit with the highest count and it gets picked). And in these cases, Houdini guesses correctly.

So you start with an initial value of max(a,b,c,d), it decreases to zero, and every time it decreases Houdini's score increases by 1.

This makes it clear, I think, that Houdini's score must equal or exceed the initial value of max(a,b,c,d).

Improve this answer
$\endgroup$

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.