# Tag Info

0

Starting from the equivalent inequality $$\frac{(a+c)(b+d)}{a+b+c+d} \ge \frac{ab}{a+b} + \frac{cd}{c+d} = \frac{ab(c+d) + cd(a+b)}{(a+b)(c+d)}$$ and cross-multiplying results in \begin{align}(a+b)(a+c)(b+d)(c+d)&\geq\{(a+b)+(c+d)\}\{ab(c+d)+cd(a+b)\}\\&=cd(a+b)^2+ab(c+d)^2+(a+b)(c+d)(ab+cd)\end{align} which (after subtracting ...

0

It is well known that $n\geq0$ lines $g_k$ $\>(1\leq k\leq n)$ divide the plane into at most $$p_n={1\over2}(n^2+n+2)$$ compartments. (For an induction proof, use that $g_{n+1}$ intersects the first $n$ lines in at most $n$ points, which means that at most $n+1$ compartments are divided in two.) Given $N$ points in the plane the minimal number $n$ of ...

0

Answer depends upon the position of the points. Nevertheless, the number of minimum lines required to separate all points is always less than $[\frac{n+1}{2}]$, where $[x]$ denotes greatest integer less than equal to $x$.

1

It's a cycling sequence, with period 8. \text{Let }k = (\sqrt{2} + 1) \\ \text{then }k^2 = (2+2\sqrt{2} + 1) \\ \text{and }k^2-2k = (2-1)=1 \\ \begin{align} \hspace{2in}x_2 &= \frac{kx_1-1}{k+x_1} \\ x_3 &= \frac{k\frac{kx_1-1}{k+x_1}-1}{k+\frac{kx_1-1}{k+x_1}}\\ &= \frac{k(kx_1-1)-(k+x_1)}{k(k+x_1)+(kx_1-1)}\\ ... 2 Yes, @mapierce271 is right. Let us assume that the first ball is white. (First ball we look at, since a circle has no 'first' point). I would start by seeing the number of balls between the 2 white balls: a) 0 - Yes, it is possible. WWRRRR b) 1 - This, too, can be done. WRWRRR c) 2 - Again. WRRWRR d) 3 - This would lead to WRRRWR, which is a cycled ... 4 I think that you are over-thinking it. Since the balls are identical, there are only3$arrangements: $$\dots WWRRRR \dots\quad \dots WRWRRR \dots\quad \dots WRRWRR \dots$$ where$\dots$means that the circle wraps around. 1 Where they write $$a_1 + (a_1 + 1) + (a_1 + 1) + \cdots + (a_1 + 1) = ka_1 + k - 1$$ is that what you're wondering about? Because$a_1$is written$k$times, and$1$is written$k-1$times (after each of the$k$instances of$a_1$, except the first one), so that's what it becomes. Clearer ways of writing the right-hand side in that respect include$k(a_1 + ...

6

First of all, welcome to Math Stackexchange! There is no such thing as a single vector representation over all of these four points. Mathematically, a vector in the Euclidean $\mathbb{R}^n$ is a tuple of $n$ numbers — for example $$\begin{pmatrix}a\\b\end{pmatrix},\quad a,b\in\mathbb{R}$$ If you consider the 2-dimensional case, just as in your question. ...

1

The second option would be upper-bounded by the first. See the triangle inequality.

0

So we start by the fact that $f(k) ≤ k$ for any $k$ and we can determine using strong induction on $n$ the value of $f (n)$ : if we have known $f(1),f(2),...,f(k)$ then by setting $n = k + 1$ we compute $f(k + 1)$. (This is already mentioned above) But this (strong induction) implies that $f$ is defined uniquely And, as was shown in the first answer, The ...

0

The given partitions $(a_1, \dots, a_k)$ are all given by \begin{align*} a_i &= \begin{cases} a_1 & \text{if $i \leq p$}; \\ a_1 + 1 & \text{if $i > p$} \end{cases} \end{align*} for $p = 1, \dots, k$. Count the number of pairs $(a_1, p)$ for which the partition sums to $n$.

1

HINT: As an alternative to an inductive approach: for each possible choice of $k$ (the number of terms), there is exactly one choice of $a_1$ that allows the inequalities to be satisfied and the sum of the $a_i$’s to be $n$.

2

For a given positive integer $n$, let $p_i(n) = (a_1, a_2, \ldots, a_k)$ be a given partition of $n$ that satisfies the criteria. For each such partition $p_i(n)$, how many ways are there to generate a unique partition $p_i(n+1)$? Is there a bijection?

0

I noticed that you had for n = 2 the solutions as 1+1, 2+0 but 2+0 cannot be a solution based on the problem constraints. Edit: My bad, as I was working through 2+0 did not make sense but 2 is clearly a solution. But I was able to prove this by thinking for each n, how many ways can you sum to n with k numbers (knowing the largest possible k is k =n where ...

1

No need to use $\phi$, simply apply inclusion/exclusion principle: $2012-\lfloor\frac{2012}{2}\rfloor-\lfloor\frac{2012}{3}\rfloor-\lfloor\frac{2012}{5}\rfloor+\lfloor\frac{2012}{2\times3}\rfloor+\lfloor\frac{2012}{2\times5}\rfloor+\lfloor\frac{2012}{3\times5}\rfloor-\lfloor\frac{2012}{2\times3\times5}\rfloor$

8

The absolute least value you can get is a rectangle topped by a half circle (the circle has the best area to arc length ratio of any shape) with a total arc length of $2 \big(1 - \frac{\pi}{8}\big) + \frac{\pi}{2} \approx 2.78539$. If you use Fourier approximation, you can come arbitrarily close to this limit. (I assume the fun of this challenge is to find ...

-1

$$f(x)=\begin{cases} cx & \text{ if } 0 \le x \le \frac{1}{c} \\ -cx+c & \text{ if } 1-c < x \le 1 \\ 1 & \text{ otherwise } \\ \end{cases}$$ If we take $c\to\infty$ we get that it is an arc length of 3.

1

You can think of it like this: The envelopes have fixed positions $1, 2, 3, 4, 5, 6, 7, 8$. Now which letter gets which envelope is described by an 8-tuple. The 8-tuple $(2, 1, 3, 4, 5, 6, 7, 8)$ means that he gets every letter right, except for letter 1 and 2. Your sample space is the set of all permutation of the number 1, ... 8: $$\Omega = \{(x_1, ... 1 The answer is 182\times 5=910. An optimal solution is \lbrace x\in[1,2000] | x\equiv 1,3,4,6 \ \text{ or } 9 \ \textsf{mod} \ 11\rbrace. (with a little more work, one can show that there are exactly 183 optimal solutions and describe them). Call a set A of integers distinguished |a-b| is not equal to 4 or 7 for any a,b\in A. Lemma 1. If ... 2 If exactly 6 of 8 are right, then exactly 2 of them have been swapped. So choose two of then to exchange. \binom{8}{2} = 28. 4 First, note the 4 is redundant. Then, a number n is divisble by none of 2,3,5 if and only if \gcd (n, 30)= 1. So, n is in a residue class prime to 30. There are \phi(30)=8 of those. So among any conscutive 30 numbers you have 8. This gives you the count from 1 to 2010. Then check the rest by hand. 4 You should ignore the "divisible by 4", since that is covered by "divisible by 2". So reword the question as How many positive integers less than 2013 are divisible by none of 2,3,5? This is close to a standard combinatorics problem. Find how many numbers are divisible by 2 (namely \left\lfloor\frac{2012}2\right\rfloor), how many by 3, ... 0 Start with x=0. You should be able to see what to do from there. 0 A number that meets the criteria is for example 1701971548138242677145600 = 5^2 3^{10} 2^{60}  it is divisible by 2, 3 and 5. The divisor count is (2+1)(10+1)(60+1)=2013 and, now answering OP's question: the sum of the exponents in the prime factorization is 72. 0 If abc = 0, WLOG a = 0, and so the common root must b x = - \frac{c}{b}. However, it is easy to check that  0 = b \frac{-c^3}{b^2} + c \frac{-c}{b} = \frac{ -c^3-c^2b } { b^2} = - \frac{ c^2 (c+b) } {b^2}, hence we must have  c = -b, which gives us x=1. Then,  0 = bx^3 + cx + a = bx^3 - bx = bx(x-1)(x+1) would have 3 real roots and we are done. ... 5 Note that any two distinct elements 5^{p_1} 13^{q_1} 31^{r_1} and 5^{p_2} 13^{q_2} 31^{r_2} are incomparable (neither divides the other) if p_1 + q_1 + r_1 = p_2 + q_2 + r_2. So a mutually incomparable set is given by$$ S_n = \left\{5^p 13^q 31^r \;\big\vert\; p+q+r=n;\; 0\le p,q,r \le 200\right\} $$for any n. The size of this set is maximal when ... 3 if a=1, for the rest 9 places, 1 can be taken anywhere, and also the rest 8 places must be 0 or the sum would exceed 2. Also if a=2, then the rest 9 places must be 0, or sum would exceed 2. Hence there are 9+1=10 such numbers. 4 since \sqrt{x} \ge 0 so is \sqrt{(B+3)^2}, minimum at B=-3, similarly for the first term we get A=B=-3 For the subsequent part in C use completing the square to arive at (C-2)^2 we know, x^2 \ge 0 so C=2 Thus, A+B+C=-3+-3+2=-4 2 It can be written as$$\sqrt{A-B}+|B+3|+(C-2)^2\ge 0$$and the zero is clearly achieved only for C-2=0, B+3=0, A=B, which gives A+B+C=-4. 0 Inequalities are very easy to compose. You start from self-evident inequalities like x^2\geq0 or well know ones like inequalities between means, or between symmetric polynomials, or geometric inequalities like \text{Area}(A)\geq\text{Area}(B) when A\supset B, etc. and then you use very evil properties of the sign \geq, plus some algebraic massaging ... 2 Notice that$$2^{1} (\bmod 10) \equiv 2 \\ 2^{2} (\bmod 10) \equiv 4 \\ 2^{3} (\bmod 10) \equiv 8 \\ 2^{4} (\bmod 10) \equiv 6 \\ 2^{5} (\bmod 10) \equiv 2 \\ 2^{6} (\bmod 10) \equiv 4 \\ \vdots$$leads us to see$$2^{n} (\bmod 10) = 2^{n+4} (\bmod 10)$$Hence$$2^{2013} (\bmod 10) = 2^{(4\cdot 503)+1} (\bmod 10) \\ = 2^{1} (\bmod 10)$$Now what can ... 3 As (2^{2013},10)=2 let us find 2^{2013-1}\pmod{\dfrac{10}2} Now 2^2\equiv-1\pmod5\implies2^{2012}=(2^2)^{1006}\equiv(-1)^{1006}\equiv1\pmod5 Now as a\equiv b\pmod m\implies a\cdot c\equiv b\cdot c\pmod{m\cdot c} \implies2^{2012}\cdot2\equiv1\cdot2\pmod{5\cdot2} 1 Once you've used the angle bisector theorem you know that the center bisector breaks up 98 into 42 and 56. Now drop a height to the 98 side. You know that it has to be closer to the 84 side than that center bisector. Why? Now break up the base into 42-x and 56+x according to where you put the height. Using the Pythagorean theorem, we know 84^2 - (42-x)^2 = ... 0 The Algorithm: Input: n=147,a=4258 Set x_1=1 Set x_2=0 Set y_1=0 Set y_2=1 Set r_1=n Set r_2=a Repeat until r_2=0: Set r_3=r_1\bmod{r_2} Set q_3=\lfloor\frac{r_1}{r_2}\rfloor Set x_3=x_1-{q_3}\cdot{x_2} Set y_3=y_1-{q_3}\cdot{y_2} Set x_1=x_2 Set x_2=x_3 Set y_1=y_2 Set y_2=y_3 Set r_1=r_2 Set r_2=r_3 If y_1>0 ... 1 Actually each remainder in the euclidean algorithm satisfies Bézout's identity. Let's start with r_0=4258, r_1=147. If r_{i+1}  is the remainder at the i-th step (dividing r_{i-1} by r_i), write r_i=u_i \cdot 4258+v_i\cdot147. Let q_i be the corresponding quotient. The algorithm translates into the relations:$$u_{i+1}=u_{i-1}-q_iu_i,\qquad ...

1

In your back substitution you're collapsing some things too much. In the second back-sub line you should have $1$ as a combination of $5$ and $142$. That is $$1=5-2\cdot\left(142-28(5)\right)=5\cdot(57)-142\cdot(2)$$. In your next line you should sub in $5=147-142$ and get $1$ as a combination of $147$ and $142$. And so on.

2

How could you do better than the problems and solutions themselves for past Putnam exams? 1938-1964 1965-1984 1985-2000 For a Putnam archive of past exam questions and solutions, check out this website maintained by Kiran Kedlaya. There are, of course, many other resources, but these are by far the best I know to date.

0

Perhaps the most elegant solution is to take all $10$ from the $10$-box and deposit the excess $7$ in the $7$-box. Then remove those $7$ and deposit the excess $4$ in the $4$-box. Then remove those $4$ and deposit the excess ball in the $10$-box. Now apply the same idea to the $7$-box: remove all $7$, deposit the excess $4$ in the $4$-box, immediately remove ...

0

Clearly we must have $x_3<4$, $x_2<16$, and $x_1<256$, so the largest possible value of $x_1$ is $255$. Since $x_3>1$, we know that $x_3\ge 2$ and hence that $x_2\ge 4$. This implies that $x_1\ge 16$. Thus, the range is from $16$ through $255$, the difference being $239$.

1

We can work backwards more easily than we can work forwards. Firstly, what does a number $x$ need to satisfy to have $\lfloor x \rfloor = 1$? Easy. We need: $$1\leq x < 2.$$ Well, suppose that $\sqrt{y}=x$ or, equivalently, $y=x^2$. Well, obviously we just square the above equation (as all of its terms are positive): $$1\leq x^2 < 2^2.$$ Suppose ...

2

The number of representations of a positive integer as a sum of two squares depends on the number of prime divisors of the form $4k+1$ (see Cox, Primes of the form $a^2+k b^2$). If we take the first two primes of such a form, $5$ and $13$, we have that $5\cdot 13$ can be represented as: $$65 = 1^2+8^2 = 4^2+7^2$$ so we have a solution with $abcd = 224$. ...

0

Hint $\$ By the FTA (Fundamental Theorem of Arithmetic - existence and uniqueness of prime factorizations), if $\,p,q,r\,$ are primes then the positive divisors of $\, p^i q^j r^k$ are precisely the naturals of the form $\,p^{\bar i}q^{\bar j} q^{\bar k}\,$ where $\,\bar i< i,\ \bar j< j,\ \bar k < k.\$ Thus the set of divisors is in bijection ...

2

Write out the numbers $\bmod 4$ in distinct lists: $1,5,9,13,\dots 1997$ $2,6,10,14,\dots 1998$ $3,7,11,15 \dots 1999$ $4,8,12,16\dots 2000$ Transform it into a graph that looks as follows but with $500$ columns, we want a maximum independent set of the graph:

0

There as many solutions as divisors of $680$. Decompose $680$ into its prime factors: $$680=2^3\cdot 5^1 \cdot 17^1.$$ Hence there are $4\cdot2\cdot 2=16$ solutions.

1

$$680=10\cdot68=2^3\cdot17\cdot5$$ So, the number of positive divisors $=(3+1)(1+1)(1+1)$

2

Here is one way to end up with $3$ balls total (which is the minimum possible by the comments above): First take all the balls in the $10$-bin, put $3$ aside, and put the last $7$ into the $4$-bin. You now have $(17, 10, 0)$ balls. Take $7$ balls from the $7$ bin, put three aside and the rest in the $4$-bin. You now have $(21, 3, 0)$ balls. Take four balls ...

1

With different types of equations come different techniques, and several different ones will be used in the following, but the key idea is usually to look for symmetry. We can actually solve the first equation $2^{\cos x}=|\sin x|$ extremely quickly given those answer choices. We note that $|\sin x|$ has period $\pi$ and that $2^{\cos x}$ has period $2\pi$, ...

6

Solution 1: Only use Cauchy-Schwarz inequality : $$(a^2_{1}+a^2_{2}+a^2_{3})(b^2_{1}+b^2_{2}+b^2_{3})\ge(a_{1}b_{1}+a_{2}b_{2}+a_{3}b_{3})^2$$ let $$a_{1}=x^{\frac{3}{2}},a_{2}=y^{\frac{1}{2}},a_{3}=1$$ $$b_{1}=x^{\frac{1}{2}},b_{2}=y^{\frac{3}{2}},b_{3}=1$$ so we have $$(x^3+y+1)(x+y^3+1)\ge (x^2+y^2+1)^2$$ so $$\sqrt{(x^3+y+1)(y^3+x+1)}\ge x^2+y^2+1$$ ...

1

You can use complex numbers to solve this problem. The computation is a little bit complicated. Without loss of generality, let $$A=0, B=1, C=e^{i\theta}, D=d, E=ae^{i\theta}.$$ Here $\theta>0, 0<d<1, a>1$. Sine $F$ is the intersection of the segments $BC$ and $DE$, we have $$F=(1-s)B+sC=(1-t)D+tE.$$ Separating the real part from the ...

0

Simple enumeration works well for this question because the number of rows is small:  \begin{array}{ccccccccc}&&&& 0 &&&& \\ \hline &&&& 1 &&&& \\ &&& 1 && 1 &&& \\ \hline &&& 3 && 3 &&& \\ && 1 && 3 && 1 ...

Top 50 recent answers are included