an incantation contest
Source: Italy TST 2009 p6
March 10, 2012
modular arithmeticcombinatorics proposedcombinatorics
Problem Statement
Two persons, A and B, set up an incantation contest in which they spell incantations (i.e. a finite sequence of letters) alternately. They must obey the following rules:
i) Any incantation can appear no more than once;
ii) Except for the first incantation, any incantation must be obtained by permuting the letters of the last one before it, or deleting one letter from the last incantation before it;
iii)The first person who cannot spell an incantation loses the contest. Answer the following questions:
a) If A says '' first, then who will win?
b) Let be the set of all possible incantations whose lengths (i.e. the numbers of letters in them) are and containing only four letters , each of them appearing at least once. Find the first incantation (arranged in dictionary order) in such that A has a winning strategy by starting with it.