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$
8
  • $\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$ Mar 10, 2017 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$ Mar 10, 2017 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$ Mar 10, 2017 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$ Mar 10, 2017 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$ Mar 10, 2017 at 21:04

1 Answer 1

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$
13
  • $\begingroup$ hmm actually I think I have the wrong number... checking. EDIT: I think that's better $\endgroup$ Mar 10, 2017 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$ Mar 10, 2017 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$ Mar 10, 2017 at 20:35
  • 3
    $\begingroup$ @DaggerOfMesogrecia, reinventing the wheel can be a lot of fun (especially if that wheel is a bracelet). $\endgroup$
    – DyingIsFun
    Mar 10, 2017 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$ Mar 10, 2017 at 22:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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