And how can you tell there aren't other solutions that may give us higher values for M?

That's the million dollar question!

Anyway, I don't know if it's particularly rigorous, but I reasoned like this:

We are required to paint

**at least** the numbers

**0 1 2 3 4 5 6 7 8** to potentially arrive at 10. (Recall the six can be used as a nine).

Also, the number

**0** must appear on both dice otherwise, counting up, we will get stuck on 06.

To go bigger than 10, some numbers will have to appear on both dice to allow us to make 11, 22, 33, 44, 55, 66 etc.

If

**0 1 and 2** are painted on both dice, it leaves enough space to include the other required numbers

** 3 4 5 6 7 8**.

If

**0 1 2 and 3** are painted on both dice, it leaves insufficient space to include the other required numbers

**4 5 6 7 8**.

Therefore, we can only duplicate

**0 1 and 2**.

Since

**3** cannot be duplicated, we know that 33 will be impossible to build, so the next highest candidate for M must be 32.

Then all that is left to do is to find an arrangement that will allow building all the numbers 01 to 32, and at least one arrangement,

Die A: 0 1 2 3 4 5

Die B: 0 1 2 6 7 8

allows us to do just that.

Rigil