Problems

Suppose there is an \(7 \times 7\) grid. We would like to travel from the bottom left corner to the top right corner in exactly 14 steps. A step is from one point on the grid to another point via a segment of length 1. How many paths are there? The picture below shows one possible path on the grid.

In an office, at various times during the day, the boss gives the secretary a letter to type, each time putting the letter on top of the pile of the secretary’s in-box. When there is time, the secretary takes the top letter off the pile and types it. There are nine letters to be typed during the day, and the boss delivers them in the order \(1,2,3,4,5,6,7,8,9\). While leaving for lunch, the secretary tells a colleague that letter 8 has already been typed, but says nothing else about the morning’s typing. The colleague wonders which of the nine letters remain to be typed after lunch and in what order they will be typed. Base upon the above information, how many such after-lunch orders are possible? (That there are no letters left to be typed is one of the possibilities.)

A library keeps track of its books by a code with two (not necessarily different) letters taken from A to Z, followed by a three digit number from 000 to 999. What is the maximum number of books one can keep in the library and still tell them apart by looking at their codes?

There is a secret gathering of a group of \(n\) aliens in a very dark room. You cannot see anyone in the room, but you hear the following questions.

1. “Is at least one of us a Goop?"

2. “Is the number of Goops amongst us an even number?"

3. “Is the number of Goops amongst us a multiple of 3?"

4. \(\dots\)

5. “Is the number of Goops amongst us a multiple of \(n\)?"

What are all the possible values of \(n\) such that this gathering can happen? Note that each of the \(n\) aliens have asked exactly one question.

You meet a group of \(n\) aliens. The first alien asks “is at least one of us a Goop?", the second alien asks “are at least two of us Goops?", the third asks “are at least three of us Goops?" and so on until the final one says “are at least \(n\) of us Goops?".

How many Goops are there?

Suppose you only knew the formula of a triangle for right-angled triangles. That is, if a base with length \(b\) and a height \(h\) of a triangle meet at a right angle, you know that the area of the triangle is \(\frac{1}{2}bh\). Can you prove the usual area formula for a general triangle?

There is a pair of parallel lines. The point \(A\) and \(B\) lie on one of the lines. The point \(C\) and \(D\) lies on the other line. We can form triangles \(\triangle ABC\) and \(\triangle ABD\). Prove that the areas of triangles \(\triangle ABC\) and \(\triangle ABD\) are equal.

The pigeonhole principle is often called “Dirichlet’s box principle". Dirichlet made good use of this tool to show a fundamental result in Diophantine approximation, now commonly known as the Dirichlet Approximation Theorem. You will now prove it yourself!

Suppose \(\alpha\) is any irrational real number and \(N\geq 1\) is any positive integer. Show that there is an integer \(1\leq q\leq N\) and an integer \(p\) such that \[\left| q \alpha - p \right| < \frac{1}{N}.\]

What’s the sum of the Fibonacci numbers \(F_0+F_1+F_2+...+F_n\)?

What’s the sum \(\frac{F_2}{F_1}+\frac{F_4}{F_2}+\frac{F_6}{F_3}+...+\frac{F_{18}}{F_9}+\frac{F_{20}}{F_{10}}\)?