Problem 5. There is a deck of 1024 cards, each with a different set of digits from 0 to 9, and all sets are distinct (including an empty card). We will call a set of cards complete if each digit from 0 to 9 appears exactly once on them.

Find all natural $k$ for which there exists a set of $k$ cards with the following condition: among them, no complete set can be selected, but adding any card from the deck violates this condition.
Solution. Answer: 512.

For each card, consider another card that complements it to a complete set (for example, for the card 3679, such a card would be 012458). It is clear that all 1024 cards can be divided into 512 non-overlapping pairs of cards that complement each other to a complete set. Next, we will prove that in any desired set, there must be exactly one card from each such pair, i.e., \( k = 512 \).

From the condition, it follows that at most one card from each pair can be among the selected ones. Now we will show that at least one card from each pair must be included.

Consider a pair of complementary cards, denoted as \( A \) and \( B \). Suppose neither of them is in the selected set. According to the condition, adding any card from the deck will result in a complete set. Adding card \( A \) to the set, we will find several cards that complement \( A \) to a complete set, i.e., all the digits on these cards simply match the set of digits on card \( B \). Similarly, adding card \( B \), we will find several cards from the set whose digits match the set of digits on card \( A \). Then, combining all these cards (which match the sets on cards \( A \) and \( B \)), we will get a complete set, which is a contradiction.

Now let's provide an example of a possible set for \( k = 512 \). Choose all cards that do not have the digit 9; there are exactly 512 such cards. It is clear that there is no complete set among them (the digit 9 is not present anywhere), and for each unselected card, its complement is among the selected ones, i.e., adding it will result in a complete set from these two cards.

## Criteria

## Points for the following achievements are summed up:

4 6. Proved that \( k \geqslant 512 \) (or that in each pair of cards that complement each other to a complete set, at least one card must be selected).

1 6. Proved that \( k \leqslant 512 \) (or that in each pair of cards that complement each other to a complete set, no more than one card should be selected).

1 6. Provided a correct example of a set of 512 cards.

1 6. Provided justification that the example set of 512 cards meets the conditions of the problem.

0 6. Only the correct answer.