The Pigeonhole Principle

Pablo Soberón
Additional contact information
Pablo Soberón: University College London, Department of Mathematics

Chapter 2 in Problem-Solving Methods in Combinatorics, 2013, pp 17-26 from Springer

Abstract: Abstract This chapter deals with several versions of the pigeonhole principle, mainly the classic version and the infinite version. It is shown how it can be used to solve olympiad problems. An introduction to Ramsey theory is presented, motivated by this principle. Also, two applications of the pigeonhole principle are shown. First, we present a proof of the Erdős-Szekeres theorem about monotone sequences. Then, we show a proof of a result in number theory by Fermat using this principle. Namely, we show how the pigeonhole principle can be used to prove that every prime number of the form 4k+1 can be written as the sum of two squares. At the end of the chapter, a list of 24 problems that can be solved with this technique.

Keywords: Number Theory; Prime Number; Rational Number; Golden Rule; Monotone Sequence (search for similar items in EconPapers)
Date: 2013
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-0348-0597-1_2

Ordering information: This item can be ordered from
http://www.springer.com/9783034805971

DOI: 10.1007/978-3-0348-0597-1_2

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().