How many non-decreasing functions [Solutions]

The problem was to find the number of ordered pairs $x = (x_1, x_2, \dots, x_n)$ such that $x_i \le x_{i+1}$ and $1 \le x_i \le m$ for all $i$, $x_i$ being a natural number.

Solution

---

We will present two solutions.

Solution 1)

The first solution uses what is called the Stars and Bars approach.

For each $k \in \{1, 2, \dots, m\}$ you look at exactly how many $x_i = k$. Call this number $y_k$ (note, it could be $0$).

We must have that $y_1 + y_2 + \dots + y_m = n$, with $0 \le y_i \le n$.

Now given a $y = (y_1, y_2, \dots, y_m)$ we can easily map this back to the $x = (x_1, x_2, \dots, x_n)$ from which it was created.

Thus it is enough to count the number of solutions to $y_1 + y_2 + \dots + y_m = n$, with $0 \le y_i \le n$.

The way to look at this is to consider $n$ stars, and $m-1$ vertical bars. Finding a solution to the above equation is equivalent to placing the $m-1$ bars among the $n$ stars. The number of stars to the left of the leftmost bar is $y_1$, the one next to it is $y_2$ and so on.

The number of ways to do this is to select the position of the stars among a total $n + m - 1$ spots: $$ \binom{n+m-1}{n}$$

Solution 2)

The second solution I find particularly elegant.

Suppose instead of $x_i \le x_{i+1}$, we had the condition $x_i \le x_{i+1}$ (i.e. strictly increasing).

Then it is easy to count: just select $n$ among $m$ = $\binom{m}{n}$ (and sort to get the increasing order).

We can reduce our problem to the strictly increasing case.

Set $z_i = x_i + i - 1$.

Now we have that $z_i \lt z_{i+1}$ (strictly increasing) and that $ 1 \le z_i \le m + n - 1$.

Thus the answer is $$\binom{m+n-1}{n}$$

Sorting with reversals

You are given an array $A$ of $n$ elements, each element being either $0$ or $1$ or $2$.

You want to sort the array.

The catch is, the only write operation you can do on the array is pick two any two indices $i \le j$, and reverse the contiguous portion of the array from $A[i]$ to $A[j]$, i.e. after the operation, $A[i]$ and $A[j]$ are swapped, $A[i+1]$ and $A[j-1]$ are swapped, $\dots ,A[i+k]$ and $A[j-k]$ are swapped (where $k \approx (i+j)/2$).

Let's say we call this operation the splice-reverse.

Can you sort the array using $O(n)$ splice-reverses?

[Solution. Also see comments below]

How many non-decreasing functions?

How many non-decreasing functions exist which map $\{1, 2, \dots, n\} \to \{1, 2, \dots, m\}$?

i.e

How many ordered pairs $(x_1, x_2, \dots, x_n)$ exist such that

$x_i \le x_{i+1}$ and $ 1 \le x_i \le m$ for all $i$?

[Solution]

Bless partner, curse partner.

You are South and hold QJ9642, 2, 5, AQ872, with E/W vul.

Your LHO is the dealer and opens 1H. Partner doubles and RHO bids 4H. You bid 4S, wondering if you missed a slam.

LHO passes, and bless partner, who bids 6S.

LHO lead the DA and you see

IMPS E/W	The Dummy ♠ AKT73 ♥ AQ ♦ KJT ♣ J94
	You ♠ QJ9642 ♥ 2 ♦ 5 ♣ AQ872

W	N	E	S
1H	X	4H	4S
P	6S	P	P
P

Curse partner. Overbid again.

While you are cursing partner, LHO goes into a tank, and emerges with a low club! Now you have a chance. Bless partner?

You play the 9, covered by the T, which you win with the Q.

Now LHO likely has the HK, DQ and the CK for his opening bid. In that case you have him, but have to time the hand correctly.

You should play all the trumps, throwing a club from dummy, then play a heart to the Q, and cash the HA and DK coming down to the DJ and CJ in the dummy and CA8 in hand.

West is squeezed in the minors.

Sum involving golden ratio [Solution]

The problem was to find

$$S_n = \sum_{k=1}^{n} [k \varphi]$$

where $\varphi$ is the golden ratio and $[x]$ is the integer part of $x$.

The challenge was to do it using polynomial in $\log n$ time.

Solution

---

If you look at the numbers of the form $a_k = [k \varphi]$ and *not* of the form $[k \varphi]$, you will notice a pattern.

The pattern is as follows:

If $a_k = [k \varphi]$ and $b_k = a_k + k$, then we have that $$\{a_1, a_2, \dots\} \cup \{b_1, b_2, \dots\} = \mathbb{N}$$

i.e, the numbers not of the form $[k \varphi]$, are precisely of the form $[k \varphi] + k$.

This observation can be proved using Beatty's theorem (and is not that difficult to prove).

Now, if you consider the numbers $\{1, 2, \dots, a_n\}$ then these can be split into two disjoint sets $\{a_1, a_2, \dots, a_n\}$ and $\{b_1, b_2, \dots, b_m\}$ for some $m$.

Thus we have that

$$1 + 2 + \dots + a_n = S_n + \sum_{k=1}^{m} b_m = S_n + S_m + m(m+1)/2$$

Thus

$$S_n = n(n+1)/2 - m(m+1)/2 - S_m$$

which is a recursive formula for $S_n$. It can be shown that $m = \theta(n)$, and thus this recursive formula gives us a polynomial in $\log n$ time algorithm to compute $S_n$.

All we need to do is compute $m$. I will leave that to you.

Limit everywhere function [Solution]

The problem was to find a function $f$ whose limit $g$ exists everywhere (i.e. $\lim_{t\to x} f(t) = g(x)$) and $f(x) = 2g(x) - \sin x$.

The key is to realize that $g$ must continuous!

(In fact one can show that $f$ is continuous almost everywhere, but that does not help this problem immediately).

If $g$ is continuous then, the functional equation implies that $f$ is too, and the result that $f(x) = \sin x$ follows easily.

To prove $g$ is continuous at $c$ we need to show that given an $\epsilon \gt 0$, there is a $\delta \gt 0$, such that $$|g(x) - g(c)| \lt \epsilon \quad \forall x, 0 \lt |x - c| \lt \delta$$ 

Now we have that there is some $\delta$ such that

$$ |f(x) - g(c)| \lt \frac{\epsilon}{2}, \quad \forall x, 0 \lt |x - c| \lt \delta$$

Also for any $x_1$ such that $0 \lt |x_1 - c| \lt \delta$ we have a $\delta_1$ such that $$|f(x) - g(x_1)| \lt \frac{\epsilon}{2} \quad \forall x, 0 \lt |x - x_1| \lt \delta_1 $$

Thus we can find an $x$ such that for any $0 \lt |x_1 - c| \lt \delta$ we have the above two to be true, and hence adding them gives us that

$$|g(x_1) - g(c)| \lt \epsilon \quad \forall x_1, 0 \lt |x_1 - c| \lt \delta$$

Finding a sum involving the golden ratio

This is a math oriented algorithms puzzle.

Let $\varphi$ be the golden ratio: $\dfrac{1+\sqrt{5}}{2}$.

Consider the following sum

$$S_n = [\varphi] + [2 \varphi] + \dots + [n\varphi]$$

i.e

$$ S_n = \sum_{k=1}^{n} [k \varphi]$$

where $[x]$ is the integer part of $x$.

Can you give an algorithm to compute $S_n$ that takes a polynomial in $\log n$ time?

[Solution]

Limit everywhere function

Here is a strange math problem.

Suppose $f:[0,1] \to [0,1]$ is function whose limit exists everywhere.

i.e $g(t) = \lim_{x \to t} f(x)$ is well defined, and gives rise to another function.

Now suppose $f$ and the limit function $g$ satisfy

$$ f(x) = 2g(x) - \sin x \quad \forall x \in [0,1]$$

Find all such $f$.

[Solution]