Jessica's Secret Bracelets

Jessica decides to make bracelets to sell to her friends. She has a large collection of red, green, and blue beads.

She decides to make the bracelets 100×10 beads in size, and threads the beads onto the bracelet strings totally at random.

Pleased with her prototype, after a quick examination, she notices that four of the red beads are aligned to form the vertices of a rectangle.

She makes another bracelet (again with random threading of beads), and this time finds two hidden rectangles; both with blue vertices. Jessica thinks this phenomenon is cool, and decides it will make an interesting sales angle: Find your secret hidden rectangle. She is curious if she will always get at least one rectangle, so goes searching for her mother.

“Mom”, she asks, “If I make these bracelets with random beads, can I tell my friends that there will always be at least one rectangle hidden in each bracelet?”

Jessica’s mom thinks about this for a second, and replies, “Yes dear, you can”, then being a shrewd mother, continues on to say, “And you know what?, you don’t need to make them quite as big. You can make them a little smaller, and still guarantee you will get at least one rectangle!”. Mother and daughter are both fans of the TV show Shark Tank, and go on to discuss the costs of goods. Requiring fewer beads means more profit for Jessica!

How small can Jessica make the bracelets and still be guaranteed at least one rectangle can be found?

Click on the image below to generate a random 100×10 bracelet.

The smallest size bracelet that Jessica can get away with is 82×4 beads.

Imagine this bracelet has 82 rows of 4 beads. There are 3⁴=81 configurations that the four beads can be found on any row (3×3×3×3). Even if the first 81 rows are distinct, from the pigeon hole principle, the 82nd row will match one of the previous rows. If we have 82 rows, we are guaranteed that there will be at least one pair of matching rows. These two rows will be one extreme of the rectangle.

Because there are 4 beads in every row, and there are only three colors, there has to be at least one repeated color in every row. The two matching rows will have this repeated color in identical positions.

These four matching beads will form the vertices of a rectangle.

Shortly after publication, I was contacted by one of my readers Andrew Buchanan, who advised me I had made a mistake.

You don't need the rows to be totally identical to force a rectangle. You just neeed two repeated columns to be indentical. My calculation used distinct rows, whereas with four columns there will be at least one pair. As there are 3 colors, and 6 pair locations, this is just 18 possibilities, so if we had 19 rows, then there is bound to be a repeated pair of columns that match up!

A 4×19 set of beads is guaranteed to contain a rectangle (this is a pretty small bracelet!)

Andrew went on to calculate different width bracelets (for instance if there are 5 columns, then there are at least 10 pair locations, meaning 3×10/2 possibilities, so a 5×16 bracelet would be required).

I'll see if I can get him to write it up …