Comment by kazinator

The pigeonhole principle informs us that if we have more pigeons than holes, some holes have two or more pigeons. But also that if we have fewer pigeons than holes, some holes will necessarily be empty.

Given two bit strings of length n, if we compare fewer than n pairs, we cannot tell whether they are equal. The strings being equal is the proposition a_0 = b_0 ^ a_1 = b_1 ^ ... ^ a_n-1 = b_n-1. You cannot simplify this formula such that any a_i or b_i primary is taken away.