New answers tagged

4

Randomly colour the members of the set black and white, independently with probabilities $1/2$ and $1/2$. The probability that any given $18$-term a.p. in the set is monochromatic is $2^{-17}$. There are $117587$ such a.p.'s, and this is less than $2^{17}$. Thus the expected number of monochromatic a.p.'s is less than one, which means that it must be ...


1

A Sketch of Proof Let $W$ be the space of polynomials over $\mathbb{C}$ in variable $X$ of degree at most $8$. Define an inner product $\langle\_,\_\rangle$ on $W$ via $$\langle AB\rangle:=V\left(A\bar{B}\right)\,,$$ where $\bar{B}$ is the complex conjugate of $B$. Prove that $\langle\_,\_\rangle$ is indeed an inner product. Now, $W$ has a basis ...


1

I try a solution. Let $E=\mathbb{R}_{8}[x]$, and define on $E$ $$<A,B>=\sum_{k=1}^{16}A(\alpha_k)B(\alpha_k)$$ We see easily that $<.,.>$ is a scalar product on $E$. Let $\{x^j, j=0,\cdots, 8\}$ the standard basis of $E$, and $A_j$, $j=0,\cdots,8$, the orthonormal basis deduced from this standard basis by Gram-Schmidt. Then the usual ...


2

If it's square, $ x^2\! + p x\! +\! qr\,$ has odd integer roots (factors of odd $qr),\,$ contra root sum $ {-}p\,$ is odd


3

And now a strange solution. Assuming that $p^2-4qr$ is a square, the polynomial $$s(x)= qx^2 + px + r $$ has to be reducible over $\mathbb{Q}$. However, $x^2+x+1$ is irreducible over $\mathbb{F}_2$, hence that cannot happen.


3

A little culture. If $p^2 - 4 q r$ were a perfect square, then we would be able to factor $$ qx^2 + p x + r $$ over the integers as $$ qx^2 + p x + r = ( q_1x + r_1) (q_2 x + r_2); $$ see Prove that if $b^2-4ac=k^2$ then $ax^2+bx+c$ is factorizable or Formula for factorization of a Quadratic Equation? However, $$ ( q_1x + r_1) (q_2 x + r_2) = q_1 q_2 x^...


1

$p^2$ is congruent to $1$ mod $8$ (it is equal to $8k+1$ for some $k$) but $4qr$ is congruent to $4$ mod $8$ (it is $8m+4$ for some $m$). Therefore the difference of those two expressions is $(1 - 4) = 5$ mod $8$ which is not the value of any perfect square mod $8$.


4

This is equivalent to proving that for odd $m$, if $4|n^2-m^2$ then $8|n^2-m^2$. This is easy if we notice $n^2-m^2=(n+m)(n-m)$, and if one of them is even, both are even, and also, one is a multiple of $4$.


7

Suppose to the contrary that $p^2-4qr=x^2$, where $x$ is an integer. Then $p^2-x^2=4qr$. It is clear that $x$ must be odd. So $p^2\equiv 1\pmod{8}$ and $x^2\equiv 1\pmod{8}$, and therefore $p^2-x^2$ is divisible by $8$. But $4qr$ is not divisible by $8$.


2

If $p,q,r$ are odd then $p^2-4qr$ is odd. So if $p^2-4qr=s^2$ then $s$ must be odd. But $4qr=(p-s)(p+s)$ The LHS is divisible by $4$ and not $8$, the RHS is divisible by $8$ because one of $p+s$ or $p-s$ is divisible by $2$ and the other by $4$.


1

Well, the first problem is the circle is an uncountable set, so the usual way of defining infinite sums with sequences and partial sums doesn't really work. There's a way to extend sums to uncountable sets, but the sum will diverge unless all but a countable subset of the terms are zero. There are also alternative summation methods which are interesting ...


-1

Assuming there are no fatalities. For $n$ fighters and we fight until there are no more fights we can schedule by the rules given. There must be exactly one fighter with no wins. Win-less fighters can only fight win-less fighters, and somebody must lose that fight. There cannot be two win-less fighters, or they would square off until there was only one. ...


0

It is unlikely that there is a characterization, because if there is, we should be able to efficiently test if an element $m$ is in this set; this is equivalent to the problem P: test if there are two subsets of $\{a_1,a_2,\ldots,a_n\}$ whose sum differs by $m$. This problem is NP-hard with a reduction from the Partition problem known to be hard: https://...


1

At the beginning we transform the original inequality: $$\dfrac{8x^4}{8x^3+5y^3}+\dfrac{8y^4}{8y^3+5z^3}+\dfrac{8z^4}{8z^3+5x^3}\geq \dfrac8{13}(x+y+z),$$ $$x-\dfrac{5xy^3}{8x^3+5y^3}+y-\dfrac{5yz^3}{8y^3+5z^3}+z-\dfrac{5zx^3}{8z^3+5x^3}\geq \dfrac8{13}(x+y+z),$$ $$\dfrac{xy^3}{8x^3+5y^3}+\dfrac{yz^3}{8y^3+5z^3}+\dfrac{zx^3}{8z^3+5x^3}\leq \dfrac1{13}(x+y+z)....


0

Let $\sum\limits_{i=1}^na_i=x\sum\limits_{i=1}^nb_i$. Since $\sum\limits_{i=1}^n\left(a_i-xb_i\right)^2\geq0$, we obtain that the inequality $$\sum\limits_{i=1}^n\left(a_i-xb_i\right)^2\geq\left(\sum\limits_{i=1}^n(a_i-xb_i)\right)^2$$ has real solution or an inequality $$\left(\left(\sum\limits_{i=1}^nb_i\right)^2-\sum\limits_{i=1}^nb_i^2\right)x^2-2\...


1

For olympiads Number Theory this is a must-"Number Theory-Andrescu Titu"-https://blngcc.files.wordpress.com/2008/11/andreescu-andrica-problems-on-number-theory.pdf And for Geometry this one-"Coxeter-Geometry Revisited"-http://www.aproged.pt/biblioteca/geometryrevisited_coxetergreitzer.pdf I have another good book,but I have no idea if it's available ...


0

One of my favorite mathematical olympiad books is this one: https://www.amazon.es/Mathematical-Olympiad-Challenges-Titu-Andreescu/dp/0817645284 by Andreescu and Gelca. It's more on the itermediate level. It is sort of a compilation on useful techniques with sample problems. I suggest you give it a go.


1

Problem solving strategy by Engel. Pretty advanced though


0

An elementary intro to combinatorics, with exercises: https://www.amazon.com/Discrete-Mathematics-Highschooler-Alexander-Sadovsky/dp/1453869670/ref=sr_1_fkmr0_1?ie=UTF8&qid=1469170334&sr=8-1-fkmr0&keywords=sadovsky+discrete+math+for+highschooler Instructional videos on combinatorics: https://www.youtube.com/watch?v=QrfA8mKOIjI Books ...


2

Solution credits to Rui Yao: According to a property of finite differences, if we set $c_n\in \mathbb{Z}$ to be the highest coefficient of $f(x)$, which has degree $n$, then $$n!c_n=\Delta ^n [f](x)=\sum_{i=0}^{n}\binom{n}{i} f(i)(-1)^{n-i}$$ Thus $$|n!c_n|=|\sum_{i=0}^{n}\binom{n}{i} f(i)(-1)^{n-i}|\le \sum_{i=0}^{n}|\binom{n}{i} f(i)(-1)^{n-i}|\...


6

We can assume $x$ and $y$ are non-zero. So, with suitable initial $0$-padding, each has $200$ digits. If $x$ ends in $00$ we are finished. Suppose now that $x$ ends in $0$ but not $00$. Then the next to last digits of $x$ and $y$ are $10$'s complements of each other, and non-zero. Each of $x$ and $y$ has $198$ digits that are $9$'s complements of each other....


1

A low-tech solution. $1985=5\cdot 397$, and $ \Phi_5(x) $ is a palyndromic polynomial, decomposable as $$ \left(x^2-\frac{x}{2}+1\right)^2-\frac{5}{4}x^2 \tag{1}$$ or as: $$(x^2+3x+1)^2-5x(x+1)^2 \tag{2}$$ that with $x=5^{397}$ is the difference of two squares, $a^2-b^2=(a-b)(a+b)$, with both $a-b$ and $a+b$ being $>5^{100}$. The claim hence follows from $...


16

I would try Aurifeuillian factorization here. Let $f(x)=x^4+x^3+x^2+x+1$ be the fifth cyclotomic polynomial. The Aurifeuillian stuff says that $f(5x^2)$ factors into a product as follows $$ f(5x^2)=\left(25 x^4-25 x^3+15 x^2-5 x+1\right) \left(25 x^4+25 x^3+15 x^2+5 x+1\right). $$ Call those two factors on the RHS $g_1(x)$ and $g_2(x)$. Your number is $$...


2

See here http://factordb.com/index.php?query=5%5E1985-1 for the partial factorization of $5^{1985}-1$. There are three factors with $200$ digits or more. No idea how the factors can be expressed. Multiply one of the factors with the smaller factors to get a decomposition of the desired form.


0

This is related to your approach, but possible easier. Hard to tell since you didn't give your argument. $$\begin{align} f(x,y)&=\frac{\frac{1}{2}(x^3+y^3)}{\frac{\frac{1}{2}(x^3-y^3)}{x-y}-xy}\\ &=\frac{x^3+y^3}{\frac{x^3-y^3}{x-y}-2xy}\\ &=\frac{x^3+y^3}{x^2+xy+y^2-2xy}\\ &=\frac{x^3+y^3}{x^2-xy+y^2}\\ &=x+y \end{align}$$ Then $f(x,y)+...


1

Let $r$ be the common root, then $$(a+b+c)(r^3+r+1)=0$$ Case I: If $r^3+r+1=0$, then $(ar^3+br+c)-a(r^3+r+1)=0$ $$\implies (a-b)r=(c-a)$$ By symmetry, $$r=\frac{c-a}{a-b}=\frac{a-b}{b-c}=\frac{b-c}{c-a}$$ $$c=\frac{a+b \pm i(a-b)\sqrt{3}}{2}$$ Or equivalently, $$r=\frac{-1 \pm i\sqrt{3}}{2}$$ that contradicts with $r^3+r+...


3

A collection of hints. You may prove through angle chasing or the cosine theorem that $DC'=DB'$. We have $\widehat{C'AB'}=3\widehat{A}$ and $\widehat{C'BD}=\widehat{B'CD}=\pi-(\widehat{B}-\widehat{C})$: notice that its supplementary angle is exactly the angle between $AH$ and $AO$, if $H$ and $O$ are the orthocenter and circumcenter of $ABC$ (they are ...


1

Lets say there are $n$ students numbered $1,2,3...,n$. The lockers which are opened an odd number of times will remain open till the end. The student $i$ interacts with locker $j$ if $i|j$. Thus lockers having odd number of divisors will remain open till the end. Since only perfect squares have odd number of divisors. The number of open lockers is $[\sqrt n]$...


3

Remark (1). Let $f:\mathbb{R} \rightarrow \mathbb{R}$ is a solution of given functional equation such that $f$ is non constant function with $f(1)=1$. Define $$Fix(f)=\{ x>0\ : \ f(x)=x \}.$$ $(1)$ For any $x\in Fix(f)$ and any $y\in \mathbb{R}$ $$f(xy)=xf(y).$$ $(2)$ $Fix(f)$ is a subgroup of the multiplicative group of positive real numbers. ...


0

In order to improve mathematics in Programming Competition you can solve problems in Project Eular ( Click Here) . You can visit Topcoder , There are some very good tutorials on Math , Number Theory , Combinations , probability .


0

COMMENT.-An example when the domaine is $\mathbb R\setminus\{-1\}$ instead of $\mathbb R$ $$f(x)=\begin{cases} 1\text{ when }x=1\\ 0\text{ when }x\ne 1\end{cases}$$ $$x=1\Rightarrow\begin{cases} f(x)f(x+y)=1\cdot f(1+y )=f(1+y)\\f(x^2+yf(x))=f(1+y\cdot 1)=f(1+y)\end{cases}$$ $$x\ne 1\Rightarrow \begin{cases} f(x)f(x+y)=0\cdot f(x+y)=0\\f(x^2+yf(x))=f(x^2+y\...


3

Let me do the calculations. The method is the one pointed out by Greg Martin in the comments. Suppose $k = 2^m \ell$, where $\ell$ is odd and $\neq1$. Then $$2^n \bmod k \geq 2^m$$ ($2^n \bmod k$ is divisible by $2^m$, but non-zero). Hence, counting the number of $k$'s of the form above (for each value of $m$): $$\sum_{k=1}^{n} 2^n \bmod k \geq \sum_{m=0}^...


1

For Part (a), examine each player's payoff for each of their two possible strategies with the other five players' strategies held fixed. So Player 1's payoff is $6-1=5$ if she chooses vaccination and $\frac{3}{6}6+\frac{3}{6}0=3$ if not. Player 2's payoff is $6-2=4$ if she chooses vaccination, and $\frac{3}{6}6+\frac{3}{6}0=3$ if not. The analysis is ...


2

There are many solutions. Let $\pi$ be any permutation of $\{1,\ldots,n\}$ and let $$ k_i=10^{i-1}\cdot2^{\min(\pi(i),n-1)}. $$ The $k_i$ are distinct because they are divisible by distinct powers of $5$. We have $$\begin{eqnarray*} \sum_{i=1}^n\frac{10^{i-1}}{k_i} &=&\sum_{i=1}^n\frac1{2^{\min(\pi(i),n-1)}}\\ &=&\sum_{i=1}^n\...


1

Maybe this helps: You give it the pizza slices and it gives you the max pizza amount that player $A$ can guarantee. #include <bits/stdc++.h> using namespace std; int A[100]; int maxline( vector <int> V){ //this solves the problem when the slices are in a line int N=V.size(); int M[100][100]; //M[i][j] stores the max pizza amount ...


2

Let $P$ be the intersection point inside $\triangle{ABC}$. Let $D$ be the intersection point of $AP$ with $BC$, and let $E,F$ be the point on $AP$ such that $AE\perp BE, AF\perp CF$ respectively. Since $\triangle{APB}=\triangle{APC}$, we have $BE=CF$ from which we know that $\triangle{BED}$ and $\triangle{CFD}$ are congruent, and so $BD=CD$. Hence, we know ...


3

Assume that $\frac{BP_A}{P_A C}=\lambda$ and $\frac{CP_B}{P_B A}=\mu$. By Ceva's theorem $\frac{AP_C}{P_CB}=\frac{1}{\mu\lambda}$. Moreover: $$ [BPP_A] = \frac{BP_A}{BC}[BPC]=\frac{BP_A}{BC}\cdot \frac{CP_B}{CA}[ABC] $$ hence $$ [BPP_A]=\frac{\lambda}{\lambda+1}\cdot \frac{\mu}{\mu+1}[ABC].$$ In a similar way you may compute $[CPP_B]$ and $[APP_C]$ in terms ...


3

It suffices to consider powers of $2,3$ separately. If $v_2(a)=r$ then $r≤v_2(b)≤6$. Of course, $v_2(a)\in \{0,1,2,3,4,5,6\}$. If $v_2(a)=0$ there are $7$ possibilities for $v_2(b)$. If $v_2(a)=1$ there are $6$ possibilities for $v_2(b)$, and so on. Thus, considering only powers of $2$, we get $$7+6+5+4+3+2+1=\frac {7\times 8}2=28$$ possible pairs. The ...


4

$ x^4 - 4x^3 - x^2 -8 x + 4$ to try to factor it as a product of two polynomials with degree two I will try this $ x^4 -4x^3 -x^2-8x+4=(x^2+ax+c)(x^2+dx+e) $ but the constant term is 4 so we have two choices $ c=1, e=4$ or $ c=2, e=2$ if you choose the second you get the equations $ a+d=-4, 4+ad=-1, 2a+2d=-8$ if you solve them you come up with a solution ...


30

Divide $x^4-4x^3-x^2-8x+4=0$ with $x^2$ in order to get the following $x^2-4x-1-\frac{8}{x}+\frac{4}{x^2}=(x+\frac{2}{x})^2-4(x+\frac{2}{x})-5=(x+\frac{2}{x}-5)(x+\frac{2}{x}+1)$. Finally, result is $(x^2-5x+2)(x^2+x+2)$.


1

Factor as $$(x^2-5x+2)(x^2+x+2)=0$$


0

We start with $$\begin{array} \\ \tag{1} a &:& t(d) \lor t(e) \\ b &:& t(c) \\ c &:& k(d) \lor t(d) \\ d &:& k(a) \lor t(a) \\ e &:& \lnot k(a) \end{array}$$ So we have five statements (a,b,c,d,e). All statements except the statement of the king and the treasurer must be true. We have some ...


3

(This space intentionally left blank.)


2

Hint: Divide the larger hexagon into $24$ congruent triangles as shown below: Can you tell what fraction of the larger hexagon's area is taken up by the smaller hexagon?


1

HINT: Those triangles are equilateral, so $h=\frac{\sqrt3}2b$. The new triangles are also equilateral, and they have side $h$.


14

The fibonacci sequence goes as follows: $\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} F_n &1&1&2&3&5&8&13&21&34&55&89&144&233&377&610&987\\ F_n\pmod{29}&1&1&2&3&5&8&13&21&5 &26&2&28&1&0&1&1\end{array}$ It is clear that the ...


1

The answer is $D$. In 1-3, solid squares go small, small, big in the bottom left. In 2-6, empty squares repeat the pattern by going small, small, big (top left instead). In 1-3, triangles at the top go empty right, full left, full left. In 2-6 the pattern is repeated (at the bottom instead): empty right, full left, full left. So square 6 has a big empty ...


0

I would say D because of the symmetry of the situation and because the first square has colours different --> the corresponding 3rd square has equal colours, the 2nd has equal colours --> corresponding 4th square has different colors, therefore the missing square must have different colours.


2

From the equality $n = d_6^2 + d_7^2 - 1$, we see $d_6$ and $d_7$ are mutually prime, $d_7 \mid d_6^2 - 1 = (d_6 - 1)(d_6 + 1)$, and $d_6 \mid d_7^2 - 1 = (d_7 - 1)(d_7 + 1)$. Suppose $d_6 = ab$ and $d_7 = cd$ with $1 < a < b$ and $1 < c < d$. Then $n$ has $6$ divisors smaller than $d_6$, namely $1$, $a$, $b$, $c$, $d$, $ac$. Hence one of $...


2

For part (a), it can be easily deduced that $f$ does not have degree 2. Further, $f$ cannot have degree 3, as an odd degree polynomial has no global minimum. So assume $$f(x) = sx^4 + bx^3 + cx^2 + dx + e$$ with $f(a) = -\sqrt{2}, f'(a) = 0$. As one last piece of guesswork, let $a = k\sqrt{2}$. Then we have $$4sk^4 + 2bk^3\sqrt{2}+2ck^2+dk\sqrt{2}+e = -\...



Top 50 recent answers are included