## Problem of the week at Lebesgue

### Put a bunch of mathematicians together, and it's just a matter of time!

Besides our grand mission of redefining digital marketing and online advertising using advanced mathematical models, statistics, and more than anything creativity, at Lebesgue we also breed a special sort of culture.

We love whiteboards here and we use them for everything, with one in every major room. In the “dev room”, at the corner of the main whiteboard (it’s a huge 2 meter tall thing leaning against the wall) we started writing down interesting brain teasers and math problems. Of course, I just had to write about it!

The problems are in general accessible to anyone and do not require any specialized maths knowledge.

You can find the latest POTW here!

### Week 1

Let $p$ be a random palindromic1 number such that $1000 \le p \le 10000$.

What is the probability that $p^2$ is divisible by $7$ (formally notated as $7|p^2$)?

#### Solution

Not all numbers between $1000$ and $10000$ are palindromes (for example, 1001 is, but 1002 isn’t), so we first have to narrow down our options for $p$ to be able to work on the rest of the problem.

The number $p$ must be read the same forwards and backward, and thus its first digit is the same as the last, and the second same as the third, for which the formal digit notation is $p = \overline{abba}$. Now, to figure out how many numbers satisfy this, we can simply multiply the number of options for digits $a$ and $b$. Since $p$ is a four digit number, $a$ cannot be zero, which means that the number of options for $p$ is $9 \cdot 10 = 90$.

Now we can move onto the other part, checking divisibility by 7. We can simplify this check by noticing that if a number is divisible 7, its square is divisible as well. For example, if a number is divisible by 7 then it can be written as $7m$ so its square is $(7m)^2 = 7^2 m^2 = 7 (7m^2) = 7m'$ which is obviously divisible by 7 (and vice versa). We only have to check if $p$ is divisible by 7, which is easier.

Using the above notation $p = \overline{abba}$ we can break it down into its place values, getting $p = 1000a + 100b + 10b +a = 1001a + 110b$. We know $1001 = 7 \cdot 143$ so it is divisible by 7, but $110 \approx 7 \cdot 15.714$ so it isn’t.

If we add a number divisible by 7 with one that isn’t, the result isn’t divisible by 7. Since 110 isn’t divisible by 7, we have to either multiply it with one that is or eliminate it, hence, $b$ can either be 0 or 7, and $a$ can be any digit from 1 to 9.

The total numbers of $p$ which are divisible by 7 is $2 \cdot 9 = 18$, and the probability that we pick a $p$ divisible by 7 is simply the number of options that satisfy the divisibility condition divided by the total number of options $18 / 90 = 0.2$.

### Week 2

Let $a_n$ and $b_n$ be arithmetic sequences2, and $n$ a positive whole number such that:

• $a_1 = b_1 = 1 < a_n < b_n$
• $a_n b_n = 2010$

What is the largest possible value of $n$?

#### Solution

Since $a_n b_n = 2010$, $a_n$ and $b_n$ must be factors of 2010. The applicable factors of 2010 are 2, 3, 5, 6, 10, 15, 30, 67, 134, 201, 335, 402, 670, 1005, since $1 < a_n < b_n$.

Now, with $a_n < b_n$ we can divide the factors between them. We can do this in two ways - either noticing that $30 \cdot 67 = 2010$ and arranging $a_n$ and $b_n$ in pairs from that factor, or by noticing that $a_n$ must be smaller than the root of 2010, hence $a_n < 44$ since $a_n$ is an integer. That means that the largest possible value for $a_n$ is 30.

We can transform the above formulas for the arithmetic sequences into $a_n - 1 = d_a(n-1)$ and $b_n - 1 = d_b(n-1)$. The possible value pairs for $d_a(n-1)$ and $d_b(n-1)$ are in the table, and to maximize $n$, we should maximize $n-1$. $d_a$ and $d_b$ are coprime (otherwise we could get a bigger $n$ by simply adding more steps), $n-1$ is the greatest common factor of these two. We can compare the values of $n-1$ for different pairs below.

$d_a(n-1)$ $d_b(n-1)$ $n-1$ (GCF)
1 1004 1
2 669 1
4 401 1
5 334 1
9 200 1
14 133 7
29 66 1

Since the largest value of $n-1$ is 7, the largest possible value is $n = 8$.

### Week 3

In how many ways can we move from the point $(-4, -4)$ to the point $(4,4)$, without entering the square $\{ (x,y): -2 \le x, y \le 2 \}$?

• The only movement premitted is to the right by one or up by one.
• We are allowed to touch the edge of the square, but not enter it.

#### Solution

What we are solving here is a North-East lattice path problem. The steps up by one are called North steps, and the steps to the right East steps. Since we can only do N and E, we cannot go back on ourselves. That means that the number of ways we can get to a point is the sum of the paths to adjecent points.

Example: There is only one way to start - bottom left. The points on the bottom edge all have only one way to get to them. The points on top, on the other hand can be reached multiple ways. The first one has only one, going straight up from the starting point. The second can be reached either from the bottom or from the left, so adding up the number of ways to reach those (which is 1 for each), we get two. By analogy, the third has three, and the final, goal point has four, as shown in the diagram.

Now, we can apply the same logic to our problem. For points in the square, we will simply say there are zero ways to get to them, and calculate as such. The number of ways to get to each point is written under it.

This yields the final solution of 2122.

1. A palindrome is a word, number, phrase, or other sequence of characters which reads the same backward as forward, such as madam or 1001. ↩︎

2. An arithmetic progression or arithmetic sequence is a sequence of numbers such that the difference between the consecutive terms is constant. For instance, the sequence 5, 7, 9, 11, 13, 15… is an arithmetic progression with a common difference of 2. ↩︎