There are 31 houses on north street numbered from 1 to 57. Show at least two of them have consecutive numbers.

Question

I thought to use the pigeon hole principle but besides that not sure how to solve.

Answer 1

HINT: For your pigeonholes take the sets $\{1,2\},\{3,4\},\ldots,\{55,56\}$ of house numbers. Even if one house is numbered $57$, you still have $30$ houses to fit into those pigeonholes.

Answer 2

More simply perhaps:

Suppose that no two houses have consecutive numbers. If $L$ is the lowest house number then the second lowest house number is at least $L + 2$, the third lowest is at least $L + 4$, and so on up the the highest house number of at least

$$L + 30 \cdot 2 = L + 60$$

Now derive a contradiction!

Answer 3

There is a unique subset with the maximum number of non-adjacent houses: {1,3,5,...,57}. The number of houses (29) in this set is less than 30.

This observation solves the problem, but it also indicates that with 30 houses there are at least 2 adjacencies. With only 1 adjacency $(i-1,i)$ you could add $+1$ to all the house numbers $\geq i$ and get a set of house numbers between 1 and 58 with no adjacencies, but there again the maximum size of set is 29, not 30. To have 30 nonadjacent numbers we need to choose them from an interval of size at least 59.

Continuing the argument to the general case, to have $H$ houses with distinct numbers between $1$ and $n$, and with $\leq k$ adjacencies, one needs $(n+k) \leq 2H - 1.$ This is optimal; the equality can hold, and in a unique way.

Answer 4

Not sure if this is the answer you were looking for, but it's one of those "so painfully simple that you likely never considered it":

North Street ends in a cul-de-sac.

But more to the point...

If houses are numbered 1 through 57 and NONE of them are consecutively numbered, they must all have odd numbers. All odd numbers from 1 to 57 (inclusive) total 29 numbers.

The problem cites 31 houses in a range which can only accommodate 29 houses without any adjacent houses. 31-29 = 2, therefore at least two of the houses must be adjacent to others in order to fit within the parameters.

Even if the question cited 30 houses, at least two would have adjacent numbers. For example, if the 30th house was numbered 2, houses 1, 2, and 3 would all have adjacent numbers.