Problem E

Ducks in a Row

There are \(10\) rubber ducks arranged in a row on a desk. On the bottom of each duck there is one of the following letters: A, B, C, D, E, F, G, H, I, or J. Each letter occurs exactly once.

Amina has written the following algorithm to find a particular letter.

Pick up the leftmost duck and look on the bottom. If it’s the letter you’re looking for, put the duck back down and stop. Otherwise pick up the next duck and look on the bottom. If it’s the letter you’re looking for, put the duck back down, swap it with the duck to its left, and stop. Repeat this until you find the letter you’re looking for.

For example, suppose the ducks were in the following order.

G, B, F, J, A, I, E, H, C, D

Amina uses her algorithm to find the letter E. She looks at the first \(6\) ducks and returns each of them to the desk. When she looks at the seventh duck and sees that it is the E, she swaps ducks E and I. So to locate the letter E, Amina looked at \(7\) ducks, and the ducks would now be in the following order.

G, B, F, J, A, E, I, H, C, D

Suppose Amina now wants to find the letter J. She looks at the G, B, and F and puts them back down. She then looks at the fourth duck, sees the J, and swaps ducks F and J. The ducks would now be in the following order.

G, B, J, F, A, E, I, H, C, D

After searching for the E and the J, Amina has looked at at a total of \(7+4=11\) ducks.

If the \(10\) ducks begin in some unknown order and Amina uses her algorithm to search for each of the ten letters exactly once, what is the maximum possible number of ducks that Amina picks up to look on the bottom?