返回官网

Mathematical Thinking Questions — Interactive

Mathematical Thinking Questions

Interactive self-assessment guide for applicants to Mathematics with Computer Science at GTIIT.

A note to the reader

The purpose of these problems is not simply to obtain the answers. Finding the answer is easy; one can ask a search engine, or even an AI system. But that is not the point.

The only thing that really matters is the mathematical work that you do by yourself. Mathematics is not mainly about collecting correct answers. It is about understanding ideas, recognizing patterns, making definitions precise, finding examples, discovering counterexamples, and building arguments.

Do not rush. Take your time. Try examples. Make mistakes. Start again. Write down your reasoning.

You are not expected to solve all problems listed here.

Need a little help? You may choose to show hint buttons or answer buttons below. You can show support only for some later items, or for all items.

1. Eventually and frequently equal to a value

Definitions

Step 1 / 38

The first item is shown. Open later items when you are ready; previous items will remain visible.

Sequences often exhibit patterns. Some patterns are temporary, some repeat infinitely many times, and some eventually stabilize. In this section we introduce two simple but useful notions.

Let $(a_n)$ be a sequence, and let $c$ be a number.

We say that $(a_n)$ is eventually equal to $c$ if, from some point on, all its terms are equal to $c$. In other words, there exists a natural number $N$ such that

\[ a_n=c \]

for every $n\geq N$.

We say that $(a_n)$ is frequently equal to $c$ if the value $c$ appears infinitely many times in the sequence. Equivalently, for every natural number $N$, there exists some $n\geq N$ such that

\[ a_n=c. \]
1. Eventually and frequently equal to a value

Warm-up problems

Step 2 / 38

The first item is shown. Open later items when you are ready; previous items will remain visible.

(a)

Consider the sequence

\[ 1,1,1,1,1,\ldots \]

Is this sequence eventually equal to $1$? Is it frequently equal to $1$?

Every term of the sequence is equal to $1$.

Yes. It is eventually equal to $1$, for example with $N=1$. It is also frequently equal to $1$.

(b)

Consider the sequence

\[ 1,2,1,2,1,2,\ldots \]

Is this sequence eventually equal to $1$? Is it frequently equal to $1$? Is it frequently equal to $2$?

The values $1$ and $2$ alternate forever.

It is not eventually equal to $1$, because $2$ keeps appearing. It is frequently equal to both $1$ and $2$.

Need a hint or an answer? Return to the support buttons above.

1. Eventually and frequently equal to a value

Understanding the distinction

Step 3 / 38

The first item is shown. Open later items when you are ready; previous items will remain visible.

(a)

Consider the sequence

\[ 5,4,3,2,1,1,1,1,\ldots \]

Is this sequence eventually equal to $1$? Is it frequently equal to $1$? Is it frequently equal to another number?

Look at what happens from the fifth term onward.

It is eventually equal to $1$ and frequently equal to $1$. It is not frequently equal to $2$, $3$, $4$, or $5$, since each appears only once.

(b)

Consider the sequence

\[ 1,2,1,1,2,1,1,1,2,1,1,1,1,2,\ldots \]

Is this sequence eventually equal to $1$? Is it frequently equal to $1$? Is it frequently equal to $2$?

The blocks of $1$'s get longer, but the value $2$ still appears again and again.

It is not eventually equal to $1$, because $2$ appears infinitely many times. It is frequently equal to $1$ and frequently equal to $2$.

(c)

Can a sequence be frequently equal to $c$, but not eventually equal to $c$? Give an example or explain why this is impossible.

Try alternating $c$ with another value.

Yes. For example, if $d\neq c$, then $c,d,c,d,c,d,\ldots$ is frequently equal to $c$ but not eventually equal to $c$.

(d)

Can a sequence be eventually equal to $c$, but not frequently equal to $c$? Give an example or explain why this is impossible.

If from some point on all terms are $c$, how many times does $c$ appear?

No. Eventually equal to $c$ always implies frequently equal to $c$.

Need a hint or an answer? Return to the support buttons above.

1. Eventually and frequently equal to a value

Formula examples

Step 4 / 38

The first item is shown. Open later items when you are ready; previous items will remain visible.

(a)

Consider the sequence

\[ a_n=\left\lfloor \frac{2026}{n}\right\rfloor+2026. \]

Compute several terms of the sequence. Is $(a_n)$ eventually equal to $2026$?

Ask when $\left\lfloor 2026/n\right\rfloor=0$.

For $n>2026$, we have $0<2026/n<1$, so $\left\lfloor 2026/n\right\rfloor=0$. Hence $a_n=2026$ for all $n\geq 2027$. The sequence is eventually equal to $2026$.

(b)

Consider the sequence

\[ b_n=\frac{1}{n}. \]

Is $(b_n)$ eventually equal to $0$? Is it frequently equal to $0$? Does there exist $c>0$ and $d<0$ such that $b_n\geq c$ or $b_n\leq d$, for all $n\in\mathbb{N}$?

The terms get closer and closer to $0$, but no term is actually equal to $0$.

It is not eventually equal to $0$ and not frequently equal to $0$, since $1/n\neq 0$ for every $n$. There is no fixed $c>0$ such that $1/n\geq c$ for every $n$. Indeed, if $c>0$, then $1/c>0$, and we can choose a natural number $n>1/c$. It follows that

\[ 0<\frac{1}{n} Also, since $1/n>0$ for every $n$, there is no $d<0$ such that $1/n\leq d$ for all $n$.

Need a hint or an answer? Return to the support buttons above.

1. Eventually and frequently equal to a value

Conceptual questions

Step 5 / 38

The first item is shown. Open later items when you are ready; previous items will remain visible.

(a)

Can a sequence be eventually equal to two different numbers $c$ and $d$?

If a late term must be both $c$ and $d$, what follows?

Only if $c=d$. If $c\neq d$, this is impossible.

(b)

Can a sequence be frequently equal to two different numbers $c$ and $d$?

Think of alternating values.

Yes. If $c\neq d$, the sequence $c,d,c,d,c,d,\ldots$ is frequently equal to both $c$ and $d$.

Need a hint or an answer? Return to the support buttons above.

1. Eventually and frequently equal to a value

Challenge

Step 6 / 38

The first item is shown. Open later items when you are ready; previous items will remain visible.

(a)

Construct, if possible, a sequence that is frequently equal to $n$, for every natural number $n$.

Try writing blocks: $1$, then $1,2$, then $1,2,3$, then $1,2,3,4$, and so on.

One construction is

\[ 1,\quad 1,2,\quad 1,2,3,\quad 1,2,3,4,\quad \ldots \]

written as a single sequence:

\[ 1,1,2,1,2,3,1,2,3,4,\ldots \]

For each fixed $n$, the value $n$ appears in every block $1,2,\ldots,k$ with $k\geq n$, hence infinitely many times.

Need a hint or an answer? Return to the support buttons above.

2. Intersections of sets

Definitions

Step 7 / 38

The first item is shown. Open later items when you are ready; previous items will remain visible.

Sets allow us to collect objects and study them together. If $A$ and $B$ are sets, their intersection, denoted by $A\cap B$, is the set of all elements that belong to both $A$ and $B$.

Thus, $x\in A\cap B$ means that $x\in A$ and $x\in B$. If two sets have no elements in common, then $A\cap B=\emptyset$.

For three sets $A$, $B$, and $C$, the intersection $A\cap B\cap C$ is the set of all elements that belong to all three sets at the same time.

If $A_1,A_2,A_3,\ldots$ is a family of sets, then

\[ \bigcap_{n=1}^{\infty} A_n \]

is the set of all elements that belong to every one of $A_1,A_2,A_3,\ldots$.

2. Intersections of sets

Computing intersections

Step 8 / 38

The first item is shown. Open later items when you are ready; previous items will remain visible.

(a)

Find $A\cap B$, for

\[ A=\{1,2,3,4\},\qquad B=\{3,4,5,6\}. \]

Look for the elements that appear in both sets.

\[A\cap B=\{3,4\}.\]
(b)

Find $A\cap B$, for

\[ A=\{1,3,5,7\},\qquad B=\{2,4,6,8\}. \]

One set contains odd numbers and the other contains even numbers.

\[A\cap B=\emptyset.\]
(c)

Find $A\cap B$, $A\cap C$, $B\cap C$ and $A\cap B\cap C$, for

\[ A=\{1,2,3,4,5\},\quad B=\{2,4,6,8\},\quad C=\{4,5,6,7\}. \]

First compare two sets at a time. Then look for elements common to all three.

\[ A\cap B=\{2,4\},\quad A\cap C=\{4,5\},\quad B\cap C=\{4,6\}, \] \[ A\cap B\cap C=\{4\}. \]

Need a hint or an answer? Return to the support buttons above.

2. Intersections of sets

Constructing sets with prescribed intersections

Step 9 / 38

The first item is shown. Open later items when you are ready; previous items will remain visible.

(a)

Construct two different finite sets $A$ and $B$ such that

\[A\cap B=\{3,5\}.\]

Put $3$ and $5$ in both sets. Then add different extra elements to each set.

For example, $A=\{1,3,5\}$ and $B=\{3,5,7\}$.

(b)

Construct three different finite sets $A$, $B$, and $C$ such that

\[A\cap B\cap C=\{1,2\}.\]

Put $1$ and $2$ in all three sets. Add some different extra elements.

For example, $A=\{1,2,3\}$, $B=\{1,2,4\}$, $C=\{1,2,5\}$.

(c)

Construct three different finite sets $A$, $B$, and $C$ such that

\[A\cap B=\{1,2\}\quad\text{and}\quad A\cap B\cap C=\{1\}.\]

Make $1$ and $2$ belong to both $A$ and $B$, but put only $1$ in $C$.

For example, $A=\{1,2,3\}$, $B=\{1,2,4\}$, $C=\{1,5\}$.

(d)

Construct three different finite sets $A$, $B$, and $C$ such that $A\cap B\cap C=\emptyset$, but none of $A$, $B$, and $C$ is empty.

This is possible even if the sets are very small.

For example, $A=\{1\}$, $B=\{2\}$, $C=\{3\}$.

Need a hint or an answer? Return to the support buttons above.

2. Intersections of sets

Pairwise intersections and full intersection

Step 10 / 38

The first item is shown. Open later items when you are ready; previous items will remain visible.

(a)

Construct three different finite sets $A$, $B$, and $C$ such that

\[ A\cap B\neq\emptyset,\qquad A\cap C\neq\emptyset, \]

but

\[ B\cap C=\emptyset. \]

Let $A$ share one element with $B$ and a different element with $C$.

For example, $A=\{1,2\}$, $B=\{1\}$, $C=\{2\}$.

(b)

Construct three different finite sets $A$, $B$, and $C$ such that

\[ A\cap B\neq\emptyset,\qquad A\cap C\neq\emptyset,\qquad B\cap C\neq\emptyset, \]

but

\[ A\cap B\cap C=\emptyset. \]

Try to make each pair share a different element.

For example, $A=\{1,2\}$, $B=\{2,3\}$, $C=\{1,3\}$. Then every pair intersects, but no element belongs to all three sets.

Need a hint or an answer? Return to the support buttons above.

2. Intersections of sets

Infinite families of sets

Step 11 / 38

The first item is shown. Open later items when you are ready; previous items will remain visible.

(a)

For every natural number $n$, let $A_n=\{1,2,\ldots,n\}$. Notice that $A_n\subseteq A_{n+1}$ for every $n$.

Compute

\[ \bigcap_{n=1}^{\infty} A_n. \]

An element must belong to $A_1$ and also to every later set.

\[\bigcap_{n=1}^{\infty} A_n=\{1\}.\]
(b)

With the same sets $A_n=\{1,2,\ldots,n\}$, compute

\[ \bigcap_{n=100}^{\infty} A_n. \]

The sets are increasing. The smallest set in this tail is $A_{100}$.

\[\bigcap_{n=100}^{\infty} A_n=A_{100}=\{1,2,\ldots,100\}.\]
(c)

More generally, for a given $N\in\mathbb{N}$, compute

\[ \bigcap_{n=N}^{\infty} A_n. \]

Again, the smallest set in the family is $A_N$.

\[\bigcap_{n=N}^{\infty} A_n=A_N=\{1,2,\ldots,N\}.\]

Need a hint or an answer? Return to the support buttons above.

2. Intersections of sets

Challenges

Step 12 / 38

The first item is shown. Open later items when you are ready; previous items will remain visible.

(a)

Construct four finite sets $A$, $B$, $C$, and $D$ such that the intersection of any three of them is nonempty, but

\[ A\cap B\cap C\cap D=\emptyset. \]

Try using the set $\{1,2,3,4\}$, and let each set miss exactly one element.

One example is

\[ A=\{2,3,4\},\quad B=\{1,3,4\},\quad C=\{1,2,4\},\quad D=\{1,2,3\}. \]

The intersection of all four is empty, but the intersection of any three contains the element missing from the fourth set.

(b)

Can you generalize the previous construction? For a given natural number $n$, can you construct $n$ finite sets such that the intersection of any $n-1$ of them is nonempty, but the intersection of all $n$ sets is empty?

Use the set $\{1,2,\ldots,n\}$, and make the $i$-th set miss only $i$.

Let

\[ A_i=\{1,2,\ldots,n\}\setminus\{i\},\qquad i=1,\ldots,n. \]

The intersection of all $n$ sets is empty. But if we omit $A_i$, then the intersection of the remaining $n-1$ sets contains $i$.

(c)

Construct a family of sets

\[ A_1\supseteq A_2\supseteq A_3\supseteq\cdots \]

such that every $A_n$ is nonempty, but

\[ \bigcap_{n=1}^{\infty} A_n=\emptyset. \]

Try removing the first few natural numbers step by step.

Take

\[ A_n=\{n,n+1,n+2,\ldots\}. \]

Then $A_1\supseteq A_2\supseteq A_3\supseteq\cdots$, and every $A_n$ is nonempty. But no natural number belongs to every $A_n$, so the full intersection is empty.

Need a hint or an answer? Return to the support buttons above.

3. Countable sets

Definition and first idea

Step 13 / 38

The first item is shown. Open later items when you are ready; previous items will remain visible.

Some infinite sets can be listed one element after another, in a single infinite row. For example, the positive even integers can be listed as

\[ 2,4,6,8,10,\ldots \]

We say that a set $A$ is countable if its elements can be listed in a sequence

\[ a_1,a_2,a_3,\ldots \]

so that every element of $A$ appears somewhere in the list.

Equivalently, the elements of $A$ can be paired with the natural numbers. For the positive even integers, the pairing is $n\longleftrightarrow 2n$.

The order of the list is not important. What matters is that every element appears at some finite position.

3. Countable sets

First examples

Step 14 / 38

The first item is shown. Open later items when you are ready; previous items will remain visible.

(a)

List the elements of the set $\{10,20,30,40,\ldots\}$. Which element is paired with the natural number $n$?

Look at the common factor.

The list is $10,20,30,\ldots$. The number $n$ is paired with $10n$.

(b)

List the elements of the set of positive odd integers. Can you exhibit an explicit pairing?

The positive odd integers are $1,3,5,\ldots$.

The list is $1,3,5,\ldots$. The number $n$ is paired with $2n-1$.

(c)

List the elements of the set $\{1,4,9,16,25,\ldots\}$. Which element is paired with the natural number $n$?

These are squares.

The list is $1,4,9,16,\ldots$. The number $n$ is paired with $n^2$.

Need a hint or an answer? Return to the support buttons above.

3. Countable sets

More challenging examples

Step 15 / 38

The first item is shown. Open later items when you are ready; previous items will remain visible.

(a)

Is it possible to list all the negative integers?

Start with $-1$, then $-2$, then $-3$, and so on.

Yes: $-1,-2,-3,-4,\ldots$ lists all negative integers.

(b)

Is it possible to list all the integers? [Hint: Yes, it is possible.]

Try alternating positive and negative integers.

Yes. One list is $0,1,-1,2,-2,3,-3,\ldots$.

(c)

List the elements of the set of all integer multiples of $3$.

Use the list of all integers and multiply by $3$.

One list is $0,3,-3,6,-6,9,-9,\ldots$.

Need a hint or an answer? Return to the support buttons above.

3. Countable sets

Combining countable sets

Step 16 / 38

The first item is shown. Open later items when you are ready; previous items will remain visible.

(a)

Suppose that the elements of a set $A$ can be listed as $a_1,a_2,a_3,\ldots$ and the elements of a set $B$ can be listed as $b_1,b_2,b_3,\ldots$. Construct a list that contains all elements of $A\cup B$.

Alternate between the two lists.

One possible list is $a_1,b_1,a_2,b_2,a_3,b_3,\ldots$, skipping repeated elements if necessary.

(b)

Use the previous idea to list all numbers in

\[ \{1,3,5,7,\ldots\}\cup \{2,4,6,8,\ldots\}. \]

This union is the set of all positive integers.

One list is $1,2,3,4,5,6,\ldots$.

(c)

Suppose $A$ and $B$ are countable sets. Is $A\cup B$ countable? Explain.

Use the alternating list idea.

Yes. If $A$ and $B$ can be listed, then $A\cup B$ can be listed by alternating between the two lists and ignoring repetitions.

(d)

Suppose $A_1,A_2,A_3,\ldots$ are countable sets. Do you think the union

\[ A_1\cup A_2\cup A_3\cup\cdots \]

must be countable?

Imagine arranging the lists in rows and moving along diagonals.

Yes. A countable union of countable sets is countable. One can arrange the elements in an infinite table and list them by diagonals.

Need a hint or an answer? Return to the support buttons above.

3. Countable sets

Pairs of natural numbers

Step 17 / 38

The first item is shown. Open later items when you are ready; previous items will remain visible.

(a)

Consider the set $\mathbb{N}\times\mathbb{N}$ of all pairs $(m,n)$ of natural numbers. Try to list its elements.

A row-by-row list fails. Diagonals work better.

One beginning is $(1,1),(1,2),(2,1),(1,3),(2,2),(3,1),\ldots$.

(b)

A first attempt might be to list the pairs row by row:

\[ (1,1),(1,2),(1,3),(1,4),\ldots \]

Why does this attempt fail to list all pairs?

Do we ever leave the first row?

It never reaches pairs like $(2,1)$ or $(3,1)$, because it stays forever in the first row.

(c)

Try instead to list the pairs by diagonals:

\[ Diag_i=\{(n,m): n+m=i+1\}. \]
  1. Identify $Diag_1$, $Diag_2$ and $Diag_3$.
  2. Put, in a finite list, all the elements of $Diag_1\cup Diag_2\cup Diag_3$.
  3. List $\mathbb{N}\times\mathbb{N}$.
  4. Explain why every pair $(m,n)$ eventually appears.

A pair $(m,n)$ lies on the diagonal determined by $m+n$.

We have

\[ Diag_1=\{(1,1)\},\quad Diag_2=\{(1,2),(2,1)\},\quad Diag_3=\{(1,3),(2,2),(3,1)\}. \]

Every pair $(m,n)$ appears on the diagonal with index $m+n-1$.

(d)

Conclude that $\mathbb{N}\times\mathbb{N}$ is countable.

If every pair appears in the diagonal list, then the pairs can be listed.

Yes, $\mathbb{N}\times\mathbb{N}$ is countable.

Need a hint or an answer? Return to the support buttons above.

3. Countable sets

Rational numbers

Step 18 / 38

The first item is shown. Open later items when you are ready; previous items will remain visible.

(a)

Every positive rational number can be written as $\dfrac{p}{q}$, where $p$ and $q$ are natural numbers. This representation is not unique. Is there a way to represent them in a unique way? Explain why this relates the positive rational numbers to $\mathbb{N}\times\mathbb{N}$.

Each fraction gives a pair $(p,q)$.

Every positive rational number comes from some pair $(p,q)\in\mathbb{N}\times\mathbb{N}$. A unique representation is obtained by requiring $\gcd(p,q)=1$.

(b)

Use the previous subsection to argue that the set of positive rational numbers is countable.

List all pairs $(p,q)$ and then read them as fractions $p/q$.

Since $\mathbb{N}\times\mathbb{N}$ is countable, the fractions $p/q$ can be listed. Repetitions do not matter, so the positive rational numbers are countable.

(c)

Do you think the set of all rational numbers is countable? Explain how one might list them.

Combine positive rationals, negative rationals, and zero.

Yes. One can list $0$, then alternate positive and negative rational numbers: $q_1,-q_1,q_2,-q_2,\ldots$.

Need a hint or an answer? Return to the support buttons above.

3. Countable sets

A tough challenge

Step 19 / 38

The first item is shown. Open later items when you are ready; previous items will remain visible.

(a)

Is every infinite set countable? In other words, can the elements of every infinite set be listed in a single infinite row?

The real numbers are the standard place where this question becomes surprising.

No. There are infinite sets that are not countable, such as the real numbers between $0$ and $1$.

(b)

Consider the set $A$ of real numbers between $0$ and $1$ whose decimal expression only contains $0$'s and $1$'s, for example

\[ 0.001101010111\ldots \quad\text{or}\quad 0.1001010000111111\ldots \]

This set is much larger than it may first appear.

This is a good test set for diagonal thinking: each number corresponds to an infinite sequence of $0$'s and $1$'s.

(c)

Try to list all the elements of $A$. What difficulties appear?

Any proposed list can be challenged digit by digit.

The difficulty is that a list has rows, and each row has infinitely many digits. One can construct a new number by changing the diagonal digits.

(d)

Suppose someone claims to have listed all the elements of $A$:

\[ r_1,r_2,r_3,\ldots \]

Can you imagine a way to construct a new real number between $0$ and $1$ that is different from every number on the list?

Make the new number differ from $r_1$ in the first digit, from $r_2$ in the second digit, and so on.

This is Cantor's diagonal idea. If the $n$-th digit of $r_n$ is $0$, choose the $n$-th digit of the new number to be $1$; if it is $1$, choose $0$. The new number differs from $r_n$ in the $n$-th digit, so it is not on the list.

Need a hint or an answer? Return to the support buttons above.

4. The Pigeonhole Principle

The principle

Step 20 / 38

The first item is shown. Open later items when you are ready; previous items will remain visible.

The Pigeonhole Principle is a simple combinatorial idea with many surprising consequences. If more than $n$ objects are placed into $n$ boxes, then at least one box contains at least two objects.

For example, if $8$ students are in a room, then at least two of them were born on the same day of the week, because there are only $7$ days of the week.

The main difficulty is often not applying the principle, but deciding what the boxes should be.

4. The Pigeonhole Principle

First examples

Step 21 / 38

The first item is shown. Open later items when you are ready; previous items will remain visible.

(a)

There are $13$ students in a room. Show that at least two of them were born in the same month.

Use the $12$ months as boxes.

There are $13$ students and only $12$ months, so two students must share a birth month.

(b)

There are $27$ students in a room. Show that at least three of them were born in the same month.

If each month had at most two students, how many students could there be?

If every month had at most two students, there would be at most $24$ students. Since there are $27$, some month has at least three.

(c)

A drawer contains only black socks and white socks. How many socks must you take to be sure that you have two socks of the same color? Explain your answer as a consequence of the Pigeonhole Principle. Which are the boxes?

The boxes are the two colors.

You need $3$ socks. With $3$ objects and $2$ boxes, one color must contain at least two socks.

Need a hint or an answer? Return to the support buttons above.

4. The Pigeonhole Principle

Remainders as boxes

Step 22 / 38

The first item is shown. Open later items when you are ready; previous items will remain visible.

(a)

Choose any $6$ integers. Show that at least two of them have the same remainder when divided by $5$.

The possible remainders are $0,1,2,3,4$.

There are $6$ integers and only $5$ possible remainders, so two have the same remainder modulo $5$.

(b)

Choose any $11$ integers. Show that at least two of them differ by a multiple of $10$.

Two integers differ by a multiple of $10$ exactly when they have the same remainder modulo $10$.

There are $10$ possible remainders modulo $10$ and $11$ integers. Two share a remainder, hence their difference is divisible by $10$.

(c)

Choose any $n+1$ integers. Show that there are two of them such that their difference is divisible by $n$.

Use remainders modulo $n$ as boxes.

There are $n$ possible remainders modulo $n$, and $n+1$ integers. Two have the same remainder, so their difference is divisible by $n$.

Need a hint or an answer? Return to the support buttons above.

4. The Pigeonhole Principle

Choosing the boxes

Step 23 / 38

The first item is shown. Open later items when you are ready; previous items will remain visible.

(a)

Choose any $6$ numbers from

\[ \{1,2,3,4,5,6,7,8,9,10\}. \]

Show that at least two of the chosen numbers have sum $11$.

Group the numbers into pairs with sum $11$.

Use the boxes $\{1,10\}$, $\{2,9\}$, $\{3,8\}$, $\{4,7\}$, $\{5,6\}$. Choosing $6$ numbers from $5$ boxes forces two chosen numbers to be in the same box, hence to sum to $11$.

(b)

Explain why the boxes $\{1,10\}$, $\{2,9\}$, $\{3,8\}$, $\{4,7\}$, $\{5,6\}$ prove the previous result.

Each box contains exactly two numbers with the desired property.

Since there are $5$ boxes and $6$ chosen numbers, one box contains two chosen numbers. The two numbers in any one box have sum $11$.

(c)

Choose any $7$ numbers from

\[ \{1,2,3,\ldots,12\}. \]

Show that at least two of the chosen numbers are consecutive.

Use boxes $\{1,2\}$, $\{3,4\}$, and so on.

There are $6$ boxes: $\{1,2\},\{3,4\},\ldots,\{11,12\}$. Choosing $7$ numbers forces two in the same box, and those two are consecutive.

(d)

In the previous problem, what are the useful boxes?

Pair consecutive numbers.

\[\{1,2\},\{3,4\},\{5,6\},\{7,8\},\{9,10\},\{11,12\}.\]
(e)

Choose any $7$ numbers from

\[ \{1,2,3,\ldots,13\}. \]

Is it necessarily true that two of the chosen numbers are consecutive? Give a proof or a counterexample.

Try choosing every other number.

No. The set $\{1,3,5,7,9,11,13\}$ has $7$ numbers and no two are consecutive.

Need a hint or an answer? Return to the support buttons above.

4. The Pigeonhole Principle

Geometric examples

Step 24 / 38

The first item is shown. Open later items when you are ready; previous items will remain visible.

(a)

Choose any $5$ points inside a square of side length $2$. Show that at least two points are at distance at most $\sqrt{2}$ from each other.

Divide the large square into four unit squares.

Four unit squares are the boxes. With $5$ points, two lie in the same unit square. The maximum distance between two points in a unit square is its diagonal, $\sqrt{2}$.

(b)

Explain why dividing the square into four unit squares is useful in the previous problem.

The diameter of each small square is exactly $\sqrt{2}$.

It creates $4$ boxes, each with the property that any two points inside the same box are at distance at most $\sqrt{2}$.

(c)

Choose any $10$ points inside an equilateral triangle of side length $3$. Show that at least two points are at distance at most $1$ from each other.

Divide the triangle into $9$ equilateral triangles of side length $1$.

The $9$ small triangles are the boxes. With $10$ points, two lie in the same small triangle, whose diameter is $1$.

(d)

Suppose every point in the plane is colored either red or blue. Show that there exist two points of the same color at distance exactly $1$ from each other.

Hint: consider the vertices of an equilateral triangle of side length $1$.

There are $3$ vertices but only $2$ colors.

Among the three vertices of an equilateral triangle of side $1$, two must have the same color. Those two vertices are at distance $1$.

Need a hint or an answer? Return to the support buttons above.

4. The Pigeonhole Principle

Challenges

Step 25 / 38

The first item is shown. Open later items when you are ready; previous items will remain visible.

(a)

Choose any $n+1$ numbers from $\{1,2,3,\ldots,2n\}$. Show that at least two have sum $2n+1$.

Pair $1$ with $2n$, $2$ with $2n-1$, and so on.

Use boxes $\{1,2n\}$, $\{2,2n-1\}$, ..., $\{n,n+1\}$. There are $n$ boxes and $n+1$ chosen numbers.

(b)

Choose any $n+1$ numbers from $\{1,2,3,\ldots,2n\}$. Show that at least two are relatively prime.

Hint: think about consecutive integers.

Use boxes of consecutive pairs.

Pair the numbers as $\{1,2\}$, $\{3,4\}$, ..., $\{2n-1,2n\}$. Two chosen numbers must lie in the same pair, and consecutive integers are relatively prime.

(c)

Choose any $n+1$ numbers from $\{1,2,3,\ldots,2n\}$. Show that at least one of the chosen numbers divides another.

Hint: write each number in the form $2^k m$, where $m$ is odd.

The odd part $m$ can only be one of $1,3,5,\ldots,2n-1$.

There are $n$ possible odd parts. With $n+1$ chosen numbers, two have the same odd part: $2^a m$ and $2^b m$. The one with the smaller power of $2$ divides the other.

Need a hint or an answer? Return to the support buttons above.

5. Build the proof

What is the task?

Step 26 / 38

The first item is shown. Open later items when you are ready; previous items will remain visible.

A proof is not only a collection of true statements. The statements must also appear in the correct logical order. Some statements depend on previous ones; some introduce definitions; some use the hypothesis; and some give the final conclusion.

In this section, each problem gives a mathematical claim and a list of statements in the wrong order. Rearrange the statements to obtain a correct proof.

5. Build the proof

Warm-up proofs

Step 27 / 38

The first item is shown. Open later items when you are ready; previous items will remain visible.

Problem 1

Claim. If $a$ and $b$ are even integers, then $a+b$ is even.

Rearrange:

  1. Therefore, $a+b$ is even.
  2. Since $a$ and $b$ are even, there exist integers $m,n$ such that $a=2m$ and $b=2n$.
  3. Then $a+b=2m+2n=2(m+n)$.
  4. Since $m+n$ is an integer, $a+b$ is divisible by $2$.

Start by using the meaning of “even”.

Correct order: (b), (c), (d), (a).

Problem 2

Claim. If $a$ and $b$ are odd integers, then $ab$ is odd.

Rearrange:

  1. Since $m,n$ are integers, $2mn+m+n$ is an integer.
  2. Then $ab=(2m+1)(2n+1)$.
  3. Therefore, $ab$ is odd.
  4. Since $a$ and $b$ are odd, there exist integers $m,n$ such that $a=2m+1$ and $b=2n+1$.
  5. Expanding, $ab=4mn+2m+2n+1=2(2mn+m+n)+1$.

Begin with the definition of odd integers.

Correct order: (d), (b), (e), (a), (c).

Need a hint or an answer? Return to the support buttons above.

5. Build the proof

Proofs by contradiction

Step 28 / 38

The first item is shown. Open later items when you are ready; previous items will remain visible.

Problem 3

Claim. If $n^2$ is even, then $n$ is even.

Rearrange:

  1. Therefore, if $n^2$ is even, then $n$ must be even.
  2. Suppose, for contradiction, that $n$ is odd.
  3. Hence $n^2$ is odd.
  4. Then there exists an integer $k$ such that $n=2k+1$.
  5. Thus $n^2=(2k+1)^2=4k^2+4k+1=2(2k^2+2k)+1$.
  6. This contradicts the assumption that $n^2$ is even.

Because this is a contradiction proof, begin by assuming the opposite of what you want to prove.

Correct order: (b), (d), (e), (c), (f), (a).

Need a hint or an answer? Return to the support buttons above.

5. Build the proof

Proofs with sets

Step 29 / 38

The first item is shown. Open later items when you are ready; previous items will remain visible.

Problem 4

Claim. Prove the inclusion

\[ A\cap(B\cup C)\subseteq (A\cap B)\cup(A\cap C). \]

Rearrange:

  1. Therefore, $x\in (A\cap B)\cup(A\cap C)$.
  2. This proves the inclusion.
  3. Suppose $x\in A\cap(B\cup C)$.
  4. Hence $x\in A$ and $x\in B\cup C$.
  5. Therefore $x\in B$ or $x\in C$.
  6. If $x\in B$, then $x\in A\cap B$.
  7. If $x\in C$, then $x\in A\cap C$.

Start by taking an arbitrary element of the left-hand side.

Correct order: (c), (d), (e), (f) and (g), (a), (b). Statements (f) and (g) are the two cases.

Problem 5

Claim. Prove the reverse inclusion

\[ (A\cap B)\cup(A\cap C)\subseteq A\cap(B\cup C). \]

Write your own proof. Try to imitate the structure of the previous problem.

Start with $x\in (A\cap B)\cup(A\cap C)$ and split into cases.

If $x\in A\cap B$, then $x\in A$ and $x\in B$, so $x\in B\cup C$, hence $x\in A\cap(B\cup C)$. Similarly, if $x\in A\cap C$, then $x\in A\cap(B\cup C)$.

Need a hint or an answer? Return to the support buttons above.

5. Build the proof

Divisibility

Step 30 / 38

The first item is shown. Open later items when you are ready; previous items will remain visible.

Problem 6

Claim. For every integer $n$, the number $n^3-n$ is divisible by $3$.

Rearrange:

  1. Therefore, one of $n-1,n,n+1$ is divisible by $3$.
  2. Hence $n^3-n$ is divisible by $3$.
  3. We can factor: $n^3-n=n(n-1)(n+1)$.
  4. Among any three consecutive integers, exactly one is divisible by $3$.

Factor first.

Correct order: (c), (d), (a), (b).

Need a hint or an answer? Return to the support buttons above.

5. Build the proof

A classical proof

Step 31 / 38

The first item is shown. Open later items when you are ready; previous items will remain visible.

Problem 7

Claim. There are infinitely many prime numbers.

Rearrange:

  1. Therefore, $q$ is a prime not among $p_1,p_2,\ldots,p_k$.
  2. Suppose, for contradiction, that there are only finitely many primes: $p_1,p_2,\ldots,p_k$.
  3. Let $N=p_1p_2\cdots p_k+1$.
  4. Hence there must be infinitely many primes.
  5. Let $q$ be a prime divisor of $N$.
  6. None of the primes $p_1,p_2,\ldots,p_k$ divides $N$, since each leaves remainder $1$.
  7. This contradicts the assumption that the list contained all primes.

Start by assuming there are finitely many primes, then construct a new number.

Correct order: (b), (c), (e), (f), (a), (g), (d).

Need a hint or an answer? Return to the support buttons above.

5. Build the proof

Challenge

Step 32 / 38

The first item is shown. Open later items when you are ready; previous items will remain visible.

Problem 8

Write a proof, by contradiction, that $\sqrt{2}$ is irrational.

You may assume as starting point that

\[ \sqrt{2}=\frac{a}{b}, \]

where $a$ and $b$ are positive integers with no common factor. Then write an integral equation that $a$ and $b$ should satisfy.

Square both sides and clear denominators.

Squaring gives $2=a^2/b^2$, hence $a^2=2b^2$. Thus $a^2$ is even, so $a$ is even. Write $a=2k$. Then $4k^2=2b^2$, so $b^2=2k^2$, hence $b$ is even. This contradicts that $a$ and $b$ have no common factor.

Need a hint or an answer? Return to the support buttons above.

6. Sequences and formulas

Definition and first idea

Step 33 / 38

The first item is shown. Open later items when you are ready; previous items will remain visible.

A sequence is a list of numbers written in a definite order:

\[ a_1,a_2,a_3,a_4,\ldots \]

The number $a_n$ is called the $n$-th term of the sequence.

Sometimes a sequence is described by giving its first few terms. Sometimes it is described by a formula. A useful skill is to move between the first terms of a sequence and a formula for its $n$-th term.

6. Sequences and formulas

Computing terms from a formula

Step 34 / 38

The first item is shown. Open later items when you are ready; previous items will remain visible.

(a)

Compute the first six terms of $a_n=(-1)^n$.

Substitute $n=1,2,3,4,5,6$.

\[-1,1,-1,1,-1,1.\]
(b)

Compute the first six terms of $b_n=(-1)^{n+1}$.

The exponent is one more than before.

\[1,-1,1,-1,1,-1.\]
(c)

Compare the two sequences above. How are they similar? How are they different?

Both alternate between $1$ and $-1$.

They have the same two values, but start with different signs. One is the negative of the other.

(d)

Compute the first six terms of $c_n=2(-1)^{n+1}$.

Use the sequence from part (b) and multiply by $2$.

\[2,-2,2,-2,2,-2.\]
(e)

Compute the first six terms of $d_n=2+2(-1)^{n+1}$.

Start from $2(-1)^{n+1}$ and add $2$.

\[4,0,4,0,4,0.\]

Need a hint or an answer? Return to the support buttons above.

6. Sequences and formulas

Finding formulas

Step 35 / 38

The first item is shown. Open later items when you are ready; previous items will remain visible.

(a)

Find a formula for $1,-1,1,-1,\ldots$.

Compare with $(-1)^n$ and $(-1)^{n+1}$.

\[a_n=(-1)^{n+1}.\]
(b)

Find a formula for $2,-2,2,-2,\ldots$.

Multiply the previous sequence by $2$.

\[a_n=2(-1)^{n+1}.\]
(c)

Find a formula for $4,0,4,0,\ldots$.

Think of it as a constant part plus an alternating part.

\[a_n=2+2(-1)^{n+1}.\]
(d)

Find a formula for $3,7,3,7,\ldots$.

The average is $5$, and the deviation is $2$.

\[a_n=5-2(-1)^{n+1}\quad\text{or}\quad a_n=5+2(-1)^n.\]
(e)

Find a formula for $10,20,10,20,\ldots$.

The average is $15$, and the deviation is $5$.

\[a_n=15-5(-1)^{n+1}\quad\text{or}\quad a_n=15+5(-1)^n.\]

Need a hint or an answer? Return to the support buttons above.

6. Sequences and formulas

Alternating between two values

Step 36 / 38

The first item is shown. Open later items when you are ready; previous items will remain visible.

(a)

Let $a$ and $b$ be two given numbers. Find a formula for $a,b,a,b,\ldots$.

Use the average $(a+b)/2$ and half-difference $(a-b)/2$.

\[x_n=\frac{a+b}{2}+\frac{a-b}{2}(-1)^{n+1}.\]
(b)

Check your formula when $a=1$ and $b=-1$.

The average is $0$ and the half-difference is $1$.

\[x_n=(-1)^{n+1}.\]
(c)

Check your formula when $a=4$ and $b=0$.

The average is $2$ and the half-difference is $2$.

\[x_n=2+2(-1)^{n+1}.\]
(d)

Explain why $a,b,a,b,\ldots$ can be thought of as a constant part plus an alternating part.

The midpoint between $a$ and $b$ is constant.

The sequence oscillates around the average $(a+b)/2$, moving alternately by $+(a-b)/2$ and $-(a-b)/2$.

(e)

Show that one possible formula is

\[x_n=\frac{a+b}{2}+\frac{a-b}{2}(-1)^{n+1}.\]

Evaluate separately for odd $n$ and even $n$.

If $n$ is odd, then $(-1)^{n+1}=1$, so $x_n=a$. If $n$ is even, then $(-1)^{n+1}=-1$, so $x_n=b$.

Need a hint or an answer? Return to the support buttons above.

6. Sequences and formulas

Looking for structure

Step 37 / 38

The first item is shown. Open later items when you are ready; previous items will remain visible.

(a)

In the formula $x_n=\frac{a+b}{2}+\frac{a-b}{2}(-1)^{n+1}$, what is the role of $\frac{a+b}{2}$?

It is the midpoint between $a$ and $b$.

It is the constant part, or average, around which the sequence alternates.

(b)

What is the role of $\frac{a-b}{2}(-1)^{n+1}$?

It changes sign depending on the parity of $n$.

It is the alternating part that moves the value from the average to either $a$ or $b$.

(c)

Explain why the formula gives $a$ when $n$ is odd and $b$ when $n$ is even.

Use $(-1)^{n+1}=1$ for odd $n$ and $-1$ for even $n$.

Odd $n$ gives $\frac{a+b}{2}+\frac{a-b}{2}=a$. Even $n$ gives $\frac{a+b}{2}-\frac{a-b}{2}=b$.

(d)

Find another way to describe the same sequence using cases:

\[ x_n= \begin{cases} ?, & n \text{ odd},\\ ?, & n \text{ even}. \end{cases} \]

Read the sequence directly: first term $a$, second term $b$.

\[ x_n= \begin{cases} a, & n \text{ odd},\\ b, & n \text{ even}. \end{cases} \]

Need a hint or an answer? Return to the support buttons above.

6. Sequences and formulas

Challenges

Step 38 / 38

The first item is shown. Open later items when you are ready; previous items will remain visible.

(a)

Find a formula for $a,b,c,a,b,c,\ldots$, where $a$, $b$, and $c$ are given numbers.

Using cases modulo $3$ is natural.

One clear rule is

\[ x_n= \begin{cases} a, & n\equiv 1\pmod 3,\\ b, & n\equiv 2\pmod 3,\\ c, & n\equiv 0\pmod 3. \end{cases} \]
(b)

Find a formula, or a clear rule, for $1,2,3,1,2,3,\ldots$.

Again use the remainder of $n$ modulo $3$.

\[x_n=((n-1)\bmod 3)+1.\]
(c)

Can the same sequence be described by two different formulas? Give an example or explain why not.

Think of the alternating sequence.

Yes. For example, $(-1)^n$ and $\cos(n\pi)$ describe the same sequence for $n=1,2,3,\ldots$.

Need a hint or an answer? Return to the support buttons above.

Interactive prototype with six sections. Each step opens progressively; optional hints and answers can be enabled above.