8
$\begingroup$

Far far away in the distant future some explorers stumble across the remains of an alien civilization. You are the teams linguist, and it's your job to attempt to translate the hodge podge of symbols that appear to be their written language. Unfortunately this seems like it's way out of your grasp. They seem to be using a system that allows for thousands of symbols, and you can't seem to find much consistency in it at all!

After weeks of struggling, you have a break through! You had noticed that certain symbols that often were present at the beginning of texts had some things in common, and you don't think it's a coincidence. You're convinced that a bunch of what you thought were different symbols are actually the same just drawn different ways, now you just need to figure out how many separate symbols there really are.

Each symbol of the language is made up of a hollow circle with 12 smaller circles overlaid. These smaller circles are each either hollow or filled. Here are some pictures along with some equivalencies (and inequalities) that you're convinced you've figured out.

enter image description here

Assuming that these patterns extend to all symbols, the goal is to find the number of possible symbols in this language that are not equivalent. If this goes for a while without any correct answers, I'll post some more specific equivalency rules, but I feel like it's more fun to try to work them out yourself from examples.

BONUS: See if you can find an equation that will give the number of possible symbols for a ring with N dots instead of 12!

BONUS to the BONUS: See if you can find the equation for a ring with N dots that each have M possible states!

$\endgroup$
  • $\begingroup$ bonus to the bonus requires a specification of equivalence amongst the colours (in the binary you seem to suggest inversion is equivalent, but with 3 colours would any rotation of the three be equivalent, or none?) $\endgroup$ – Jonathan Allan Mar 10 '17 at 20:10
  • 1
    $\begingroup$ @Jonathan Allan Good catch, that is a bit unclear. You could consider the any rotation of the colors to be equivalent. For some examples ABB = BAA = ACC = BCC = CAA = CBB $\endgroup$ – DaggerOfMesogrecia Mar 10 '17 at 20:14
  • $\begingroup$ @Silenus Each symbol of the language looks like that. The fact that symbols were at the beginning of the text is just what gave you the hint that they might be equivalent (the fact that they are at the beginning can be ignored). If you think that's misleading I can add it as a hint. $\endgroup$ – DaggerOfMesogrecia Mar 10 '17 at 20:16
  • $\begingroup$ What about (2,2,2,3,3) =?= (2,3,2,3,2)? There are no examples provided to suggest whether these are equal or if they are not equal. $\endgroup$ – Ian MacDonald Mar 10 '17 at 21:00
  • $\begingroup$ @IanMacDonald I'd say the last case covers that no? As I read your example (6-on, 6-off) vs (4 on 3 off 2 on 3 off), which seem different by that image. Maybe I misinterpreted though. $\endgroup$ – Jonathan Allan Mar 10 '17 at 21:04
7
$\begingroup$

In the language of combinatorics the number of symbols, assuming only purely rotational and reflectional geometric symmetry* is:

the number of binary (or 2-ary) bracelets, with the added equivalence of complementing the two colours. For twelve beads that is $122$.

* as pointed out by Ian MacDonald and Silenus, this has not been guaranteed

This is then (for two colours, but for an abitrary number of beads, $n$):

$B_c(n)=\frac12 (N_c(n) + 2^{\lfloor \frac n2 \rfloor})$
where $N_c$ is the number of necklaces with the allowed complementing of the two colours:
$N_c(n)=\frac1{2n}\sum_{d|n}{\phi(2d)2^{\frac{n}d}}$
where the sum is over the divisors of $n$; and
$\phi(x)$ is the Euler totient (the count of the natural numbers up to $x$ that are relatively prime to $x$):
$\phi(x)=x\prod_{p|x}{1-\frac1{p}}$
where the product is over the distinct prime divisors of $x$.

Putting that all together for the twelve bead case:

The divisors of $12$ are $\{1,2,3,4,6,12\}$
Doubled these are $\{2,4,6,8,12,24\}$
Their prime divisors are $\{\{2\},\{2\},\{2,3\},\{2\},\{2,3\},\{2,3\}\}$ The Euler totients needed are then:
$\phi(2)=2 \times (1-\frac12)=1$ $\phi(4)=4 \times (1-\frac12)=2$
$\phi(6)=6 \times (1-\frac12) \times (1-\frac13)=2$
$\phi(8)=8 \times (1-\frac12)=4$
$\phi(12)=12 \times (1-\frac12) \times (1-\frac13)=4$
$\phi(24)=24 \times (1-\frac12) \times (1-\frac13)=8$

$N_c(12)=\frac1{24}(1 \times 2^{\frac{12}{1}} + 2 \times 2^{\frac{12}{2}} + 2 \times 2^{\frac{12}{3}} + 4 \times 2^{\frac{12}{4}} + 4 \times 2^{\frac{12}{6}} + 8 \times 2^{\frac{12}{12}})$
$N_c(12)=\frac1{24}(4096 + 128 + 32 + 32 + 16 + 16)$
$N_c(12)=\frac{4320}{24}=180$

$B_c(12)=\frac12 (N_c(12) + 2^{\lfloor \frac {12}2 \rfloor})$
$B_c(12)=\frac12 (180 + 2^6)=\frac{244}2=122$


This entry in the OEIS has the same formula, $B_c$, given above in terms of this other entry, which has the sub-formula, $N_c$, given above.

To prove such formulae I think one would probably use the Pólya enumeration theorem.

For a treatment of such sequences see this paper.

the bonus to the bonus of assuming $M$ colours with rotational symmetry (what is usually refereed to as $k$) has not yet been covered here.

$\endgroup$
  • $\begingroup$ hmm actually I think I have the wrong number... checking. EDIT: I think that's better $\endgroup$ – Jonathan Allan Mar 10 '17 at 20:32
  • $\begingroup$ Wow, I had no idea that the situation I was describing had already been so thoroughly described in mathematics... To the point where images on the wiki page even look similar to the image I included. Really cool! I'm going to hold off on the chosen answer for now just to see if the both the bonuses end up included (Even if they are trivial now since anyone could just google based on your answer). $\endgroup$ – DaggerOfMesogrecia Mar 10 '17 at 20:34
  • $\begingroup$ That is the reason we use spoilers, so if someone want to work it out, and can resist temptation, they can! $\endgroup$ – Jonathan Allan Mar 10 '17 at 20:35
  • 3
    $\begingroup$ @DaggerOfMesogrecia, reinventing the wheel can be a lot of fun (especially if that wheel is a bracelet). $\endgroup$ – GoldenGremlin Mar 10 '17 at 20:46
  • 2
    $\begingroup$ This answer isn't quite right, because with bracelets, the first equivalence in the question image wouldn't hold. $\endgroup$ – user2357112 Mar 10 '17 at 22:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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