An inventory consists of a list of $115$ items, each marked "available" or "unavailable." There are $60$ available items. Show that there are at least two available items in the list exactly four items apart.
I think the problem can be worded this way:
Every permutation of a $115$-bit string with exactly sixty $1$'s will each be found to have two $1$'s separated by exactly four $1$'s or $0$'s.
Best Answer
Hint: Number the items $1$ to $115$.
Divide the numbers into $5$ groups. (i) the ones diviible by $5$; the ones that leave a remainder of $1$ on division by $5$: and so on up to the ones that leave a remainder of $4$ on division by $5$.
Count how many there are in each group. Show that if we have $60$ items, there are "too many" items in at least one of the groups.
By too many items, think of a much smaller group like $1,6,11,16,21,26,31,36,41,46$. Note that if we take $6$ items from this group, at least two will be $4$ apart.
Added: Each of the congruence classes modulo $5$ has $21$ members, and there are $5$ of them. So if we have $60$ numbers, one of the congruence classes at least must have $12$ or more representatives in the bunch of $60$. They are sepaated by $5$ or $10$ or more. We cannot arrange for them to be all separated by $10$ or more, since there are too many.