Coursify

Bijections in the Pigeonhole Model: When Can a Function Be Both One-to-One and Onto?

Bijections in the Pigeonhole Model: When Can a Function Be Both One-to-One and Onto?

Verified Sources
Sep 12, 2026

Let PP be the set of pigeons with ∣P∣=m|P|=m and let HH be the set of boxes (pigeonholes) with ∣H∣=n|H|=n. A function f:P→Hf: P \to H is:

  • keyword if f(p1)=f(p2)f(p_1)=f(p_2) implies p1=p2p_1=p_2.
  • keyword if for every h∈Hh\in H there exists p∈Pp\in P with f(p)=hf(p)=h.
  • keyword.

For finite sets, a function f:P→Hf: P\to H can be both one-to-one and onto (i.e., keyword exists) iff the sets have the same cardinality: m=nm=n.

This directly answers the multiple-choice options: only case (ii) works.

Bijections, Injective and Surjective Functions (Intro to Functions)

Key finite-set facts (cardinality constraints)

For a function f:P→Hf: P \to H with ∣P∣=m|P|=m and ∣H∣=n|H|=n:

  1. Injective (11–11) is possible only if the domain is no larger than the codomain:
    If m>nm>n, then by the pigeonhole principle you cannot assign mm distinct pigeons to only nn boxes without two pigeons landing in the same box.

  2. Surjective (onto\text{onto}) is possible only if the domain is at least as large as the codomain:
    If m<nm<n, then there are not enough pigeons to cover all nn boxes.

  3. Therefore, bijective (both 11–11 and onto) requires both inequalities simultaneously:

    • injective requires m≤nm \le n
    • surjective requires m≥nm \ge n

    Together these imply m=nm=n.

A compact way to state the result:

  • keyword. So the function is one-to-one and onto exactly when m=nm=n.

Choose the correct option (proof by contradictions using injective/surjective requirements)

  1. 1
    Step 1

    Model the assignment of pigeons to boxes as a function f:P→Hf:P\to H where ∣P∣=m|P|=m and ∣H∣=n|H|=n.

  2. 2
    Step 2

    If m>nm>n, then injectivity fails because you would need mm distinct images inside a codomain of only nn boxes.

  3. 3
    Step 3

    If m<nm<n, then surjectivity fails because you cannot cover nn boxes using only mm pigeons.

  4. 4
    Step 4

    To be both injective and surjective, both m≤nm\le n and m≥nm\ge n must hold, hence m=nm=n.

  5. 5
    Step 5

    Option (ii) m=nm=n.

Pro Tip

For finite sets, bijection is governed purely by cardinality: ff can be one-to-one and onto only when the counts match (m=nm=n).

Common mistake

Thinking that m<nm<n could still be onto by “reusing” boxes is correct for surjectivity only if boxes are fewer or equal; but the direction is strict: onto requires at least as many pigeons as boxes (m≥nm\ge n).

Feasibility of being one-to-one and onto (bijective)

For a function from m pigeons to n boxes (finite sets).

How the logic narrows the cases

Need injective

Step A

Injective requires m≤nm \le n (otherwise pigeonhole collisions are forced)."

Need surjective

Step B

Surjective requires m≥nm \ge n (otherwise some boxes remain empty)."

Both together

Step C

Only m=nm=n satisfies both simultaneously."

Answer & quick explanations

Bijection in the Pigeonhole Setting

1 / 4
Question · Term

If $f:P\to H$ is one-to-one, what inequality must hold for finite sets?

Click to reveal
Answer · Definition

You must have m≤nm \le n (domain size cannot exceed codomain size).

Knowledge Check

Question 1 of 4
Q1Single choice

Let ∣P∣=m|P|=m pigeons and ∣H∣=n|H|=n boxes. For a function f:P→Hf:P\to H to be both one-to-one and onto (bijective), which case must hold?

Explore Related Topics

1

Algorithm Property for Clear, Unambiguous Steps: Definiteness

The course clarifies that definiteness is the algorithm property requiring every step to be precise and have exactly one interpretation, distinguishing it from finiteness, effectiveness, and generality.

  • Definiteness: each instruction is specified so precisely that only one meaning is possible.
  • Finiteness concerns termination, effectiveness concerns executability, and generality concerns applicability to all valid inputs.
  • Example: “repeat 3 times” is definite, while “repeat several times” is not.
  • Exam tip: associate words like “clear,” “precise,” or “unambiguous” with definiteness.
  • Algorithm quality can be expressed as Algorithm quality={definiteness, finiteness, effectiveness, input/output clarity} \text{Algorithm quality} = \{\text{definiteness},\ \text{finiteness},\ \text{effectiveness},\ \text{input/output clarity}\}.
2

Maximum number of edges in a bipartite graph: why $\lfloor n^2/4\rfloor$ is optimal

3

Object-Based Logical Models: Logical, View, or Physical Level?

Browse all research articles