A flag is defined via 3 colors (ordering doesn't matter)with nine colors what is the maximum number of flags one can have given that any two flags can share at most 1 color?

14

jiantao, can you explain how you got 14? Are you allowing a flag to have the same color more than once (e.g. a flag that is red, red, blue)?If not, then I don't see how that is possible. With each flag required to have 3 distinct colors then no one color may appear on more than 4 flags. Using the digits 1-9 in place of colors, this becomes obvious; in order to have "1" appear on 4 flags, we need to include:123145167189(equivalently with some permutation of 2-9)This places an absolute ceiling of 12 on the number of flags allowed (4*9/3 = 12)I'm pretty sure the max is actually 10, but haven't proven it yet. Here is one set of 10 flags that obeys the rules:123145167189246258279347359369 EDIT: thanks to karafka for pointing that out. 368 was supposed to be the last entry, not 369

Sorry. I understood the question wrong. I agree with you that 12 is the upper bound.

your last two entries are not "obeying" the rule. 359369 The answer is 12.There are C(9,2) = 36 unique pairs of colors. Each flag represents C(3,2) = 3 such pairs, therefore there can be maximum 36/3 = 12 such flags.

Here is a solution with your notation:123147158169248259267349357368456789

the general case is related to the constant-weight code. the problem posed here asks for A(9,4,3).formula for A(n,4,3) (i.e., given n colors) is known, e.g., Brouwer et al. (1990), or see A001839----- ----- ----- ----- -----a related note, the upper bound mentioned earlier: (n \choose 2)/(3 \choose 2)=n(n-1)/6 is achieved iff n=1 or 3 (mod 6), for which the Steiner triple system exists (the page has a nice illustration of the case n=9 asked here). the result was known to Kirkman in 1847, and is related to his famous schoolgirl problem.