Try it on paper first. A hint, the key idea and the worked solution are here when you need them.
Ten students of different heights stand in a line in some order. A teacher wants to pick some of them and keep their order in the line. The picked students must get taller from left to right, or get shorter from left to right.
Prove that she can always pick at least students this way. Then show that this is the best possible promise for a line of : give an order of heights, say to , in which no students are getting taller and no are getting shorter. Use labels as in the proof of Erdős and Szekeres.
objects in boxes put at least in some box. To force objects into one of boxes you need . Some number in a list is at least the average.
Check an answer or open a hint to unlock the worked solution.
Have you tried it?
Work it out on paper first. It is fine to get stuck or make a mistake: that is how we learn. When you are ready, go through the solution one step at a time, and check each step against your own.
Plan. Use the labels . Then build a line of that avoids runs of length .
Step 1. Labels. For each student let be the length of the longest run of getting taller that ends at that student, and the longest run of getting shorter that ends there.
Step 2. The labels differ. Take students before . If is taller, can join the best taller run ending at , so of exceeds of . If is shorter, of exceeds of . Heights are all different, so one case holds.
Step 3. Pigeonholes. Suppose no run had length . Then and are among , which gives labels. Ten students with ten different labels do not fit. So some run has length at least .
Step 4. A line of nine with no run of four. Take heights 3, 2, 1, 6, 5, 4, 9, 8, 7. A taller run can use at most one height from each block of three, so it has length at most . A shorter run stays inside one block, so it also has length at most .
Answer: from students she can always pick , and the line of above shows that students cannot promise it. Proof complete.
Log in to join the discussion.
Loading…