Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

My friend is designing a logo. The logo can essentially be reduced to 24 coloured dots arranged in a circle, and they can be either red or white. We want to produce a individual variation of this logo for each employee. That, if I have worked it out right, (since this appears analogous to a 24-bit binary string), means we could have an individual logo for 2^24 employees, obviously way more than we need.

But of course, we don't really want logos that don't have a lot of white dots as they may look too sparse. So we stipulate that there must always be at least half + 1 = 13 in the logo. How many combinations does that restrict us to?

My initial thought is 12 (half) + 1 + 2^11, but I'm not good enough to prove it.

Also, how can we generalise this formula for $x$ dots, $y$ individual colours and at least $n$ colours of a single type? If that's too general, what about just the case $y = 2$ as we have above?

share|improve this question
    
Your formulation of the multiple-color restrictions is unclear; what do you mean by "at least $n$ colours of a single type"? Did you mean to say "at least $n$ uses of a certain colour"? "at least $n$ uses of each colour"? "at least $n$ colours used"? Or something else yet? –  alexis Jan 21 '13 at 23:13

4 Answers 4

up vote 1 down vote accepted

There are $\binom{24}{12}$ $12$-element subsets of the $24$ positions; those correspond to the designs that have $12$ dots of each color. Half of the remaining $2^{24}-\binom{24}{12}$ subsets have at least $13$ elements. Thus, the answer to the main question is

$$\frac12\left(2^{24}-\binom{24}{12}\right)=2^{23}-\frac12\binom{24}{12}=16,777,216-1,352,078=15,425,138$$

logos. The general problem is significantly harder: for this one we can take advantage of the fact that we’re looking at exactly half of an easily computed number. However, for two colors and a majority of white dots it’s not bad. If there are $2n$ dots, the same reasoning leads to the result

$$\frac12\left(2^{2n}-\binom{2n}n\right)=2^{2n-1}-\frac12\binom{2n}n\;.$$

If there are $2n+1$ dots, exactly half of the $2^{2n+1}$, or $2^{2n}$ designs, have a majority of white dots.

Added: Note that I am assuming, as you implicitly did in saying that there are $2^{24}$ unrestricted patterns, that identical patterns in different orientations are counted as different patterns (e.g., that the $24$ patterns with a single red dot count as $24$ patterns, not as one). The problem becomes much more complicated if patterns that can be rotated into one another are considered identical.

share|improve this answer

If rotations of the circle are allowed, you need to apply Pólya's coloring theorem. The relevant group for just rotations of 24 elements is $C_{24}$, whose cycle index is: $$ \zeta_{C_{24}}(x_1, \ldots x_{24}) = \frac{1}{24} \sum_{d \mid 24} \phi(d)x_d^{24 / d} = \frac{1}{24} \left( x_1^{24} + x_2^{12} + 2 x_3^{8} + 2 x_4^{6} + 3 x_6^4 + 4 x_8^3 + 6 x_{12}^2 + 8 x_{24} \right) $$ For 13 red and 11 white ones (use $r$ and $w$ for them) you want the coefficient of $r^{13} w^{11}$ in $\zeta_{C_{24}}(r + w, r^2 + w^2, \ldots, r^{24} + z^{24})$. The only term that can provide exponents 13 and 11 is the first one: $$ [r^{13} w^{11}] \zeta_{C_{24}}(r + w, r^2 + w^2, \ldots, r^{24} + z^{24}) = [r^{13} w^{11}] \frac{1}{24} (r + w)^{24} = \frac{1}{24} \binom{24}{13} $$ Flipping over is left as an excercise ;-)

(I'm sure that as soon as I post this, somebody will post a simple reason why this is so by considering that 24 is even, and 13 and 11 odd...).

share|improve this answer
    
(+1) Added to the list of Burnside/PET computations. –  Marko Riedel Jun 18 at 22:48

To get a general answer to your question, consider the number of possible patterns with exactly $k$ red dots, for $k \le 24$. It is $\binom{24}{k}$, since the problem boils down to "choosing" $k$ out of the 24 positions.

The number of patterns with at least 13 red dots is then

$$\sum_{k=13}^{24} \binom{24}{k}$$

And similarly for other values instead of $24$ and $13$ (but still for just two colors).

But there's an extra detail to consider: Do your circular logos have a fixed orientation? Unless there is a natural "up" side, you need to account for rotational symmetries. You can't just divide the above number by 24, since some patterns are self-symmetric. (E.g., there's only one pattern with 24 red dots, and rotating it doesn't change that).

share|improve this answer

Another try: Consider the 11 positions of the white dots around the circle. There is no possibility of arranging them so that a rotation repeats the pattern, because 11 is a prime (any shuffling of dots must exchange pairs, or rotate groups of 3, or...). So for each linear order of the dots (there are $\binom{24}{13}$ of those) can be rotated into 24 positions, giving again $\frac{1}{24} \binom{24}{13}$. There are two ways of flipping the logo over: Through two dots, or through the lines connecting adyacent dots. But the last one will have an odd number of white dots at one side and an even one at the other, can't give the same. By exchanging left and right through vertically oposite dots, by the same reasoning one has to be red and the other white. This leaves 6 red and 5 white dots to be arranged the same way at each side, and with the selection of red or white dot at the top this then gives $2 \binom{11}{6}$ configurations that can't be distinguised by flipping over. So, allowing flipover the total number of logos is (half of the original have to be subtracted as they result from flipping over, but the ones which are the same flipped over have to be added back in): $$ \frac{1}{2} \cdot \cfrac{1}{24} \cdot \binom{24}{13} + 2 \binom{11}{6} $$

share|improve this answer
    
Your argument only applies to the exactly 13 case. But the problem states "at least 13", and you can't simplify the other calculations this way. –  alexis Jan 28 '13 at 12:55
    
"There is no possibility of arranging them so that a rotation repeats the pattern, because 11 is a prime" -- not quite: You also need that 11 and 24 are relatively prime; if you had a 22-dot circle and colored every other one, you'd have lots of symmetries. Interesting question, though; there must be a well-established answer, but I've got no recollection of it... –  alexis Jan 28 '13 at 13:02

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.