1

In the game of tetris you are guaranteed to get each of the 7 unique pieces in some random order. For this we will call them abcdefg. This would give us 7! or 5040 unique starts.

However, there is also a "hold feature", which will swap the current piece out with one that has been previously held, or with none the first time swapped.

Given this, (using only 4 pieces to simplify), if we have the sequence abcd, we can create the sequences bacb, bcad, bcda, badc, .... through different uses of holding.

Is there a way to generate a set of all possible starts such that no members of the set can be made from another? Is this the same set as a set of all starts that can be used to generate all 5040 sets? Is there a name for this kind of set?

John Howard
  • 225
  • 1
    What do you mean by "a set of all possible starts"? There's only one set of all possible starts, and it clearly doesn't have the property you want -- don't you mean "a set of starts"? Also, presumably you want a maximal such set? (Otherwise you could simply use the empty set.) – joriki Apr 11 '16 at 17:09
  • Sorry if I wasn't very clear, I wasn't quite sure how to describe what I am looking for. I want The smallest set of all starts that would allow us to generate all 5040 permutations of abcdefg making use of the hold feature. – John Howard Apr 11 '16 at 17:52
  • 1
    I see. For $n$ pieces, you have $n-1$ decisions to swap or not, so any start can generate at most (in fact I believe exactly) $2^{n-1}$ starts. Thus a lower bound for the number of starts you'll need is $\lceil2^{-(n-1)}n!\rceil$, which for $n=7$ is $\lceil7!/2^6\rceil=79$. – joriki Apr 11 '16 at 18:04

0 Answers0