22
votes
Accepted
Summation of a subset of numbers from given intervals.
Let $b_0, b_1, \cdots, b_{99}$ be integers, such that $b_i \in [-i, 99-i]$ for every $i$.
Consider the sequence $S_0, S_1, \cdots$ defined recursively by $$S_0 = 0, S_{i + 1} = S_i + b_{S_i}.$$
Since $...
- 10.4k
13
votes
Polynomial $f(x)$ has positive coefficients and all roots as real. How many polynomials formed from terms of $f(x)$ also have only real roots?
Consolidating and revising my comments into a partial answer ...
In concordance with Petter Brändén's paper "Unimodality, Log-Concavity, Real-Rootedness and Beyond" (PDF link via arxiv.org), ...
- 78.8k
12
votes
AM-GM inequality (but equality cannot be attained)
You did not apply AGM correctly. One has
$$
\frac{x_1+...+x_n}n\ge\sqrt[n]{x_1\cdots x_n}.
$$
So you are missing a factor 6,
$$
\frac16\ge\sqrt[6]{ab^2c^3/108}\iff ab^2c^3\le \frac{108}{6^6}=\frac1{...
- 129k
10
votes
Solving $\int_0^{\infty}x^3e^{-x^2}dx$
This is a much quicker solution that involves the Gamma function. Recall:
$$\Gamma(a)=\int_0^{\infty}x^{a-1}e^{-x}dx,\forall a>0$$
Let us use the substitution $x^2=u \implies xdx=\frac{du}{2}$
This ...
- 1,661
8
votes
Accepted
Finding the point that a sequence of midpoints converges to
First, show that we can do this on a per-coordinate basis. Henceforth, we restrict to a single coordinate.
Let the limit be represented by $f(A_1, A_2, A_3, A_4)$ for any starting real values.
Prove ...
- 71.8k
7
votes
Accepted
Finding the maximum squared distance between a pair of coordinates from a set of coordinates
If the number of points is low, don't worry about quadratic complexity.
Otherwise
build the convex hull of the point set for instance by the Monotone Chain (Andrew's) algorithm. This takes time $O(n\...
- 3,322
7
votes
Accepted
Show that there are an infinite number of positive integers that cannot be represented in the form of $a^{bc} - b^{ad}$.
Let's show that no number of the form $8k+3$ can be represented in this form. Suppose that $a^{bc}−b^{ad}=8k+3$ for some $k$. If the numbers $a,b$ had the same parity, the number $a^{bc} − b^{ad}$ ...
- 143
7
votes
If $ \int_0^{\infty}f(x)<{\infty}$, then $\int_0^{\infty}{f(x)}^2<{\infty} $?
Firstly, you have to ensure that $f(x)$ does not tend to $0$ as $x\to\infty$ uniformly. Because then, after a certain $M$, $f(x)<1$ for all $x\geq M$ and hence, $f(x)^{2}$ will have a faster decay ...
- 15.2k
6
votes
Compute the number of ways the frog can move from A to B.
The bivariate generating function for the words on the alphabet $\{ L, U \}$ not containing the subwords $LLL$, $UUU$ is
$$
g(x,y) = \frac{1}{1-x-y + \frac{x^3}{1+x+x^2} + \frac{y^3}{1+y+y^2} }
$$
...
- 10.2k
5
votes
Accepted
Arthur Engel Number Theory Divisibility
It's an ad hoc method of computing (a multiple of) the order of $\,a\bmod n\,$ by elimination when a nice "splitting" is obvious: $\, 1 + a^j\:\! b\equiv 0\equiv \color{#c00}{a^\ell+b^k}\...
- 276k
4
votes
Accepted
Checking for $343$ cases
We may replace $a_i$ with $a_i\bmod 7$, so $0 \le a_i\le 6$.
If any $a_i$ is zero, we can set $b_i=1$; so we may assume all $a_i$ are non-zero.
If any $a_i$ is $> 3$, we can replace it with $7-a_i$...
- 65.6k
4
votes
Checking for $343$ cases
This is just PGH principle.
Pigeons: Consider the $8$ values of the form $ c_1 a_1 + c_2 a_2 + c_3 a_3 $, where $ c_i \in \{ 0, 1 \}$.
Holes: The remainder mod $7$.
PGH: There are $2$ values with the ...
- 71.8k
4
votes
Accepted
Let ${x_1, x_2, x_3, . . . , x_n}$ be a set of $n$ distinct positive integers, that the sum of any $3$ of them is a prime. What is the max of $n$?
You're very much on the right track with the modulo 3 pigeon holes.
If there are numbers in each hole, then one number from each hole will sum to be divisible by 3 (and strictly larger than 3).
If ...
- 202k
4
votes
Tedious Inequality from Spanish Olympiad
Preamble: Here's a standard approach using just AM-GM. There's nothing too tricky here, so I'm surprised the official solution isn't along these lines. Note that all of the ideas are essentially ...
- 71.8k
4
votes
Compute the number of ways the frog can move from A to B.
An elementary (if tedious and error prone) method.
Note: I am including this at the OP's request. In practice, I would automate the search...the pencil and paper method is a bit too error prone to be ...
- 72.5k
4
votes
A quadratic function question from a Olympiad practice test
Write the quadratic function $f$ as follows: $f=R(x-S)^2+T$. It turns out that the parameters $R$ and $T$ are irrelevant. One might just well take $R=1$ and $T=0$. Now $f$ is a parabole, symmetric ...
- 3,919
4
votes
Accepted
Can you prove that a convex quadrilateral is cyclic?
Reflect $A$ with respect to the angle bisector of $\angle ABC$, that is $BD$. We get $A'\in BC$ and $A'\neq C$ because $A'B=AB\neq CB$. Therefore $$\angle DAB=\angle DA'B=180º-\angle DA'C=180º-\angle ...
- 144
4
votes
Accepted
Confusion about how this part of inequality is true.
That's just applying the base case, which you already said is simple. Namely, when $m = 1, n = 2$
$$ \frac{1}{1 + a } + \frac{1}{1+b} \leq \frac{ 2}{ 1 + \sqrt{ab} }. $$
Then you sum it up over the $...
- 71.8k
4
votes
AM-GM inequality (but equality cannot be attained)
A properly constructed AM-GM bound is always sharp. But we have to be careful how to construct this bound.
Given the problem
$a+b+c=1; a,b,c>0; \text{ maximize }ab^2c^3$
we first render
$1=a+b+c=\...
- 42.3k
4
votes
Solving $\int_0^{\infty}x^3e^{-x^2}dx$
$$
\begin{aligned}
\int_0^{\infty} x^3 e^{-x^2} d x&=-\frac{1}{2} \int_0^{\infty} x^2 d\left(e^{-x^2}\right) \\
& =-\frac{1}{2}\left(\left[x^2 e^{-x^2}\right]_0^{\infty}-\int_0^{\infty} e^{-x^...
- 23.7k
4
votes
Solving $\int_0^{\infty}x^3e^{-x^2}dx$
You know that when $p(x)$ is a polynomial, then differentiating $p(x)e^{-x^2}$ gives $$\left[p'(x)-2xp(x)\right]e^{-x^2}$$
Can $p'(x)-2xp(x)=x^3$?
$p$ would have to be quadratic, leading coefficient $...
- 55.4k
3
votes
Accepted
Let $\mathcal{F}$ be a set of subsets of $\{1,2,...,n\}$ satisfying some conditions. Let $f$ be maximum $|\mathcal{F}|$. Prove $n^2-4n\le 6f\le n^2-n$
An even better lower bound can be achieved by construction. Let $\mathcal F$ consist of the triples $\{x,y,z\}$ such that $n$ divides $x+y+z$. It satisfies the restriction because if $x+y+z_1$ and $x+...
- 10.2k
3
votes
Accepted
Code intercepted - BLASE+LBSA=BASES. Can there be two solutions?
$E+A\ge 10$ is not possible.
Looking at the units' digits, if $E+A\ge 10$ then $E+A=10+S$ with a carry to the tens' digits. Then
either $S+S+1=E$ in the tens digits with no carry to the hundreds' ...
- 160k
3
votes
find one positive integer solution for $x^3+101=y^2$ without computer
Not sure if this is going to help, but since the problem has already been solved by Travis, I just wanted to remind you that equations of the form
$$y^2 = x^3 + k$$
were studied extensively by Mordell ...
- 9,882
3
votes
Maximum number of black cells in a table where each cell has at most two adjacent black cells: Generalizations of JBMO 2019 P4
For $5 \times 100$, the maximum for the original question is indeed $302$. But for the related question where only the black cells must have at most two black neighbors, the maximum (obtained via ...
- 48.2k
3
votes
Arthur Engel Number Theory Divisibility
Is there something special about the number $641$ that I am suppose to know? Or is it something about $x^{2^k}+1$?
What is special is the historical background. If $2^m + 1$ is prime then $m$ must be ...
- 48.7k
3
votes
Find the minimum of $x^2 + y^2$ given $xy(x^2 - y^2) = x^2 + y^2, x \neq 0$
I think a nice approach would be to use polar coordinates. Write $$x=r\cos\theta\\y=r\sin\theta$$
Then you want the minimum of $r^2$ given $$r^4\sin\theta\cos\theta(\cos^2\theta-\sin^2\theta)=r^2$$
...
- 38.2k
3
votes
Accepted
Find the minimum of $x^2 + y^2$ given $xy(x^2 - y^2) = x^2 + y^2, x \neq 0$
Let $a := x^2 + y^2, b := xy$. Using
$(x^2 + y^2)^2 - (x^2 - y^2)^2 = 4(xy)^2$ and the condition, we have $b^2(a^2 - 4b^2) = a^2$ which results in
$$a = \frac{2b^2}{\sqrt{b^2 - 1}}
= 2\sqrt{b^2 - 1} + ...
- 41.2k
3
votes
Understanding a particular way of solving $(4 + \sqrt{15})^x + (4 - \sqrt{15})^x = 62 $
I think the comment is very abbreviated, and not a lot shorter.
First of all, the question in the video is to find $x$ if $$(4 + \sqrt{\color{red}{15}})^x + (4 - \sqrt{\color{red}{15}})^x = 62.$$ It ...
- 15.2k
3
votes
Solving $\int_0^{\infty}x^3e^{-x^2}dx$
A boring alternative solution:
You used a substitution, and then integration by parts once. But what if you start out with integration by parts?
$$
\begin{align}
\int x^3e^{-x^2}\,dx
&=\int -\...
- 55.4k
Only top scored, non community-wiki answers of a minimum length are eligible