geometry
geometric transformation
rotation
analytic geometry

The Riverside Bed and Breakfast Inn serves three married couples breakfast at their round table which seats exactly six people.  The hostess wants to seat guests so that no husband and wife sit next to each other and the guests alternate male and female.  How many different arrangements are possible?  A rotation of an arrangement is not considered a different arrangement.

Is there a way to do this problem w/o listing all of the possibilities?

[hide]2[/hide]

A pentagon P has vertices A=(0,0), B=(7,0), C=(13,8), D=(5,14) and E=(0,14).  Line L passes through the origin and divides P into two quadrilaterals with equal perimeters.  What is the sum of the coordinates of the point F where L meets segment CD?  Express your answer as a decimal to the nearest tenth.

[hide]19.8[/hide]

[hide="1"]
Assume the people are A, A', B, B', C, C', where the ' represents the spouse of the person with the corresponding letter.

First seat A.  There is only one place for A' to sit, which is directly across the table (it cannot be in the other two possible spots because then A' would be next to A).

Then, since B is the same gender as A and A occupies one of the 3 seats, B has 2 spots they can go.  Then, B' has to sit across the table from them.

For C and C', there is only one possible spot for them to go.

Since the only place where we have a bit of an option of seating is when we seat B to the 2 seats not occupied by A, we have [b]2[/b] seating arrangements in total.
[/hide]

[quote="Ocean8"][quote="infinity4ever"]
First seat A.  There is only one place for A' to sit, which is directly across the table (it cannot be in the other two possible spots because then A' would be next to A).
[/quote]

I don't get this part.  Aren't there three choices for A'?  Thanks for your help.[/quote]No, you have to keep the male and female alternate seating... So if A is male, next to him is a female, and next to female is A'? Contradiction.

Thanks for the input on number 1.

Can someone post a solution to the second problem?

[hide="HINT #2"]Try taking the coordinates and graphing them on a coordinate plane.[/hide]


geometry
probability
FTW
Pythagorean Theorem

[b][i]15.[/i][/b] In a soccer league with 8 teams, each team earns [b]2[/b] points for a win, [b]1[/b] point for a tie and [b]0[/b] points for a loss. The league standings are based on the total points earned by each team. After a total of [i]40[/i] games, each team has played the same number of games and the top four teams have earned point totals of [b]15[/b],[b]13[/b],[b]12[/b], and [b]11[/b]  points. There is one team in fifth place and three teams tied for sixth place. How many points has the fifth-place team earned?

[b][i]23.[/i][/b]  A right triangle has side lengths [b]3[/b],[b]4[/b], and [b]5[/b] units. Another triangle has sides of length [b]4[/b],[b]x[/b], and [b]y[/b] units and has the same area as the right triangle.  If the value of [b]x[/b] is less than or equal to the value of [b]y[/b], what is the smallest possible value of [b]y[/b]? Express your answer in simplest radical form.

[b][i]30.[/i][/b]  Gracie starts at her house and walks one block east. After each block she walks, she flips a fair coin. She walks one block east if the coin lands heads; otherwise one block west. She stops her walk the first time she lands back at home. What is the probability she stops her walk after walking exactly eight blocks? Express your answer as a common fraction.

[hide="15"] Each game contributes two points overall to the sum of all points. There are forty games, so there are a total of eighty points. 51 points are already accounted for. Let the fifth place team have x points and the others have y.

We know x+3y=29. Taking mod 3, we have x is congruent to 2 (mod 3). If we let x be 2 or 5, there are no positive solutions. If x=8, then y=7. Thus, our answer is 8.[/hide]

[hide="23"] y will always be greater than or equal to x, so it is minimized when y=x. The area of the first triangle is 6. The second triangle is isosceles, so drawing an altitude to the side of length 4, we find that the altitude has length 12/4=3. Now using the Pythagorean Theorem, we have $ x\equal{}y\equal{}\sqrt{13}$.[/hide]

[hide="30"] Clearly she must walk east for her second block and west for her seventh and eighth blocks.

Thus, letting W=west and E=east, her moves are E E _ _ _ _ W W. There must be an equal number of Ws and Es, so at most, there are $ \binom{4}{2}\equal{}6$ ways to fill in the _s. However, some may result in Gracie reaching home before eight blocks. Checking, five of the six work (the only that doesn't is WWEE). There are a total of 128 possibilities (2 for each of the blocks after the first), so our answer is $ \frac{5}{128}$.[/hide]

[quote="xpmath"] Each game contributes two points overall to the sum of all points. There are forty games, so there are a total of eighty points. [/quote]
Aah... Thanks xp, but couldn't there be ties? How do you know if all the teams won or lost all forty games?  :huh:

regardless, there are 2 points. if there was a clean win, one team gets 2 and the other gets zero. if its a tie, each team gets 1, for a total of 2 points.

yeah. every game gives 2 points. so, there are 40*2 points. You have to not think about it as "how many wins did this guy get?" or else it will take ages.

[hide="15"]Let's look at what happens in each game.

If one team wins, 2 points will be distributed. If there is a tie, 2 points will be distributed.

Since there are 40 games played, there must be 80 points distributed among the 5 teams. We already know that the first four teams got 15,13,12, and 11 points, so 51 points already distributed. There are 29 points left. Since the last three places got an equal number of points, the possibilities for 5th 6th 7th 8th are 2/9/9/9, 5/8/8/8, 8/7/7/7, 11/6/6/6... As we can see, only 8/7/7/7 fits the problem requirements, so the fifth place winner got 8 points.[/hide]

[hide="23"] The area of the 3,4,5 right triangle is 6 square units. Since $ x \le y$, the least $ y$ can be is if $ y\equal{}x$ (you can see why this is so, because if $ y>x$, you can always make the two closer together without changing the area).

Since its an isosceles triangle, we cut it up into two right triangles. Each of these have area 3 and base 2, so they have height 3. The hypotenuse is $ x\equal{}y$, which is $ \sqrt{2^2\plus{}3^2}\equal{}\sqrt{13}$.
[/hide]

[hide="30"]
Draw it out.
Let the house be 0 and every succeeding block east be 1, 2, 3...
Make a list of 8 steps of the number of ways that she can walk.
Realize that the first step has to be east and the last step has to be west. So we just have to fill in the middle 6 steps.

On the second slot, she starts at 1 and cannot move to west to 0, so  she must move east to 2. Start brute forcing here: make lists of arrangements of 3 w's and 3 e's, starting with e such that there is never more w's than e's at any point in the list. You'll find 5 of them, namely eeewww, eeweww, eewwew, ewewew, and eweeww. The odds that she takes precisely those arrangements of steps after going east 1 block (which is definite) is 5/64, and the odds that, after ending on block 1 after the 7th flip, she goes back home west is 1/2, so the final answer is 1/2 x 1/64 = 1/128.

[/hide]

Oh, my bad. I should have thought more carefully....
Thanks, though.  :D

[quote="xpmath"]No, each game has to give a total of two points.

If it is a tie, both teams get 1, so that gives 2 points.
If a team wins, that team gets 2, the other doesn't, so that is 2 points.

This way, a team can only get an odd number of points if it is in an odd number of ties, so there always have to be an even number of teams with an odd amount of points, which is true in this case. (15, 13, 11, 7, 7, 7 are odd).

If I'm not understanding what you're saying, please say so.

Beaten.[/quote]

I think you're overthinking it... all you have to do is subtract 1,13,12, and 11 points from 80, giving you 29. now, you divide by 4 to give a good estimate, which is 7.25. now guess and check works. First, you can try fifth getting 8, and 6th getting 7, and you find it works. therefore, our answer is 8. Notice how you can't have 11,6,6,6 because 11 is already there.

You don't need to do all of what I said above. In fact, right after getting 29 as the sum of the last few teams, you can get the answer by just checking. It goes a lot quicker when you're actually doing it.

EDIT: FAIL

note to self: stop being such a smart alec.

okay, si-...xpmath.

Actually, I did mean teams. You know that the sum of the first five teams here is 59, so the sum of the last three is 21  :wink: .

Bleh still need to take some more teams. Get on ftw so I can chat and thus procrastinate.


There are n points on the plane with no three collinear. Show that there exists P, a set of at most 2n-5 points (on the same plane), such that there is at least one point (of P) in every triangle whose vertices are from the given n points.

This problem comes from ISL 1991. See :
http://www.kalva.demon.co.uk/short/soln/sh918.html

We used it in France for our 'Concours Gnral' which was our TST in 1998.
I love this problem...

Pierre.

P.S. If you are looking for an answer, please do not post a new topic into the solved problem section ;)


inequalities
quadratics
inequalities proposed

Let $a,b,c,d,e$ be non-negative numbers such that $a \ge b \ge c \ge d\ge e$. Prove that
$(a+b+c+d+e)^2 \ge 8(ac+bd+ce)$.
Determine when equality occurs.

The idea is classical one :
Just consider this inequality as quadratic (of second degree) inequality with respact to e, Then consider the determinant $D$ , but $D \leq 0 $ is equivalent to $ (c-b)\cdot (c-d) \leq 0$ and we are done. The rest follows.

congratulations!
Vasc you generalize it!
indeed it works
the discriminent is the sum of $(a_{k+1}-a_i)(a_{k+1}-a_{i+k})$

[quote="math_sipo"]congratulations!
Vasc you generalize it!
[/quote]
I think that's pretty usual  :P

A more general inequality is the following:

Let $a_1, a_2,...,a_{4k}$ be real numbers such that $a_1 \ge a_2 \ge...\ge a_{4k}$. Prove that
$(a_1+a_2+...+a_{4k})^2 \ge 4k(a_1a_{k+1}+a_2a_{k+2}+...+a_{4k}a_k)$.

Notice that for $a_{2k+2}=a_{2k+3}=...=a_{4k}=0$, we get the above inequality.
Moreover, for $a_{3k+1}=a_{3k+2}=...=a_{4k}=0$, we get the inequality
$(a_1+a_2+...+a_{3k})^2 \ge 4k(a_1a_{k+1}+a_2a_{k+2}+...+a_{2k}a_{3k})$.


A polynomial $ P(x)$ of the n-th degree satisfies $ P(k)\equal{}2^k$ for $ k\equal{}0,1,2,...,n$. Find the value of $ P(n\plus{}1)$ :lol:

Posted before $ P(x)\equal{}C_x^0\plus{}C_x^1\plus{}...\plus{}C_x^n$, therefore $ P(n\plus{}1)\equal{}2^{n\plus{}1}\minus{}C_{n\plus{}1}^{n\plus{}1}\equal{}2^{n\plus{}1}\minus{}1$.

See the discussion [url=http://www.artofproblemsolving.com/Forum/weblog_entry.php?t=211560]here[/url].

[quote="Rust"]Posted before $ P(x) \equal{} C_x^0 \plus{} C_x^1 \plus{} ... \plus{} C_x^n$, therefore $ P(n \plus{} 1) \equal{} 2^{n \plus{} 1} \minus{} C_{n \plus{} 1}^{n \plus{} 1} \equal{} 2^{n \plus{} 1} \minus{} 1$.[/quote]
I don't understand this solution; take any x smaller than n (say n-1), then $ P(n\minus{}1)$ is not defined since $ C_{n\minus{}1}^n$, or I assume to be $ \binom{n\minus{}1}{n}$, is not defined.

$ C_x^k\equiv \frac{x(x\minus{}1)...(x\plus{}1\minus{}k)}{k!}$ is defined for any x and positive integer k (for k=0 $ C_x^0\equiv 1$).


what is the maximal dimension of a subalgebra of $M_n(K)$ ?

It is incredible how the most natural questions are so difficult. Do you have any progress on it, Alekk? I found only that it is somewhere between $n^2-n/2$ and $ n^2-n$ and I think it is $n^2-n$. But I don't know how to prove.

in the case of $K=\mathbb{C}$ for example I think it is $n^2-n+1$ because for any non trivial subalgebra $A$, there is a nontrivial subspace stable under $A$. And $n^2-n+1$ is reached.


I would like to state that the LaTeX how-to is kind of outdated:

1) The small-miktex-<some numbers> should be changed to basic-miktex-<some numbers>, and who says you can't download the complete?

2) If you're going to use C:\texmf for your root directory, then watch out, the default used to be C:\texmf but it's now C:\Program Files\MiKTeX <some numbers>.

3) When TeXnicCenter starts the configuration wizard, the stuff in there is somewhat similar, but now this is what happens; TeXnicCenter asks you for the directory where the LaTeX applications are (latex.exe, tex.exe) and then by default it starts Yap (located in the same place as those files) when it searches for it in that directory.  Type "C:\texmf\miktex\bin" then it will progress.  Just accept the defaults (leave the PostScript viewer blank as always) and you're done.

Also, some of the things I would like you to include in the useful packages list are xlop and polynom.  They really would help a lot if you tried them.

That's all, best regards in updating the LaTeX html page!  :D

Hello?  Anybody going to change anything?  If not, I'll just post the same thing in "Questions, Suggestions and Announcements."


[url=http://www.isketch.net]A great big waste of time[/url]

I used to play , too many spammers though...


The inequality is homogeneous, so multiply out and use Rearrangement.   :rotfl:

[quote="MrWise"][quote="violetcraze"]$a, b, c > 0$

Prove:

$\frac{1}{a^3 + b^3 + abc} + \frac{1}{b^3 + c^3 +abc} + \frac{1}{c^3 + a^3 + abc} \leq \frac{1}{abc}$[/quote]

It's a simple ineq.  :)

$a^3+b^3 \ge ab(a+b) \Leftrightarrow a^3+b^3+abc\ge ab(a+b)+abc$
so we get
$\sum \frac{1}{a^3+b^3+abc} \le \sum \frac{c}{abc(a+b+c)} \le \frac{1}{abc}$[/quote]

Thanks  :D


algebra
polynomial
modular arithmetic
induction
algebra unsolved

it is known of a polynomial over Z that p(n)>n for every positive integer n. consider x_1=1, x_2=p(x_1), ...
We know that, for any positive integer N, there exists a term of a sequence divisible by N. Prove that p(x)=x+1 :?

Let $Q(x)=P(x)-x$. Suppose that, for some $x_1$, there's some $k$ such that $k \mid Q(x_1)$. Then $P(x_1) \equiv x_1 \pmod{k}$. By induction, $x_m \equiv x_1 \pmod{k}$ for all $m$. Then, if $k$ divides any of the terms of this sequence, it must divide $x_1$. In other words, $Q$ is a polynomial such that, if $k \mid Q(n)$, then $k \mid n$. Since, given $n$, we can take $k=Q(n)$, this implies $Q(n) \mid n$ for all $n$. Then either $Q(x)=a$ or $Q(x)=ax+b$. In the first case, $a$ must be a positive integer (since $P(n)>n$ for all $n$) and, in particular, it must be $1$, since it must divide all positive integers. In the second case, since all roots of $Q(x)$ must be roots of $x$, $Q(x)=ax$ for some integer $a$; in particular, since $ax \mid x$, we have $Q(x)=x$. But then $P(x)=Q(x)+x=2x$. Since this polynomial clearly doesn't satisfy the original condition (for example: $x_1=2, x_m=2^m$, and then $k=3$ doesn't divide any term of the sequence)... we must have $Q(x)=1$, that is, $P(x)=x+1$.


Ring Theory
set theory
real analysis
real analysis theorems

I realize this question doesn't really fit here, but I don't know where else to put it. I am doing homework for my course in measure theory and the following is an assigned problem:

"If $D$ is a class of sets, then there exists a ring $R_{0}$ such that $D\subset R_{0}$ and that for any ring $R$ containing $D$, $R$ contains also $R_{0}$".
(Note that there is always an underlying space $X$ in the text).

Now, after some thought I suppose this problem is fairly straightforward. If we let $M$ be the collection of all rings $R$ containing $D$ then we can just let $R_{0}$ be the intersection of $M$. However, I always worry when doing mathematics, and especially when it's close to pure set theory since I have a loose basis in that.

First of all I worry about the mere existence of $M$. This is possibly a huge set and in a real situation there's no apparent way to determine $M$ (more than uncountable infinity makes me nervous). How can I be sure that it does exist? In one way, I guess $M$ is no different from all other sets I create, specifying that I want all elements from some set with some given properties. But for some other reason I feel unsure about this... not familiar working with abstract sets I guess.

Secondly, I wonder what happens with the intersection of $M$. I suppose $M$ is non-empty because the power set of the underlying space $X$ exists and is a ring. However, even if $M$ were empty we could interpret the intersection as the whole power set and $R_{0}$ would still out to be a set with the wanted properties. Is this a coincidence? Empty sets also make me nervous!

How worried do I have to be about set theory in general? I used to think that set theory was uninteresting formalism, but the contradictions of "naive set theory" lie so close to everything I do (like there is always a problem with empty sets, it seems). My university offers no course on set theory, but I sometimes feel that it is needed. Do other universities typically not teach set theory and rely on the naive notion of sets existing, or is it just mine?

As long as you have $X$, you don't have to worry. Define $M$ as the set of all subrings of $2^{X}$ that contain $D$, etc.

Also, if $\{E_{\alpha}\colon \alpha\in A\}$ is a family of subsets of $X$ indexed by $\alpha$, then $\bigcap_{\alpha\in A}E_{\alpha}=X$ when $A$ is empty. Indeed, an element $x\in X$ belongs to $\bigcap_{\alpha\in A}E_{\alpha}$ iff $\forall \alpha\in A \ x\in E_{\alpha}$, and the latter is vacuously true. With the same reasoning, $\sup\varnothing=-\infty$ and $\inf\varnothing=+\infty$.

If I have two infinite sets $X$ and $Y$ and if I know the cardinality of $X$ is less than that of $Y$, can I find a subset of $Y$ with the same cardinality as $X$?

If $X$ has cardinality greater than $Y$, $X$ and $Y$ can be put into bijection with two ordinals $\omega_{1}$ and $\omega_{2}$, respectively, such that $\omega_{1}> \omega_{2}$.  But then $\omega_{2}\subset \omega_{1}$, and so we restrict the bijection between $X$ and $\omega_{1}$ to $\omega_{2}$ to find a subset of $X$ in bijection with (and hence having the same cardinality as) $Y$.


Let$ A\in M_{n}\mathbb{(R)}$ and $ A^{2k} + I = 0$ , $ k\in N$,$ k \geq1$ .Prove that : $ detA = 1$
:juggle:
[b] Love math must come from heart !!! [/b]
sorry!!!

I think it is't true:
\[ det( \minus{} 2008I) \equal{} det(A^{2k}) \equal{} (det(A))^{2k}
\]
, so $ det(A)\neq 1$

:blush:
 :blush: [b] Sorry , I Edited !!! [/b]

$ det( \minus{} I) \equal{} det(A^{2k}) \equal{} (det(A))^{2k}$, so $ det(A)$ must be root of 2k degree from $ det( \minus{} I)$ and we know thet $ detA$ is real number, so $ n$-even and $ detA \equal{} 1$ or  $ detA \equal{} \minus{} 1$.

No det(A)=-1 because : $ \lambda^{2k} \plus{} 1 \equal{} 0$ have different root of 2k (because i write english so bad )
Wairt !!! :roll:

Eigenvalues are roots of $ x^{2k} \plus{} 1$(no real roots), and $ A$ real so if $ z$ is root than $ conjugate(z)$ is also root, $ detA$ is product of eigenvalues group roots in this way
(z, conjugate(z)), we will have $ detA \equal{} 1$, because $ z*conjagate (z) \equal{} 1$.


calculus
derivative
function
real analysis
real analysis unsolved

1) Let $f: [a,b] \rightarrow \mathbb{R}$ be a derivative function such that $f(x)=0,\forall x \in D$, where $D$ is a dense subset of $[a,b]$. Prove (or disprove) that $f(x)=0, \forall x\in [a,b]$
2) Let $f: [a,b] \rightarrow \mathbb{R}$ be a derivative function. Prove(or disprove ) that there exists $D$,a dense subset of $[a,b]$, such that $f$ is continuous in every point of $D$.

This is just to remind everybody of the [b]one-problem-per-post[/b] policy.:)  The exception can be made for very closely related problems, but this is not the case here. Problems (1) and (2) in xirti's post have very little to do with each other. Actually both have been discussed earlier. I wonder whether mathlinkers still remember them :P.

I looked them up on the site:
here is the link for the first problem.
http://www.mathlinks.ro/Forum/viewtopic.php?t=2822

here is the link for the second problem.
http://www.mathlinks.ro/Forum/viewtopic.php?t=22366&highlight=derivative+dense

sorry :blush:


What is the greatest common factor of 30, 90 and 75?

Between 30,75 it is 15, and 90 is divisible by 15, so 15.

[center][font=Times New Roman]To find the greatest common factor we must see what factors they share. We can see that  3 + 0 = 3, 9 + 0 = 9 , and 7 + 5 = 12. We can see that that the digits all add up to a multiple of 3. Thus all of these numbers have a common factor of 3. We can also see  that all of them have a common factor of 5 since all of them end in either 5 or 0. So now that we  know our common multiple we can thus find our answer by multiplying our factor that we found.
 $3\cdot5=\boxed{15}$[/font][/center]


function
limit
calculus
derivative
algebra
domain
calculus computations

I'm having trouble finding any material on derived numbers, so I'm posting questions here.  In fact, wikipedia does not have a page on derived numbers.

1) Prove that a derived number exists at each point $ x_{0}$ of a function $ f$.
-For this one, I was thinking that you could choose your $ h_{n}$ so that $ f(x_{0}\plus{}h_{n})$ is defined, but I haven't figured out how to avoid the $ 0/0$ case.  Is there a better way?

2) Prove that a function is differentiable at $ x_{0}$ if and only if all of the derived numbers at $ x_{0}$ agree.
-For this one, I'm looking for a more rigorous argument than intuition.

The definition I am using is: Given a function $ f: \mathbb{R}\rightarrow\mathbb{R}$, an extended real number $ \lambda$ is called a derived number for $ f$ at $ x_{0}$ if there exists a sequence $ h_{n}\rightarrow 0$ ($ h_{n}\neq 0)$ such that $ \lim_{n\rightarrow\infty}\frac{f(x_{0}\plus{}h_{n})\minus{}f(x_{0})}{h_{n}}\equal{}\lambda$.

Question 1:

We let, for convenience $ g(x) \equal{} \frac{f(x)\minus{}f(x_0)}{x\minus{}x_0}$ noting that at $ x \equal{} x_0$ the function is undefined.

Split into two cases:

(a)   $ g(x)$ is bounded in the vicinity of $ x_0$

Rigorously this means that there exist $ \epsilon > 0$, $ \delta > 0$ (both assumed to be finite) such that for all $ x \neq x_0$ satisfying $ |x \minus{} x_0| < \delta$ we have $ |g(x)| < \epsilon$.

Pick any sequence $ x_n$ in this interval with $ x_n \to x_0$. Let $ h_n \equal{} x_n \minus{} x_0$. Then the sequence $ g_n \equal{}  g(x_0 \plus{} h_n)$ is bounded (note that the condition $ x \neq x_0$ implies that $ h_n \neq 0$ and so $ g$ will thankfully never be evaluated at $ x_0$) . So by Bolzano-Weierstrass we may pick a convergent subsequence, $ g_{n_j}$, tending to some finite $ \lambda$. So indeed $ h_{n_j}$ is a sequence satisfying the desired properties (any subsequence of a convergent sequence converges to the same limit).

(b)   $ g(x)$ is unbounded in the vicinity of $ x_0$

Without loss of generality, we assume that $ g(x)$ is unbounded above (the reasoning for unbounded below is entirely similar).

So for any $ \delta > 0$ and $ \epsilon > 0$ there exists $ x$ such that $ |x \minus{} x_0| < \delta$ and  $ |g(x)| \geq \epsilon$. (If you are familiar with mathematical logic, then this is just the negation of statement in (a)).

So we can pick a sequnce $ \delta_n \equal{} 1/n$ and $ \epsilon_n \equal{} n$. Therefore we can find for each $ n$ an $ x_n$ satisfying this. Let $ h_n \equal{} x_n \minus{} x_0$, noting that $ h_n \to 0$. But since $ \epsilon \to \infty$ then cleary $ g_n$ (as defined above) tends to $ \infty$.

I have never used extended reals before, but I assume it is just the reals union $ \infty$.

Also note that no property of the function $ g$ has been assumed, we could apply precisely the same argument if $ g(x_0)$ were well defined.

Question 2

Forward Implication:

The condition that $ f$ is differentiable at $ x_0$ is, in the notation of the previous post, $ g(x) \to \lambda$ as $ x \to x_0$ for some (finite) real $ \lambda$. There is a well known theorem that states for general functions "$ g(x) \to \lambda$ as $ x \to x_0$ if and only if for every sequence $ x_n \to x$ with $ x_n \neq 0$ we have $ g(x_n) \to \lambda$". So the forward implication is a trivial corollary of this well known theorem.

Backward Implication:

This is not actually true in general.

(From Question 1 there exists no $ f$ such that precisely none of the $ g(x_n)$ converge...so we are spared consideration of this case.)

Consider the (signum) function $ f(x) \equal{} 0$ at $ x \equal{} 0$, $ f(x) \equal{} \minus{}1$ for $ x < 0$, $ f(x) \equal{}1$ for $ x > 0$. Then for $ x_0 \equal{}0$, $ g(x) \equal{} \frac{1}{|x|}$ and $ g(x_n) \to \infty$ for any sequnce $ x_n \to 0$. This means that all derived numbers do agree, all being $ \infty$ assuming that the derived numbers are allowed to be infinite...which is neccessary for Question 1 to be true. But $ f$ is clearly not differentiable at $ x_0 \equal{} 0$

Consider $ \lambda$ finite. The proof of the converse in this case is not just the backward implication of the "well known" theorem cited above. The theorem assumes that all sequences $ x_n \to x$ have to satisfy $ g(x_n) \to \lambda$ for $ g(x) \to \lambda$ to hold. The subtle difference here is that only those sequences which converge, converge to the same limit $ \lambda$. The aim is to prove that in such a case, all sequences do converge to $ \lambda$, and then the "well known" theorem can be used.

$ g$ must be bounded in the vicinity of $ x_0$. If it were not we could construct a sequence $ x_n \to x_0$, as explained in the previous post, that has $ g(x_n) \to \infty$ and we would get a contradiction in our assumption that $ \lambda$ is finite. So suppose that there exists a sequence $ x_n \to x_0$ such that $ g(x_n)$ does not converge to $ \lambda$. Rigorously, this means that there exists $ \epsilon > 0$ such that for all natural numbers $ N$ there exists $ n > N$ such that $ |g(x_n) \minus{} \lambda| \geq \epsilon$. So we can therefore pick a subsequence $ x_{n_j}$ of this satisfying $ g(x_{n_j}) \geq\lambda \plus{} \epsilon$ (or $ g(x_{n_j}) \leq \minus{} \lambda \minus{} \epsilon$). But $ g(x_{n_j})$ is bounded above (or respectively below), and by Bolzano-Weierstrass we can find a convergent subsequence $ g(x_{n_{j_k}})$ converging to some finite $ \mu$ satisfying $ \mu \geq \lambda \plus{} \epsilon$ (repectively $ \mu \leq \minus{}\lambda \minus{} \epsilon)$. This contradicts the assumtion that for all $ x_n \to x_0$ that converge we have $ g(x_n) \to \lambda$. So all sequences $ x_n \to x_0$ have $ g(x_n) \to \lambda$. Thus $ f$ is differentiable.

Thank you very much for your assistance.

A much simpler argument on #1:
Let $ h_n\equal{}\frac1n$ (or pretty much anything going to zero). We get a sequence of values $ s_n\equal{}\frac{f(x_0\plus{}h_n)\minus{}f(x_0)}{h_n}$. The extended real numbers are compact, so some subsequence of the $ s_n$ converges to an extended real $ \lambda$. That's it.

Also, #2 is not quite true. For a counterexample, look at $ f(x)\equal{}\sqrt[3]{x}$ near zero; the "derivative" is $ \infty$, so it's not differentiable.
Other than the handling at $ \pm\infty$, this is the same as the equivalence of the sequential definition of continuity and the usual definition on $ \mathbb{R}$.

I did not take the course on metric and topological spaces at my university...so I don't know enough about compactness to use it. And, I had already sighted a counterexample for (2) in my argument above. Also, the converse of (2) for finite $ \lambda$ is slightly different than the standard definition of sequencial continuity...which I explained, and then proved that it indeed is equivalent...

[quote="jmerry"]For a counterexample, look at $ f(x)\equal{}\sqrt[3]{x}$ near zero; the "derivative" is $ \infty$, so it's not differentiable.[/quote]
I'm allowing derived numbers to take on $ \pm\infty$ as values, so that is okay.

And with regards to 1, that is what I would have tried, but how do we know that $ f(x_{0}\plus{}1/n)$ is even defined?  That is one of the things I was unsure of.

Although the derived numbers are allowed to be infinite, the definition of differentiable requires the derivative to be finite, so jmerry is correct (note that jmerry has put inverted commas around "derivative").

I think it is fair to assume that there exists a neighbourhood about $ x_0$ in the reals such that the function is defined. If there is such a neighbourhood $ (x_0 \minus{} \eta, x_0 \plus{} \eta)$ for some $ \eta > 0$ then it means that for large enough $ n$ ($ n > \frac{1}{\eta}$ will do), we must have $ f(x_0 \plus{} \frac{1}{n})$ defined. All we do is just start our sequence at the point when we get into this neighbourhood. Now, if you didn't have such a neighbourhood then things would appear to go wrong: consider for instance function defined on the irrational reals. Let $ f(x) \equal{} 0$ for all irrational $ x$. $ \lambda \equal{} 0$ for all sequences, but $ f$ is certainly not differentiable. Indeed it is not even continuous.

My post was intended mainly as a way to point out more general principles, not as a criticism of sludgethrower's original arguments. They're fine, and appropriately elementary.
On the arguments over domain- the original problem assumed $ f$ was defined on all of $ \mathbb{R}$. Replacing $ \frac1n$ with some sequence going to zero, my argument would work at any point of the domain of $ f$ which is also an accumulation point. At anything that's not an accumulation point, we can't possibly have a derived value.

I wasn't doubting sludgethrower, just asking for clarification.  And I guess I forgot my own assumption that $ f$ is defined on all of $ \mathbb{R}$, so in that case, the argument is just as simple as I would have expected.


i think you missed a little something. maybe the $a_i$ are integers and you mean irreducible over $\mathbb Z$?

It's bveen discussed before a number of times. Here's the most significant link:

[url]http://www.artofproblemsolving.com/Forum/viewtopic.php?highlight=Perron+criterion&t=150[/url]


probability
function
articles
number theory
relatively prime
totient function

Two distinct numbers between 1 and 9, inclusive, are chosen. What is the probability that they are relatively prime?

[quote="daermon"][hide]by casework looking at each number, $1-\frac{3+2+1+2}{36}=\boxed{\frac{7}{9}}$[/hide][/quote]
Sorry, I don't think that's correct.  :(
Could you please explain your casework more thoroughly? This is the reason you need to show not only your answer, but also how you got it. Otherwise, if you get it wrong, no one will be able to explain to you how to fix it.  :wink:

[hide]There are 36 possible ways to choose two possible numbers. Counting non-relatively prime combinations:

2, 2
  ,4
  ,6
  ,8
3,3
  ,6
  ,9
4,4
  ,6
  ,8
5,5
6,6
  ,8
  ,9
7,7
8,8
9,9

There are 17 of these combinations, so the are 19 combinations of 2 relatively primes.

$\frac{19}{36}$[/hide]

EDIT: THIS ANSWER WAS WRONG! CORRECT ANSWER BELOW.

kheg_k, you must choose 2 [b]distinct[/b] numbers. :D

Oh. ok.

New answer

[hide]
Unrelatively prime
2, 4
,6
,8
3,6
,9
4,6
,8
6, 8
,9

9 unrelatively prime pairs, so 36-9=27 relatively prime pairs, so 27/36=$\frac{3}{4}$
[/hide]

Yes, I believe that the answer is
[hide]$\frac34$[/hide]
, so your answers are correct.

Here's a similar problem:
Two distinct numbers between 4 and 10, inclusive, are chosen. What is the probability that they are relatively prime?

And here's a harder problem (there are a lot more possibilties, so you'll have to find a way to generalize instead of listing it out):
Two distinct numbers between 1 and 20, inclusive, are chosen. What is the probability that they are relatively prime?

EDIT: Changed it to 1-20.

[quote="SplashD"]use the totient function?[/quote]
No, I don't think the totient function is necessary for this problem. However, I believe that it requires PIE (Principle of Inclusion-Exclusion).
[hide="Hint"]Consider all the multiples of 2 (from 1 to 20). Any 2 of them are [i]not[/i] relatively prime. So how many ways can you pick two of them? Do the same thing for multiples of 3 and for the other primes. However, we're not quite done yet, because (this is where PIE comes in) this counts multiples of 6 pairs twice (as in 6 and 12), so we have to subtract that out once.[/hide]

[quote="kheg_k"]what is the totient function?[/quote]
Take a look at [url=http://www.artofproblemsolving.com/Wiki/index.php/Euler%27s_totient_function]this article[/url].

[quote="SplashD"]there's a closed form from x to y where $x\le y$?[/quote]
Probably not. But from $1$ to $x$.


$ \left\{ \begin{array}{c}
a_{1},\ a_{2},\dots,\ a_{n}\in\left(0,\ \plus{}\infty\right)\\
S\equal{}\sum_{k\equal{}1}^{n}a_{k}\\
\ a_{n\plus{}1}\equal{}a_{1}\end{array}\right|\Longrightarrow\sum_{k\equal{}1}^{n}\sqrt{\frac{a_{k}\plus{}a_{k\plus{}1}}{2S\minus{}a_{k}\minus{}a_{k\plus{}1}}}\ge2$.

$ \sqrt{\frac{2S\minus{}a_k\minus{}a_{k\plus{}1}}{a_k\plus{}a_{k\plus{}1}} \cdot 1} \le \frac{\frac{2S\minus{}a_k\minus{}a_{k\plus{}1}}{a_k\plus{}a_{k\plus{}1}}\plus{}1}{2} \equal{} \frac{S}{a_k\plus{}a_{k\plus{}1}}$

$ \Rightarrow \sum \sqrt{\frac{a_{k}\plus{}a_{k\plus{}1}}{2S\minus{}a_{k}\minus{}a_{k\plus{}1}}} \ge \sum \frac{a_k\plus{}a_{k\plus{}1}}{S}\equal{}2$


Thanks  :D I have to admit that I had some difficulties with the second observation: I was always writing $a_{n}-2a_{n-1}= 2^{n-1}+2^{n-2}+...+4+2+1 = 2^{n}-1$  :P

Another approach, using characteristic equations:

Writing $n+1$ instead of $n$ we get

$a_{n+2}-3a_{n+1}+2a_{n}=2^{n+1}=2\cdot 2^{n}\qquad (*)$

From the initial equation $2^{n}=a_{n+1}-3a_{n}+2a_{n-1}$. Plugging that into $(*)$ and rearranging, we get

$a_{n+2}-5a_{n+1}+8a_{n}-4a_{n-1}=0$

Hence the characteristic equation is $t^{3}-5t^{2}+8t-4=0$. Factorize the LHS:

\begin{eqnarray*}t^{3}-5t^{2}+8t-4 &=& t^{3}-t^{2}-4t^{2}+4t+4t-4\\ &=& t^{2}(t-1)-4t(t-1)+4(t-1)\\ &=& (t-2)^{2}(t-1)\end{eqnarray*}

So the roots are $t_{1}=t_{2}=2, t_{3}=1$, hence the general solution is $a_{n}=(An+B)2^{n}+C\cdot 1^{n}$. Since $a_{3}=11$, we make the system

$2(A+B)+C=1$
$4(2A+B)+C=3$
$8(3A+B)+C=11$

Solving it we get $A=1, B=-2, C=3$, hence $a_{n}=(n-2)2^{n}+3$, which is of course the same as [b]Kurt Gödel[/b]'s answer.


function
probability
calculus
derivative
analytic geometry
graphing lines

There exists an example of a function $F(x)$ differentiable a.e. such that $F' = 0$ a.e. but $F$ isn't constant, for example $F$ - can be Cantor function. But in this example $F$ is constant on each of the intervals, composing $[0,1]-C$.
Are there any examples of , say, an injective function $F$ such that $F' = 0$ a.e. but $F$ isn't constant ?

Yes, there is this example, which I saw a long time ago in a magazine article by Patrick Billingsley.

Imagine that you are at a casino, and the for some unexplained reason, the only game you can play is a game (something like betting on one of two colors at roulette) in which the payoff is the same as the bet. This being a casino, the odds do favor the house - your chance of winning that game are $p,$ where $p<\frac12.$ Your problem is that there's a loan shark waiting for you outside who will kill you unless you emerge with a certain amount of money, an amount which is larger than your current stake. What should your betting strategy be to maximize your probability of living, and what is that probability, given your current stake?

The maximizing strategy is to bet as boldly as possible but no bolder than necessary. Normalize things so that your target stake is $1.$ Suppose your current stake is $x\in(0,1).$ If $x\le\frac12,$ then bet $x.$ With probability $q=1-p,$ you lose and reduce your stake to zero (dying). With probability $p,$ you win and have a stake of $2x$ going into the next hand. But if $x>\frac12,$ then bet $1-x.$ With probability $p,$ you win, increase your stake to $1,$ and walk out. With probability $q,$ your stake goes down to $2x-1.$

Let $f(x)$ be your probability of surviving, given that your stake is $x.$ This function will be the function that you want. Some things are immediately clear: $f(0)=0, f(1)=1,$ and $f$ is nondecreasing on $[0,1].$ The key equation that determines the properties of $f$ is the self-similarity:

$f(x)=\begin{cases}pf(2x)&0\le x\le\frac12\\p+qf(2x-1)& \frac12\le x\le1\end{cases}.$

It is posible to work out a representation of $f(x)$ based on the binary representation of $x.$ From that we will be able to show that $f$ is continuous and strictly increasing. To determine the derivative, consider for any given $x$ the sequence of decreasing dyadic intervals that shrink to that point, and compute the slope of the chord. If $f$ were differentiable at that point, the derivative would be the limit of the slopes of the chord. But the slope of each chord is either $(2p)$ or $(2q)$ times the slope of the previous chord; the only way such a sequence can converge would be for it to converge to zero. But this happens almost everywhere. For instance, if the factors of $(2p)$ and $(2q)$ are equally likely, on average for each pair of factors we are multiplying by $4p(1-p)$ which is less than one.

Suppose we have a nonatomic Radon measure $\mu$ on $[0,1]$ such that: (A) $\mu(I)>0$ for any nontrivial subinterval of $[0,1]$; and (B) $\mu$ is purely singular with respect to the Lebesgue measure. Then $F(x)=\mu([0,x])$ is a continuous strictly increasing function and $F'=0$ a.e.

A common way to build $\mu$ is to use Riesz products. For instance, the nonnegative function $\prod_{k=1}^{n}\left (1+\frac12\cos (4^{k}2\pi x)\right)$ integrates to $1$ on $[0,1]$ and therefore determines a probability measure. Taking weak* limit as $n\to\infty$, we obtain $\mu$.

assume that $f_{n}(x)$ is function that on $(r_{n},s_{n})$ where$r_{n},s_{n}\in \mathbb{Q}$ is contraction of cantor function and for $x<r_{n}$ is $0$ and for $x>s_{n}$ is $\frac{1}{2^{n}}$then what you want is $\sum f_{n}$ for every pair of rational number.

A few more details of the Billingsley example:

Fix $p$ such that $0<p<\frac12,$ and let $q=1-p.$

Suppose $x=\sum_{n=1}^{\infty}e_{n}2^{-n},$ where $e_{n}=0$ or $1.$ For a fixed $x,$ define $s_{n}=\sum_{k=1}^{n}e_{n}.$

Then $f(x)=\sum_{n=1}^{\infty}e_{n}p^{n-s_{n-1}}q^{s_{n-1}}.$

(It turns out that this is well-defined - it gives a consistent answer even for the points with two different dyadic representations.)

Now, fix $x$ and let $a_{n}=\sum_{k=1}^{n}e_{k}2^{-k}$ and let $b_{n}=a_{n}+2^{-n}.$ Then $a_{n}\le x\le b_{n},$ and $\lim a_{n}=\lim b_{n}=x.$ If $f$ is differentiable at $x,$ then

$f'(x)=\lim_{n\to\infty}\frac{f(b_{n})-f(a_{n})}{b_{n}-a_{n}}.$

We can calculate that $f(b_{n})-f(a_{n})=p^{n-s_{n}}q^{s_{n}}.$ Therefore, if $f$ is differentiable at $x,$ then

$f'(x)=\lim_{n\to\infty}(2p)^{n-s_{n}}(2q)^{s_{n}}$

The only possible limit this can have is zero. It does have the limit zero whenever

$\limsup\frac{s_{n}}n<\frac{1}{1-\frac{\ln(2q)}{\ln(2p)}}=R$

But $-\frac{\ln(2q)}{\ln(2p)}=\frac{\ln(1+\delta)}{-\ln(1-\delta)}<1,$ so $R>\frac12.$

By the Weak Law of Large Numbers, the event that $\limsup\frac{s_{n}}n$ is less than a fixed number greater than $\frac12$ has probability $1.$ Hence, $f$ is differentiable almost anywhere.

However the set on which this fails is an uncountable dense set of measure zero. It's dense, because at the very least, $f$ fails to be differentiable at the dyadic rationals.

a slight modification of cantor's function is what is required. if g is the cantor function define $f(x)=\sum_{n=1}^{\infty}2^{-n}g(2^{n}(x-r_{n}))$ where $r_{n}$ is an enumeration of the rationals. it is easy to see that f is strictly increasing. for if $x<y$ there is a rational between them and remembering that g is defined as 0 outside$[0,1]$ we get $0=f(x)<f(y)$ . clearly $f'(x)=0$ for almost all x


[quote="Pirkuliyev Rovsen"]Let $ a,b,c \in (0; \plus{} \infty)$ such that $ 3abc \equal{} 1$
Prove that $ \frac {3a^5}{3a^{5} \plus{} 2bc} \plus{} \frac {3b^{5}}{3b^{5} \plus{} 2ca} \plus{} \frac {3c^{5}}{3c^{5} \plus{} 2ab}\ge 1$
[/quote]
$ \Leftrightarrow$

$ \sum \frac{3a^6}{3a^6 \plus{} \frac{2}{3}} \geq 1$

$ \Leftrightarrow$

$ \sum \frac{9a^6}{9a^6 \plus{} 2} \geq 1$

But we have :

$ \sum \frac{9a^6}{9a^6 \plus{} 2} \geq \frac{(\sum 3a^3)^2}{\sum(9a^6 \plus{} 2) }$ (By C-S)

And

$ \frac{(\sum 3a^3)^2}{\sum(9a^6 \plus{} 2) } \geq 1$

$ \Leftrightarrow$

 $ 18\sum a^3b^3 \geq 6$ (by AM-GM)

So main inequality holds .
 :wink:


I need a better title for this (preferably something clever/catchy):

http://www.contestmath.com/

any suggestions?

haha well im keeping the domain name, but i just want a new title... something better than "Contest Math Resources"

What if you came up with a different meaning for AoPS?

go for it... lol i posted here because i'm not verbally creative

i needed a catchy name so i used this one


If $ a$ is an even positive integer and $ A\equal{}1\plus{}a\plus{}a^2\plus{}....\plus{}a^n,n\in N^*$ is a perfect square.Prove that $ 8|a$.

It is a very easy problem,and the most of you will solve it with the first view....

as u said ,it is easy and it sufficies to use congruences modulo 8 and using the fact that $ 8 | a^3$

[quote="Dimitris X"]If $ a$ is an even positive integer and $ A \equal{} 1 \plus{} a \plus{} a^2 \plus{} .... \plus{} a^n,n\in N^*$ is a perfect square.Prove that $ 8|a$.

It is a very easy problem,and the most of you will solve it with the first view....[/quote]
If $ n \geq 3$:
Clearly $ 8|a^3 \plus{} a^4 \plus{} .... \plus{} a^n$.$ A$ is odd,and every odd perfect square is congruent to 1 modulo 8,It follows that $ a^2 \plus{} a \plus{} 1 \equiv 1 ( mod 8 )$,or $ a(a \plus{} 1) \equiv 0( mod 8 )$,since $ a \plus{} 1$ is odd,the result follows immediately.

If $ n \equal{} 1$ or $ n \equal{} 2$:
Then,we must have $ a \plus{} 1 \equiv 1 ( mod 8 )$ and $ a^2 \plus{}a\plus{}1 \equiv 1 ( mod 8 )$,both of them lead to $ 8|a$ which was desired.


[b]Let A and B be real 3nx3n matrices such that [/b] : $ 4A^{2} \plus{} 9B^{2} \equal{} 6AB .$ [b]  Prove that [/b] : $ det(BA \minus{} AB) \geq 0$
[b] Do Math To Love Math , Love Math Must Do Math !!! [/b]
[b] Love Math , Do Math ,Math Is My life ! [/b]

For 2A=C , 3B=D then $ C^{2} \plus{} D^{2} \equal{} CD$   I will prove that : $ det(DC \minus{} CD) \geq 0$ (check eassy !!!)
Set  $ G \equal{} C \plus{} j.D , G^{*} \equal{} C \plus{} j^{*}D , J \equal{} \frac { \minus{} 1 \plus{} i.\sqrt {3}}{2} , J^{*} \equal{} \frac { \minus{} 1 \minus{} i.\sqrt {3}}{2}$
Since : $ J \plus{} J^{*} \equal{} \minus{} 1,J.J^{*} \equal{} 1$ , We have :
                         $ G.G^{*} \equal{} (C \plus{} j.D)(C \plus{} j^{*}.D) \equal{} C^{2} \plus{} D^{2} \plus{} J^{*}.CD \plus{} j.DC \equal{} J.(DC \minus{} CD)$
since :$ 0 \leq det(G.G^{*}) \equal{} det(G)det(G*) \equal{} j^{3n}.det(DC \minus{} CD) \equal{} det(DC \minus{} CD)$ ,
( because : $ J^{3n} \equal{} cos(\frac {6n.\pi}{3}) \plus{} i.sin(\frac {6n.\pi}{3}) \equal{} 1$) , therefore : $ det(DC \minus{} CD) \geq 0$
- Now , Let C and D be real 2x2 matrices such that $ C^{2} \plus{} D^{2} \equal{} CD$,
Since ,$ det(G.G^{*})$ is a real number .
Therefore :$ det(j(DC \minus{} CD) \equal{} (cos(\frac {4.\pi}{3}) \plus{} i.sin(\frac {4.\pi}{3})det(DC \minus{} CD)$ to $ det(DC \minus{} CD) \equal{} 0$ ,
Therefore :
$ (DC \minus{} CD)^{2} \equal{} Tr(DC \minus{} CD)(DC \minus{} CD) \minus{} det(DC \minus{} CD). I_{2} \equal{} 0_{2}$ (proplem Romania 2004) , $ I_{2 }$ is a identity 2x2 ,matrix.
I think I like matrix !!! :D  :P

1) I don't understand the reason why you post your solution so quickly.
2) the hypothesis $ dim(C)\equal{}3n$ is useless because if $ 3$ isn't a divisor of $ dim(C)$ then $ det(DC\minus{}CD)\equal{}0$.


Harvard
college
number theory
relatively prime

Here's a problem from the AOPS Introduction to Number Theory.  I didn't really like the explanation that the book gave in the solutions manual:

What are the five smallest primes after 1000?

The solutions manual told me to use the Sieve of Nygard.  I know what it is, but it did not elaborate on the steps before using the sieve.  I need help!!  Please, if you looked at the solution and only wish to copy it, don't bother.  You've been warned. :bruce:

Does the Sieve of Nygard have a more common name?  Introduction to Number Theory seems to be the only place where the term occurs.

look at page 32 in the introduction to number theory problem book.

let's say you want to find numbers from 32-48 that are relatively prime to 42.

42 has prime factors 2,3,7

32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48
cross out all multiples of 2:
33,35,37,39,41,43,45,47
then cross out all multiple of 3:
35,37,41,43,47
then cross out all multiples of 7:
37,41,43,47

edit: then if you want to find the primes greater than 1000 then uh... it takes a while to find them. just guess and check.
1001 is a multiple of 11, 1002 is a multiple of 2, 1002 is a multiple of 3,... and just check them. a lot less work than using a sieve.
i hope that helped.

are the sieve of nygard and the sieve of eratosthenes the same thing, by any chance?

it's pretty much the same thing as the sieve of erastosthenes.

I searched in google and no other reference exists about "sieve of nygard" except the book of AOPS. So I don't think that something like that exists. It's just a special case of Eratosthenes sieve.

Alexandros

yeah, it's just this one harvard professor who wants to be famous by reinventing a sieve and putting his name on it. :lol: basically, it said in the book that the only reason that the so-called "sieve of Nygard" was even put in the book is that Will Nygard helped write the solutions.

:rotfl:   :rotfl:  :rotfl:  Anyway, there should be a simple way to do this problem.  Then again, I could use my extremely useful TI-programs to solve the problem, but that would defeat the purpose.  Is there a smarter way to do this?  This question's format is pretty simple.  Help is welcome.

1001-immediately see that it is divisible by 11.
1002-immediately see that it is divsible by 2.
1003-17*59
1004-immediately see that it is divisible by 2.
1005-divisible b 5
1007-19*53.

...i think this is the fastest way.


Let $k = 2^{2^n} + 1$ for some $n \in N$. Show that k is prime if and only if k
divides $3^{\frac{k-1}{2}}+1$

Have a look here :

[url]https://aops.com/community/p192796[/url]

Pierre.

Here is a the more general theorem than Pepin's test:
If [tex]x^{n-1}\equiv 1(mod n)[/tex] and [tex]p[/tex] is prime number,  divides [tex]n-1[/tex] such that:[tex]gcd(x^{\frac{n-1}{p}-1,n)=1[/tex] then n is a prime number and x s.t:[tex]ord_n(x)=n-1[/tex](sorry, i don't know English well) :D

Hi Megus,
Prove the following:
Let $F_n = 2^{2^{\scriptstyle n}} + 1$ for some $n \in N$.
$F_n$  is prime if and only if $F_n$ divides $S_{2^{\scriptstyle n}-2}$ where: $S_0=5$ and $S_i=S_{i-1}^2-2$.
Tony

18 year bump...

($\rightarrow$) By Euler's criterion, it suffices to show that \[ \left(\frac{3}{k}\right) = -1.\] By the Law of Quadratic Reciprocity, \[ \left(\frac{3}{k}\right) = \left(\frac{k}{3}\right) = \left(\frac{2}{3}\right) = -1, \] as required.

($\leftarrow$) Let $p$ be any prime divisor of $k$. Then since $k-1$ is the order of $3$ modulo $k$, it follows that $k-1 \mid \varphi(k)$. Since the inequality $\phi(n) \le n-1$ always holds, equality must hold for $n=k$, and hence $k$ is prime, as desired.


function
induction
algebra unsolved
algebra

Let a function $ f: \mathbb{N} \to \mathbb{N}$ satisfy: $ f(n\plus{}1) > f(n)$ and $ f(f(n))\equal{}3n$ for all $ n \in \mathbb{N}$. Find $ f(2009)$.

Yes, it has been posted many times :)

Some hints to get you started lol

[hide="Hint 1"]
Try to determine the vaule of $ f(1)$. There's an obvious contradiction when $ f(1) \equal{} 1$, and if $ f(1) \geq 3$, $ f(f(1))$...
[/hide]

[hide="Hint 2"]
With the value of $ f(1) \equal{} 2$ we've earned, try to evaulate the values of numbers.
You will easily obtain the following;
$ f(1) \equal{} 2$, $ f(2) \equal{} 3$, $ f(3) \equal{} 6$, $ f(6) \equal{} 9$
Now, $ 6 \equal{} f(3) < f(4) < f(5) < f(6) \equal{} 9$, so two [b]positive integers[/b] are between 6 and 9.
This implies that $ f(4) \equal{}$..
[/hide]

[hide="Hint 3"]
Doing what we've done in Hint 3, we have $ f(1) \equal{} 2$, $ f(2) \equal{} 3$, $ f(3) \equal{} 6$, $ f(4) \equal{} 7$, $ f(5) \equal{} 8$, $ f(6) \equal{} 9$, $ f(7) \equal{} 12$, $ f(8) \equal{} 15$, $ f(9) \equal{} 18$,..
Anything particular visible?
Try to write the values in base 3.
Now, anything visible?
[/hide]

[hide="Hint 4"]
Now, I guess we can guess what $ f$ is:
If $ n \equal{} 1 a_1 a_2 .. a_k$ (base 3), $ f(n) \equal{} 2 a_1 a_2 .. a_k$ (base 3)
If $ n \equal{} 2 a_1 a_2 .. a_k$ (base 3), $ f(n) \equal{} 1 a_1 a_2 .. a_k 0$ (base 3)
It's obvious that this satisfies the given condition - but how shall we prove this is the [b] only [/b] solution?

Think before you click Hint 5 :)
Something that we should always try when we're dealing with positive integers.
[/hide]

[hide="Hint 5"]
Mathematical Induction kills the problem.
[/hide]

This is problem was given on the [size=150]2nd round[/size] of the Bulgarian Olympiad for 10th grade 2 years ago.


I am an international senior from Romania and have just applied to a couple of Universities in the US(MIT,Princeton,Northwestern,Tufts,Oberlin,Clark etc).I was wondering what my chances are (if any).
Here are my credentials:
Class rank:15 out of 180( so that would be 10%)
GPA:9.67 on a 10 scale
SAT I:2200(790 Math,740 CR, 670 WR)
SAT II:770 Math II,710 Math I, 710 German, 690 Physics(this sucks I know)
I attend the best High School in town; hardest profile,16 courses per semester, all AP, all mandatory.

Won 3rd Prize at the National Math Olympiad(9th,11th grades)+numerous prizes at regional contests.
Organzied and participated in this Math Symposium

Played guitar in a rock band(GBOB(global battle of the bands) national finalists, won "Future Heroes" contest at B'estival-Romania's largest music festival, recorded a 3 song EP 25+ concerts)
Theater Club-2 leading parts
Community service at a children's home(2 years)
Event manager for several social events held in our school(haloween party etc).
Boy Scout(although not that involved anymore)

Strong essay, I guess.

Sounds good. I wouldn't be offended if you were a freshman at my school. There's no formula that will give you an actual probability though. You just have to be confident that you did your best, and then wait and hope. Speculating is kinda pointless, and there are already too many threads about it in this forum.

I wouldn't be offended if you were offended because that would mean I'm in. :lol:

There aren't enough good student musicians at Princeton (besides classical musicians of course). I hope you do get in.  :)

Well thanks a lot for the support. It's out of my hands now really(which gives me both a feeling of relief and apprehension).
I also have some interviews scheduled(most of them conducted over the phone). Any advice on that?

I didn't do interviews for college, so I don't have any personal experience to share. I'd say, don't think about what you "should" say in order to make the best impression. Instead, say what you believe. Try to talk about things you care about or are passionate about especially. Don't brag about yourself excessively, but don't hide anything in the name of modesty either!

I had my interview for Princeton over the phone too :) (I am applying to Princeton this year too) and it went on very very well... I would say, just be yourself and talk to the interviewer very clearly about where your passion really lies and what you are interested in doing etc. And ask him/her anything about Princeton you would like to know :) All the best for your admissions process!


I was talking with someone at my school, and I said that I answered 21 questions, $ 6*21\plus{}4*1.5\equal{}132$ So I could afford to miss 2 questions and still have 120, which we were assuming was the cutoff for AIME. He said he answered 22 questions, $ 6*22\plus{}3*1.5\equal{}136.5$ So he could still only miss 2 questions and have atleast 120. It seems to us, That if you're only concerned about making AIME, it is better to answer 21 questions, rather than 22. After all, you are more likely to miss 3 questions out of 22 than out of 21.

Yes, this is also true for the 12

If you answer 15 questions, it is better to randomly guess on 3 then leave them all blank.

Reasoning is that if you get 15 right, you have a 105, so even if you guess incorrectly on 3 then you will still qualify.

However, if you get one wrong, then you now have a 99; say you also guessed on three though and guessed one of them right, now you have a 100.5 and make it.

I did this exactly in the AMC 10B. Except it was more of I'm not 100% sure but pretty sure. I had 19 problems answered for a total of 123, but decided to go on 2 more questions i wasn't entirely sure on. It turned out I was wrong with one of the original 19, but right with one of my 2 new ones so I got a 120

@ignite: I think you switched 100.5 and 105, but that's a pretty good strategy  :)

I answered 20 questions, so I had room for only one mistake. Luckily, I only  got the seed problem wrong. Someone make a guide to scoring above 120 or 100 on the AMC 10/12  :wink:


Very nice proof, Hung. :)
With this nice solutions, now we get at least 7 solutions for this nice inequality. :)
Regards

[quote="hungkhtn"]Let $ a_1,a_2,...,a_n$ be any non-negative real numbers. Prove that
\[ \sum ab^3 \plus{} 9\sum a^3b \ge 6\sum a2b^2 \plus{} 4abc(a \plus{} b \plus{} c).
\]
PS. Sorry Can, I found a mistake, so I've post a new problem.[/quote]
Oh, I am sorry, Hung. I didnot check it carefully. :(
here is my solution for your problem.
The inequality is equivalent to
\[ \sum ab(3a\minus{}b)^2 \ge 4abc\sum a\]
By Cauchy Schwarz Inequality, we get
\[ \left( \sum ab(3a\minus{}b)^2\right) \left( \sum c\right) \ge \left( \sum \sqrt{abc}(3a\minus{}b)\right)^2 \equal{}4abc\left( \sum a\right)^2\]
That is
\[ \sum ab(3a\minus{}b)^2 \ge 4abc\sum a\]
We have done.
:)


inequalities
function
induction
inequalities proposed

Prove that for any positive real numbers $ a,b,c,d,x,y,z,t$ we have the inequality:
   $\sum{a^4x}+2abcd\cdot min(x,y,z,t)\geq\sum {ab \frac{a^2+b^2}{2}\cdot min(x,y)}$. Here, the first sum has 4 terms and the second 6 terms.

Harazi, to be honest, I expected something more spectacular from you...  :?

This time we can set $x\geq y\geq z\geq t$ again and it remains to show

$a^{4}x+b^{4}y+c^{4}z+d^{4}t+2abcdt\geq $
$ab\frac{a^{2}+b^{2}}{2}y+ac\frac{a^{2}+c^{2}}{2}z+bc\frac{b^{2}+c^{2}}{2}z+ad\frac{a^{2}+d^{2}}{2}t+bd\frac{b^{2}+d^{2}}{2}t+cd\frac{c^{2}+d^{2}}{2}t$.

This follows by summing up the following four inequalities:

[list][*] $a^{4}\left( x-y\right) \geq 0$ (since $x\geq y$);

[*]$a^{4}\left( y-z\right) +b^{4}\left( y-z\right) \geq ab\frac{a^{2}+b^{2}}{2}%
\left( y-z\right) $ (since $y\geq z$ and $a^{4}+b^{4}\geq ab\frac{a^{2}+b^{2}}{2}$; the latter inequality follows from the stronger inequality $a^{4}+b^{4}\geq ab\left( a^{2}+b^{2}\right) $);

[*]$a^{4}\left( z-t\right) +b^{4}\left( z-t\right) +c^{4}\left( z-t\right) \geq ab\frac{a^{2}+b^{2}}{2}\left( z-t\right) +ac\frac{a^{2}+c^{2}}{2}\left( z-t\right) +bc\frac{b^{2}+c^{2}}{2}\left( z-t\right) $ (this is because $z\geq t$ and $a^{4}+b^{4}+c^{4}\geq ab\frac{a^{2}+b^{2}}{2}+ac\frac{a^{2}+c^{2}}{2}+bc \frac{b^{2}+c^{2}}{2}$; the latter follows by summing up the inequalities $\frac{a^{4}+b^{4}}{2}\geq ab\frac{a^{2}+b^{2}}{2}$, $\frac{b^{4}+c^{4}}{2}\geq bc\frac{b^{2}+c^{2}}{2}$, $\frac{a^{4}+c^{4}}{2}\geq ac\frac{a^{2}+c^{2}}{2}$);

[*]$a^{4}t+b^{4}t+c^{4}t+d^{4}t+2abcdt\geq $
$ab\frac{a^{2}+b^{2}}{2}t+ac\frac{a^{2}+c^{2}}{2}t+bc\frac{b^{2}+c^{2}}{2}t+ad\frac{a^{2}+d^{2}}{2}t+bd\frac{b^{2}+d^{2}}{2}t+cd\frac{c^{2}+d^{2}}{2}t$ (this follows from $t\geq 0$ and Turkevici).[/list]

  Darij

Well, I am so sorry I have deceived you...  :(  :(  :(  But... the last inequality you wrote does not follow from Turkevici inequality...

Oh, sorry, I wrote nonsense since I thought it would be analogous to the last one. Anyway I'll try again.

  Darij

Anyway, you found a really nice approach, my congratulations. Hoping I will not deceive you forever, I will submit to your attention another inequality derived from a very well known one. I am curious to see your approach:
   For any positive real numbers $ a_1,a_2,...,a_n, x_1,x_2,...,x_n$  such that $ a_1 a_2...a_n=1$ we have the inequality:
   $(n-1)\sum_{i=1,n}{ a_i^2\cdot x_i}+n\cdot min(x_1,x_2,...,x_n)\geq\sum_{1\leq i,j\leq n}{a_i\cdot a_j\cdot min (x_i, x_j)}$. Sorry again if they are trivial.

Do you mean $(n-1)(a_1^2+a_2^2+...+a_n^2)+n\geq (a_1+a_2+...+a_n)^2$ is true if $a_1a_2...a_n=1$? I think it is not a well known inequality.
If it is true then I solved your inequality.

Yes, Myth, the inequality you indicated is true. I said it is well known because it appeared several times on this forum. In general I do not think it is very known.

[quote="Myth"]$(n-1)(a_1^2+a_2^2+...+a_n^2)+n\geq (a_1+a_2+...+a_n)^2$ is true if $a_1a_2...a_n=1$[/quote]
I think I proved this via calculus.

Now about your inequality.
Inequality holds for $n=2$.
We can WLOG suppose $x_1\geq x_2\geq ...\geq x_n\geq 0$. If $x_n\neq x_{n-1} $ then $LHS-RHS$ is a linear function with respect to $x_n$. So it has minimum if $x_n=0$ or $x_n=x_{n-1}$. If minimum point is $x_n=0$ then we apply induction proposition. If minimum point is $x_n=x_{n-1}$ then we consider $LHS-RHS$ is a linear function with respect to $x=x_{n}=x_{n-1}$. Minimum point of this function is $x_{n-2}$ or 0, and so on. I hope you understand my idea.
After $n-1$ steps we obtain inequality $(n-1)(a_1^2+a_2^2+...+a_n^2)x+nx\geq (a_1+a_2+...+a_n)^2x$.

That's all.

First inequality in this topic can be easily analyzed in the same way.
But how to prove $\sum a^4+2abcd\geq \sum ab(a^2+b^2)/2$?
And what is Turkevici?

LOL Double Myth's solution. Very enjoyable, indeed. :D  :cool:  ;)

Beautiful solution, Myth! I think I wrote incorrectly the name of Turkevici, who proposed his inequality:
  $ a^4+b^4+c^4+d^4+2abcd\geq a^2b^2+b^2c^2+c^2d^2+d^2a^2+a^2c^2+b^2d^2$ in Kvant long time ago. The stronger form of Turkevici inequality (the one that appears in the problem I initially posted) is a direct consequence of Suranyi inequality:
  $ (n-1)(x_1^n+x_2^n+...+x_n^n)+nx_1\cdot...\cdot x_n\geq (x_1+x_2+...+x_n)(x_1^{n-1}+...+x_n^{n-1})$. I think I posted the solution of Suranyi inequality somewhere in the forum, but I do not find it anymore.

[quote=Myth]
But how to prove $\sum a^4+2abcd\geq \sum ab(a^2+b^2)/2$?
[/quote]
See here:
http://www.artofproblemsolving.com/community/c6h1245257p6799973


calculus
derivative
limit
function
algebra
polynomial
real analysis

I found this derivatives proof that has me stumped,

[b] Problem.[\b] For \[ f(x)\equal{}\left\{\begin{array}{cl} e^{\minus{}\frac{1}{x^2}} & x\neq 0\\ 0 & x\equal{}0\end{array}\right.,\]
prove that $ f^{(n)}(0)\equal{}0$ ($ n$-th-derivative at $ x\equal{}0$ is 0).

Ok, so I tried using the definition of a derivative and ended up with $ \lim_{\Delta x\rightarrow\infty}\frac{f(\Delta x)}{\Delta x}\equal{}\lim_{\Delta x\rightarrow\infty}\frac{2}{\Delta x^3}f(\Delta x)$, but then im looking at this and don't have any idea where to go.  My question, can you just put those delta x's in the denominator of the RHS up to that limit on the LHS and make it so that you can put as many of those as you want in any derivative?  Perhaps its been discussed before...if it has then if someone could provide a link to that, if not your comments on how it should be attacked would be appreciated.

Ok.. This is a long shot! You can observe that

$ \lim_{x \rightarrow 0}e^{\minus{}\frac{1}{x^2}}\equal{}0$

and that is the same value that you have for $ f(0)$. Therefore, my thinking is that you could just derivate $ e^{\minus{}\frac{1}{x^2}}$ as a continues function on all $ \mathbb{R}$ and then use the limit as $ x \rightarrow 0$ to the function's derivate. If that can be done, then it's obvious that $ f^n(0)\equal{}0$ because the the exponential factor "sticks" in the derivations, but it is multiplied by a polynomial, and when we use the limit, we know that the "strength" of the exponent part tending to 0 is stronger than the "strength" of the polynomial part tending to $ \infty$.

Away from zero, the $ n$th derivative is $ \frac{p_n(x)}{x^{3n}}e^{\minus{}1/x^2}$, where $ p_n$ is a polynomial. You want the show that the $ (n\plus{}1)$st derivative at zero is zero- that is, $ \lim_{x\to 0}\frac{p_n(x)}{x^{3n\plus{}1}}e^{\minus{}1/x^2}\equal{}0$

The $ p_n$ factor is irrelevant- we're multiplying by something continuous. The other part is what matters, and it's about the exponential dominating the power of $ x$.
The details here are inductive- we need that $ f^{(n)}(0)\equal{}0$ for the preceding calculation of $ f^{(n\plus{}1)}(0)$ to work.


trigonometry
search
geometry solved
geometry

Locate point P on side BC of triangle ABC so that  if circle centered at P
       with radius PC  intersects AC at  M,  circle centered at P with radius PB
       intersects AB at N,    then  AP,BM.CN   are concurrent.

        Maj.  Pestich

Using some straightforward trigonometry, I have found that the lines AP, BM and CN are concurrent if and only if

$\frac{BP}{PC}=\frac{a^2S_B+c^2\left(b^2-c^2\right)}{a^2S_C+b^2\left(c^2-b^2\right)}$,

with Conway's notations $S_A=\frac{b^2+c^2-a^2}{2}$, $S_B=\frac{c^2+a^2-b^2}{2}$, $S_C=\frac{a^2+b^2-c^2}{2}$.

These are quite messy terms, so I wouldn't search for a synthetic proof. Also, the line AP and the two similarly constructed lines for the vertices B and C concur if and only if the triangle ABC is isosceles or right-angled.

  Darij


I qualified to take the AIME this year through the USAMTS. When do we need to enter our CEEB School Code in by? I don't even know what this code is, so how would I find out? Thanks.

Try using this lookup tool to find out your school's CEEB code:

http://apps.collegeboard.com/cbsearch_code/codeSearchHighschool.jsp


1)Let $P(x)\in\mathbb{R}[x],\deg{P}=n$ , with leading coefficient $a$. Suppose $P(x)$ has $n$ distinct real roots $x_{1},x_{2},...,x_{n}$ all not equal to $0$. Prove that
\[\frac{(-1)^{n-1}}{ax_{1}x_{2}...x_{n}}\sum_{i=1}^{n}\frac{1}{x_{i}}=\sum_{i=1}^{n}\frac{1}{x_{i}^{2}P'(x_{i})}. \]
2)Does there exist a $P(x)\in\mathbb{R}[x],\deg{P}=n$ , with leading coefficient $1$, such that  $P(x)$ has $n$ distinct real roots $x_{1},x_{2},...,x_{n}$ all not equal to $0$, satisfying
\[\sum_{i=1}^{n}\frac{1}{x_{i}P'(x_{i})}+\frac{1}{x_{1}x_{2}...x_{n}}=0? \]

WLOG $a=1$ so $P(t)=\prod (t-x_{j})$, and $P'(x_{i})=\prod_{j\neq i}(x_{i}-x_{j})$.  Now,

$f(t) = \sum_{i=1}^{n}\frac1{x_{i}}\prod_{j\neq i}\frac{t-x_{j}}{x_{i}-x_{j}}$

is a polynomial of degree $\leq n-1$ satisfying $f(x_{i})=\frac1{x_{i}}$ for each $i$.  Another such polynomial is

$g(t) = \frac{1-\prod(1-t/x_{j})}t$,

so $f(t)=g(t)$ for all $t$.  In particular,

$\sum \frac1{x_{i}^{2}}\frac{(-1)^{n-1}\prod x_{j}}{P'(x_{i})}= f(0) = g(0) = \sum\frac1{x_{i}}$.

For (2), we let

$f(t) = \sum_{i=1}^{n}\prod_{j\neq i}\frac{t-x_{j}}{x_{i}-x_{j}}$.

This is a polynomial of degree $\leq n-1$ with $f(x_{i})=1$ for all $i$, so $f(t)=1$ for all $t$.  Setting $t=0$, we get

$\sum_{i=1}^{n}\frac1{x_{i}P'(x_{i})}= \frac{(-1)^{n-1}}{\prod x_{i}}$,

so the answer to your question is yes iff $n$ is even.


trigonometry
AMC
USA(J)MO
USAMO
algebra
partial fractions

Here is a solution to the final individual problem from the contest:

Simplify the following sum:

$\sum_{i=0}^{17}{\frac{\tan(17 \cdot 2^i)}{\cos(17 \cdot 2^{i+1})}}$

[hide="Solution:"]

$\frac{\tan {\theta}}{\cos {2 \theta}} = \frac{\sin {\theta}}{\cos {\theta} \cos {2 \theta}} = \frac{\sin {\theta}}{\cos {\theta} (2 \cos^2 {\theta} - 1)}$

Now use partial fractions to separate the denominator.

$\frac{\sin {\theta}}{\cos {\theta} (2 \cos^2 {\theta} - 1)} = \sin {\theta} \Bigg[\frac{A}{\cos {\theta}} + \frac{B \cos {\theta} + C}{2\cos^2 {\theta} - 1}\Bigg]$ for some constants A, B, and C.

Or equivalently, $1 = A(2\cos^2 {\theta} - 1) + (B\cos {\theta} + C)(\cos {\theta})$

Letting $\theta = \pi/2$ we get that $1 = A(-1)$, so $A = -1$
Now letting $\theta = 0$ we get $1 = -1 + (B + C)$, or $B + C = 2$
And letting $\theta = \pi$ we get $1 = -1 + (-B + C)(-1)$, or $B - C = 2$

These equations imply $B = 2$ and $C = 0$, so:

$\frac{\sin {\theta}}{\cos {\theta} (2 \cos^2 {\theta} - 1)} = \sin {\theta} \Bigg[\frac{2\cos {\theta}}{2\cos^2 {\theta} - 1} - \frac{1}{\cos {\theta}}\Bigg] = \frac{\sin{2\theta}}{cos{2\theta}} - \frac{\sin {\theta}}{\cos {\theta}}$

Therefore, $\frac{\tan {\theta}}{\cos {2 \theta}} = \tan {2\theta} - \tan {\theta}$, and the sum [b]telescopes[/b] leaving only the last term minus the first term.

So  $\sum_{i=0}^{17}{\frac{\tan(17 \cdot 2^i)}{\cos(17 \cdot 2^{i+1})}} = \tan (17 \cdot 2^{18}) - \tan (17)$[/hide]

That's supposed to take 10 minutes?? It looks more like a USAMO problem. It is really good though, and I feel like I should have been able to guess something like that--things like these are usually telescoping...

It's supposed to take more like 5 minutes...you have to do number 7 in those 10 minutes as well ;)

Well, #7 is just a good guess. Speaking of which, can you prove that 7 is the only solution?

Scorpius provided a solution for #7 [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=62441]here[/url]

That PFD is completely unneccesary. Instead, expand $\sin x = \sin (2x-x)$ and it will immediately simplify down to the telescoping sum.


induction
combinatorics proposed
combinatorics

Hello,

$n$ is a positive integer. Prove that the set $\{1^{2},2^{2},\cdots, n^{2}\}$ can be partitioned into four subsets each having the same sum of elements if and only if : $n\in \{16,24,32,\cdots, 8k,\cdots\}$ or $n\in \{15,23,31,\cdots, 8k-1,\cdots\}$.

$\sum_{k=1}^{n}k^{2}=\frac{n(n+1)(2n+1)}{6}$. As a result, the sum is divisible by 4 if and only if n is 0 or -1 mod 8. I think that examples are not hard to find....maybe induction works :)


quadratics
calculus
derivative
inequalities
analytic geometry
triangle inequality

[i]For $ |x|<\equal{}1$, $ |ax^2\plus{}bx\plus{}c|<\equal{}1$. Prove \[ |cx^2\plus{}bx\plus{}a|<\equal{}2\] for $ |x|<\equal{}1$[/i]
[hide]
\[ \text{For contradiction, assume there is a point in }[\minus{}1,1]\text{ such that }|cx^2\plus{}bx\plus{}a|>2\]
Notice that at each of $ x\equal{}\pm1,\qquad|cx^2\plus{}bx\plus{}a|\equal{}|ax^2\plus{}bx\plus{}a|\equal{}|a\pm b\plus{}c|<\equal{}1$.
Therefore $ |cx^2\plus{}bx\plus{}a|$ takes its maximum at its vertex, which must lie in $ (\minus{}1,1)$.
It follows that $ cx^2\plus{}bx\plus{}a$ must have two real roots, because its vertex lies locally farthest from the $ x$-axis. [b]Therefore $ b^2\minus{}4ac$ is positive.[/b]
Taking derivatives, the vertex of $ cx^2\plus{}bx\plus{}a$ [b]occurs at $ x\equal{}\minus{}b/2c$ which must be in $ (\minus{}1,1)$ so $ |b|<2|c|$[/b].
At this $ x$-value, $ |cx^2\plus{}bx\plus{}a|$ attains the value $ \left|\frac{b^2\minus{}4ac}{4c}\right|\equal{}\frac{b^2\minus{}4ac}{4|c|}$. We assumed earlier for contradiction that this was greater than $ 2$, [b]which is equivalent to $ b^2\minus{}4ac>8|c|$.[/b]

Going back to the original quadratic, $ f(x)\equal{}ax^2\plus{}bx\plus{}c$, we know that $ |f(\minus{}1)|,|f(0)|,|f(1)|<\equal{}1 \qquad \implies |c|<\equal{}1,|a\pm b\plus{}c|<\equal{}1$. By the triangle inequality, $ |a\pm b|<\equal{}|a\pm b\plus{}c|\plus{}|c|<\equal{}2$ thus $ |a|\plus{}|b|<\equal{}2$.

If $ ac>0$, then \[ b^2>b^2\minus{}4ac>8|c|>4|b|\iff (2\minus{}|b|)^2>4\iff |b|<0\], a clear contradiction (we used $ 2\minus{}|b|\equal{}|a|>0$).

Otherwise, $ ac<\equal{}0$. Hence \[ b^2\minus{}4ac\equal{}b^2\plus{}4|ac|>8|c|\iff \\ \iff b^2>8|c|\minus{}4|a\parallel{}c|\equal{}4(2\minus{}|a|)|c|\equal{}4|b\parallel{}c|>\equal{}2b^2\iff \minus{}b^2>0\], another contradiction.

We conclude $ |cx^2\plus{}bx\plus{}a|<\equal{}2$ in $ [\minus{}1,1]\qquad \square$
[/hide]

[hide]
Let $ P(x)\equal{}ax^2\plus{}bx\plus{}c,Q(x)\equal{}cx^2\plus{}bx\plus{}a,j\equal{}P(\minus{}1),k\equal{}P(0),l\equal{}P(1)$. We must have
\[ P(x)\equal{}j\cdot \frac{x^2\minus{}x}{2}\plus{}k\cdot (1\minus{}x^2)\plus{}l\cdot \frac{x^2\plus{}x}{2}\]
For $ |x|\geq 1$, we have
\[ |P(x)|\leq |j|\cdot \frac{|x^2\minus{}x|}{2}\plus{}|k|\cdot |1\minus{}x^2|\plus{}|l|\cdot \frac{|x^2\plus{}x|}{2}\]
\[ \leq \frac{|x^2\minus{}x|}{2}\plus{}|1\minus{}x^2|\plus{}\frac{|x^2\plus{}x|}{2}\equal{}\frac{x^2\minus{}x}{2}\plus{}(x^2\minus{}1)\plus{}\frac{x^2\plus{}x}{2}\]
\[ \equal{}2x^2\minus{}1<2x^2\]
so that $ |Q(1/x)|<2$. As a result, $ |Q(y)|<2$ if $ y\in [\minus{}1,1]$ and $ y\neq 0$.

Similarly, $ Q(0)\equal{}\frac{j}{2}\minus{}k\plus{}\frac{l}{2}$ so $ |Q(0)|\leq 2$ as well.
[/hide]

Nice proof, i was thinking of doing one in that style originally but i never could get it to work out. Anyway i just realized a way to eliminate the cases in my proof and simplify it:
[hide="Proof 2.0"]
\[ \text{For contradiction, assume there is a point in }[ \minus{} 1,1]\text{ such that }|cx^2 \plus{} bx \plus{} a| > 2
\]
Notice that at each of $ x \equal{} \pm1,\qquad|cx^2 \plus{} bx \plus{} a| \equal{} |ax^2 \plus{} bx \plus{} a| \equal{} |a\pm b \plus{} c| \leq 1$.
Therefore $ |cx^2 \plus{} bx \plus{} a|$ takes its maximum at its vertex, which must lie in $ ( \minus{} 1,1)$.

Thus the $ x$ coordinate of the vertex must lie in $ ( \minus{} 1,1)$ so $ |b| < 2|c|$.
The $ |y|$ value is $ >2$: $ \left|\frac {b^2 \minus{} 4ac}{4c}\right|>2$.

Going back to the original quadratic, $ f(x) \equal{} ax^2 \plus{} bx \plus{} c$, we know that $ |f( \minus{} 1)|,|f(0)|,|f(1)| \leq 1 \qquad \implies |c| \leq 1,|a\pm b \plus{} c| \leq 1$. By the triangle inequality, $ |a\pm b| \le |a\pm b \plus{} c| \plus{} |c| \leq 2$ thus $ |a| \plus{} |b| \leq 2$.

Hence
\[ |b^2| \plus{} |4ac| \ge |b^2 \minus{} 4ac| > 8|c|\iff \\
\iff b^2 > 4(2 \minus{} |a|)|c| \ge 4|b\parallel{}c| \geq 2b^2\iff \minus{} b^2 > 0
\]
contradiction.

We conclude $ |cx^2 \plus{} bx \plus{} a| \leq 2$ in $ [ \minus{} 1,1]\qquad \square$
[/hide]

[quote="me@home"][i]For $ |x| < \equal{} 1$, $ |ax^2 \plus{} bx \plus{} c| < \equal{} 1$. Prove
\[ |cx^2 \plus{} bx \plus{} a| < \equal{} 2
\]
for $ |x| < \equal{} 1$[/i]
[hide]
\[ \text{For contradiction, assume there is a point in }[ \minus{} 1,1]\text{ such that }|cx^2 \plus{} bx \plus{} a| > 2
\]
Notice that at each of $ x \equal{} \pm1,\qquad|cx^2 \plus{} bx \plus{} a| \equal{} |ax^2 \plus{} bx \plus{} a| \equal{} |a\pm b \plus{} c| < \equal{} 1$.
Therefore $ |cx^2 \plus{} bx \plus{} a|$ takes its maximum at its vertex, which must lie in $ ( \minus{} 1,1)$.
It follows that $ cx^2 \plus{} bx \plus{} a$ must have two real roots, because its vertex lies locally farthest from the $ x$-axis. [b]Therefore $ b^2 \minus{} 4ac$ is positive.[/b]
Taking derivatives, the vertex of $ cx^2 \plus{} bx \plus{} a$ [b]occurs at $ x \equal{} \minus{} b/2c$ which must be in $ ( \minus{} 1,1)$ so $ |b| < 2|c|$[/b].
At this $ x$-value, $ |cx^2 \plus{} bx \plus{} a|$ attains the value $ \left|\frac {b^2 \minus{} 4ac}{4c}\right| \equal{} \frac {b^2 \minus{} 4ac}{4|c|}$. We assumed earlier for contradiction that this was greater than $ 2$, [b]which is equivalent to $ b^2 \minus{} 4ac > 8|c|$.[/b]

Going back to the original quadratic, $ f(x) \equal{} ax^2 \plus{} bx \plus{} c$, we know that $ |f( \minus{} 1)|,|f(0)|,|f(1)| < \equal{} 1 \qquad \implies |c| < \equal{} 1,|a\pm b \plus{} c| < \equal{} 1$. By the triangle inequality, $ |a\pm b| < \equal{} |a\pm b \plus{} c| \plus{} |c| < \equal{} 2$ thus $ |a| \plus{} |b| < \equal{} 2$.

If $ ac > 0$, then
\[ b^2 > b^2 \minus{} 4ac > 8|c| > 4|b|\iff (2 \minus{} |b|)^2 > 4\iff |b| < 0
\]
, a clear contradiction (we used $ 2 \minus{} |b| \equal{} |a| > 0$).

Otherwise, $ ac < \equal{} 0$. Hence
\[ b^2 \minus{} 4ac \equal{} b^2 \plus{} 4|ac| > 8|c|\iff \\
\iff b^2 > 8|c| \minus{} 4|a\parallel{}c| \equal{} 4(2 \minus{} |a|)|c| \equal{} 4|b\parallel{}c| > \equal{} 2b^2\iff \minus{} b^2 > 0
\]
, another contradiction.

We conclude $ |cx^2 \plus{} bx \plus{} a| < \equal{} 2$ in $ [ \minus{} 1,1]\qquad \square$
[/hide][/quote]
Do we have that x is real, or can x be complex?

Sorry, yes $ x$ is real otherwise none of these ideas are really useful.


trigonometry
number theory
least common multiple
logarithms
geometry
3D geometry
trig identities

The problems are located here: http://www.math.sc.edu/contest/1992/exam/PDF/exam1992.pdf

I wasn't able to get #19,21,29. In fact, I don't even understand #19 :maybe:

[hide="16"]$1.0009765625=9765625 \cdot 10^{-10}+1=\frac{1025}{2^{10}}\Longrightarrow 9765625=\frac{10^{10}}{2^{10}}=5^{10}$. The sum of the digits therefore is $40$.[/hide]

[hide="17"]The sum is equal to $\cos{\pi/100}-\cos{0}+\cos{2\pi/100}-\cos{\pi/100}+...+\cos{\pi}-\cos{99\pi/100}=\cos{\pi}-\cos{0}=-2$[/hide]

[hide="18"] Let $n$ be the number of people. We have that $7n+10=8n+5 \Longrightarrow n=5$. Therefore, there are $45$ cards and $x=9$.[/hide]

[hide="20"]We take the LCM of the three numbers and add $2$. Therefore, $x=30+2=32$ and the sum of the digits is $32$.
[/hide]

[hide="22"]The number of digits of $12^{10}$ is $[10 \cdot \log{12}+1]$. Notice that $\log{12}=\log{2^{2}\cdot 3}=2\log{2}+\log{3}\approx 1.079$. Therefore $[10 \cdot 1.079+1]=11$
[/hide]
[hide="23"]$?^{2}=8^{2}+4^{2}-5^{2}=55$. The answer is $\sqrt{55}$ [/hide]

[hide="24"]Notice that the sum we are looking for is $\sqrt{2+\sqrt{2+\sqrt{2+\sqrt{2}}}}$. Also, note that $\sqrt{2}/2=\cos{45}$. We suspect that we can use the half angle formula with $\cos{45}$ which is $\sqrt{\frac{1+\sqrt{2}/2}{2}}$ multiple times. And indeed, after using it three times, we have $2\cos{\theta}$, where $\theta=\pi/4 \cdot (1/2)^{3}=\frac{\pi}{32}$.[/hide]

[hide="25"]The volume will be a cylinder (with the same radius) but a height of $4$, and half of a cylinder with a height of $6$ with radius $3$ as well. The total volume therefore is $63\pi$.[/hide]

[hide="26"]Notice that $1 \cdot 3 \cdot 5 \cdots 31$ has $15$ even numbers remaining to become $31!$. Using the numbers $15!$ from $16!$ and $2^{15}$ from $2^{16}$, we can make all the even numbers. Thus our expression simplifies to $31! \cdot 2 \cdot 16=32!$.[/hide]

[hide="27"]Notice that $\cos{20}>\sin{20}$, since smaller angles between $0^\circ-90^\circ$ make $\cos$ bigger and $\sin$ smaller (using the unit circle). We also have to keep in mind that the largest value $\cos$ and $\sin$ can take on is $1$. Thus, $\cos(\sin{20}))$ has the smallest angle value for $\cos$ giving the largest numerical value for $\cos$. That is our answer.[/hide]

[hide="28"]WLOG, let $CB=1$. We know that $\triangle{CGH}$ is a $30,60,90$ triangle, therefore $HC=AC=2$. We also have that $[\triangle{CGH}]=\sqrt{3}/2$. Thus $[\triangle{ABC}=\frac{1}{2}\cdot 1 \cdot 2 \sin{120}=\sqrt{3}/2$. Using the law of cosines, we find that $AB=\sqrt{3}$. Now we have that $[\triangle{AID}]=\frac{1}{2}\cdot 2 \cdot \sqrt{3}\sin{160}$ and $[\triangle{FEB}]=1 \cdot \sqrt{3}\sin{140}$. Clearly $[\triangle{AID}]>[\triangle{BFE}]$, however, $[\triangle{AID}]<\sqrt{3}/2$, since $\sin{160}<\sin{30}$ and therefore $<1/2$. It follows that $\triangle{ABI}$ and $\triangle{CGH}$ have the same areas and there is no largest triangle. [/hide]

[hide="30"]This problem just involves reasoning to get the answer as $3$. Of course, what you could also do is rip out a sheet of paper and fold it into a cube and start marking down numbers to easily visualize it. [/hide]

Time to fill in more gaps!

[hide="19"](c) We have $a^{10}a^{4}=a^{3}a^{4}$, so $a^{7}=a^{14}$.[/hide]

[hide="21"](d) We see that $(\frac{1}{2})^{100}=\frac{5^{100}}{10^{100}}$. Then we want the third digit from the right of 5^{100}. Note that $5^{4n}$ will always end in 625, because $5^{4}=625$ and $625^{2}$ is congruent to 625 mod 1000. Hence the answer is 6.[/hide]

[hide="29"](d) Observe that $54_{10}=110110_{2}$. Then m may not have a 1 in the 1's or 8's place by Lucas's theorem. But m has two possibilities in each of the other 4 places, yielding 16 possibilities for m (all at most n).[/hide]


The area of a circle with a diameter of $ 4\pi$ is written as $ a\pi^b$, where $ a$ and $ b$ are positive integers. What is the value of $ ab$?

Radius is $ 2\pi$, so the area is $ 4\pi^{2}\cdot \pi\equal{}4\pi^{3}$, so $ ab\equal{}12$.


Write $ 2^{\frac12}\plus{}2^{\frac12}$ in simplest radical form.

hello, the answer is [hide=here]$ 2\cdot 2^{\frac{1}{2}}\equal{}2\cdot\sqrt{2}$.[/hide]
Sonnhard.

On FTW, I got this question. When i put in 2rt2, it said [hide=...]it was wrong and the right answer was 2sqrt2[/hide]. I thought you could use rt.

No, you can't. In case you're wondering, rt stands for right triangle.

Oh, well in alcumus it accepts rt for sqrt


This problem is inspired by AP Government :P.

Suppose you have a contiguous region $R$ and a subregion $S$ (not necessarily contiguous) such $\text{area}(S) > \frac{1}{2}\cdot \text{area}(R)$. Can we always partition $R$ into contiguous subregions $P_{1}, P_{2}, \ldots, P_{n}$ such that

$\text{area}(P_{i}\cap S) > \frac{1}{2}\cdot \text{area}(P_{i})$

for all $i$? Basically, can we divide $R$ such that $S$ contains more than half of the area in each division. This would make the process of redistricting very effective for the majority party :wink:.

[quote="t0rajir0u"]I'm finding it hard to solve this with any rigor   :rotfl:[/quote]

Same haha. I think it's true though; at least I can't find any counterexamples...

[quote="JBL"] perhaps you want to require all the $P_{i}$ to have equal areas?  In that case, I can generate counter-examples.[/quote]

Hmm.  I think this would be more faithful to the motivation for the problem.  What's the counterexample?

[quote="JBL"]By "contiguous," I assume you really mean "connected."  Also, you really don't have very many constraints ... perhaps you want to require all the $P_{i}$ to have equal areas?  In that case, I can generate counter-examples.

Although, on further thought, another reasonable constraint would be that $R$ and the $P_{i}$ be open, in which case the counter-example I imagined wouldn't work.[/quote]

Perhaps, I haven't thought out the problem very clearly, but it would be interesting to see counterexamples for any case that you have one for.

[quote="JBL"]The counter-example is an "asymmetric bow-tie."  The top triangle has area between $\frac{1}{2n}$th and $\frac{1}{n}$th of the whole thing.  The yellow region is $S$.

Any connected set which contains points from the top half and points from the bottom half must contain the "knot" of the bow-tie, the single point in the middle.  Thus, we can say about each half of the tie that it must be subdivided into several regions, each with area $\frac{1}{n}$, except that they are each entitled to one region of area at most $\frac{1}{n}$.  Since the total area of the top half is at most $\frac{1}{n}$, it must fall entirely within one of the $P_{i}$.  But since its area is at least $\frac{1}{2n}$ and the area of the $P_{i}$ is $\frac{1}{n}$, this $P_{i}$ shares at most half of its area with $S$.

Adding openness voids this counter-example, since it's not possible to create a bottleneck in the way I just did.

If we don't require the $P_{i}$ to be of equal area but we do require the boundary between $S$ and $R \setminus S$ to be at least in part a smooth curve, we can always find a solution by taking all but one of the $P_{i}$ to be extremely tiny disks along the boundary and the final $P_{n}$ to be all of $R$ except these disks.[/quote]

That's tricky. What if we force $R$ to be convex? Is it still possible to construct a counterexample when the area of the $P_{i}$ are all equal?


[quote="SonicX"]Sa se determine un $x\in\mathbb{Z}$ astfel incat $241x\equiv 1$ $\pmod{1000}$.[/quote]

nu exista nici un astfel de x.

offtopic: ce clasa esti? :P

eu zic ca exista
[hide="o varianta"]
$x=241^{\varphi(1000)-1}$.
$\varphi(1000)$ chiar se calculeaza usor, dar nu am rabdare acum:)
[/hide]

[hide="Raspuns"]Da, si $\phi(1000)=1000 \cdot \frac{1}{2}\cdot \frac{4}{5}= 400$. Dupa un calcul simplu (preferabil in C++ :) ) se obtine $241^{399}\equiv 361 \pmod{1000}$, adica inversul cautat e $361$.
De fapt, este bine-stiut ca pentru $a, m \in \mathbb{Z}, m > 0$ cu $(a, m) = 1$, $a^{-1}\equiv a^{\phi(m)-1}\pmod{m}$.[/hide]

Un numar care verifica relatia este $x=-639$.
($241\cdot639+1=154000$)

$P.S.$ Este evident ca numarul cautat intr-adevar exista.  :P


Let $a,b,c$ be non-negative real numbers. Find the maximum and minimum values of \[(\frac{a}{a+b+c})^{2}+(\frac{b}{b+c+d})^{2}+(\frac{c}{c+d+a})^{2}+(\frac{d}{d+a+b})^{2}.\]

It is easy to see that $Min \le 1/2$ and $Max \ge 2$.
Are $1/2$ and $2$ indeed the minimal and maximal value?

Certainly, minimum isn't $1/2$. Let $a=b=c=d$ then the value is $4/9<1/2$.

the easier part of the problem is showing that $A<2$ and $2$ cannot be improved.
indeed:
$A=\sum_{cyc}(\frac{a}{a+b+c})^{2}\le \sum_{cyc}(\frac{a}{a+c})^{2}<2$
and by taking $a=b=0$ and $c\rightarrow inf$
$A\rightarrow 2$


Let $x,y,z$ be positive real numbers in $\left[0,\frac{1}{2}\right]$ with sum $1.$ Prove that \[\sum_{\mathrm{cyclic}}\frac{x^{4}+x^{2}+1}{x^{4}-x^{2}+1}>3\sqrt{2}.\]

[quote="bodan"]Let $x,y,z$ be positive real numbers in $\left[0,\frac{1}{2}\right]$ with sum $1.$ Prove that \[\sum_{\mathrm{cyclic}}\frac{x^{4}+x^{2}+1}{x^{4}-x^{2}+1}>\sqrt{2}.\] [/quote]
Just sum over
$\frac{x^{4}+x^{2}+1}{x^{4}-x^{2}+1}\ge 1$


Find the number of ordered pairs $ (m,n)$ where $ (m,n) \in {{1,2,....20}}$ such that $ 3^m\plus{}7^n$ is a multiple of 10

Hi. Yes, I've got $ 100$ now.  I had $ 7^{3} \equal{} 6$ modulo $ 10$ when it should be $ 3$. This gives $ (3, 3)$ modulo $ 10$.

Each of the possibilities $ (1, 1), (2, 4), (3, 3), (4,2)$ gives $ 25$ possibilities for $ (m, n)$, making it $ 100$ altogether.

$ 7^3\equiv 6mod10 \ ?? \ it \ should \ be \ 7^3\equiv 3mod10$

Yes, that was one of the two mistakes I made the first time. My last post says it is $ 3$. (I also counted $ 5$ instead of $ 25$ for $ (1, 1)$). This gave me $ 5 \plus{} 25 \plus{} 25 \equal{} 55$ where I now have $ 25\plus{}25\plus{}25\plus{}25\equal{}100$.


Find the smallest $ n\in{N}$ such that this equation has a positive integer solution:
                $ y^2 \equal{} x^{1992} \minus{} x^{1990} \plus{} (2n \minus{} 1)x^3 \minus{} x$

it's true but send a complete solution,plz(disprove that there exists solution if $ n \equal{} 1,2$)

تایپ لاتکس حال می خواد و راه حل برای تایپ نسبتا طولانیه
ممنون از سوال خوبت
امسال دوره بودی؟
من یک رو با استقرا(بازگشتی) و دو رو با همنهشتی به پیمانه 4 رد کردم


This time we are starting at 15, simply because boys outnumber the girls a lot to three.... :|

Good luck all!!!! I'll start :wink: .

[b]15[/b]

CONGRATS GIRLS!!!!!!!
Girls-2, Boys-1.
Good job everyone!

[b]11[/b]

boys beat us last time.. u were afk :(

[b]9[/b]

oh. well we'll beat them this time!!!! :D

You meant 9 and I post [b]8[/b].

Yes. :D

[b]7[/b]

they don't even kno about this!!!

tho i did post it on ftw

so they can't say i didn't tell them!!

6.

This will be funny if we're the only posters.

[b]7[/b] yes, that would be funny

i'll tell them when we're done :wink:

I swear the number changed.  Right before I posted, the last post said '3!!'.  Then I went to go get lunch.  Weird.   :(

@westiepaw: oh, i get it now.

@PowerOfPi: yup!! now it's 2-1!!

later, please... i just did two rounds in one hour and i am exhausted!!!

plus, most of the girls (which still is not many) are afk right now... :D

There's a new thread now.    :D
@jjfun1: sorry, i made the thread right before you posted.

that's ok.. i posted in that one

btw: r u a boy or girl?? :blush:

Girl.  I minus 1 every time, don't I?   :)  :P

hmm i never looked back at your posts... yay you can help izzy and I!!! :D

Yay!  Wonder where izzy is.  She was here earlier...  :D

yeah... hope she stops being afk!!!! :maybe:

Because there is already a winner and this game is already done....... there is no point in posting anymore :|


trigonometry
Pythagorean Theorem
geometry
trig identities
Law of Sines

Find, with proof, the maximum possible value of $5cos(x)+12sin(x)$.

[hide]Pythagorean theorem on the complex plane $\boxed{13}$[/hide]

EDIT:  :rotfl:  :rotfl: I admit it I graphed it and made up a reason.  I thought it made sense though...

Let $f(x) = a\sin x+b\cos x+c$. Both upper bounds $\sqrt{3}\sqrt{a^{2}+b^{2}+c^{2}}$ and $\sqrt{a^{2}+b^{2}}+c$ are correct by Cauchy.
But which one is the best?  :wink:

If you're going to use Cauchy you should check to make sure that maximum is attainable.

I was doing some random other problem when posting that thing above(which I kinda edited)

[hide="proof that its attainable"]
Equality holds in Cauchy when
$\frac{\cos x}{5}=\frac{\sin}{12}$
$\iff \frac{12}{5}=\tan x$
So it definitely is attainable.

(do I need the stuff below?)
Proof that nothing higher is attainable:
Assume $5\cos x+12\sin x>13$
Then
$\frac{5}{13}\cos x+\frac{12}{13}\sin x>1$
Let $\cos\theta=\frac{5}{13},\sin\theta=\frac{12}{13}.$
Then we have
$\cos\theta\cos x+\sin\theta\sin x>1$
$\cos(\theta-x)>1$
which is a contradiction.

[/hide]

[hide]
\[5\cos x+12\sin x=13\sin \left( x+\arcsin \frac{5}{13}\right)\]
This is less than or equal to 13, with equality when $x=\arccos \frac{5}{13}$
[/hide]

You can also use the law of sines to prove that the maximum is attainable, noting that $ cos x = sin{\frac{\pi}{2}-x}$

And then you get a right triangle with legs $ A = 5, B = 12$ and angles $ a = \frac{\pi}{2}-x, b = x$

By the law of sines, $ \frac{cos x}{5}= \frac{sin x}{12}$


What is the formula for the chicken mcnugget theorem for three numbers?

[quote="Dr Sonnhard Graubner"]hello, see here
http://www.mathlinks.ro/viewtopic.php?t=229244
Sonnhard.[/quote]

Yeah, I don't know if there is a good thread about this topic on the site, but that one definitely isn't any good.

The first person to respond says to use the formula for two numbers twice (which I've already discussed with several people is a [i]very[/i] wrong way to do it).  Then later, we have someone post about the Frobenius number of 4, 6, and 10, which isn't even defined.

As far as I know, there is no "formula" for three numbers, in general.  That is, there is a polynomial-time algorithm, but there isn't a simple, closed equation.

To give you an idea of the situation, I don't even think we know of a polynomial time algorithm for four numbers (or maybe we do for four, but not five - I can't remember exactly).  Therefore, it shouldn't be surprising that there isn't a nice equation for 3 numbers.

With that said, though, I'm sure there are some special cases where we can solve for the frobenius number of three numbers easily, but I'm not able to categorize them all.  For instance,
6, 9, n, where 3 doesn't divide n.
Note that 6 and 9 will make exactly those multiples of 3 that aren't 3 itself.  It follows "somewhat" easily that
2n+3 is the largest number that cannot be made by summing 6, 9, and n.

I think you can extend this to
2p, 3p, and n, where the prime p doesn't divide n.
I [i]think[/i] that the number will be (p-1)n + p


algebra
polynomial
superior algebra
superior algebra unsolved

prove that $ X^n \minus{} X^{n\minus{}1} \minus{} t \in \mathbb{Q}(t)[X]$ is irreducible

Why? The coefficient of $ X^{n\minus{}1}$ is not divisible by t.


The graphs of $y=2^{x}$ and $y=x^{2}$ intersect 3 times. Find the sum of the y-coordinates of the intersection points that have positive x-coordinates.

[hide="solution"]$2^{x}=x^{2}$

If you graph them, one of the solutions is negative and two are positive.  $x=2$ and $4$ work (brute force) so its $\boxed{20}$[/hide]


I'm not sure what age students you are talking about (knowing that would help a lot) but here is my all time favorite, which works for all ages equally well: make a hole in a standard (say, 8x11 inches) piece of paper through which you can go :)

:wink: The age group is high school students, most of them probably have had algebra and are in/have had precalculus.

Tthough I have seen it before, that puzzle is interesting. :lol:

[quote="Hamster1800"]A great puzzle with basis in algebraic topology:

Take a picture and hang it on two nails with one piece of rope such that it stays up, but if either nail is removed, it falls down.[/quote]

...are you allowed to put the two nails and connect them by the rope, then place the picture on that rope?

Of course, not!

Here are two more puzzles that may keep one occupied for a few minutes ;)

a) You have 2 fuses each of which burns exactly 1 minute (but you are not guaranteed that the fire travels over the fuse at a constant speed). Your task is to measure a 45 second time interval using nothing but these 2 fuses and a lighter.

b) The English letter H is drawn on the plane. Draw 3 more straight lines in such a way that the resulting picture contains 7 disjoint triangles.

Well in that case...

Neither nail can be through the picture, because then the picture wouldn't fall down upon removal of the other nail.  The rope can't be going through the picture either.  So the rope must be connecting the nails, which are pinned into the wall, giving us the setup i mentioned...assuming you're hanging it on a planar wall parallel to the net force of gravity...

[quote="Hamster1800"]The specifications are: The wall is vertical (where vertical is parallel to the force of gravity), the rope must end connected to the picture at its top left and top right corners. The rope may not be cut. Thus, the rope + picture form a closed loop. The nails are nailed into the wall.[/quote]

[hide="i think i got it, is this right?"]
Arrange the nails vertically, one above the other.

Make an "M" shape. Place it so that the bottom nail is right above the "V" of the "M" in the middle.
Take the left hand side of the "M", the "^" shape, and place the "peak" right over the top nail. Do NOT twist the "^" from how it was in the "M".
Do the same for the right hand side, but DO make a 180degree twist to it.
Attach frame to dangling ends.

Taking out the bottom nail, the "V" will go around the top nail, from right to left above the nail, and the frame falls.
Take out the top nail, and the "^"s of the M will fall, the bottom nail being above the rope does not hold the rope up, and the frame falls.
[/hide]

Yes, that is a solution. Now describe it with the nails horizontal. (The placement of the nails doesn't actually matter, but if you give this to someone, give them the nails drawn on a piece of paper so they can't move them)

A similar puzzle: Draw three rings such that they are linked but if any one of them is removed they are unlinked.

Could you post of a picture of that solution? I don't really get it...

[quote="Hamster1800"]

A similar puzzle: Draw three rings such that they are linked but if any one of them is removed they are unlinked.[/quote]

Can they be deformed?  Ie are they rubber bands?  Because no two rings can be linked through one another, it's impossible with circular rings...

The fact is, if you allow that, then the rings can always be deformed back, right?

Yes, the ring puzzles is impossible with rigid rings. It's more like closed loops of rope.

[quote="pianoforte"]the picture looks kinda innappropriate...  :ninja:

they look saggy[/quote]

okay thanks I understand now  :D

neat puzzle

[hide="ring puzzle"]

Make each into a kind of "saddle shape": here's one way to think of it:

Take a cube and put black paint on four parallel edges.  Now these four edges connect two faces.  On one face, paint two parallel edges, and on the other face, paint two parallel edges NOT parallel to the edges on the first face.  The painted part of the cube shows what this saddle shape looks like.

If you pinch the two saddles together at each side, you get something which looks like a tetrahedron.  Now you have to thread these saddles through each other.  It must be that any two of the rubber bands are connected because they're threaded in this way.  It's really hard to describe...maybe I should take a picture or something[/hide]

EDIT: It also works for $ n$ rings, btw

Once we are talking about this, here is a very old puzzle. Still, many people seem to be unaware of it. You take two people and 2 long ropes. Then you tie the ends of the ropes in loops around people's wrists so that they coldn't slide them off their hands but not too tightly. You do it in such a way that the first rope together with the body of the first person and the second rope together with the body of the second person form 2 linked "circles" (it is quite a lame explanation but I hope you understand what is meant). The task is to untangle the people from each other without cutting the ropes or taking the ropes off their hands.

[quote="fedja"]...so that they coldn't slide them off their hands but not too tightly...[/quote]

Is it relevant that they aren't too tight?  If the ropes are attached to their arms, you essentially have two rubber bands                                                  (okay maybe more complicated than that) which are linked...

yeah, it's important

i think i saw this one in a magic book, can't remember the solution

[hide="ok, i tried it with real rope, and got"]
note: from my point of view, MY rope is left side on top, right side on bottom.

slip your rope into loop around my right hand on top, from behind
bring it around the hand so it's now on the bottom

they should be separate now

ed: so essentially, there is a cut in the loop created by my hand and the loop. it only looks like a closed loop because my hand can't get out
[/hide]

These are very cool puzzles. :lol:

Can someone try explaing the situation in the last puzzle by fedja?

Keep those puzzles coming. :)

Here is one more (it is simple arithmetic, but): Using the numbers 1,3,4,6 each one time and 4 arithmetic operations ($ \plus{},\minus{},\times,/$), get 24. Parentheses are allowed but you cannot make 2-digit numbers, raise to powers or do any other tricky stuff. This one can take from 5 minutes to 5 days to solve :lol:.

[hide="answer"]
$ \frac{6}{1\minus{}\frac{3}{4}}$
[/hide]
Similar puzzle is 8,8,3,3.

[hide="answer"]
$ \frac{8}{3\minus{}\frac{8}{3}}$
[/hide]

Those answers of Hamster1800 do not count because they use something OTHER than "(+,-,X,/)" to achieve 24.

Answers:
[hide]6/(1 - 3/4)  and 8/(3 - 8/3)[/hide]

I'm not "dude."

Hurry up and understand that using THOSE symbols as picked out by the problem giver and horizontal fraction bars as given by another user are not
equivalent for the purpose of getting a puzzle exactly right.

Uh... What? The "horizontal bar" is the exact same thing as a slash...

No, what THOSE forms using the horizontal fraction bars have is the same intent
when it comes to the value, but neither of those is a "slant divider."

That's why I put in QUOTES the four symbols (in the parentheses) the problem proposer who listed them THAT WAY to make them stand out that that they were to be the exclusive forms of the four operators.  You must use THOSE symbols, unless that proposer gave exception.  It is the proposer's fault if he or she did not.

Puzzles can rely on being exceptionally picky for sticking to the forms, WHETHER
OR NOT, the proposer intended them to be or not.

Watch your wording in puzzle making, in general.

First, 24 is not one of those puzzles which is extremely picky about forms.

Second, the poster said "The four arithmetic operations ($ \plus{}, \minus{}, \times, /$)" not "The symbols $ \plus{}, \minus{}, \times, /$". A fraction bar is still one of the four arithmetic operations. It's just that a slash, or $ \div$ is how it's represented in a list of the four.

"...or do any other trick stuff."

"...is not one of those puzzles which is extremely picky about forms."

These are inconsistent statements.  DON'T make certain statements with the
puzzle to begin with, or don't make certain statements after the fact.

You cannot have it both ways.

Come on, I just tried to describe the puzzle in an inambiguous way :(!. Hamster1800's solution is correct (you may rewrite it as 6/(1-3/4), of course, to satisfy every formal requirement but this rewriting is obvious). Anyway, this thread is supposed to be a helpful collection of  puzzles rather than a heated discussion of what is and what isn't a solution...

box of rocks is a troll: you'd all do best to simply ignore it and hope it goes away.

[quote="AstroPhys"]I need to find a few puzzles for a club at my school.  They are not to be restricted to purely competition typed problems but, rather, puzzles of any kind. Topology, combinatorics, lateral, etc.
So if anyone has really good ones, or where to find some online, that would be cool. :)
Do not want this to sound like a homework assignment or anything, but by the end of this weekend if possible.  Past that, keep posting puzzles, just that the first few are needed by early next week.[/quote]

i got a really good one

[code]http://www.robmathiowetz.com/[/code]

its pretty famous so you might already know it. Also I have a book called psychometric testing. Its like a iq test. I could scan some pages from the book if you want?

Speaking of "lateral puzzles", here are two my friend told me today.

1) A blind man was given 4 round pills: 2 black and 2 white. All 4 pills are of exactly the same shape. The prescription says: "Take one white pill and one black pill today at Noon and do the same tomorrow. Under no circumstances take two black pills or two white pills at once!". Noon is now and, unfortunately, all 4 pills are in one bag and there is nobody around to help. What can the blind man do?

2) Inside a room there are 3 ordinary lightbulbs connected to 3 switches outside (all the wiring is inside the walls and cannot be seen). Each switch turns one of the light bulbs on and off. Originally all switches are in the off position and the room door is closed.
You can do whatever you want with the switches (without destroying anything). After that you are allowed to enter the room and do whatever you want there (again, no vandalism, please :)). Your task is to tell which switch corresponds to which lightbulb before you leave the room.

[quote="fedja"]1) A blind man was given 4 round pills: 2 black and 2 white. All 4 pills are of exactly the same shape. The prescription says: "Take one white pill and one black pill today at Noon and do the same tomorrow. Under no circumstances take two black pills or two white pills at once!". Noon is now and, unfortunately, all 4 pills are in one bag and there is nobody around to help. What can the blind man do?[/quote]
[hide="Solution?"]Cut each pill in half, and eat half of each pill today.  Save the rest for tomorrow.[/hide]

[hide="Solution for 2"]Turn two of the switches on. After a couple minutes, turn one of them off, and go into the room. The bulb that is still on is obviously the one corresponding to the switch in the "on" position. Now feel the other two bulbs. The warmer one should correspond to the switch you turned off.[/hide]