Guaranteed Repeats by the Pigeonhole Principle

Think of the n possible values as boxes and the n+1 array entries as items placed into those boxes.

If more items than boxes are placed, at least one box must receive more than one item.

1. 1. Map values to pigeonholes

   Treat each of the $n$ possible values as a box, and place each of the $n+1$ array entries into the box matching its value.

2. 2. Apply the principle

   Since there are more items ($n+1$) than boxes ($n$), the pigeonhole principle guarantees some box receives at least two items, meaning some value repeats.

Answer: The pigeonhole principle.