Functions — “s’wat” Math is about !! :-)

Reference: Nordic Mathematical Contest 1987, R. Todev:

Question:

Let f be a function, defined for natural numbers, that is strictly increasing, such that values of the function are also natural numbers and which satisfies the conditions $f(2)=a>2$ and $f(mn)=f(m)f(n)$ for all natural numbers m and n. Define the smallest possible value of a.

Solution:

Since, $f(n)=n^{2}$ is a function satisfying the conditions of the problem, the smallest possible a is at most 4. Assume that $a=3$. It is easy to prove by induction that $f(n^{k})={f(n)}^{k}$ for all $k \geq 1$. So, taking into account that f is strictly increasing, we get

${f(3)}^{4}=f(3^{4})=f(81)>f(64)=f(2^{6})={f(2)}^{6}=3^{6}=27^{2}>25^{2}=5^{4}$

as well as ${f(3)}^{8}=f(3^{8})=f(6561).

So, we arrive at $5. But, this is not possible, since $f(3)$ is an integer. So, $a=4$.

Cheers,

Nalin Pithwa.

Journos have a problem!

A problem posed in Nordic Mathematical Contest 1987:

Question:

Nine journalists, each from a different country, participate in a press conference. None of them can speak more than three languages, and each two journalists have at least one common language. Prove that at least five of the journalists can speak the same language.

Solution1:

Assume the journalists are $J_{1}, J_{2}, J_{3}, \ldots, J_{9}$. Assume that no five of them have a common language. Assume the languages $J_{1}$ speaks are $L_{1}, L_{2}$ and $L_{3}$. Group $J_{2}, J_{3}, \ldots, J_{9}$ according to the language they speak with $J_{1}$. No group can have more than three members. So, either there are three groups of three members each, or two groups with three members and one with two. Consider the first alternative. We may assume that $J_{1}$ speaks $L_{1}$ with $J_{2}$, $J_{3}$, and $J_{4}$, $L_{2}$ with $J_{5}$, $J_{6}$, and $J_{7}$, and $L_{3}$ with $J_{8}$, $J_{9}$ and $J_{2}$. Now, $J_{2}$ speaks $L_{1}$ with $J_{1}$, $J_{3}$, and $J_{4}$, $L_{3}$ with $J_{1}$, $J_{8}$, and $J_{9}$. $J_{2}$ must speak a fourth language, $L_{4}$, with $J_{5}$, $J_{6}$, and $J_{7}$. But, now $J_{5}$ speaks both $L_{2}$ and $L_{4}$ with $J_{2}$, $J_{6}$, and $J_{7}$. So, $J_{5}$ has to use his third language with $J_{1}, J_{4}, J_{8}$ and $J_{9}$. This contradicts the assumption we made.

So, we now may assume that $J_{1}$ speaks $L_{3}$ only with $J_{8}$ and $J_{9}$. As $J_{1}$ is not special, we conclude that for each journalist $J_{k}$, the remaining eight are divided into three mutually exclusive language groups, one of which has only two members. Now, $J_{2}$ uses $L_{1}$ with three others, and there has to be another language he also speaks with three others. If this were $L_{2}$ or $L_{3}$, a group of five would arise (including $J_{1}$). So, $J_{2}$ speaks $L_{4}$ with three among $J_{5}, \ldots, J_{9}$. Either two of these three are among $J_{5}$, $J_{6}$, and $J_{7}$, or among $J_{8}, J_{9}$. Both alternatives lead to a contradiction to the already proved fact that no pair of journalists speaks two languages together. Hence, the proof. QED.

Reference:

Nordic Mathematical Contest, 1987-2009.