[[Christmas]] New Year Streak 88/88: Happy New Year!

Number Theory Level 5

For a natural number N , N, define e ( N ) = { 0 ( N is odd. ) 1 ( N is even. ) e(N)=\cases{0~~(N~\text{is odd.}) \\ \\ 1~~(N~\text{is even.})}

For two natural numbers n , k n,~k and an integer x x where − n + ⌊ k + 1 2 ⌋ ≤ x ≤ n − ⌊ k 2 ⌋ , -n+\left\lfloor\dfrac{k+1}{2}\right\rfloor \le x\le n-\left\lfloor\dfrac{k}{2}\right\rfloor,

define a function A 2 n k ( x ) A_{2n}^k (x) inductively as:

A 2 n k ( x ) = { A 2 n 1 ( x ) = ∣ 2 x − 1 ∣ ; A 2 n k + 1 ( x + e ( k ) ) = { A 2 n k ( x ) + A 2 n k ( x + 1 ) ( x 2 + e ( k ) 2 ≠ 0 ) 0 ( x 2 + e ( k ) 2 = 0 ) A_{2n}^k (x)=\cases{ A_{2n}^1(x)=|2x-1|; \\ \\ A_{2n}^{k+1}\left(x+e(k)\right)=\cases{\begin{aligned} &A_{2n}^{k}(x)+A_{2n}^{k}(x+1) & (x^2+e(k)^2\neq0) \\ &0 & (x^2+e(k)^2=0)\end{aligned}} }

Now let f ( n ) f(n) as the number of ordered pair ( k , x ) (k,~x) that satisfies A 2 n k ( x ) ≡ 0 ( m o d 67 ) , A_{2n}^{k}(x) \equiv 0 \pmod{67}, where ∣ x ∣ < 70. |x|<70.

lim ⁡ n → ∞ ⌊ f ( n ) + α + 5 g ( n ) ⌋ = 3 \displaystyle \lim_{n\to\infty} \left\lfloor \dfrac{f(n)+\alpha+5}{g(n)}\right\rfloor = 3 for some constant α \alpha and a polynomial function g ( n ) g(n) where g ( 0 ) = 0. g(0)=0.

α ≥ P \alpha \ge P if and only if Q < g ( 44 ) ≤ R , Q<g(44)\le R, for some constants P , Q P,~Q and R . R.

Find the value of P + Q + R . P+Q+R.

Notation: ⌊ ⋅ ⌋ \lfloor\cdot\rfloor denotes the floor function .

This problem is a part of <Christmas Streak 2017> series .


The answer is 206.

Boi (보이) by Boi (보이) , 19, South Korea

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Boi (보이)
Jan 1, 2018

First off, let's list all A 2 n 1 ( x ) A_{2n}^{1}(x) horizontally.

2n-1 2n-3 ... 7 5 3 1 1 3 5 7 ... 2n-3 2n-1

Now let's write the second line with A 2 n 2 ( x ) . A_{2n}^{2}(x). It's same as writing the sum of two adjacent numbers of the first line below them, except 1 1.

2n-1 2n-3 ... 7 5 3 1 1 3 5 7 ... 2n-3 2n-1
4n-4 4n-8 ... 12 8 4 0 4 8 12 ... 4n-8 4n-4

Huh. Since we're looking for multiples of 67 , 67, we can divide the whole second line by 4 , 4, surely.

2n-1 2n-3 ... 7 5 3 1 1 3 5 7 ... 2n-3 2n-1
n-1 n-2 ... 3 2 1 0 1 2 3 ... n-2 n-1
2n-3 ... 7 5 3 1 1 3 5 7 ... 2n-3
n-2 ... 3 2 1 0 1 2 3 ... n-2

Oh wow, we just returned to the first line except the length is two less. Let's call these modified lines of A 2 n k ( x ) A_{2n}^{k}(x) as B 2 n k ( x ) . B_{2n}^{k}(x).

We infer that 0 only exists on the even line, where there is a total of 2 n 2n lines, leading to a conclusion that we add n n after counting the non-zero ones.

Now let's cut that table in half and look at the right side. It's symmetrical so we can just multiply 2 2 at the end.

Since ∣ x ∣ < 70 , |x|<70, the odd lines just can't contribute anything to f ( n ) , f(n), but the even lines can.

We note that the far right of B 2 n 2 k ( x ) B_{2n}^{2k}(x) is n − k , n-k, which should be bigger than or equal to 67 67 to produce 67. 67.

Then k ≤ n − 67 , k\le n-67, and therefore there are n − 67 n-67 of k k that satisfies the given condition. ( x x is kinda fixed here!)

Now as we said, f ( n ) = 2 ( n − 67 ) + n = 3 n − 134. f(n)=2(n-67)+n=3n-134.

Since lim ⁡ n → ∞ ⌊ 3 n − 134 + α + 5 g ( n ) ⌋ = 3 , \displaystyle \lim_{n\to\infty}\left\lfloor\dfrac{3n-134+\alpha+5}{g(n)}\right\rfloor=3, we figure that g ( n ) = β n . g(n)=\beta n.

If α ≥ 129 , \alpha\ge 129, then 3 4 < β ≤ 1 , \dfrac{3}{4}<\beta\le1, where if α < 129 \alpha<129 then 3 4 ≤ β < 1. \dfrac{3}{4}\le\beta<1.

Therefore the case is the former, which, 33 < g ( 44 ) ≤ 44. 33<g(44)\le 44.

So, we figure that P = 129 , Q = 33 , R = 44 P=129,~Q=33,~R=44 so that P + Q + R = 206 . P+Q+R=\boxed{206}.

3 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...