HelpContactFor teachers and institutes
>_StemPy Lab
Mock TestsClasses

>_StemPy Lab

Learn. Solve. Code the solutions. Test yourself.

Live examsFree mock exams, timed and rankedEveryone starts together, and your score and rank come the moment it ends.See the exams →
Live examsInternational live exams are comingTell us which exam you want first. Timed practice papers are open now.See what is coming →

Learn

  • Physics
  • Chemistry
  • Mathematics
  • Biology
  • Python Programming
  • Statistics & Data Science
  • Computer Science
  • Space Science and Astronomy
  • Earth and Environmental Science
  • Classes
  • Groups

Practice

  • Problems
  • Quizzes
  • Mock Tests
  • Prepare for an Exam
  • Question Sets
  • Exams
  • Certificates
  • Python Labs
  • AI Practice Generator
  • Student-Created Tests

Community

  • Discussions
  • Resources
  • Notes
  • Glossary
  • Blog

Account

  • Log in
© 2026 senLearn. All rights reserved.HelpFor SchoolsAboutContactPrivacy PolicyTerms of UseRefund Policy
  1. Problems
  2. /Ten students of different heights stand in a line in some order…
AdvancedMathematicsHigh School (11–12)Pigeonhole Principle, Recursion and Graph TheoryproofNumericalOlympiad

Ten students of different heights stand in a line in some order…

StemPy LabContributed by StemPy Lab

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 444 students this way. Then show that this is the best possible promise for a line of 999: give an order of 999 heights, say 111 to 999, in which no 444 students are getting taller and no 444 are getting shorter. Use labels (a,d)(a, d)(a,d) as in the proof of Erdős and Szekeres.

Check your answer

Work it out on paper, then type your number. The answer itself stays hidden.

Need a reminder? The key ideaShowHide

NNN objects in kkk boxes put at least ⌈Nk⌉\left\lceil \dfrac{N}{k} \right\rceil⌈kN​⌉ in some box. To force rrr objects into one of kkk boxes you need k(r−1)+1k(r - 1) + 1k(r−1)+1. Some number in a list is at least the average.

The worked solution

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 (a,d)(a, d)(a,d). Then build a line of 999 that avoids runs of length 444.

Step 1. Labels. For each student let aaa be the length of the longest run of getting taller that ends at that student, and ddd the longest run of getting shorter that ends there.

Step 2. The labels differ. Take students xxx before yyy. If yyy is taller, yyy can join the best taller run ending at xxx, so aaa of yyy exceeds aaa of xxx. If yyy is shorter, ddd of yyy exceeds ddd of xxx. Heights are all different, so one case holds.

Step 3. Pigeonholes. Suppose no run had length 444. Then aaa and ddd are among 1,2,31, 2, 31,2,3, which gives 3×3=93 \times 3 = 93×3=9 labels. Ten students with ten different labels do not fit. So some run has length at least 444.

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 333. A shorter run stays inside one block, so it also has length at most 333.

Answer: from 101010 students she can always pick 444, and the line of 999 above shows that 999 students cannot promise it. Proof complete.

Log in to save this for later
← All Problems
← A class of 50 students takes a quiz marked out of 10…The numbers 1, 2, …, 12 are written round a circle in any order, like a clock face that has been… →
More onPigeonhole Principle, Recursion and Graph Theory

Discussion (0)

Log in to join the discussion.

Loading…

Learn it in

  1. The generalised pigeonhole principleThe Pigeonhole Principle

More on this topic

  1. The 15 edges of K₆ are coloured red or blue…Advanced
  2. Three houses each need a path to each of three wells, nine paths in all, drawn on flat ground…Advanced
  3. A connected planar graph with 10 vertices is drawn without crossings, and every face of the…Hard
  4. The complete bipartite graph K_(m,n) joins each of m left vertices to each of n right vertices…
Advanced
  • A river town has five land areas, A, B, C, D and E, joined by ten bridges…Hard
  • All problems on this topic →