6
$\begingroup$

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

$\endgroup$
  • 5
    $\begingroup$ Tell that to the Ninja Turtles who get their pizza delivered to $122 \frac{1}{8}$. $\endgroup$ – corsiKa Dec 7 '15 at 23:45
  • 3
    $\begingroup$ You should probably specify that house numbers must be integers.If not, what defines consecutive in the context of fractional addresses? $\endgroup$ – Fake Name Dec 8 '15 at 0:00
  • 1
    $\begingroup$ Iterating housenumbers 1 and 57 would also violate this. I think we have a strictly increasing sequence of integers. $\endgroup$ – Pieter21 Dec 8 '15 at 12:11
  • $\begingroup$ This is a pretty muddily phrased question. For one thing, most real streets (at least in the US and UK) never have consecutively numbered houses, since they have odd and even numbers on opposite sides. Also, it's trivial (as @Pieter21 points out) to arrange the houses to have no consecutive numbers. The missing detail (I'm guessing) is that all houses are on the same side and must be arranged in ascending (or descending) order. $\endgroup$ – Dancrumb Dec 8 '15 at 17:34
  • 1
    $\begingroup$ The question does NOT say that the houses with consecutive numbers have to be adjacent. And while it is not explicit that the numbers have to be integers, it is an obvious from the question that this is intended. Of the two complaints brought up here, one is false, and the other is trivial, and a complaint that could be made of perhaps the majority of questions on this site. So why was this question put on hold? $\endgroup$ – Paul Sinclair Dec 8 '15 at 18:18
26
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Nice move with the pigeonhole definition $\endgroup$ – Simon S Dec 7 '15 at 23:48
25
$\begingroup$

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!

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Assuming that no screwup has given the same number to two houses. Or does "equal" qualify as " adjacent"? :-) $\endgroup$ – WGroleau Dec 7 '15 at 22:50
  • $\begingroup$ One can generalize to "the house numbers all differ by at least $k$", or "the sum of differences of the house numbers that differ by less than $k$ is at most $S$" and so on. $\endgroup$ – ASCII Advocate Dec 7 '15 at 23:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.