Chain of Pearls

Logic Level 4

Imagine you are given a chain made of 2 2 or more pearls by a king and asked to find all the unique shapes of the chain without breaking it. The order of pearls must remain the same, and therefore you can only change the connection of each adjacent pair of pearls, which can be either straight or perpendicular. Rotations and reflections are considered as the same shapes looked at from different angles.

The unique forms of chains with n = 2 , 3 , 4 n=2, 3, 4 pearls are shown in the table.

What is the number of unique forms for n = 5 n=5 pearls?

Note: It is not as easy as it seems to get all possible shapes. Therefore, please think hard.


The answer is 13.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Zeeshan Ali
Apr 29, 2018

Here is how to do it the easy way;

  • When we had only one pearl, there was only one form. Now, when we have another pearl added to it, we can place it to 3 different positions as follows;
  1. Parallel to A---B (as A---B---C)

  2. Above B in A---B

  3. Below B in A---B (this form would be simply a reflection of above second form therefore we neglect it)

Therefore there are only two unique forms of the chain formed with 3 3 pearls.

  • After you know the two different forms above, you can extend them one by one by adding one more pearl to its all possible positions.

Following are all the possible forms or shapes when we have five pearls;

As we see here, there are 13 13 unique structures or forms of the chain formed with 5 5 pearls.

Oded Barash
Jan 26, 2019

This problem can be solved by systematically enumerating all possible chains while eliminating those which are equivalent due to rotation or reflection symmetries. For this purpose, let us encode the orientation of each pearl in a chain with one of the following symbols describing the path from the current pearl to its consecutive one:

S – go straight

R - turn right

L – turn left

A chain of N N pearls can be represented by a string of N 2 N-2 symbols (the first and last pearls need not be included) for a total of 3 N 2 3^{N-2} possible strings. For the case of 5 peals, this gives a total of 27 possibilities. This number includes also all possible symmetries which need to be excluded.

As an example, the string RLL represents this chain: It is easy to see that strings RXX are equivalent to strings LXX (where X stands for any symbol) due to reflection. We can therefore ignore LXX strings, leaving only 18 possibilities as follows:

Chains #3,7,8,9 are equivalent to other chains and therefore are excluded from the counting.

Chain #14 is possible if you allow the pearls to occupy the same position (for example, lie on top of each other).

Therefore, the number of unique chains is either 14 or 13 (if chain #14 is not allowed).

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...