We say a number is irie if it can be written in the form $1+\dfrac{1}{k}$ for some positive integer $k$. Prove that every integer $n \geq 2$ can be written as the product of $r$ distinct irie numbers for every integer $r \geq n-1$.
Problem
Source: Centroamerican 2016, problem 5
Tags: number theory
22.06.2016 02:25
Fun fact: "Irie" is a Jamaican word meaning "alright" or "feeling great". (Centroamerican 2016 is being hosted by Jamaica.)
22.06.2016 02:35
Each irie number can be written as $\frac{k+1}{k}$. So for each integer $n \geq 2$, we will prove that $n$ can be written as the product of the first $n-1$ distinct irie numbers. Proceed by induction. Base case: $n=2$ can be written as $\frac{1+1}{1}$ with k=1. Inductive step: Say that for all integers $n$ we can write $n$ as the product of the first $n-1$ irie numbers. So this means that $n+1=n \cdot \frac{n+1}{n}=\prod_{i=1}^{n}\frac{i+1}{i}$ which is simply the product of the first $n$ irie numbers and thus we are done.
22.06.2016 03:01
Nice sol, but it says for every integer r... what about some $r > n-1 $ such that r is odd?
22.06.2016 05:03
Notice that every $irie$ number can be written as $1+\frac{1}{k}=\frac{k+1}{k}$ Consider $k\in\mathbb{Z^+}.$ $n=(\frac{kn}{kn-1}*\frac{kn-1}{kn-2}...\frac{k(n-1)+1}{k(n-1)})*\frac{n-1}{n-2}*\frac{n-2}{n-3}....\frac{2}{1}$ Here there are $k+n-2$ numbers multiplying $Q.E.D$
22.06.2016 05:21
@godfjock use induction on the fact that $\frac{n}{n-1}=\frac{2n}{2n-1}\cdot \frac{2n-1}{2n-2}$, which adds 1 irie number to the product.
24.06.2016 20:10
Actually induction was supposed to be done on r not on n.
22.07.2016 01:25
First post on this forum, so I'm kinda nervous. This was so much fun to solve though! Denote $a_k=1+\frac{1}{k}=\frac{k+1}{k}$ as the $k$-th irie number. We'll induct on $r$. For $r=n-1$, the product $$n=\prod_{i=1}^{n-1}a_i$$consists of $n-1$ distinct irie numbers and is easily verifiable. Now, assume that a positive integer $n$ can be expressed as the product of $m$ distinct irie numbers. Let $a_t$ be the smallest irie factor in such product. Notice that $$a_t=\frac{t+1}{t}=\frac{2t+2}{2t}=\frac{2t+1}{2t}\cdot\frac{2t+2}{2t+1}$$which implies $a_t=a_{2t}a_{2t+1}$. Thus, we can replace the $a_t$ factor in the product with terms $a_{2t}$ and $a_{2t+1}$, resulting in a product of $m+1$ irie numbers and preserving equality. Finally, observe that $a_{2t+1}<a_{2t}<a_t<a_s$ for any other factor $a_s$ in the product, guaranteeing that all $m+1$ factors are still distinct. This completes the induction and the result follows.
04.11.2018 05:32
q.e.d.