Own Problems « Bboyjordan's Blog

04/11/2009

A list of own problems

Filed under: Own Problems — bboyjordan @ 5:38 PM

Problem 1 Define the sequence of $\{x_i\}_{i \in \mathbb{N}_0}$ such that $x_i = i$ for $i \in \{1,2,3\}$ and $\displaystyle x_{n + 3} = \frac {x_{n + 2}^{5} + x_n^2}{ x_{n + 1}^{ 3}}$ for all $n \in \mathbb{N}_0$ . Find all $m \in \mathbb{N}_0$ such that the equation $\displaystyle x_m = \frac{a^{3} + b^{7}}{c^{13}+d^{17}}$ has no solutions in $(a,b,c,d) \in \mathbb{Z}^4$ .

Problem 2 Let $X: = \{x_1,x_2,\ldots,x_{29}\}$ be a set of $29$ boys: they play with each other in a tournament of Pro Evolution Soccer 2009, in respect of the following rules:
i) every boy play one and only one time against each other boy (so we can assume that every match has the form $(x_i \text{ Vs } x_j)$ for some $i \neq j$ );
ii) if the match $(x_i \text{ Vs } x_j)$ , with $i \neq j$ , ends with the win of the boy $x_i$ , then $x_i$ gains $1$ point, and $x_j$ doesn’t gain any point;
iii) if the match $(x_i \text{ Vs } x_j)$ , with $i \neq j$ , ends with the parity of the two boys, then $\frac {1}{2}$ point is assigned to both boys.
(We assume for simplicity that in the imaginary match $(x_i \text{ Vs } x_i)$ the boy $x_i$ doesn’t gain any point).
Show that for some positive integer $k \le 29$ there exist a set of boys $\{x_{t_1},x_{t_2},\ldots,x_{t_k}\} \subseteq X$ such that, for all choice of the positive integer $i \le 29$ , the boy $x_i$ gains always a integer number of points in the total of the matches $\{(x_i \text{ Vs } x_{t_1}),(x_i \text{ Vs } x_{t_2}),\ldots, (x_i \text{ Vs } x_{t_k})\}$ .

Problem 3 Define $\displaystyle \Phi_n(x):=\sum_{i=0}^{n-1}{x^i}$ for all $n \in \mathbb{N}_0$ , where $\mathbb{N}_0:=\mathbb{N} \setminus \{0\}$ .
Let $a \in \mathbb{N} \setminus \{0,1\}$ fixed; show that exist infinitely many $n \in \mathbb{N}_0$ such that $\displaystyle \text{gpf}(\Phi_n(a))>n\log_a{n}$ .

Problem 4 Let $\{\sigma(1), \sigma(3), \sigma(5),..., \sigma(2009)\}$ be a permutation of $\{1,3,5,\ldots,2009\}$ .
If we know that $\displaystyle P(x)=\sum_{i=0}^{1004}{(-1)^i\sigma(2i+1)x^{2i}}$ is not monic, show that if exist $\alpha \in \mathbb{R}$ such that $P(\alpha)=0$ then $\alpha+29>0$ .

Problem 5 Let $a \in \mathbb{N} \setminus \{0,1\} \text{ and } b \in \mathbb{N}_0$ fixed. Show that exist infinitely many $n \in \mathbb{N}_0$ such that $\displaystyle \log_a{(\text{gpf}^b(\Phi_n(a)))}<n$ .

Problem 6. Let $\{L_i\}_{i \in \mathbb{N}}$ be the Lucas sequence defined by $L_0=L_1+1=2 \text{ and } L_{n+2}=L_n+L_{n+1}$ for all $n \in \mathbb{N}$ . Show that every odd divisor of $L_{2n}$ has a even tens digit. (by Gebegb)

Problem 7. Let $n \in \mathbb{N}_0$ fixed, and define $s(n): = \{x \in \mathbb{Z}: 1 \le x \le n \text{ and } x \mid 2^x + 1\}$ , and let a real $k > 0$ fixed. Show that $2\ln(n) < |s(n)| < kn$ holds definitively.

Solution. We can begin noting that the infinite sequence of positive integers $\{x_i\}_{i \in \mathbb{N}}$ defined by $x_0:=1,x_{n+1}:=2^{x_n}+1$ for all $n \in \mathbb{N}$ verify the divisibility relation $x_n \mid 2^{x_n}+1$ . Easily by PMI, if $x_i \mid 2^{x_i}+1$ for all $i<n$ , then $\displaystyle 2^{x_n}+1=2^{2^{x_{n-1}}+1}+1=\left(2^{\frac{2^{x_{n-1}}+1}{x_{n-1}}}\right)^{x_{n-1}}+1 \text{ } \vdots \text{ } 2^{x_{n-1}}+1=x_n$ . On the other hand it is also true that the infinite sequence of positive integer $\{y_i\}_{i \in \mathbb{N}}$ defined by $y_i:=3^i$ verify the divisibility relation too, infact $1=y_0 \mid 2^{y_0}+1$ , and again by PMI, if $y_i \mid 2^{y_i}+1$ for all $i<n$ then $\displaystyle y_n=3y_{n-1} \mid 2^{3y_{n-1}}+1=\left(2^{y_{n-1}}+1\right)\phi_3(-2^{y_{n-1}})$ . So it is enough to show that $\displaystyle 2^{2 \cdot 3^{n-1}}-2^{3^{n-1}}+1 \text{ }\vdots \text{ }3$ , that is true since in $\mathbb{F}_3$ we have $4^{3^{n-1}}-2^{3^{n-1}}+1=1-(-1)+1=0$ .

We can show now that only the sequences $\{x_i\}_{i \in \mathbb{N}}$ and $\{y_i\}_{i \in \mathbb{N}}$ have only a finite number of common elements: in fact if $x_a=y_b$ for some $(a,b) \in \mathbb{N}^2$ then $2^{x_{a-1}}+1=3^b$ , but it is well known the equation $2^x+1=3^y$ has only finitely many solution in $\mathbb{N}$ , since by the Lifting Lemma $y=\upsilon_3(3^y)=\upsilon_3(2^x+1)=\upsilon_3(x)+1$ , but $2^x<2^x+1=3^y<4^{1+\upsilon_3(x)}<2^{2+2\ln(x)}$ , that is false definitively (it can be seen also as a corollary of Mihailescu Theorem).

Obviusly both sequences are strictly increasing, so it is true that each sequences have at least respectively $\lfloor \text{log}_{2,1}(n) \rfloor$ and $\lfloor \text{log}_3(n) \rfloor$ elements that are not greater than $n$ , so $|s(n)|> \lfloor \text{log}_{2,1}(n) \rfloor+\lfloor \text{log}_3(n) \rfloor > 2 \ln(n)$ definitively.

About the upper bound, it is equivalent to show that $\displaystyle \lim_{n \to +\infty}{\frac{|s(n)|}{n}}=0$ .

Note that $p \mid 2^{pk}-2^k$ for all $(p,k) \in \mathbb{P} \times \mathbb{N}$ , so that $\text{ord}_p(2)=\text{ord}_p(2^p)$ . Now if $p \mid 2^t \pm1$ then $2^t \ge p \mp 1 \ge 2^{\ln(p)}$ for all $p \in \mathbb{P}$ sufficiently large. It means that $\text{ord}_p(2) \ge \ln(p)$ , and also that if $p \mid x \in s(n)$ then $x \ge \ln(p)$ . So, in the set $s(n)$ there are at most $\displaystyle n\left(p\ln(p)\right)^{-1}$ numbers multiple of $p$ .

Let $q \in \mathbb{P}$ fixed and define $\displaystyle r_q(n):=\{x \in \mathbb{N}: 1\le x \le n \text{ and gpf}(x)<q\}$ . Clearly we have that $\displaystyle \ell\left(\ln(n)\right)^q < | r_q(n) |$ for some positive real $\ell$ fixed.

It is enough to conclude since $\displaystyle \lim_{n \to +\infty}{\frac{|s(n)|}{n}} \le \lim_{n \to +\infty}{\frac{|r_q(n)|+\sum_{q \le p \in \mathbb{P}}{n\left(p\ln(p)\right)^{-1}}}{n}}$ $\displaystyle \le \lim_{n \to +\infty}{\ell \frac{\left( \ln(n) \right)^q}{n}}+\lim_{n \to +\infty}{\sum_{q \le p \in \mathbb{P}}{\left(p\ln(p)\right)^{-1}}}$ , but if $q \in \mathbb{P}$ is sufficiently large, then both limits can be arbitrary small. []

Problem 8. Let a convex quadrilateral $ABCD$ fixed such that $AB = BC$ , $\angle ABC = 80, \angle CDA = 50$ . Define $E$ the midpoint of $AC$ ; show that $\angle CDE = \angle BDA$

Solution . X in BE such that CXE=CDE so DECX cyclic so DXE=DCE=180-CDA-CAD=180-CAB-CAD=180-BAD, so ABXD cyclic so BDA=AXB=CXE=CDE.

Problem 9. Find all $(x,y,z) \in \mathbb{Z}^3$ such that $x^3 - 5x = 1728^{y}\cdot 1733^z - 17$ .

Solution. 2 doesn’t divide f(x):= x³ – 5x + 17 that is integer, so min{y,z}>-1 and y = 0. If $z = 0$ there are no solutions, so $f(x) \ge 1733 \implies x > 10$ Now $f(x) \in \{0,1,3,5,6\}$ in $\mathbb{F}_7$ so we have the only case $3 \mid z$ . So $f(x)$ must be a cube, but $(x - 1)^3 < f(x) < x^3$ for all $x > 10$ .

Problem 10. Define the function $g(\cdot): \mathbb{Z} \to \{0,1\}$ such that $g(n) = 0$ if $n < 0$ , and $g(n) = 1$ otherwise. Define the function $f(\cdot): \mathbb{Z} \to \mathbb{Z}$ such that $f(n) = n - 1024g(n - 1024)$ for all $n \in \mathbb{Z}$ . Define also the sequence of integers $\{a_i\}_{i \in \mathbb{N}}$ such that $a_0 = 1$ e $a_{n + 1} = 2f(a_n) + \ell$ , where $\ell = 0$ if $\displaystyle \prod_{i = 0}^n{\left(2f(a_n) + 1 - a_i\right)} = 0$ , and $\ell = 1$ otherwise. How many distinct elements are in the set $S: = \{a_0,a_1,\ldots,a_{2009}\}$ ?

Solution. Consider the obvious bijection between {1,…,2048} and the strings of 11 binary digits. The problem states that we begin with $x_1: = 1$ , and that if $x_n = 0\ell$ or $x_n = 1\ell$ (where $\ell$ is a string of 10 binary digits) then $x_{n + 1} = \ell 1$ if we can find i<n+1 such that $x_i = \ell$ , otherwise $x_{n + 1} = \ell 0$ . Define $k: = \max\{n \in \mathbb{N}: \prod_{1 \le a < b \le n}{(x_a - x_b)} \neq 0\}$ and $S: = \{x_1,...,x_k\}$ . Suppose that $x_k = ey$ for some e in {0,1} and a string y of 10 binary digits, then $x_{k + 1} = y0 \in S$ by definition of k, so define $x_i: = y0 \in S$ the other i such that 1<i<k+1. And, if $x_k = ey$ then define j that integer such that 0<j<k+1 and $x_j: = y1 \in S$ (it must exist since $x_{k + 1} = y0$ ). If j>1 then $\{x_{i - 1},x_{j - 1}\}$ exist and is $\{0y,1y\}$ , then $x_k \in \{x_{i - 1},x_{j - 1}\}$ , contradiction, so j=1. It means that $latex y=0 \in S$, and if $e = 1$ then $x_{k - 1} \in \{0,x_k\}$ , contradiction, so $x_k = 0$ . Clearly $1 \le k \le 2048$ ; suppose that $k < 2048$ . A number $a \in \{0,1\}$ and a string $b$ of 10 binary digits exist such that $ab \not \in S$ , and suppose $b0 \in S$ (clearly $b \neq 0$ ).Define $x_w: = b0 \in S$ for some 1<w<k+1, then there exist 0<z<k+1 such that $x_z = b1 \in S$. As before if z>1 then $\{x_{w - 1},x_{z - 1}\}$ exist and is $ab \in \{0b,1b\} \subseteq S$ , contradiction; and if z=1 then b=0, again contradiction. So a number $ab$ does not belong to S only if $b0 \not \in S$ . But in this way we can define a sequence of number that do not belong to S, and that is eventually null, but $a_k = 0$ .
It shows that $\prod_{0 \le i < j \le 2047}{(a_i - a_j)^2} > 0$ .[]

Problem 11. Let $a,b$ be two positive integer fixed such that $b>1$ . Evaluate $\min\{n \in \mathbb{N}_0: \lfloor \text{log}_b(n)+\text{log}_b(b^a+1) \rfloor - \lfloor \text{log}_b(n) \rfloor >a \}$ .

Solution. It is equivalent to search the minimum positive integer integer n such that $nb^{a+1}$ and $n(b^a+1)$ have the same number of digit in base $b \in \mathbb{N} \setminus \{0,1\}$ . Working in base $b$ , if $(x,y) \in \{0,1,2...,,b-1\}^2$ then $x+y<2b$ , so the max “report” when we compute $nb^a+n$ in the leftmost place is 1.And trivially $n$ need to have at least $a+1$ digits. So the minimum integer is $n=b^{a+1}-b+1$ .[]

Problem 12. (a) Let $a,b,c$ positive integer such that $a+b+c \mid a^2+b^2+c^2$ . Show that $a+b+c \mid a^n+b^n+c^n$ for infinitely many positive integer $n$ . (Laurentiu Panaitopol,TST Romania1987)

(b) Show that there exist infinitely many triple of positive integers $(a,b,c)$ such that $\text{gcd}(a,b,c)=1$ and $a+b+c \mid a^2+b^2+c^2$ and $a+b+c \nmid a^n+b^n+c^n$ for infinitely many positive integer $n$ . (Me)

Solution. (a) Since $a^n+b^n+c^n$ is a symmetric polynomial, it can be written in terms of $\sigma_1:=a+b+c$ , $\sigma_2:=ab+bc+ca$ and $\sigma_3:=abc$ (see the fundamental theorem of symmetric function). Now since $\sigma_1 \mid \sigma_2$ by assumption, if $a^n+b^n+c^n$ is made only by monomial of the form $\sigma_3$ , then it has a degree multiple of 3. But $|\mathbb{N} \setminus 3\mathbb{N}|=+\infty$ .

(b) There exist infinitely many primes $p \in \mathbb{P}$ such that $6 \mid p-1$ (in fact, if this set is finite and P is the product of its elements, then $4P^2+3$ should have only prime divisor of the form $6k-1$ but it is false since $\left(\frac{-3}{q}\right)=-1$ for all prime $q$ such that $6 \mid q+1$ ; in all way, it is a corollary of Dirichlet theorem). Set $b:=1$ and $c:=p-(a+1)$ then $p \mid a^2+1+(a+1)^2$ ; it means that if $p>2$ and $6 \mid p-1$ then $p \mid (2a+1)^2+3$ for some integer $a \in \mathbb{Z} \cap [1,p-2]$ (in fact $2a+1$ takes a complete residue system in $\{0,1,\ldots,p-1\}$ and $a \in \{p-1,0\}$ does not work). Define $a_0$ this integer, so $a_0+1+(p-a_0-1)=p \mid a_0^2+1^2+(p-a_0-1)^2$ and $p \nmid a_0^n+1^n+(p-a_0-1)^n$ for infinitely many positive integer $n$ . This is true, since it is enough to take $n=k \frac{p-1}{2}$ and by Euler criterion we have $a_0^n+1^n+(p-a_0-1)^n=\left(\frac{a_0}{p}\right)^k+1+\left(\frac{p-a_0-1}{p}\right)^k$ in $\mathbb{Z}/p\mathbb{Z}$ . But a sum of odd number of odd addends is odd, and in particulat it is non null.[]

Problema 13. Fix a strictly increasing sequence of $\{a_i\}_{i \in \mathbb{N}}\subseteq \mathbb{N}_0$ such that ten n-th terms is not bigger than nx+y definitively for some $(x,y) \in (\mathbb{R}^+)^2$ . Show that $\displaystyle \omega\left(\prod_{i \in \mathbb{N}}{a_i}\right)=+\infty$ .

Solution. By contradiction if $S$ is set of prime divisor of $\displaystyle \prod_{i \in \mathbb{N}}{a_i}$ and $|S|<+\infty$ then we’ll have that $\displaystyle \sum_{i \in \mathbb{N}}{\frac{1}{xi+y}}$ $\displaystyle \le \sum_{i \in \mathbb{N}}{\frac{1}{a_i}} \le \prod_{p \in S}{\left( \sum_{j \in \mathbb{N}}{\frac{1}{p^j} }\right)}$ definitively, that is clearly a contradiction. []

Problem 14. Prove that in the set $S :=\{2008,2009,...,4200\}$ there are $5^3$ elements such that any three of them are not in arithmetic progression.

Problem 15. Let $0<a_1<a_2<a_3<...<a_{10000}<20000$ be integers such that $\text{gcd}(a_i,a_j) < a_i, \forall i < j$ ; is $500 < a_1$ (always) true ?

Solution. It is enough to show that if we have $2n > 3^k$ distinct positive integers s.t. noone divides another one, so the smallest element is at least $2^k$ . Let $\upsilon_p(x)$ be the $p -$ adic valuation of $x$ , so naturally there exist a bijective function from $\{\frac {a_i}{\upsilon_2(a_i)}\}$ to $\{2i - 1\}$ , where $1 \le i \le 10^4$ . Consider the numbers s.t. $\upsilon_p(a_i) = 0, \forall p > 3$ : if $\upsilon_2(a_i) \le \upsilon_2(a_j)$ and $\upsilon_3(a_i) \le \upsilon_3(a_j)$ we have contradiction: it follows that $\upsilon_2(a_i) + \upsilon_3(a_i) \ge k$ , so the only number $a_h$ with $\frac {a_h}{2^{\upsilon_2(a_h)}} = 1$ has the property that $\upsilon_2(a_h) \ge k$ . Now it is enough to prove that $h = 1$ , but it is quite easy considering the number in the form $2^a3^bp$ and using similar tecnique as above.

Problem 16. Let $(a,b,c)\in \mathbb{N}_0^3$ fixed and let $p(\cdot),q(\cdot),r(\cdot)\in \mathbb{N}[x]$ be three polynomial such that $\min\{\text{deg}(p(\cdot)),\text{deg}(q(\cdot)),\text{deg}(r(\cdot))\}>0$ . Show that the equation $\displaystyle \pi^a(p(n)) = s^b(q(n)) + \sigma_0^c(r(n))$ has only a finite number of solutions, where $s(m)$ denotes the sum of digit of a positive integer $m$ .

Problem 17. Let $(a,b)\in \mathbb{Z}^2$ fixed such that $\min\{a,b\}\ge 2$ and fix also non constant polynomials $p_i(\cdot):\mathbb{R}\to\mathbb{R}$ for each $i\in\mathbb{Z}\cap[0,a+4]$ . Now define the function $f_4(\cdot):\mathbb{N}\to\mathbb{Z}\cap [0,4):x\to x-4\lfloor x\cdot 4^{ - 1}\rfloor$ and $g_b(\cdot):\mathbb{N}\to\mathbb{N}_0$ such that $g_b(x)=x^b$ if $b$ appears in the decimal representation of $x$ , otherwise $g_b(x) = b^x$ .
Show that it does not exist a non-zero polynomial $P[x_1,x_2,\ldots,x_{a + 5}]\in\mathbb{R}[x_1,x_2,\ldots,x_{a + 5}]$ such that for all $n\in\mathbb{N}_0$ the equation :
$\displaystyle P[p_0(\sigma_0(n)),p_1(\sigma_1(n)),$ $\displaystyle \ldots,p_a(\sigma_a(n)),p_{a + 1}(\omega(n)),p_{a + 2}(\varphi(n)),p_{a + 3}(f_4(n)),p_{a + 4}(g_c(n))] = 0$ holds.

Bboyjordan's Blog

04/11/2009

A list of own problems

Blogroll

Follow “Bboyjordan's Blog”