# 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?
How small can Jessica make the bracelets and still be guaranteed at least one rectangle can be found?

## Try it out

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

## Solution

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 34=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.