Tag Info

New answers tagged

0

Just to allow this question to disappear from the "unanswered" list, here's a rephrase of one of the proves found in the link Elaqqad gave in a comment, with a few minot gaps removed. Let $n$ be such a number and $p$ the smallest prime divisor of $n$ (which exists because $n>1$). Write $n=p^km$ with $p\nmid m$ and $k\ge 1$. We shall show that $m=1$. ...


0

It might be more helpful to do this recursively. Let $T(n) = \prod_{k=1}^n k!$. We will use the notation: $2^{r} \| m$ to mean that $2^r$ is the largest power of $2$ that divides $m$. Then we have $2 \| 2! = T(2)$. We also know that $2 \| 3!$, so $2^2 \| T(3) = 3! T(2)$. Continuing: $$2^3 \| 4!$$ $$2^3 \| 5!$$ $$2^4 \| 6!$$ $$2^4 \| 7!$$ $$2^7 \| 8!$$ ...


0

How many times $2$ divides the product $\prod_{i=1}^{19}i!$ ? Let's call each term inside a factorial $i$. That way, $i = 1$ occurs in 19 factorials, $i = 2$ occurs in 18 factorials, and $i = 3$ occurs in 17 factorials etc. $i = 2$ occurs 18 times. $1 \times 18 = 18$ $i = 4$ occurs 16 times. $2 \times 16 = 32$ $i = 6$ occurs 14 times. $1 \times 14 = 14$ $i ...


2

A simple trick to compute $k$ such that $2^k|n!$ is to compute $\sum_{i=1}^\infty \left\lfloor\frac{n}{2^i}\right\rfloor$, this is because $n$ has $[n/2]$ numbers divided by $2$, if we pick out these numbers and find out that there're $[n/4]$ numbers divided by $4$.. If we continue this procedure, we see that ...


2

$ x \equiv 0\pmod{\!17}\!\iff\! x = 17\color{#c00}n.\,$ $\, {\rm mod}\ 9\!:\ {-}1\equiv x\equiv 17n\equiv -n$ $\!\iff\!$ $n\equiv 1$ $\!\iff\!$ $\color{#c00}{n = 1\!+\!9k}$ Therefore $\ x = 17\color{#c00}n = 17(\color{#c00}{1\!+\!9k}) = 17+153k$


-1

Hint first solve $$ 9x\equiv 1\mod 17$$ which gives $x\equiv2\mod17$. Then solve $$17x\equiv1\mod 9$$ which gives $x\equiv-1\mod9$. Then you will get $$ x\equiv 2\times0\times 9+(-1)\times(-1)\times 17=17\mod 153. $$


0

You start with B├ęzout's identity: $2\cdot 9-1\cdot 17=1$, from which you derive the basic solution: $$x=2\cdot \color{red}{0}\cdot 9-1\cdot(\color{red}{-1})\cdot 17=17.$$


2

You will indeed use the pigeonhole principle: if $n = km + 1$ objects are distributed among $m$ boxes, then the pigeonhole principle asserts that one of the box will contain at least $k + 1$ objects. To expand a bit about my comment, you can even actually use the result for $6$ vertices an $2$ colors, to solve for $17$ vertices and $3$ colors. The simpler ...


1

You cannot conclude from $$\sin(\frac{142m\pi}{n}) = 0$$ that $\frac{142m\pi}{n} = \pi$. In fact, this would give $$z^{142} = -1$$ (since $\cos\pi=-1$), which is clearly not what you want. Letting $\theta = \frac{142m\pi}{n}$ for brevity, the condition $z^{142}=1$ is equivalent to $\cos\theta = 1$ and $\sin\theta = 0$. So in fact $\theta = 2k\pi$ in ...


1

This is an example of the knapsack problem, a notorious group of combinatorics/optimisation problems, for which there are algorithms and approaches that are the best and fastest for varying constraints but none that give the best solution in the fastest time for all problems. In particular your problem is a discrete or classic knapsack problem: one in which ...


1

the maximum common divisor of the coins is $15$ cents so the best you can strive for is $15\cdot46$ cents which is actually $6.90$ dollars. You already proved it is possible. In general this is a hard problem, look up the frobenius coin problem in google.


2

Dan Schwarz (one of the major problem proposers for EGMO, RMM, Balkan...) has posted a solution at here. I'll briefly sketch it here. First, one takes the midpoints $M_1$, ..., $M_5$ of $A_1A_2$, ..., $A_5A_1$. Then at each angle $A_i$, one takes the circumcircle of triangle $M_{i-1}A_iM_{i+1}$ (which has radius $\frac 12 R_i$) and the point diametrically ...


1

Your target is to have all six numbers the same, i.e. $$a_1 = a_3 = a_5 = a_2 = a_4 = a_6$$ which would then imply $$a_1 + a_3 + a_5 = a_2 + a_4 + a_6$$ and so $$S=0$$ which we know is impossible from the starting point as $S$ is a constant $2$ under the permitted change. The argument in words is that if the sum of the values in the even positions and the ...


1

Each factor of the product with exponent $2^k$ is equal to the difference with exponent 2^(k+1) divided by the difference with the same exponent of the considered factor (because an scholar identity with squares). Then the product finally gives the equation 6^(64) - 5^64 = $6^x$ - $5^y$. WARNING: there is an obvious solution x = y but it is not unique! ...


9

Use the fact that $a^2-b^2 = (a+b)(a-b)$ Multiplying $(6-5)$ on your LHS, we obtain: $$\prod\limits_{k=0}^5(5^{2^k}+6^{2^k})=(6-5)\prod\limits_{k=0}^5(5^{2^k}+6^{2^k})$$ $$=(6^2-5^2)\prod\limits_{k=1}^5(5^{2^k}+6^{2^k})=(6^4-5^4)\prod\limits_{k=2}^5(5^{2^k}+6^{2^k})=...$$ Iterating for all the terms in the products, you should get $x=y=2^6=64$, so $x-y=0$


0

Here's a relatively simple way with just some basic trigonometry. Based on this diagram: We have $$\sin\alpha=\frac3s$$ $$s\sin\beta=4$$ However, notice that $\beta=120^{\circ}-\alpha$. Applying our subtraction rule for $\sin$, we have $$s\left(\sin120^{\circ}\cos\alpha-\cos120^{\circ}\sin\alpha\right)=4\\ \implies s\left( ...


-1

The questions says no calculators. It means you dont need it. It looks easy and it is. I dont know the math terms to explain but the answer is 3 times root 2. Draw a line where most obvious the height difference and find 15 degrees. Then find 45 degrees giving us the answer. Look at a geometry problem from a geometrical angle then its easy.


-4

As far as I can tell, there are three main ways to go at this problem. First, we can try to brute force it by exanding it all into one huge fraction. Only problem is, you end up with something like 81 terms in the numerator. I tried this and just got bogged down in the algebra. The second way is to consider it case by case; that is, for each x, y and z you ...


2

Multiplying and dividing each of the expressions numerator by $(1 + x)$, $(1 + y)$ and $(1 + z)$ respectively: $$ \frac{z^3+1}{(z+1) \left(x^2+z^2+1\right)}+\frac{x^3+1}{(x+1) \left(x^2+y^2+1\right)}+\frac{y^3+1}{(y+1) \left(y^2+z^2+1\right)} $$ Further simplifying: $$ 1+ \frac{x^2-x+1}{x^2+y^2+1}-\frac{x^2+z}{x^2+z^2+1}+\frac{y^2-y+1}{y^2+z^2+1} $$ ...


3

Here is a way to use CS to solve the inequality. First, we re-write what we want to prove as $$\frac{(x+1)^2}{x^2+1}+\frac{(y+1)^2}{y^2+1} \ge 2-\frac{(z+1)^2}{z^2+1} = \frac{(z-1)^2}{z^2+1}$$ Now the constraint gives $z = \dfrac{x+y-xy}{x+y-1}$. Using this, we need to only show $$\frac{(x+1)^2}{x^2+1}+\frac{(y+1)^2}{y^2+1} \ge ...


2

Let's slightly generalize the problem by considering clocks where the hour hand makes one round in $n$ hours (for our normal clocks we have $n=12$; however e.g. for this clock you have $n=24$). Let's measure the time in hours. The minute hand makes one cycle every hour, so it gives the position modulo $1$; that is, the minute hand at times $t_1$ and $t_2$ ...


3

Using (Like) pigeonhole principle Let's assume that every $x_i=\epsilon_i+h_i$ with $h_i \in \Bbb Z$ and $\epsilon_i\in [0,1]$ and assume that (we can alawys find an increasing order for $\epsilon_i$): $$0\leq \epsilon_1\leq \epsilon_2\leq \cdots \leq \epsilon _n<1$$ if for every $i$ we have $\epsilon_{i+1}-\epsilon_i>\frac{1}{n}$ take $(i,j)=(1,n)$ ...


8

This problem is "isomorphic" to the one where you have the $n$ points on a circle and must show that two of them are as near as $1/n$ to each other. This is because you can take away an integer from $x_i - x_j$, so it always lands on $[0, 1]$ and zero and one are identyfied.


2

Since $r,s$ are two roots of $x^3+ax+b=0$, we have $$ r^3+ar+b=0,s^3+as+b=0 \tag{1}$$ and hence $$ (r^3-s^3)+a(r-s)=0. $$ Assuming $r-s\neq0$, we have $$ r^2+rs+s^2+a=0.\tag{2}$$ Similarly since $r+4,s-3$ are two roots of $x^3+ax+b+240=0$, we have $$ (r+4)^3+a(r+4)+b+240=0,(s-3)^3+a(s-3)+b+240=0\tag{3}$$ and hence $$ [(r+4)^3-(s-3)^3]+a(r-s+7)=0.$$ Assuming ...


5

Reformulate: Let $a,b \in [0,1)$ and $m,n \in \mathbb Z$. Solve $$(m+a)n = 7\\ (n+b)m = 8$$ Rearrangement gives $$nm = 8 - bm = 7 - an$$ The product on the left is an integer so we already know that $bm, an\in \mathbb Z$ or in other words $$a = \frac kn; \quad b = \frac lm$$ With $k,l\in\mathbb Z$. Substituting this back gives us $$mn = 8-l = 7-k$$ ...


2

Let's measure time in units of $12$ hours, measure angles as a fraction of $2\pi$ and consider a period from midnight to noon. Time will run from $0$ to $1$. The hour hand position is $t$. The minute hand position is $12 t \pmod 1$, the fractional part of $12t$ The times when you can't tell the time is when you can interchange the hands and get a legal ...


0

Another solution is to find the common "left header" of m and n. Bitwise AND of this common left header definitely results in 1, while the remaining right part results in 0 since at least 1 bit in a number between m and n is 0. Below is the Python code: def rangeBitwiseAnd(self, m, n): shift = 0 #find the common left header (or, same prefix) of m ...


0

Under $H_0,$ the random variable $X$ has the distribution $Binom(4,.2),$ so the PDF (or PMF) which gives $P(X = k),$ for $k = o, 1, 2, 3, 4,$ can be computed as below (unless you know about R statistical software, ignore the first two rows below; they are just a quick way to make the table). k = 0:4; pdf = dbinom(k, 4, .2) cbind(k, pdf) k pdf 0 ...


6

$x^3+x^2=2^y+16$. The RHS is positive, so $x^2(x+1)>0\iff x\ge 1$. Since $2^y$ is an integer, we have $y$ is a positive integer too ($y=0$ won't give a solution). $x,y$ are positive integers. $x^3+x^2-16=2^y$. You see a cubic polynomial on the LHS that could easily be strictly bounded between two consecutive cubes (namely $x^3$ and $(x+1)^3$) for most ...


0

Hint: $(x+y+z)^2=x^2+y^2+z^2+2(xy+yz+xz)$ Hint 2: this is a quadratic equation which places constraints on $x+y+z$ and $x^2+y^2+z^2$


5

I think my method is essentially equivalent to Archaick's, but it might make it more clear how you can count without it being brute force per se. Note that the number we are squaring is $\frac{10^{1992}-1}{9}$, so we are counting the digits of $$ \left(\frac{10^{1992}-1}{9}\right)^2 = \frac{1}{81}(10^{3984} - 2\cdot 10^{1992} +1) $$ To write this out as an ...


1

Sum $=9n+((n \bmod 9)-9) (n \bmod 9)$ where $n=$ number of digits. Check: n = 1992; 9 n + (Mod[n, 9] -9) Mod[n, 9] Total@IntegerDigits[FromDigits[ConstantArray[1, n]]^2]


2

For any positive integer $n$, let $p = \lfloor \sqrt{n} \rfloor$. To simplify derivation, we will treat all integrals involved as Riemann Stieltjes integral. This will allow us to integrate functions with jump discontinuities (e.g $\lfloor \sqrt{x}\rfloor$ ) by part. Change variable to $u = \sqrt{x}$, we have: $$\begin{align} \int_1^n ...


2

This is not particularly pretty but I figured I'd share the complications which arise in using this method. If you multiply this out the way that most elementary students are taught to multiply numbers (at least in the US), you'll have a sum of the form $(11\ldots11)\sum_{i=1}^{1992}10^i$, lined up into $1991*2+1=3983$ columns. In the first column, there ...


2

$$\lfloor\sqrt x\rfloor=\begin{cases}1,~x\in[1,4)\\ 2,~x\in[4,9)\\ 3,~x\in[9,16)\\ \vdots\\ 31,~x\in[961,1000]\end{cases}$$ Use this to rewrite the integral as, $$I=\left(\sum_{i=1}^{p-1}\int\limits_{i^2}^{(i+1)^2}ix\,\mathrm dx\right)+\int\limits_{p^2}^npx\,\mathrm dx$$ where $p\in\Bbb{Z}$ such that $p^2\leq n\leq (p+1)^2$ ...


0

Let $k$ be the greatest integer $k$ such that $k^2\leq n$ henece: $$\int_1^n x \lfloor \sqrt x \rfloor dx=\sum_{i=1}^{k-1}i\int_{i^2}^{(i+1)^2}xdx+k\int_{k^2}^nxdx=\sum_{i=1}^{k-1}i\frac{(i+1)^4-i^4}{2}+\frac{k(n^2-k^4)}{2} $$


2

Notice the pattern among last digits of ascending powers of $2$ Last digits of: $2^1$ is $2$, $2^2$ is $4$, $2^3$ is $8$, $2^4$ is $6$, $2^5$ is $2$, $2^6$ is $4...$ etc Also notice that the last digits of $2^4$, $2^8$, $2^{12}$, $2^{16}$... will all be $6$ We note that as $2004$ is also a multiple of $4$, therefore $2^{2004}$ will have a last digit of ...


1

We will show that $S(x)$ exists for a single polynomial of degree $d$ for each $d$. Let $P_d(x)=x(x-1)(x-2)\cdots(x-(d-1))$. So $P_0(x)=1$, $P_{d+1}(x)=(x-d)P_d(x)$. Then $P_d(x)$ is of degree $d$. Show that $P_{d+1}(x+1)-P_{d+1}(x)=(d+1)P_d(x)$. Thus, letting $S_d(x)=\frac{1}{d+1}P_{d+1}(x)$ we get that $S_d(x+1)-S_d(x)=P_d(x)$. Now, since the $P_d$ are ...


1

Perhaps this book is helpful for finding good strategies: Arthur Engel - Problem-Solving Strategies


0

Hint: Think about what the sequences are doing (by tracing out a line in the plane). The finite sequence starts at a point on the $y$-axis and moves around eventually stopping at some point on the $x$-axis. If essentially cut the 1st quadrant into two sections, the chunk on the inside of the loop (including the origin) and the chunk on the outside of the ...


1

The smallest (nonnegative) number that is evenly divisible by a given list of integers $a_1, \dots, a_n$ is called the least common multiple of $a_1, \dots , a_n$. So you could be looking for the least common multiple of $1, 2, \dots, 20$. With this keyword you will find varied information. A common multiple is always given by the product $a_1 \times \dots ...


0

Say that you have your convex polygon $P$ and sides $A_1,A_2,\cdots A_k$. Now, reflect $P$ across side $A_i$ to $P'$. Keep doing that; reflect $P'$ across some new side, etc ,etc. It is easy to see (but you have to do some induction -where you'll also use convexity- to make it rigorous) that in this way you can cover the whole plane. This can actually be ...


4

I can help find a generating function, but judging from my first impressions this is not a simple problem. Let us consider an infinite sum. We treat $x$ as a "dummy" variable, and consider only the coefficient in front of this. $$\sum_{n=0}^\infty s(n)x^n$$ Where $s(n)$ denotes the value of the amount of ways to create a number as a sum of 3's and 2's. ...


1

Without counting order ($3+3+2$ and $3+2+3$ are counted once) In this case the question is how many pair of non negative integers $(x,y)$ are there such that $2x+3y=N$ and in this case we have: If $N=2t$ then the number of solutions is $\left\lfloor\frac{t}{3} \right\rfloor$ If $N=2t+1$ then the number of solutions is $\left\lfloor\frac{t-1}{3} ...


2

Let $c_k$ be the number of ways that $k$ can be written as a sum of two's and three's. If reorderings are not distinct, the problem is trivial. By inspection, $c_0 = 1, c_1 = 0, c_2 = c_3 = c_4 = c_5 = 1$. After that, the pattern repeats, but increasing by $1$ with each group of $6$. That is to say, $$ c_k = \lfloor k/6 \rfloor + c_{k \bmod 6}, \qquad k ...


1

I'd start by just looking at how many $a$ and $b$ satisfy $$2a + 3b = N$$ The quickest way I'd do this is by checking $N - 3b$ is even for increasingly larger $b$.


0

There is no formal proof, because it is not always true. In fact, it is possible to select $A$ and $b$ such that (2) is feasible but (1) is not. The properties of the objective function are basically irrelevant. You just happen to be lucky for your particular instance. I am sure there are particular cases where the two problems are equivalent, mind you. But ...


4

Let's allow leading zeroes in the numbers, but require that they have exactly $2015$ digits ($10^{2015}$ is the smallest number with $2016$ digits). Then, following user MJD's hint, we realize that the number of such numbers with digits in non-decreasing order is the same as the number of ways to put $2015$ balls into $10$ boxes (the number of balls in the ...


1

First of all, note that $\angle VAW = 180^{\circ}-\angle BAC$ and $\angle BAC = 180^{\circ}-\angle CPB$, so $\angle VAW = \angle CPB$. It remains to prove that $\angle WVA = \angle BCP$. $QWAV$ is cyclic ($\angle QWA + \angle QVA = 180^{\circ}$), so $\angle WVA = \angle AQW = 90^{\circ} - \angle QAW = 90^{\circ} - \angle QAB$. Now $\angle QAB = \angle ...


1

$$\int 1/(x^{23}+x^{50}) dx=\int \frac{x^4}{x^{27}+x^{54}} dx$$ Now $$\frac{1}{x^{27}+x^{54}}=\frac{1}{x^{27}(x^{27}+1)}=\frac{1}{x^{27}}-\frac{1}{x^{27}+1}$$ This Yields $$=\int \frac{x^4}{x^{27}+x^{54}} dx=\int \frac{x^4}{x^{27}}dx+\int \frac{x^4}{x^{27}+1} dx$$ The first integral is easy to calculate, while for the second, unless I am missing ...



Top 50 recent answers are included