Functions · step 8 of 13

Pigeonhole consequences for injections

If |A| > |B| then no function A → B is injective — some two inputs must collide. That is the pigeonhole principle stated in function language, and it is the engine behind hash collisions, the fact that lossless compression cannot shrink every file, and many existence proofs. The generalised form says some output is hit at least ⌈|A|/|B|⌉ times.

Practise pigeonhole consequences for injections free → All Functions subtopics

✓ Unlimited questions · marked criterion by criterion · no card needed

Method: how to approach it

The order below is what examiners expect to see, and each step carries its own marks.

Identify the pigeons and the holesPigeons are the domain elements, holes the codomain. Getting these backwards inverts the conclusion.
Compare the sizesMore pigeons than holes forces a repeat. State the counts explicitly.
Use the generalised bound when neededWith m pigeons and n holes, some hole holds at least ⌈m/n⌉ pigeons.
Construct the map for harder problemsMost exam problems are pigeonhole in disguise — the work is choosing what to map to what, so define the function explicitly.

Worked example

Show that among any 13 people, two share a birth month, and that some month has at least 2 of them.

Define f from the 13 people to the 12 months, sending each person to their birth month.
|domain| = 13 > 12 = |codomain|.
So f cannot be injective: two distinct people map to the same month.
Generalised form: some month has at least ⌈13/12⌉ = 2 people.

Answer. No injection exists from 13 people into 12 months, so at least two share a birth month.

Where marks get dropped

These are the specific errors that cost credit on pigeonhole consequences for injections questions — QED's rubric penalises each of them separately.

Swapping pigeons and holes, which yields a true-sounding but unjustified conclusion.
Using ⌊m/n⌋ instead of ⌈m/n⌉ in the generalised principle. The bound is a ceiling.
Not defining the map. "Obviously two must coincide" earns nothing; the function has to be exhibited.

Practise this until it is automatic

Unlimited fresh questions

QED generates new pigeonhole consequences for injections problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.

Marked like an examiner

Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.

Answer in real notation

A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.

Saved to your library

Every question you generate is kept and re-takeable as a timed exam, and your Functions mastery is tracked so you know when this is exam-ready.

Pigeonhole consequences for injections — frequently asked questions

What is the generalised pigeonhole principle?

With m objects in n boxes, some box contains at least ⌈m/n⌉ objects. The basic form is the case m > n, giving at least 2.

Does the converse hold?

If |A| ≤ |B| an injection exists, but a particular function need not be injective. Pigeonhole rules out injectivity; it never establishes it.

Where does this matter in computing?

Hash collisions are inevitable when the key space exceeds the table size, and no compression scheme can shorten every input — both are pigeonhole in one line.

The rest of Functions

Injective, surjective, bijective, composition, inverse. Each subtopic below has its own method, worked example and mark-losing traps.

Ready to make pigeonhole consequences for injections exam-proof?

Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.

Start practising free →