13
$\begingroup$

Fifty cards are arranged on a table so that only the uppermost side of each card is visible. Each card bears two numbers, one on each side. The numbers range from 1 to 100, and each number appears exactly once.

Vasya must choose any number of cards and flip them over, and then add up the 50 numbers now on top. What’s the highest sum he can be sure to reach if

  1. he has to flip all the cards that he wants to, simultaneously?

  2. he can flip the cards one at a time?

Note: a card can be flipped at most one time.

Source: 1999 St. Petersburg City Mathematical Olympiad.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
16
$\begingroup$

Part (1)

Vasya can achieve a score of at least 2525. If the exposed cards sum to a number that is 2525 or greater, Vasya can simply flip none of them. If the exposed cards sum to a number that is less than 2525, the backsides of all of them will sum to a number greater than 2525 (since the total sum of the cards is (100)(101)/2 = 5050). So Vasya can get a number greater than 2525 by flipping every card.

Part (2)

2525 still seems to be the limit, because it is fairly easy to orchestrate a hypothetical that will interfere with any strategy. For example, let's say the fronts of the cards show the numbers 26-75, inclusive. These numbers sum to 2525 ((75)(76)/2 - (25)(26)/2 = 2850 - 325 = 2525). It's impossible to come up with a consistent strategy to flip a single card in this scenario, since that card may very well have a number 1-24 on it. In fact, any number of flips that aren't either all or none of them have the possibility to result in a number less than 2525. Suppose the first flip is a 1, the second flip is a 2, the third flip is a 3, et cetera. Even though it's unlikely, it is possible and a result greater than 2525 can't be guaranteed.

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ Regarding the first question, what's the proof that he cannot do better than 2525 in a guaranteed way? $\endgroup$
    – Hemant Agarwal
    Commented Nov 5 at 23:22
  • $\begingroup$ Part 2 proves the upper bound for both cases. $\endgroup$
    – Florian F
    Commented Nov 5 at 23:24
  • $\begingroup$ @HemantAgarwal Part 2 does prove the upper bound for both cases; it's honestly possible to consolidate them in one explanation but I felt like keeping it in line with the question with the two-part answer was better. $\endgroup$
    – ilikecorgis
    Commented Nov 5 at 23:26
  • $\begingroup$ Another way to think about it, flipping one at a time can't help to get a guaranteed outcome, since we must assume the worst possible result of flipping each card. The worst outcome of a random flip makes the score go down, which then requires flipping another card. We can just flip all the cards we earmark as "potential flips" all at once, since in the worst case we're guaranteed to wind up flipping every one of them anyway (otherwise they wouldn't even be "potential" flips). $\endgroup$
    – Nuclear Hoagie
    Commented Nov 6 at 16:33
  • 1
    $\begingroup$ Perhaps a more interesting question would be what strategy gives the highest expected score, while still guaranteeing this minimum assurable value. For instance, a strategy of turning over only cards that have a higher value not already showing (e.g. if 99 and 100 were showing, you would not turn over those cards) will still guarantee the minimum, but almost assuredly give a higher result than turning over all cards. $\endgroup$
    – Paul Sinclair
    Commented Nov 6 at 18:03
0
$\begingroup$

If it's less than $2525$, he can just flip all of them and get a bigger sum.

A configuration with the smallest sum where flipping is no better than not flipping would be this:

$1$ shouldn't face up in any possible configurations.

If $2$ and $3$ are facing up, $4$ and $5$ must face down for the sums of the two and three smallest visible numbers to not be exceeded by the first two/three invisible ones. Then $6$ and $7$ can face up. Rinse and repeat, which means each $4k+2$ and $4k+3$ integer must face up for the smallest guaranteed sum, which is $2525$. This configuration also ensures Vasya can't do any better in the worst case scenario even if he has the option to flip cards one by one.

This isn't necessarily the only configuration, but the point is that such a configuration with a sum of $2525$ exists.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Are you claiming that this is the only configuration with the smallest sum? $\endgroup$
    – noedne
    Commented Nov 7 at 10:56
  • $\begingroup$ Not necessarily, but finding one is enough. $\endgroup$
    – Nautilus
    Commented Nov 7 at 11:05

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.