Counting subsets of fixed size which differ by more than one element.

65 Views Asked by At

The board game Dominion is randomized at the start of play to allow players to purchase from 10 different piles, each pile chosen at random from 26 different choices. This number (26) has increased greatly over the years as more and more expansions have been added, and it now sits around 360.

The number of distinct 'games' is easy to count: ${26\choose 10}$. But games which differ by one card do not, in my experience with the early expansions, differ greatly in play style. Is there a reasonable estimate to the number of games which differ by two cards? To be more precise, is there a reasonable estimate to the number of games one could play which never (pairwise) overlap by 9 cards?

1

There are 1 best solutions below

0
On BEST ANSWER

The question as stated is not well posed. There are many possible sets which fit the description "set of games where each pair differ by two or more cards," you can cannot ask "the" size of such a set. It is reasonable to ask what the largest possible such set of games is, so I will assume you mean that.

This is likely an open problem. In the literature, a collection of subsets where every pair differ in a prescribed number of elements is known as a constant weight binary code. According to https://www.win.tue.nl/~aeb/codes/Andw.html, there exists $222775$ subsets of $\{1,2,\dots,26\}$ of size $10$ where each pair have at most $8$ elements in common (see the $A(n,4,w)$ table, $n=26,w=10$). It is unknown if you can push this number any higher. They cite [Brouwer et. al.] for the construction of this set of sets. Note that the data goes no where near close to $n=360$, so I have no answer on how many such games you can have for the full Dominion set.

A. E. Brouwer, J. B. Shearer, N. J. A. Sloane & W. D. Smith, A new table of constant weight codes, IEEE Trans. Inform. Theory 36 (1990) 1334-1380. (http://www2.research.att.com/~njas/codes/Andw/)