Problem 941

[DeatH_StaR]

What does it mean "Denote by pn the place..." - does it mean that pn actually equals n?

[philiplu]

$a_1,a_2,\dots,a_N$ will all appear in $C(10,12)$ somewhere, and not necessarily in that order. For example, it might be that $a_3$ appears first when you look at where each of the $a_i$ appear in $C(10,12).$ If that were the case, then $p_3 = 1$, since $a_3$ was first (and no, I've no idea if $p_3 = 1$, that's just an example).

So $p_n$ is the (1-based) order of $a_n$ in the list of all the $a_i$ when you arrange those in order by where they show up in $C(10,12).$

[Stache]

Isn't it true for C(3,2) that 0001021122 is lexicographically smaller than 0010211220 and meets the definition of C(k, n) given in the problem? I realize this is not a de Bruijn sequence, but the problem statement doesn't say that each combination must appear exactly once.

[mdean]

Consider all sequences of shortest possible length that contains every possible combination of the digits.
Denote by $C(k,n)$ the lexicographically smallest of these.

0001021122 does not contain "20".

[Stache]

yea, I was thinking 20 was included cyclically, but then of course there would be another 0 at the end and it wouldn't be the shortest sequence....thanks!