Maths Olympiad Prep

Library / /6 of 13

Algebra Difficulty 6.2 National olympiad Find the answer

Given an integer m m, define the sequence {an} \left\{a_{n}\right\} as follows:
a1\equalm2, an\plus1\equalanan, if n1 a_{1}\equal{}\frac{m}{2},\ a_{n\plus{}1}\equal{}a_{n}\left\lceil a_{n}\right\rceil,\textnormal{ if }n\geq 1
Find all values of m m for which a2007 a_{2007} is the first integer appearing in the sequence.

Note: For a real number x x, x \left\lceil x\right\rceil is defined as the smallest integer greater or equal to x x. For example, π\equal4 \left\lceil\pi\right\rceil\equal{}4, 2007\equal2007 \left\lceil 2007\right\rceil\equal{}2007.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let {an} \{a_n\} be a sequence defined by:
a1=m2,an+1=ananfor n1. a_1 = \frac{m}{2}, \quad a_{n+1} = a_n \left\lceil a_n \right\rceil \quad \text{for } n \geq 1.
We need to find all values of m m such that a2007 a_{2007} is the first integer in the sequence.

First, we note that a2=a1a1=m2m2 a_2 = a_1 \left\lceil a_1 \right\rceil = \frac{m}{2} \cdot \left\lceil \frac{m}{2} \right\rceil . The sequence will produce an integer at the first appearance of a term when:
an=an=integer. a_{n} = \left\lfloor a_{n} \right\rfloor = \text{integer}.

Given the sequence rule:
an+1=anan, a_{n+1} = a_n \left\lceil a_n \right\rceil,
for a2007 a_{2007} to be the first integer, and since a1 a_1 is not an integer unless m m is even, we need to control the growth and progression of this sequence in terms of whether and when each an a_n becomes an integer.

The crucial value for the sequence to be integer for the first time at a2007 a_{2007} is:
a1=m2 a_1 = \frac{m}{2}
such that:
a2006=1 a_{2006} = 1
hence:
a2007=a20061=1. a_{2007} = a_{2006} \cdot 1 = 1.

This implies that the sequence's progression must exert enough multiplications by ceiling of previous numbers for 2006 iterations to truncate back into 1.

Assuming each an a_n results in multiplying by 2 2 until the last n n , we equate the number of necessary changes needed:
m222006=1. \frac{m}{2} \cdot 2^{2006} = 1.

Solving for m m , we find:
m=22006(2s+1)+1 m = 2^{2006} \cdot (2s+1) + 1
where s s is some integer representing alternate multiplicative forms when cutting down to define integer steps. Thus:
m=22006(2s+1)+1. \boxed{m = 2^{2006}(2s + 1) + 1}.
This expression satisfies the conditions and guarantees that a2007 a_{2007} is the first integer in the sequence.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.