Maths Olympiad Prep

Library / /22 of 32

Combinatorics Difficulty 6.1 National olympiad Prove it Netherlands

We consider security codes consisting of four digits. We say that one code dominates another code if each digit of the first code is at least as large as the corresponding digit in the second code. For example, 49614961 dominates 07610761, because 404 \ge 0, 979 \ge 7, 666 \ge 6, and 111 \ge 1. We would like to assign a colour to each security code from 00000000 to 99999999, but if one code dominates another code then the codes cannot have the same colour.
What is the minimum number of colours that we need in order to do this?

Solution

3737

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.