Pigeon-hole principle question.

Question

Consider a street with $17$ houses.

Show that we can demolish $12$ of the houses so that the remaining $5$ houses have the property that as one walks down the street, one sees

• either houses that get bigger and bigger
• or houses that get smaller and smaller.

This question was put on hold.

I have figured it out. This is based on Erdős–Szekeres theorem. here n = 4 , when 4^2+1 elements ,there will be 4+1 = 5 monotonic increasing or decreasing. [http://www.skidmore.edu/~adean/MC2151401/Handouts/ErdosSzekeresProof.pdf] How can we remove put on hold to add this answer separately

Answer 1

This is a hard problem. Let me give you some hints.

First, you either have to assume that all the houses are different sizes, or that "bigger and bigger" means "not smaller," and "smaller and smaller" means "not bigger."

1. Label each house with an ordered pair $(i,d)$ where $i$ is the length of the longest increasing subsequence that starts at that house, and $d$ is the length of the longest decreasing subsequence that starts at that house.
2. Prove that no two houses have the same label.
3. Apply the pigeonhole principle.