A Necklace Puzzle: Professor Pailyn's PMQ43

Alice’s mother had bought her a set of beads with which to make some necklaces. Alice had originally frowned upon this as an attempt to give her something girlie-ish. However, she did enjoy making patterns so started playing with the beads. But on this particular day, Alice was getting bored with her pattern-making skills.

"I need to find a really clever pattern; something to impress Zeta. I know just the person to ask."

-=*=-

“OK, let’s start with a simple example. Pick just two colours...”

“Pink and... orange!” Alice interjected.

“Isn’t that a touch... garish?” enquired the Professor.

“It’s not garish... it’s colourful!” beamed Alice. It was, indeed, going to be hideous but it was for her cousin.

“Alright, then pick a maximum length for the beads – let’s pick 3 to make the numbers small.”

“Three! That’s not a necklace, that’s an earring!” Alice was having fun mocking the good Professor. He knew this and happily played along.

“Wait a minute, my impatient child! Now, we’re going to make a necklace where all possible 3-bead permutations exist. How many beads do you think you’ll need?” It was the Professor’s turn to smile with his ‘show-me-how-clever-you-are’ question.


“Well, let me find all the ways of laying out three beads. Pink-pink-pink! That was easy. Pink-pink-orange.” Alice laid out her beads as asked and found there were 8 permutations.

“Good. So if we want a necklace that has within it every such pattern, we could just string them all together. That would give us a necklace with 24 beads, right?” Alice agreed. “Now here comes the clever part: we can make just such a necklace, but with fewer beads! Firstly, take those arrangements that are cyclic permutations of each other. What I mean is, take the first bead and move it to the other end and you’ll end up with another permutation. Keep doing this until you get a set that are all cyclic permutations of each other; like pink-pink-orange, pink-orange-pink and orange-pink-pink.” Alice was in deep concentration. “Then pick just one from that set; the one that comes first alphabetically.”

“Alphabetically!? What does that mean? Orange comes before pink because the letter O comes before P?”

“Something like that. We could label them 0 and 1, or A and B, or even O and P, if you wish. The important thing is to think of them as having an alphabetical order, like in a dictionary. This means that 0 comes before 00 even though they may both look like the number zero. And 001 comes before 01; just as ‘aardvark’ comes before ‘abacus’ in a dictionary.”

“But ‘abacus’ starts with 010. Where would that go?”

“OK, 01 is equivalent to the word ‘ab’.” The Professor was thinking... “As in the blood group AB. So in a  dictionary, ‘AB’ comes after ‘aadvark’ but before ‘abacus’. Is that clearer?”

“Yes!” Alice lied.

“So let’s do it your way, with O for orange and P for pink. We have seen that P-P-O, P-O-P and O-P-P are in the same set as they are cyclic permutations. Now, which one is alphabetically the first?”

“O-P-P, of course!”

“Right, so let’s keep that one and discard the other two. Now, are there any more cyclic perms?”

“Yes, O-O-P, O-P-O and P-O-O.” Alice giggled. “So... O-O-P comes first in the dictionary... so, keep it and discard the other two!”

“Very good!”

“But now we have just four sets of three beads. What do we do next?”

“Well, we next get rid of the two extremes: O-O-O and P-P-P. This is because we want to be left with only the aperiodic strings of beads. Notice that O-P-P and O-O-P are both asymmetrical.”

“Uh-hum...” Alice nodded. “So after all of this, we’re left with just two strings of beads?!”

“Yes. However, one last thing: we need to add the solitary beads O and P. So in the end we have four sets of beads. Now we need to put them in alphabetical order.” Professor Pailyn hadn't quite forgotten the full instructions but rather thought it best not to complicate the matter for the moment.

“That’s... O first, then OOP, then OPP and finally the P. Erm... I’ve forgotten what we’re supposed to be doing!” Alice confessed.

“OK, if we now join these beads together we get the sequence OOOPOPPP. And if we put them on a necklace we can find all our 8 initial permutations but only using 8 beads! Look, the first three beads give us OOO, the second three OOP, then OPO, POP, OPP and PPP. But as these are now in a circle we can carry on with PPO and finally – your favourite – POO!” Alice just had to laugh again.

“Wow!” she finally got it, “I finally get it! But... we’ve still ended up with a very small bangle and not really a necklace.”

“True, but as I said, this was a simple example to keep the numbers small.”

“So... if I now want to pick 3 colours, can I do the same thing?”

“Yes, of course, but you still need to decide on how long your basic string will be.”

“Five!” blurted Alice as she needed to let out all that hard thinking.

“May I suggest 3 again. If you try 5 it will take you a considerable amount of time to actually make the necklace. I think that 3 colours and a basic string of 3 beads will give you the perfect length.”

“OK, let me pick another colour; something to make it extra-garish!” Alice thought a bit about this. She was looking forward to seeing Zeta’s face when she received the necklace. But even more so, she was especially looking forward to explaining to her how incredibly clever her necklace was. “Blue! That’s it: pink, orange and blue.” Alice got down to work.

So, how many beads will Alice’s necklace have and what will be the order of the three colours?

Remember that the aim is to form a necklace of the shortest length in such a way that every permutation of 3 beads in 3 colours is included as a subsequence within the cyclic sequence of beads. You may use the letters B, O and P to designate each colour.

Have fun!

Feel free to comment, ask questions and even check your answer in the comments box below powered by  Disqus Google+.

}

This space is here to avoid seeing the answers before trying the problem!

}

If you enjoy using this website then please consider making a donation - every little helps :-)

You can receive these questions directly to your email box or read them in an RSS reader. Subscribe using the links on the right.

Don’t forget to follow Gifted Mathematics on Google+, Facebook or Twitter. You may add your own interesting questions on our Google+ Community and Facebook..

You can also subscribe to our Bookmarks on StumbleUpon and Pinterest. Many resources never make it onto the pages of Gifted Mathematics but are stored in these bookmarking websites to share with you.