inequalities
geometry
perimeter
geometry proposed

let A1A2....A2007 be an equable polygon with 2007 sides and B1B2...B6 an equable polygon with 6 sides having the same circumscirbed circle. Proof that:

2*B1B2/A1A2 > 669*(1-1/pi)

nobody knows? it`s a simple problem because of a simple reason: is composed by me  :rotfl:

[quote="maky"]what`s an equable polygon ?  :blush:[/quote]

maybe i didn`t write well...I mean regulary, A1A2=A2A3=A3A4=.... and as well B1B2=B2B3=B3B4=....

1-1/pi < 3/pi

and because L=R its enough to proof that:

2piR>2007L which is logical because the perimeter of the circumscirbed circle is bigger then the perimeter of the polygon


geometry
rectangle
trigonometry
area of a triangle
Heron\u0027s formula
calculus
calculus computations

A long flat piece of sheet metal, $ 12 \ \text{in.}$ wide is to be bent to form a long trough of pentagonal cross section. Find the values of $ a$, $ b$, and $ \alpha$ that maximize the area of the cross section.

http://img132.imageshack.us/my.php?image=72708381ps2.jpg

I divided it up into a rectangle and triangle? But I can't find the other side of the rectangle.

That's what the angle $ \alpha$ is for. Use some trigonometry.

[hide="In more detail"]The width of the trough is $ 2a\cos\alpha.$

The problem becomes this:

Maximize $ A\equal{}2ab\cos\alpha\plus{}a^2\sin\alpha\cos\alpha$

subject to the constraint $ 2a\plus{}2b\equal{}12$ in the region $ a\ge 0,b\ge 0,0\le \alpha \le \frac{\pi}2.$[/hide]

I used opposite interior angle are congruent and deduced that the with of the trough was $ \frac{a}{\sin \alpha}$. Then the area of the rectangle is $ a b \sin \alpha$.

Then I used Heron's Formula  to get area of triangle. Then $ \text{Total Area} \equal{} a b \sin \alpha \plus{} A_{\text{triangle}}$.

Set $ \alpha\equal{}0$ (flat-bottomed trough, triangle of area zero, all of the area is in the rectangle) and look carefully at what you just wrote, and ask yourself it it makes any sense.

I got $ a \equal{} b \equal{} 3$ and $ \alpha \equal{} \frac{\pi}{4}$.


CHRISTMAS AT FUNCIA'S HOUSE

Funcia has 4 siblings:Athena, Melanie, Clarence & Lucy.
If they all exchange gifts and everyone has to get 2 gifts and give 2 gifts how many combinations of who gives who gifts can be made?(Note: you cannot get a gift from a person who gave you one)

Special Note: My mother is offering 5 for this question to be answered and I will gladly ship you money if you answer this and explain how you did it...

[hide]I got 12. First of all, funcia must give two gifts and receive two gifts, all from different people. There are only 4 people besides funcia, so two of them have to give him gifts, and two of them have to get gifts. The people getting gifts can be chosen 4 choose 2 ways, which is 6. Now there are 4 people left, and lets just say that Athena and Melanie gave funcia gifts, and Clarence and Lucy got gifts. Athena has to give one more gift, and it has to be to clarence or lucy. There are two ways for the 4 to distribute gifts, so the answer is 6 times 2 or 12[/hide]

I'm printing that out now..... :lol: I don't see any flaws myself...oh and i'll edit that question

My mum said that the reason that is wrong is me! It turns out you can give to a person who gave to you!!! Is their anyone who would like to try this problem? :lol:  :blush:

heavens to betsy  - no lol ill pass on this one  :wink:

I got 12. First of all, funcia must give two gifts and receive two gifts, all from different people. There are only 4 people besides funcia, so two of them have to give him gifts, and two of them have to get gifts. The people getting gifts can be chosen 4 choose 2 ways, which is 6. Now there are 4 people left, and lets just say that Athena and Melanie gave funcia gifts, and Clarence and Lucy got gifts. Athena has to give one more gift, and it has to be to clarence or lucy. There are two ways for the 4 to distribute gifts, so the answer is 6 times 2 or 12.

I'll be expecting the 5 dollars - just run up a DNS whois search on http://www.lunchlady.org or something.

[quote="mustafa"]I got 12. First of all, funcia must give two gifts and receive two gifts, all from different people. There are only 4 people besides funcia, so two of them have to give him gifts, and two of them have to get gifts. The people getting gifts can be chosen 4 choose 2 ways, which is 6. Now there are 4 people left, and lets just say that Athena and Melanie gave funcia gifts, and Clarence and Lucy got gifts. Athena has to give one more gift, and it has to be to clarence or lucy. There are two ways for the 4 to distribute gifts, so the answer is 6 times 2 or 12[/quote]

[quote="treething"]I got 12. First of all, funcia must give two gifts and receive two gifts, all from different people. There are only 4 people besides funcia, so two of them have to give him gifts, and two of them have to get gifts. The people getting gifts can be chosen 4 choose 2 ways, which is 6. Now there are 4 people left, and lets just say that Athena and Melanie gave funcia gifts, and Clarence and Lucy got gifts. Athena has to give one more gift, and it has to be to clarence or lucy. There are two ways for the 4 to distribute gifts, so the answer is 6 times 2 or 12. [/quote]

Way to copy and paste my answer :rotfl:

Yes way to copy and paste!! but how about my other question without that other restraint?

Oh and this is the new question:
I want to know if there is a better way other than to brute force it to check my answer of 252(and really, how to do it since I'm not sure if that is correct):
A,B,C,D,and E all exchange gifts for Christmas. They all give two gifts to two different people and receive two gifts(from two different people.) How many ways can they give/receive gifts?

Ok, for question 1, I'm almost done, and there are at least 44 possibilities.(i'll explain when I'm done, but this could take awile!!!)

Lets say it took 5min. per brute force.  Thats.....[hide]21 hours!!!![/hide]

no with brute force i got 252 since I took away a constraint mustafa you try reading it again

Hello hello is there anyone in here please help and check or expl what i did wrong

Lets number the people 1-5.  1 can give 5 two of the presents remember, this being the flaw in your origanal answer.

it's a nice way of looking at it though but i'll show my mother that ....
could ((((((6*6)-x)*6)-y)*6)-z)
help where
 x y and z are the repeats of gift giving through the steps (ex. i give to athena and clarence and athena gives to clarence and mely) so clarence is a repeat?

 or is the fact that depending if you repeat or not  for the first two people :

[hide="if you do"]clarence(3rd person) has 3 choices to choose from[/hide]
or
[hide="if you dont"] clarence has 1 choice to pick from[/hide]
oh and jdilllon actually it was 1 can give 5 and 5 can give 1but they also have to give and receive from different people(can't give two gifts to same person)

[quote="funcia"](can't give two gifts to same person)[/quote]

Oh, sorry.   :blush:

Another problem with t0rajir0u's solution is that it differentiates between Gift #1 and gift #2. For example, it distinguishes between person 1 giving Gift #1 to person 2 and Gift #2 to person 3, and giving gift #2 to person 2 and gift #1 to person 3.

Well perhaps you can try your hand at it? Or try it again?

obvious? could you give your reasoning? :lol: that throws me for a loop.... :rotfl:

Is the answer...
[hide]
$4680$?
[/hide]

If it's right I'll give you my solution.

yeah it isn't in the range :wink: reread the problem....
umm other person above ubemaya i don't know the answer that is why i am asking  :lol:

now i have a strange answer:256 you notice in my old notes i said there were a few with 6 for C and 1 for C well there are a bunch with 3 for C also :)


geometry
Pythagorean Theorem
power of a point
AMC

In the figure, $\overline{AB}$ and $\overline{CD}$ are diameters of the circle with center $O$, $\overline{AB} \perp \overline{CD}$, and chord $\overline{DF}$ intersects $\overline{AB}$ at $E$. If $DE = 6$ and $EF = 2$, then the area of the circle is
[asy]
size(120); defaultpen(linewidth(0.7));
pair O=origin, A=(-5,0), B=(5,0), C=(0,5), D=(0,-5), F=5*dir(40), E=intersectionpoint(A--B, F--D);
draw(Circle(O, 5));
draw(A--B^^C--D--F);
dot(O^^A^^B^^C^^D^^E^^F);
markscalefactor=0.05;
draw(rightanglemark(B, O, D));
label("$A$", A, dir(O--A));
label("$B$", B, dir(O--B));
label("$C$", C, dir(O--C));
label("$D$", D, dir(O--D));
label("$F$", F, dir(O--F));
label("$O$", O, NW);
label("$E$", E, SE);[/asy]
$\textbf{(A)}\ 23\pi \qquad
\textbf{(B)}\ \dfrac{47}{2}\pi \qquad
\textbf{(C)}\ 24\pi \qquad
\textbf{(D)}\ \dfrac{49}{2}\pi \qquad
\textbf{(E)}\ 25\pi$

Put G on $\ \overline{CD}$ such that $\ \overline{GF} \perp \overline{CD}$ then use similar triangles and pythagoras.

[hide]Let $r$ be the radius. By Pythagorean Theorem, $OE=\sqrt{36-r^2}\Rightarrow EB=r-\sqrt{36-r^2}$.
By Power of a Point,
$12=\left( r+\sqrt{36-r^2}\right) \left( r-\sqrt{36-r^2}\right)=2r^2-36\Rightarrow r^2=24$
making the area $24\pi$. [b](C)[/b][/hide]

Another way

Extend $FC$ and we see that $\triangle {DFC}$ is similar to $\triangle {DEO}$ (since $DC$ is the hypotenuse and so it must be a right triangle), so by calling $OD$ and $OC$ as $x$, we can set up the proportion: $\frac{8}{x}=\frac{2x}{6}$, and we get that $x^2=24$, so the area is $\boxed{24\pi}$


Let A = {a,b,c,d,e} and P and Q be two non empty subsets of A. then determine the number of ways in which P and Q can be selected such that P$\bigcap$Q has atleast one element .

too easy .
 $4^{5}-3^{5}$

 It's simple really. use Principle of Negation.
 build $P$ and $Q$ such that they have no element
 in common. this can be done in :

 $\binom{5}{1}*(2^{4}-1)+\binom{5}{2}*(2^{3}-1)+\binom{5}{3}*(2^{2}-1)+\binom{5}{4}*(2^{1}-1)$
 i think you can understand how this works out.
 that is equal to $180$.

 the total number of ways to choose non-$\phi$ would be
 $(2^{5}-1)(2^{5}-1) = 961$.

 Required answer is $961-180 = 781$
 thi works out to be $4^{5}-3^{5}$.


A three-digit number is selected at random. What is the probability
that none of the three digits are prime? Express your answer as a
common fraction.

The only non prime digits are 0, 4, 6, 8, and 9. The first digit cannot be a 0, so there are 4 choices. For the next two digits there are 5 choices. Thus, $ 5\cdot 5\cdot 4\equal{}100$ numbers are success. There are a total of $ 9\cdot 10\cdot 10\equal{}900$ ways to make 3 digit numbers, to the probability is $ \frac{100}{900}\equal{}\frac{1}{9}$.

Actually, 1 isn't prime either. Using the same logic as above (but with 1 counting),

$ \frac{6\cdot{6\cdot{5}}}{900}\equal{}\frac{1}{5}$

[quote="TrueshotBarrage"][quote="dragon96"]Oh. I thought it said were composite.[/quote]

But $0$ isn't a composite number either, so...[/quote]

lol :P


Everyone knows that counterexamples in Analysis are very elegant.Here is one.
Give an example of a system of sets $\mathcal{S}$ and an example of $\sigma$-algebra,such that it doesn't contain the set $X=\bigcup_{A\in{\mathcal{S}}}{A}$ but it contains all sets of $\mathcal{S}$.

Am I horribly misunderstanding this problem? As far as I understand, we are given a system of sets, and are asked to construct a $\sigma$-algebra which does not contain the union of the sets in the system. The given system could be $\{x\}$ for some $x$, for example. What am I missing here? :?

[quote="jmerry"]Let $S$ be $\{\{x\}: x\in \mathbb{R}\}$. The $\sigma$-algebra these generate consists of all countable subsets of $\mathbb{R}$.[/quote]
But then what is theunit set of that algebra i.e. $E\in{\sigma(\mathcal{S})}$,s.t. $E{\cap}A=A$ for all $A\in{\sigma(\mathcal{S})}$.

The existence of a unit set which is a member of a $\sigma$-algebra is not in the definition. In this case, it doesn't exist.

Algebra of sets is a ring of the sets with a unit set.Isn't it the definition?  :?

Guys, I'm getting really confused here. Could someone please answer my question in post no. $3$?

BTW, as far as I know, a $\sigma$-algebra is a collection of sets which contains the empty set, for each set $A$ in it, it also contains the complement of $A$, and for each countable family of sets in it, it also contains the union of that family. Is this wrong?

Edit:

I have now seen Levon's edited question. Thanks :).

Sorry- I didn't read the whole definition. The source I'm using has that complements, unions, and countable unions are legal. The complements are with respect to some $X$ which we know in advance contains everything.

In that case, we can establish very quickly that the unit set exists: Consider the union of $A$ and the complement of $A$. This is the entire set and therefore the union of the entire collection.

Now, for the requested counterexample: Let $A$ be the $\sigma$-algebra of measurable sets in $\mathbb{R}$ and $S$ be a set of points such that no two of them differ by a rational number and every real number differs from one by a rational. The union of this collection is a non-measurable set.

But I think such an example does exist. Take the example you gave, except that we consider a larger $X$. Take $X=\mathbb C$, for example. I think it should work, but I'm not sure.

Actually, that is the right way to do it. Consider the $\sigma$-algebra generated by the one-element subsets of $\mathbb{R}$ and the entire set $\mathbb{R}^2.$ This consists of countable sets of real numbers and their complements in $\mathbb{R}^2.$ It does not contain $\mathbb{R}.$

Your previous post crossed my edits, grobber.

[quote="LevonNurbekian"]Dear [b]jmerry[/b] and [b]grobber[/b] in your definition you use the word complement in your definitions.The complements respect to which set?[/quote]

As jmerry said, complement with respect to some set $X$. Call it the "universe" of the algebra, if you like :). I've only seen definitions of a $\sigma$-algebra as being a collection of subsets of some set $X$ with those properties I listed in one of my previous posts.


I remember people talking about this on these forums but I don't know if anything was ever changed.  For example, when you use the eqnarray environment you get:

\begin{eqnarray*}
x+y &=& 10\\
y+z &=& 10\\
z+z &=& 10\\
\end{eqnarray*}

Yeah I know that's to be changed. It will be soon, but I got a lot of other stuff on my mind at this point :P Sorry ...


Source: SIMUW 2006 Application (they've finished the selection process)

I didn't get this question when I was applying:

Let $A, B,$ and $C$ of an acute triangle satisfy $A < B < C$. Prove that

$\sin^2{B}\sin{\frac{A}2}\sin{\left(A + \frac{B}2\right)} > \sin^2{A}\sin{\frac{B}2}\sin{\left(B + \frac{A}2\right)}$

I didn't either.  paladin8 says that when he expanded it out with product-to-sum formula the result was trivial, but I couldn't get it in a neat form  :(

(Got in anyway.   ;) )

I'm in their second pick  (if not everyone decides to come)

I also applied for SUMAC, and I think my application there is stronger.

But anyway, I also tried product to sum, didn't seem to help me any.

I did it like so:

$\sin^2{B} = 2\sin{B}\sin{\frac{B}{2}}\cos{\frac{B}{2}}$ (just double-angle here)

and then

$\cos{\frac{B}{2}}\sin{(A+\frac{B}{2})} = \frac{1}{2}[\sin{(A+B)}+\sin{A}]$ (product-to-sum).

Do that for both sides (with $A$ and $B$ switched of course) and we end up with

$\sin{B}\sin{\frac{B}{2}}\sin{\frac{A}{2}}[\sin{(A+B)}+\sin{A}] >$ its corresponding $A$ version.

Basically this all boils down to

$\sin{B}\sin{(A+B)} > \sin{A}\sin{(A+B)}$

which is true because $A < B < 90$ and $\sin{(A+B)} > 0$.

Not a particularly elegant inequality, but its true by a lot of computation so yeah.


algebra
function
domain
abstract algebra
calculus
integration
Ring Theory

Here we deal with modules $ M$ over an integral domain $ A$. Such a module is said to be [url=http://mathworld.wolfram.com/DivisibleModule.html]divisible[/url] if for every non-zero $ a\in A$, multiplication by $ a$ in $ M$ is onto (that is, for all $ x\in M$ we can find $ y\in M$ such that $ ay\equal{}x$). It's not difficult to show that any [url=http://en.wikipedia.org/wiki/Injective_module]injective[/url] module over an integral domain is divisible.

Prove that a module over a [url=http://en.wikipedia.org/wiki/Dedekind_domain]Dedekind domain[/url] is injective iff it is divisible. Show also that this characterizes Dedekind domains: if an integral domain has the property that all divisible modules are injective, then it must be Dedekind.

$ \Rightarrow$: let $ M$ be a divisible module over a dedekind domain $ A$. to show that $ M$ is injective, it suffices to lift homomorphisms $ f: I \to M$ to $ A \to M$, where $ I$ is an ideal of $ A$ (baer's criterion).

we may assume $ I \neq 0$. then $ I$ is invertible, say $ I*J\equal{}A$ with a fractional ideal $ J$. then we find $ a_1,...,a_n \in I$ and $ q_1,...,q_n \in J$ s.t. $ a_1 q_1 \plus{} ... \plus{} a_n q_n \equal{} 1$. since $ M$ is divisible, we find $ m_i \in M$ s.t. $ f(a_i) \equal{} a_i m_i$. now put $ m\equal{}q_1 a_1 m_1 \plus{} ... \plus{} q_n a_n m_n$. since, $ q_i a_i \in J*I\equal{}A$, we have $ m \in M$. now $ a \mapsto am$ is a homomorphism $ A \to M$, which extends $ f$: for every $ a \in I$ we have $ f(a)\equal{}f(q_1 a a_1 \plus{} ... \plus{} q_n a a_n) \equal{} q_1 a f(a_1) \plus{} ... \plus{} q_n a f(a_n)\equal{} am$.

If injective is equivalent to divisible, quotients of injective modules are injective, so the global dimension is 1. This implies that submodules of projective modules are projective, in particular, all ideals are projective. An ideal is invertible iff it is projective, so we are done. owk


calculus
integration
logarithms
LaTeX
calculus computations

It seems like should be easy, but I've spent almost 2 hours to solve this problem and the answer I got is wierd, Anyone can help?

Hmm. The integrand is non-negative, from Tonelli's theorem we have
$\int_{[1,2]\times[0,1]} \frac{x}{x^2+y^2} d\sigma = \int_1^2 \left(\int_0^1 \frac{x}{x^2+y^2}dy\right) dx
$

$\int_0^1 \frac{x}{x^2+y^2}dy = x\int_0^1 \frac{1}{x^2+y^2}dy = \left.x\cdot \frac{1}{x}\arctan\frac{y}{x}\right|_{y=0}^1 = \arctan\frac{1}{x}$

Hence the integral becomes $\int_1^2 \arctan\frac{1}{x} dx$

Integrate by part

$\int_1^2 \arctan\frac{1}{x} dx = \left.x \arctan\frac{1}{x}\right|_1^2 + \int_1^2 \frac{x}{1+x^2}dx = 2\arctan\frac{1}{2} - \frac{\pi}{4} + \left.\frac{1}{2}\ln(1+x^2)\right|_1^2 = 2\arctan\frac{1}{2} - \frac{\pi}{4}+ \frac{1}{2}\ln\frac{5}{2}$

This is the particular forum where this problem belongs. And kessie - you really should give this LaTex stuff a try. Trial and error, using the preview button many times.

If you enter the following:

(dollar)\int\int_R \frac{x}{x^2+y^2}dA(dollar) where (dollar)R=[1,2]\times[0,1](dollar)

you see the following display:

$\int\int_R \frac{x}{x^2+y^2}dA$ where $R=[1,2]\times[0,1]$


inequalities
LaTeX
inequalities unsolved

PROVE that  a inequality  is correct with all a, b, c are non negative and p = const , q= const satisfying that  p >= -2 , q <= 2 p + 1  and PROve that :
     ( a ^2  + qbc )/ ( b^ 2 + pbc + c^2 )  + ( b ^2  + qac )/ ( a^ 2 + pac + c^2 ) +( c ^2  + qba )/ ( b^ 2 + pba + a^2 ) >= 3 . ( q +1 )/ (p + 2)

o0o_nhocemma_o0o wrote
PROVE that a inequality is correct with all a, b, c are non negative and p = const , q= const satisfying that $ p\ge \minus{}2 , q\le 2p\plus{} 1$:
$ \frac{ a ^2 \plus{} qbc }{b^ 2 \plus{} pbc \plus{} c^2} \plus{} \frac{ b ^2 \plus{} qac }{ a^ 2 \plus{} pac \plus{} c^2} \plus{}\frac{c ^2 \plus{} qba }{ b^ 2 \plus{} pba \plus{} a^2}\ge 3 \frac{ q \plus{}1 }{p \plus{} 2}$
You should learn write Latex more.
And this inequality can prove by S.O.S method. :)


inequalities
function
inequalities unsolved

This might be easy for you.

Given a < b < c
and ab + bc + ca = 1
and a + b + c = 2

I'm trying to prove something. A part of it I proved.

I just need to prove that c < 4 / 3.

I tried with all inequalities I know but I can't get to c < 4 / 3.

Thank you very much.

Assume $ c>\frac{4}{3}$. Then, $ a\plus{}b< \frac{2}{3}$; also by AM-GM have $ ab\equal{}(\sqrt{ab})^2\le(\frac{a\plus{}b}{2})^2<\frac{1}{9}$.
Now, consider $ f(x)\equal{}x(2\minus{}x)$. We have $ f'(x)\equal{}2\minus{}2x$ so $ f'(x)\equal{}0$ only when $ x\equal{}1$ and $ f'(x)<0$ for $ x>1$ so the function is decreasing on $ (1,\infty)$. So, if $ c>\frac{4}{3}$ then $ c(2\minus{}c)<\frac{4}{3}(2\minus{}\frac{4}{3})\equal{}\frac{8}{9}$
Therefore, $ ab\plus{}bc\plus{}ca\equal{}ab\plus{}c(a\plus{}b)\equal{}ab\plus{}c(2\minus{}c)<\frac{1}{9}\plus{}\frac{8}{9}\equal{}1$ which contradicts the condition of the problem $ ab\plus{}bc\plus{}ca\equal{}1$.
Therefore, $ c\le \frac{4}{3}$. Note when $ a\equal{}b\equal{}\frac{1}{3},c\equal{}\frac{4}{3}$ everything is fine.
So it should be $ c\le \frac{4}{3}$ and not $ c<\frac{4}{3}$.

QED

[quote="rem"]Assume $ c > \frac {4}{3}$. Then, $ a \plus{} b < \frac {2}{3}$; also by AM-GM have $ ab \equal{} (\sqrt {ab})^2\le(\frac {a \plus{} b}{2})^2 < \frac {1}{9}$.
Now, consider $ f(x) \equal{} x(2 \minus{} x)$. We have $ f'(x) \equal{} 2 \minus{} 2x$ so $ f'(x) \equal{} 0$ only when $ x \equal{} 1$ and $ f'(x) < 0$ for $ x > 1$ so the function is decreasing on $ (1,\infty)$. So, if $ c > \frac {4}{3}$ then $ c(2 \minus{} c) < \frac {4}{3}(2 \minus{} \frac {4}{3}) \equal{} \frac {8}{9}$
Therefore, $ ab \plus{} bc \plus{} ca \equal{} ab \plus{} c(a \plus{} b) \equal{} ab \plus{} c(2 \minus{} c) < \frac {1}{9} \plus{} \frac {8}{9} \equal{} 1$ which contradicts the condition of the problem $ ab \plus{} bc \plus{} ca \equal{} 1$.
Therefore, $ c\le \frac {4}{3}$. Note when $ a \equal{} b \equal{} \frac {1}{3},c \equal{} \frac {4}{3}$ everything is fine.
So it should be $ c\le \frac {4}{3}$ and not $ c < \frac {4}{3}$.

QED[/quote]

Ok, thanks!

Well in the problem given it does not say the equal sign.

But thanks for the quick answer.

i think it's easy.
we have $ ab\equal{}(c\minus{}1)^2,a\plus{}b\equal{}2\minus{}c$,so apply this inequality $ (a\plus{}b)^2\geq 4ab$ we have $ (2\minus{}c)^2\geq4(c\minus{}1)^2$
$ \Rightarrow 0\leq c\leq\frac{4}{3}$


solve the equation :

1+q^2+...+q^n=p^m

that p,q are prime & m,n are positive integers.

I had solved that [b]n+1 [/b]is prime & some relations between q,m,n,p but not anything more.[/b]

I see that you meant solve the equation:
\[ 1+q+q^{2}+...+q^{n}=p^{m}\]
where $ p,q$ are prime and $ m,n$ are positive integers.

Note that this is a generalization of the conjecture that there are an infinite amount of Mersenne primes.  Indeed, the case $ m=1$ and $ q=2$ is open.  Now, my question is the following:

Is this still an open problem for $ m>1$ when $ q=2$ (that is when we exclude the case $ p$ is a Mersenne prime)?

[quote="hph"]$ 1+q+...+q^{n}=q^{n+1}-1=p^{m}$ [/quote]
Not quite, $ 1+q+...+q^{n}=\frac{q^{n+1}-1}{q-1}=p^{m}$

P.S.  Use dollars signs around math notation, for example: [code]$1+q+...+q^{n}=2$[/code]
and welcome to the forum!


As I was searching for "Yue Yang", one Argentinian gold medalist, I found that "Yue Yang" and "Yu Yang" were the same people (in this page: http://www.imo.org.yu/index.php?options=gl|imotres&p=02mL13&imetakm=Yu,%20Yang). Copy the link if you want to open the page.

Well, the thing is that "Yu Yang" got 41 points in 1989, representing China. Then "Yue Yang"  got 15 points (bronze) in 2002, 20 (silver) in 2003 and 34 (gold) in 2005, representing Argentina.

Well, the thing is I don't think they're the same people, but I do know that "Yue Yang", who represented Argentina, was born in China... Is this page wrong, isn't it???????

That's  quite interesting but obviously impossible. Because of the age limit, this guy had to be at most 4 yrs old when he was writing IMO in 1989. :lol:

True. I didn't thought about it, thanks. However, they could be relatives... does anyone know??? Maybe some Chinese MathLinker...

Given that many words in Chinese have the exact same Latin phonetic spelling...I doubt it. It's more likely to be coincidence I would say.

Yang is one of the most common family name in China, while Yue and Yu are the most often-used first name in China. So you can't say that they are relatives just by looking at their names. It's just like there is no connection between the English Prime Minister Chamberlin and the basketball star Chamberlin.

Hey,I know YU Yang,because he's from my high school.And his family name is YU,that's the habit of us.


Thank you very much.  Now, the solution:
   Use the identities (a+b+c)^3=sum a^3+3sum a^2(b+c)+6abc
                            (a+b+c)(a^2+b^2+c^2)=sum a^3+ sum a^2(b+c).
  The inequality becomes 3* sum a^3+ 3*sum a^2(b+c)+6abc+2 sum a^2*sqrt(sum a^2)>4 sum a^3+4 sum a^2(b+c), or (a+b+c)*(a^2+b^2+c^2)<6abc+2*(sum a^2)^3/2. But 2*(sum a^2)^3/2>=2(a^2+b^2+c^2)(a+b+c)/sqrt(3)>(a+b+c)(a^2+b^2+c^2).


1) $ f_1(x)\equal{}x^2\plus{}x$ and $ g_1(x)\equal{}x\minus{}2$
2) $ f_2(x)\equal{}2x^2\minus{}x$ and $ g_2(x)\equal{}2x$
3) $ f_3(x)\equal{}x^2\plus{}x$ and $ g_3(x)\equal{}x\plus{}2$

Addition, substraction, and multiplication defined on functions are allowed operations. For $ i \in \{1,2,3\}$, if we get $ h(x)\equal{}x$ from $ f_i$ and $ g_i$ by using allowed operations, we label $ F_i\equal{}1$, otherwise $ F_i\equal{}0$. What is $ (F_1,F_2,F_3)$?

A) $ (0,0,0)$ B) $ (0,0,1)$ C) $ (0,1,0)$ D) $ (0,1,1)$ E) None

[hide][1] take either $ x \equal{} 2, \minus{} 1$ and its impossible to write $ h \equal{} 2, \minus{} 1$ as a combination of $ (f_1,g_1) \equal{} (6,0),(0, \minus{} 3)$ respectively; [2], if we take $ x \equal{} 1/2$, we have to express a combination of $ f_2 \equal{} 0$ and $ g_2 \equal{} 1$ as the non-integer $ h \equal{} 1/2$, contradiction;  [3] is $ h \equal{} g_3^2 \minus{} f_3 \minus{} 2g_3$. Hence $ \textbf{(B)}$. [/hide]


Solve equation:
$ (3\plus{}2\sqrt{2})^x\equal{}(\sqrt{2}\minus{}1)^x\plus{}1$

Let $ X\equal{}(\sqrt{2}\minus{}1)^x$, we have $ X^3\plus{}X^2\minus{}1\equal{}0.$

[quote="NguyenDungTN"]Solve equation:
$ (3 \plus{} 2\sqrt {2})^x \equal{} (\sqrt {2} \minus{} 1)^x \plus{} 1$[/quote]

$ (3\plus{}2\sqrt2)^x \equal{} (\sqrt{2} \plus{} 1)^{2x} \equal{} (\sqrt {2} \minus{} 1)^x \plus{} 1$

Now if $ X \equal{} (\sqrt{2} \plus{} 1)^x$
$ X^2 \equal{} \frac1{X} \plus{} 1$

But is solving the resulting cubic easy?? I doubt :(


Let $ A\subseteq [0,1]$ measurable set, such that $ \lambda(A) > 0$. Prove that there exist $ t_1,t_2\in A$ such that $ t_1 \minus{} t _ 2$ is rational.

This follows from [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=173156]another problem you posted[/url].

We observe sets $ A\plus{}q_i,i\in\mathbb{N}$, where $ [0,1]\cap \mathbb{Q}\equal{}\{q_1,q_2,\dots \}$, then $ A\plus{}q_i\subseteq [0,2]$, If sets $ A\plus{}q_i$ where to be disjoint , then we would have $ \sum_{i\in\mathbb{N}}\lambda (A)\equal{}\sum_{i\in\mathbb{N}}\lambda (A\plus{}q_i)\leq \lambda ([0,2])\equal{}2$ , which is possible only if $ \lambda (A)\equal{}0$.

I have different solution for other problem.

It's been discussed many times that $ A\minus{}A$ contains a ball around zero, which is certainly enough for the conclusion.


Hi all, I have a problem related to probability.  I'm not sure if it's appropriate to post here.

Suppose there's a string of information of size 2n + 2.
The first bit checks the even parity of the first n information bits, the second bit checks the even parity o the second n information bits.
Find the probability of error detection failure in terms of probability of successful error-detection o single parity check code.

Any hint would be helpful
Thanks!

There isn't a better place for probability in the college forums, so here is fine.

You essentially have two error-detecting codes stuck together; you will detect an error (and not know how to fix it) if either of those subcodes detects an error. You'll get a false negative if at least one subcode has a false negative, and the other doesn't detect an error. Since the two subcodes are independent,  this is enough information to find the probability you're looking for if you can find the probabilities of an error detection and of any error for a subcode.

what's a false negative? is that when you detect an error but there shouldn't be?

and a false positive? when there are 2 errors and the code couldn't detect?

if both subcodes detect errors, would the whole string detect false negative since it's even parity check?

Isn't the Probability of finding out error detection failure the same as probability of undetectable changes such as even # of bits flipped?

thanks!

I don't know all the jargon you're using, so I substituted something I thought was more understandable. In particular: what's an "error detection failure"?

I shouldn't use "false positive"- that was a mistake, as we are guaranteed to have an error if we detect one.
The whole point of having two check bits is so that we can test each independently.

probability of error detection failure is the probability when there's an error and you fail to detect (by changing even numbers of bits).  There's no way to detect from the parity bit if for example 2 bits were flipped.

So is the probability of 1 subcode fail to detect erorrs the same as the probability of the whole frame failing to detect an error?

No. That probability is not enough information; you also need to know the probability of a detected error or the probability that everything works. An error occurs and no error is detected when one subcode has an undetected error and the other detects no error. There are three ways for this to happen; find the probabilities and add them up.


$ a_1,a_2,a_3,a_4$ are four positive numbers such that $ \sum_{1\leq i < j\leq4}a_ia_j \equal{} 1$

show that $ a_1 \plus{} a_2 \plus{} a_3 \plus{} a_4\geq\sqrt {2 \plus{} \sqrt {\frac {1}{3} \plus{} 4a_1a_2a_3a_4}}$


function
calculus
derivative
real analysis
calculus computations

64.  Suppose that $ f$ is a continuous real-valued function defined on the closed interval $ [0,1]$.  Which of the following must be true?

I.  There is a constant $ C > 0$ such that $ |f(x)\minus{}f(y)| \le C$ for all $ x$ and $ y$ in $ [0,1]$.

II.  There is a constant $ D > 0$ such that $ |f(x)\minus{}f(y)| \le 1$ for all $ x$ and $ y$ in $ [0,1]$ that satisfy $ |x\minus{}y| \le D$.

III.  There is a constant $ E > 0$ such that $ |f(x)\minus{}f(y)| \le E|x\minus{}y|$ for all $ x$ and $ y$ in $ [0,1]$.

My thoughts:

Since $ f$ is continuous, $ f$ is bounded on a closed interval.  So I is definitely true.

II is pretty much the definition of continuity.  So that's true.

III is the one I am puzzled about.  The way I am interpreting it is that the derivative is bounded on the interval -- which seems to be true.  I think my interpretation is wrong though.

Not to be a stickler, but II is true because continuous functions are [b]uniformly[/b] continuous on a closed interval.

III is a Lipschitz condition. So the question is, must a continuous - even uniformly continuous - function satisfy a Lipschitz condition? It is clearly true that a Lipschitz function must be uniformly continuous, but what about the converse?

[hide="Answer."] False. Example: $ f(x)\equal{}\sqrt{x}$ on $ [0,1].$[/hide]


Four horizontal lines and four vertical lines are drawn in a plane. In how many ways can four lines be chosen such that a rectangular region is enclosed?

Well, there are $ \binom{4}{2}$ ways to choose $ 2$ vertical lines and $ \binom{4}{2}$ ways to choose $ 2$ horizontal lines so the answer is $ 6 \times 6$, or $ \boxed{36}$.

[hide=my solution???]you can draw 4 vertical lines and 4 horizontal lines, then you can see that they enclose a 3-by-3 grid of squares. We now need to count the number of rectangles formed by this 3-by-3 grid.We could use casework, or combinations for the left-right sides and top-bottom sides to get $6\cdot 6=\boxed{36}$

[hide=Bashy solution]Graph it out and count the rectangles[/hide]

How did you get 4 choose 2 ways to choose 2 vertical lines and 4 choose 2 ways to choose 2 horizontal lines?


inequalities
floor function
number theory proposed
number theory

For each positive integer $ m$ let $ q_m$ be the product of the primes not greater than $ m$ and let $ c_m$ be the number of distinct primes dividing $ m$.

Determine all positive integers $ n$ such that \[ \sum_{k\in\mathbb{Z}^\plus{}}{\sum_{\begin{array}{c} d|q_n\\ c_d\equal{}k\end{array}}{(\minus{}1)^k\frac{n}{d}}}\] is less than or equal to \[ \sum_{k\in\mathbb{Z}^\plus{}}{\sum_{\begin{array}{c} d|q_n\\ c_d\equal{}k\end{array}}{(\minus{}1)^k\left\lfloor\frac{n}{d}\right\rfloor}}\]

:)

[hide="edited"]Today I am not so lazy as I was yesterday when originally post the problem so today's statement is probably nicer.[/hide]

Well, the answer is [hide]n=1, 2, 3[/hide].

:)

[quote="ElChapin"]Well, the answer is n=1, 2, 3[/quote]
Prove, please!

Ok, The Nguyen, here I left my proof.

[hide="Proof"]Let $A_n$ and $B_n$ be the first and second numbers, respectivley, for each $n$. We have $A_1=B_1$, we'll prove that $A_n\ge B_n$ for $n\ge 2$ with equality at $n=2$ and $n=3$. Note that
\[A_n+n=\sum_{d|q_n}{\left((-1)^{c_d}\frac{n}{d}\right)}=n\prod_{p|q_n}{\left(1-\frac{1}{p}\right)}\]
and, by the cross classification principle
\[B_n+n=\sum_{d|q_n}{\left((-1)^{c_d}\lfloor\frac{n}{d}\rfloor\right)}=1\] since $B_n+n$ counts how many postive integers not greater than $n$ have no prime factor. So we need to prove that
\[n\prod_{p|q_n}{\left(1-\frac{1}{p}\right)}\ge 1\]
This follows from (note that we need $n\ge 2$ at the middle but it magically works for $n=1$ at the end)
\[n\prod_{p|q_n}{\left(1-\frac{1}{p}\right)}=n\prod_{k=1}^{\pi(n)}{\left(1-\frac{1}{p_k}\right)}\ge n\prod_{k=1}^{\pi(n)}{\left(1-\frac{1}{k+1}\right)}=\frac{n}{\pi(n)+1}\ge 1\]
(note that we need $n\ge 2$ at the middle but it magically works for $n=1$ at the end) Where $p_k$ is the $k$-th prime and $\pi(n)$ is the number of primes not greater than $n$. There, we used the inequalities $p_k\ge k+1$ and $n\ge \pi(n)+1$, which attain equality only for $k=2, 3$ and $n=1, 2, 3$ respectively. This finishes the proof.[/hide]

:)


slove this equation:

$ \sqrt[4]{x}\plus{}\sqrt[4]{2x\minus{}1}\equal{}\sqrt[4]{\frac{4x\minus{}1}{3}}\plus{}\sqrt[4]{\frac{5x\minus{}2}{3}}$

[quote="thanhnam2902"]solve this equation:

$ \sqrt [4]{x} \plus{} \sqrt [4]{2x \minus{} 1} \equal{} \sqrt [4]{\frac {4x \minus{} 1}{3}} \plus{} \sqrt [4]{\frac {5x \minus{} 2}{3}}$[/quote]

Is it true that the only real solution to $ n \ge 2$
$ \sqrt [n]{1\plus{}x} \plus{} \sqrt [n]{1\plus{}x\plus{}y} \equal{} \sqrt [n]{1\plus{}x\plus{}k} \plus{} \sqrt [n]{1\plus{}x\plus{}y\minus{}k}$
is for $ x\equal{}y\equal{}k\equal{}0$ ?

This solution can be done by way:
$ \bullet$ $ \frac {\sqrt [4]{a} \plus{} \sqrt [4]{b}}{2} \le \sqrt {\frac {\sqrt {a} \plus{} \sqrt {b}}{2}} \le \sqrt [4]{\frac {a \plus{} b}{2}}$

$ \Longrightarrow$ $ \frac {\sqrt [4]{a} \plus{} \sqrt [4]{b} \plus{} \sqrt [4]{c}}{3} \le \sqrt [4]{\frac {a \plus{} b \plus{} c}{3}}$, (1).

$ \bullet$ Aply (1) $ \Longrightarrow \sqrt [4]{a} \plus{} \sqrt [4]{b} \plus{} \sqrt [4]{c}\le \sqrt [4]{\frac {a \plus{} 2b}{3}} \plus{} \sqrt [4]{\frac {b \plus{} 2c}{3}} \plus{} \sqrt [4]{\frac {c \plus{} 2a}{3}}$, (2)

$ \bullet$ Aply (2) $ \Longrightarrow \sqrt [4]{x} \plus{} \sqrt [4]{x} \plus{} \sqrt [4]{2x \minus{} 1}\le \sqrt [4]{x} \plus{} \sqrt [4]{\frac {5x \minus{} 2}{3}} \plus{} \sqrt [4]{\frac {4x \minus{} 1}{3}}$ $ \Longleftrightarrow \sqrt [4]{x} \plus{} \sqrt [4]{2x \minus{} 1} \le \sqrt [4]{\frac {4x \minus{} 1}{3}} \plus{} \sqrt [4]{\frac {5x \minus{} 2}{3}}$

$ \Longleftrightarrow x \equal{} 2x \minus{} 1 \Longleftrightarrow x \equal{} 1$.

-------------------------------------------------------------
My school site is http://www.chuyenquangtrung.com.vn

[quote="thanhnam2902"]This is my solution, but it's long and difficult. Who can done it by other way?[/quote]

I wouldn't call that long and difficult.  Not exactly easy to see at first, but very well done.  If I'm interpreting this right, you are using the power-mean inequality on fourth roots instead of regular variables?  So then, for two different power means of the same sets to be equal, the individual pieces of the set must be equal.

My only question: how exactly do you justify equation 2?  I think it is correct, but can't quite see why it works.

Yes. I tried to done it. But I can't find other solution.


Pat wants to buy four donuts from an ample supply of three types of donuts: glazed, chocolate, and powdered. How many different selections are possible?

$ \textbf{(A)}\ 6 \qquad \textbf{(B)}\ 9 \qquad \textbf{(C)}\ 12 \qquad \textbf{(D)}\ 15 \qquad \textbf{(E)}\ 18$

[hide] Let the donuts be represented by Os. We wish to find all combinations of glazed, chocolate, and powdered donuts that give us 4 in all. The six donuts we want can be represented as OOOO. Notice that we can add two "dividers" to divide the group of donuts into three different kinds; the first will be glazed, second will be chocolate, and the third will be powdered. For example, O|OO|O represents one glazed, two chocolate, and one powdered. We have six objects in all, and we wish to turn two into dividers, which can be done in $ \binom{6}{2}\equal{}15$ ways. Our answer is hence $ \boxed{\text{(D)}15}$. Notice that this can be generalized to get the balls and urn identity.[/hide]

Let's look at this using casework:
There are three possible ways of picking donuts
$*$ all four are the same kind, such as picking $4$ glazed donuts
$*$ there are exactly $2$ of each kind, such as picking $2$ glazed donuts and $2$ chocolate donuts
$*$ there are exactly $3$ kinds, such as picking $1$ glazed, $2$ chocolate, and $1$ powdered
$*$ there are $2$ kinds with $1$ donut of one kind and $3$ donuts of the other kind, such as picking $3$ glazed and $1$ chocolate

$G = $ glazed, $P = $ powdered, $C = $ chocolate
For the first case, there are $3$ possible combinations: $GGGG$, $PPPP$, and $CCCC$
For the second case, there are $3$ different combinations: $GGPP$, $GGCC$, and $CCPP$
For the third case, there are $3$ possibilities: $PPGC$, $GGCP$, $CCGP$
For the fourth case, there are $6$ possibilities: $PPPG$, $PPPC$, $GGGP$, $GGGC$, $CCCP$, $CCCG$

The total number of ways is therefore, $3 + 3 + 3 + 6 = \boxed{\textbf{(D)}\ 15}$

[hide=Solution]By a formula whose name I forgot, we have $\dbinom{4+3-1}{3-1}=\boxed{\textbf{(D)}~15}$ selections possible.[/hide]

Am I seriously looking at #19 on an AMC10???

Um this would literally be a problem 2 on a modern amc 10
[hide=Solution]By Stars and Bars,
$$\binom{4+3-1}{3-1}=\binom{6}{2}=\boxed{15}$$


rotation
geometry
geometric transformation
reflection

[quote="236factorial"]I notice that given a graph on a piece of paper, if you rotate it clockwise 90 degrees, flip the paper over, and look at it while facing a light, you will see the inverse of the function. Is this true, and if so, why?[/quote]

I think because when you look on the other side you see the reflection over the y-axis, and then the rotation does the rotation of the graph thing. The inverse is supposed to be the reflection of the graph over the line y=x so it makes sense...sort of

What an excellent topic brought up by 236factorial!

Good job 236factorial, below is a bigger result that you can prove in advanced geometry:

Any euclidean rotation is a composition of two euclidean reflections.

:)

So, instead, if you reflected in line y=x and then flip over, you obtain the 90 degrees counterclockwise rotation.

PS: 236factorial, it is not clockwise, it is counterclockwise.
PSS: The result above can be shown extremely easy if you use affine transformations but this is a topic too hard for Getting Started forum.

Well, this depends on how you flip the paper over.
With a 90 degree clockwise rotation, it is flipped on the horizontal axis.
With a 90 degree counterclockwise rotation, it should be flipped along the vertical axis.


When all possible diagonals are drawn from one vertex of a 50-sided polygon, how many triangles are formed?

Every diagonal makes a new triangle, and there are 47 diagonals from that vertex.
However, the last diagonal splits a quadrilateral into 2 triangles, so one extra is made.

This means that $ 48$ triangles are formed.

[asy]size(250);
void kn(int n) {
pair[] points;
for(int i=0; i<n; ++i) {
points[i]=dir(360.0/n*i);
}

for(int i=0; i<n; ++i) {
draw(points[0]--points[i]);
}
}
kn(50);
draw(polygon(50));[/asy]

It should look like this. The polygon looks more like a circle. You can count out the triangles if you want.


inequalities
LaTeX
inequalities proposed

Jeane,this one is trivial.Just use Cauchy-Schwarz in the well known form and then apply the inequality:

                             $x^{n}+y^{n}\geq\frac{(x+y)^n}{2^{n-1} }$ ;)

 Hope I'm not doing any stupid mistakes. ;)

[quote="jianuovidiu"]Let $n \in {\mathbb N}^*$ and $a,b>0$ such that $a+b \geq 1$. Prove $\frac{a^{2n}}{b} + \frac{b^{2n}}{a} \geq 4^{1-n}$.

 :ninja:[/quote]

       $\frac{a^{2n}}{b}+\frac{b^{2n}}{a}\geq\frac{a^{n}+b^{n}}^2}{a+b}$ ;)

   Jeane,It's 4 in the morning.can you please remediate my Latex formula?
    I'm falling asleep.


If $ f(x,y,z) \equal{} x^2 \minus{} 4y^2 \plus{} 2z^2 \minus{} 3xy \plus{} 4yz \plus{} 2y \minus{} 3z$ find the stationary points.

So $ \nabla f \equal{} (2x\minus{}3y, \minus{}8y\minus{}3x\plus{}4z\plus{}2, 4z\plus{}4y\minus{}3)$. Then set this equal to $ 0$.

So $ 2x\minus{}3y \equal{} 0 \implies y \equal{} \frac{2}{3} x$

$ \minus{}8y\minus{}3x\plus{}4z\plus{}2 \equal{} 0 \implies 8y \equal{} \minus{}3x\plus{}4z\plus{}2$

$ 4z\plus{}4y\minus{}3 \equal{} 0 \implies 4y \equal{} 3\minus{}4z$

Now what?

You now have three equations in three unknowns so you try to solve them.  Plug one equation into another, solve it, then plug that into your third equation and solve, and then you can solve for your other two.

but there are no points for which this is true.

There is exactly one point, as is typical for systems of $ n$ linear equations in $ n$ variables. You've made a mistake in calculation.


Iparxei sinartisi f:R->R me tin idiotita oti f(A)=R gia kathe diastima A ?

Didali gia kathe diastima A kai kathe pragmatiko arithmo x iparxei arithmos y sto A oste f(y)=x.

Stergios

[quote="Anto"]Iparxei sinartisi f:R->R me tin idiotita oti f(A)=R gia kathe diastima A ?[/quote]

Just perfect :) Να δώσω ένα hint (ελπίζω σωστό...):
[hide]
Έστω η $ f(x) \equal{} \frac{1}{\sqrt{x}}\minus{}1$ αν $ x\in(0,1]$ και $ 0$ άλλως.

Προσπαθείστε πάνω σε κάθε ρητό να τοποθετήσετε ένα πολλαπλάσιο αυτής της συνάρτησης, με τέτοιο τρόπο ώστε στο τέλος να προκύπτει κάτι καλό :)
[/hide]

Cheerio,

Durandal 1707

Το hint του Παναγιώτη για ρητούς με οδήγησε σε μία άλλη προσέγγιση δυστυχώς non-elementary .
Ελπίζω να δουλεύει :
[hide]Let $ H \equal{} (h_i)_{i\in A}\cup\{1\}$ η hamel basis του $ R$ επί του $ Q$ . Για κάθε $ x$ γράφουμε $ x \equal{} r_1 \plus{} r_2a_i$ όπου $ r_1,r_2$ ρητοί αριθμοί . Επιλέγουμε $ f(1) \equal{} 0$ και $ f(r) \equal{} 0$ για κάθε ρητό $ r$ και επιπλέον δίνουμε στην $ f$ την προσθετική ιδιότητα .
Τέλος θεωρούμε μία 1-1 και επί αντισοιχία $ g$ από το  $ H\setminus\{1\}$ σto $ R$ και ορίζουμε $ f(x) \equal{} g(x)$ για κάθε $ x\in H\setminus\{1\}$ . Εύκολα μπορούμε να δούμε ότι η συνάρτηση αυτή έχει τις ζητούμενες ιδιότητες .[/hide]

Poli oraia Silouane ! Bravo !

Tin lisi sou den tha tin elega non-elementary. To mono pou xreiazese einai to limma tou Zorn (i to axioma epilogis) gia na apodeikseis tin iparxi basis tou R epi tou Q.

Mporei kaneis na skeftei mia kataskeuastiki apodeiksi ?

Thanks Stergio . Mipos i apantisi stin parakato erotisi einai :
[quote="Anto"]
Mporei kaneis na skeftei mia kataskeuastiki apodeiksi ?[/quote]

[hide]Καταμέτριση 0 και 1 στην decimal representation ?[/hide]

Iparxei mia kataskeui se auto to styl ;-)

Stergios

Θα δώσω και μια άλλη λύση η οποία χρησιμοποιεί μια πολύ σημαντική μεθοδο η όποια ονομαζεται `Just do it'. Ο τρόπος που χρησιμοποιείται αυτή η μέθοδος είναι ο εξής: Θέλουμε να φτιάξουμε μια συνάρτηση (ή ενα σύνολο, ή μια ακολουθία, ή ...) η οποία να ικανοποίει ορίσμενες συνθήκες. Αυτό που κάνουμε είναι να βάλουμε τις συνθήκες σε κάποια σειρά και να τις ικανοποιούμε μία προς μία με τέτοιο τρόπο ώστε στο τέλος να έχουμε ικανοποιήσει όλες τις συνθήκες.

Δυστυχώς σε αυτό το παράδειγμα θα χρειαστώ να χρησιμοποιήσω αριθμησιμότητα και transfinite induction (απολογούμαι για την αγγλική ορολογία, αν κάποιος γνωρίζει την αντίστοιχη ελληνική ας μου την πει). Ίσως επανέλθω σε άλλο post με πιο απλές χρήσεις αυτής της μεθόδου. (Έχω πρόσεξει μερικές ασκήσεις ΙΜΟ που θα μπορούσαν να λυθούν με αυτή την μέθοδο.)

Το πρώτο βήμα είνα να δώσω μια νέα διάταξη <' στο R με την εξής ιδιότητα: Για κάθε υποσύνολο A του R, υπάρχει x στο A έτσι ώστε x <' y για κάθε y=/= x που ανήκει στο A. (Αυτή είναι μια από τις πιο γνωστές εφαρμόγες του αξιώματος της επιλογής και θα τη θεωρήσω δεδομένη.)

Αρχίζουμε:

Από την πιο πάνω ιδιότητα το R έχει κάποιο ελάχιστο στοιχείο x_1. Θα ορίσουμε σε κάποιες τίμες την f έτσι ώστε να παίρνει το x_1 σε κάθε διάστημα. Αρκέι μόνο να κοιτάξουμε τα διαστήματα της μορφής (p,q) όπου τα p και τα q είνα ρητοί. Είναι αριθμήσιμα αυτά τα διαστήματα άρα έχουμε ορίσει την f σε αριθμήσιμο αριθμό σημείων μέχρι στιγμής.

Συνεχιζουμε:

Από την πιο πάνω ιδιότητα το R-{x_1} έχει κάποιο ελάχιστο στοιχείο x_2. Θα ορίσουμε σε κάποιες τίμες την f έτσι ώστε να παίρνει το x_2 σε κάθε διάστημα. Μπορούμε να το κάνουμε αυτό; Ναι διότι μέχρι στιγμής η f έχει οριστεί σε αριθμήσιμο αριθμό σημείων ενώ κάθε διάστημα έχει μή αριθμήσιμο αριθμό σημείων (Cantor).

Συνεχίζουμε "επαγωγικά". Κάποιος που γνωρίζει από transfinite induction μπορεί εύκολα να τελειώσει την απόδειξη (χρείαζεται μια ακόμη ιδιότητα της <' που δεν έχω γράψει) γι'αυτό θα παραλείψω την συνέχεια. Αν δεν έχετε δει transinite induction τότε απλώς πιστέψτε με πως η διάταξη <' όντως μου επιτρέπει να σύνεχίσω επαγωγικά όπως θα έκανα αν δούλευα στους φυσικούς αριθμούς και όχι στους πραγματικούς.

Ελπίζω η μεθοδολογία να έχει γίνει κατανοητή έστω και αν το παράδειγμα θέλει γνώσεις που ενδεχομένως να μην έχετε.

Poli oraia  :)

Nomizo oti itan poli kali idea na anefertheis stin methodo 'just do it' ! Opoios thelei mporei episeis na riksei mia matia sta site : http://www.dpmms.cam.ac.uk/~wtg10/justdoit.html (to site tou Gowers periexei poli endiaferon iliko genikotera) kai http://gowers.wordpress.com/2008/08/16/just-do-it-proofs/

Stergios

[quote="Anto"]Eisai sigouros oti auti i methodos mporei na doulepsei ?  Perimene ligo kairo mipos thelei kaneis na asxolithei kai istera grapse tin proseggisi sou.

Stergios[/quote]

Guys, να γράψω κι εγώ τη δική μου προσέγγιση μιας και έχει λυθεί η άσκηση. O Στέργιος σωστά το μυρίστηκε ότι είναι προβληματική και δυστυχώς δεν έχω προλάβει να ασχοληθώ άλλο μαζί της... οπότε την κάνω post μήπως σώζεται...

Λοιπόν, έστω $ r_n$ μία απαρίθμηση των ρητών και έστω η συνάρτηση $ f$ με $ f(x) \equal{} \frac {1}{\sqrt {x}} \minus{} 1$ αν $ x\in (0,1)$, $ f(x) \equal{} 0$ άλλως.

Τότε, ας θεωρήσουμε τη συνάρτηση $ g(x) \equal{} \sum_{n \equal{} 1}^\infty ( \minus{} 2)^{ \minus{} n} f(x \minus{} r_n)$.

Θα έχουμε $ \left|\int_{ \minus{} \infty}^\infty g(x)\, dx \right| \leq \int_{ \minus{} \infty}^\infty |g| \leq\ldots\leq\sum_{n \equal{} 1}^\infty 2^{ \minus{} n} \equal{} 1$ (σε ό,τι αφορά τεχνικές λεπτομέρειες, η μονότονη σύγκλιση είναι που μας επιτρέπει να ενάλλαξουμε ολοκλήρωση και άθροιση). Συνεπώς, η $ g$ θα πρέπει να είναι ολοκληρώσιμη και άρα πεπερασμένη σε όλο το $ \mathbb{R}$ εκτός από ένα σύνολο μέτρου $ 0$. Σε αυτό το σύνολο μπορούμε να επαναορίσουμε την $ g$ όπως θέλουμε οπότε και μας προκύπτει μία καινούρια συνάρτηση $ g_0: \mathbb{R}\to\mathbb{R}$.

Η $ g_0$ απειρίζεται σε κάθε ρητό και, επειδή δεν μπορούν να απαριθμηθούν οι ρητοί με μονότονο τρόπο, έπεται ότι σε οποιαδήποτε περιοχή γύρω από κάθε $ x\in \mathbb{R}$, η $ g_0$ θα απειρίζεται και θετικά και αρνητικά, δηλ. δεν είναι φραγμένη σε κανένα διάστημα.

Σε αυτό το σημείο επαναπαύθηκα και πίστευα ότι λόγω της μορφής της $ g_0$ είχε λυθεί το πρόβλημα αλλά αυτό σίγουρα δεν είναι προφανές (η $ g$ δεν είναι ακριβώς συνεχής :P) και δεν ξέρω αν είναι καν σωστό (ότι δηλαδή είναι επί του $ \mathbb{R}$ σε κάθε διάστημα).

Για να πω την αλήθεια, συμμερίζομαι τις αμφιβολίες του Στέργιου για το κατά πόσο δουλεύει αυτή η προσέγγιση αλλά, anyway, αυτό ήταν που είχα στο μυαλό μου... you're more than welcome to fix it or to kill it :)

Anto, thx για το πολύ ωραίο πρόβλημα, δεν το είχα ξαναδεί! Επίσης παιδιά, sorry αν παραπλάνησα κανένα με λάθος hint, είχα βιαστεί πολύ στο πρώτο post :(

@Silouan,Demetres: decimal counting and "just do it" for the win! Well done, I say!!! :thumbup:  :clap2:

Cheerio,

Durandal 1707

Πριν πέσω για ύπνο χτες σκέφτηκα μία ακόμα κατασκευή... τώρα, αν δουλέυει, άλλου παπά ευαγγέλιο :)

Συστατικά:
1. Το [url=http://en.wikipedia.org/wiki/Cantor_set]σύνολο Cantor[/url] $ C$.
2. Μία επί απεικόνιση $ \phi: C\to (0,1)$ (π.χ. αλλάξτε βάση αναπαράστασης τον αριθμών από 3 σε 2 ή κοιτάξτε το αρθράκι της Wikipedia).
3. Η αγαπημένη σας επί απεικόνιση $ f: (0,1)\to\mathbb{R}$ (π.χ. κάποια $ \tan$).

Εκτέλεση:

1. Πάρτε το σύνολο Cantor βασισμένο στο $ [0,1]$ και θεωρείστε την [i]επί[/i] απεικόνιση $ g_1: [0,1]\to\mathbb{R}$ όπου $ g_1 \equal{} \phi\circ f: C\to\mathbb{R}$ στο σύνολο Cantor και $ 0$ έξω από αυτό.

2. Πηγαίνετε στη μεγαλύτερη "τρύπα" του C (δηλ. το διάστημα $ (1/3,2/3)$), προσαρμόστε εκεί ένα νέο σύνολο Cantor με συνολικό μήκος $ \frac {1}{3}$ και θεωρείστε την ίδια σύνθεση συναρτήσεων με παραπάνω, μόνο να είναι scaled down κατά $ 1/3$ (επίσης, πετάξτε έξω τα άκρα $ 1/3,2/3$ αφού αυτά τα έχουμε ήδη βάλει στο παιχνίδι). Ονομάστε τη καινούρια [i]επί[/i] συνάρτηση $ g_2$.

3. Πηγαίνετε στις τρύπες με μήκος $ \frac {1}{9}$ (δύο από το αρχικό Cantor και μία από το προηγούμενο) και κάντε την ίδια δουλειά για να πάρετε μία συνάρτηση $ g_3$ που να είναι $ 0$ εκτός από το $ (1/9,2/9)\cup(4/9,5/9)\cup(7/9,8/9)$ και να είναι επί σε κάθε ένα από αυτά τα διαστήματα.

4... Proceed ad infinitum.

Αν δεν κάνω λάθος, η συνάρτηση $ g \equal{} \sum_{n \equal{} 1}^\infty g_n$ έχει τη ζητούμενη ιδιότητα στο $ (0,1)$ επειδή κάθε υποδιάστημα του $ (0,1)$ θα περιέχει κάποιο αντίγραφο του Cantor (ένας τρόπος για να πεισθείτε είναι να δείτε ότι αυτό ισχύει για οποιοδήποτε διάστημα μήκους π.χ. $ \geq 1/9$ και να χρησιμοοποιήσετε την αυτοομοιότητα του Cantor ώστε να μη χρειαστεί να σκεφτείτε μικρότερα διαστήματα).

Copy-paste σε κάθε διάστημα $ [n,n \plus{} 1]$ του $ \mathbb{R}$... eh voila :)

Remarks: αν δουλεύει η παραπάνω προσέγγιση, τότε η συνάρτηση μας έχει το ενδιαφέρον χαρακτηριστικό ότι είναι 0 σχεδόν παντού!  :o  Επίσης, νομίζω ότι γλυτώνει το αξίωμα επιλογής (αφού η $ \phi: C\to(0,1)$ νομίζω ότι δε χρειάζεται choice).

Cheerio,

Durandal 1707

Πολύ ωραία κατασκευή. Αν δεν έχω κάνει λάθος, η g που μας περιέγραψες οριζεται ως εξής:

Γράφουμε το $ x \equal{} 0.x_1 x_2 x_3 \ldots$ σε τριαδική μορφή. Αν k είναι μέγιστο ώστε $ x_k \equal{} 1$ τότε $ g(x): \equal{} \phi(10^k x \minus{} [10^k x])$. Άν δεν υπάρχει τέτοιο k, τότε $ g(x): \equal{} 0$.

Από αυτόν τον ορισμό φαίνεται σχεδόν αμέσως ότι η g έχει την ιδιότητα που θες. Ακόμη, μπορείς όντως να ορίσεις την $ \phi$ χωρίς το αξίωμα της επιλογής.

[quote="Demetres"]Γράφουμε το $ x \equal{} 0.x_1 x_2 x_3 \ldots$ σε τριαδική μορφή. Αν k είναι μέγιστο ώστε $ x_k \equal{} 1$ τότε $ g(x): \equal{} \phi(10^k x \minus{} [10^k x])$. Άν δεν υπάρχει τέτοιο k, τότε $ g(x): \equal{} 0$.[/quote]

Huh, thanks for bothering to work it out :)

Εν τω μεταξύ, τώρα που το βλέπω έτσι γραμμένο σκέφτομαι ότι ίσως αυτή ήταν η κατασκευή που είχε ο Sil στο μυαλό του. Όταν διάβαζα την ιδέα του, νόμιζα ότι θα μετρούσε $ 0$, $ 1$ στους ρητούς για να φτιάξει μία απεικόνιση που να έχει τη ζητούμενη ιδιότητα στο $ \mathbb{N}$ και μετά θα έκανε interpolate στους πραγματικούς με κάποιο έξυπνο τρόπο... που τώρα που το σκέφτομαι καλύτερα, δε μου είναι προφανές με ποιον τρόπο μπορεί να γίνει αυτό.

Οπότε Sil, τι είχες εσύ τελικά στο μυαλό σου?

Cheerio,

Durandal 1707

Αυτό που πάνω κάτω έκανε ο Demetres !  :)
Well -done και στους δυό σας για τις πολύ καλές ιδέες .


probability
graph theory
combinatorics proposed
combinatorics

Here is a nice one from Russia 1999:

In a class every boy knows at least one girl. Prove there exist a group with at least half of the students such that each boy in the group knows an odd number of girls in the group.

we have a bipartite graph on $n$ vertices with vertex partition $(V_1,V_2)$,with $d(v) \geq 1$ for all $v\in V_1$.we want a set $V$ of atleast $n/2$ vertices such that for each $v\in V\cap V_1,d_{V}(v)$ is odd(induced degrees).let $|V_2|=k,|V_1|=n-k.$
let $S \subset V_2,S \neq \emptyset$;define $V(S)=\{v \in V_1| |N(v)\cap S|$ is odd$\}.$ clearly $V(S)\cup S$ is a choice for V. Suppose the result is not possible,i.e. for each nonempty $S \subset V_2,|V(S)|+|S|<n/2$.
let us count the number of pairs $(v,S)$ with $v \in V_1,S \subset V_2$ such that $|N(v) \cap S|$ is odd.by the above definition, the number of such pairs is $\displaystyle\sum_{\emptyset\neq S \subset V_2}|V(S)|$. On the other hand, each vertex $v \in V_1$ is contained in $2^{d(v)-1}2^{k-d(v)}=2^{k-1}$ sets $S$(note that since $d(v) \geq 1,S \neq \emptyset$). hence this sum is $(n-k)2^{k-1}$.
on the other hand by the assumption,
     $|V(S)| + |S| < n/2$ for each choice of $\emptyset \neq S \subset V_2$.summing all these up gives,
 $\displaystyle\sum_{\emptyset\neq S \subset V_2}|V(S)| + \sum_{\emptyset\neq S \subset V_2}|S|<(2^k-1)n/2$ so we have $2^{k-1}(n-k)+k2^{k-1}<(n/2)(2^k-1) \Rightarrow\\$
    $n2^{k-1}<n2^{k-1} - n/2$ and that is a contradiction.

my solution is a probabilistic one: let $E$ be the expected size of a set $A$ constructed in the following way: pick some set of girls $G$ and put $G$ in $A$, and also put in $A$ every men with an odd number of friends in $G$. we easily see $E=m/2+n/2$ so result follows.

I understand your argument, but i dont understand how do you get to the expected size of E. Would you mind making a more detailed explanation. Thanks

for every girl, the probability of her being in $A$ is $1/2$ right? now, for every boy, since he knows at least a girl, there are $2^{n-1}$ sets of girls such that he knows an odd number of grils in the set. so the probability for a men to be in $A$ is also $1/2$. Now $E=1/2+1/2...+1/2$(m+n times)

Let $x$ be the number of boys, $y$ be the number of girls, and $d_i$ be the degree of boy $x_i.$ Construct $S$ by the following:
[list]
[*]Take each girl to be in $S$ with probability $p.$
[*]If a boy has an even degree in $S,$ don't add him.
[/list]
We claim that $\mathbb{E}[|S|]$ is [b]strictly[/b] greater than $\tfrac{x+y}{2}$ for sufficient $p.$ Note that $$\mathbb{E}[|S|]=yp+\sum_{i}\left(1-\sum_{j=0}^{x_i}\binom{x_i}{2j}p^{2j}(1-p)^{x_i-2j}\right).$$ Consider terms of the form $\tfrac{yp}{x}+\left(1-\sum_{j=0}^{x_i}\binom{x_i}{2j}p^{2j}(1-p)^{x_i-2j}\right).$
The first term is increasing in $p$ while the second term is symmetric about $\tfrac{1}{2},$ and since the first term is linear in $p$ while the second is at most quadratic, the linear term dominates and it should reach a value greater than what it would be when $p=\tfrac{1}{2},$ so this function can reach a maximum of $\tfrac{1}{2}(\tfrac{y}{x}+1)+\varepsilon.$ Summing over all boys, we see that $\mathbb{E}[|S|] \geq \tfrac{x+y}{2}+x\varepsilon>\tfrac{x+y}{2}$ as desired.

Randomly take a subset of girls; the expected number of girls is $\frac{\text{No. of Girls}}{2}$. Then, add all the boys who know an odd number of girls among the subset. You can get that out of all subsets of girls, each boy is in exactly half of them. By LoE, the expected number of students in each selection is $\frac{\text{No. of Girls} + \text{No. of Boys}}{2}$. Yet, the empty set of girls also cannot have any boys. Thus, we can make the bound strict.

Unless I am mistaken, this is not from russia 1999.

We can actually pick a group with strictly more than half of the students. First put each girl into the group with probability $\tfrac{1}{2}$. Then, since every boy knows at least one girl, by symmetry reasons/binomial theorem, each boy has a $\tfrac{1}{2}$ probability of knowing an odd number of girls in the group—if they do, then add them to the group. We expect exactly half of the students to be in the group. However, equality cannot hold everywhere, since if no girls are placed into the group (which occurs with positive probability), then no boys can be placed into the group either, so there must also be a group with strictly more than half of the students. $\blacksquare$

Suppose there were $a$ girls and $b$ boys. Randomly take a nonempty subset of girls. If we just took a random subset of the girls, then each boy would have a probability of $\frac{1}{2}$ of liking an odd number of girls in the subset. Since the boys can't like an odd number of girls in the empty set, each boy has a probability $\frac{2^{a-1}}{2^a - 1} > \frac{1}{2}$ of liking an odd number of girls in this subset since each boy likes at least one girl. Therefore the expected number of students in the group exceeds $\frac{a + b}{2}$, so there must be some group with more than half of the students.

Let $G$ be the number of girls in the school and $B$ be the number of boys in the school. Take a random subset of girls and add every boy that liked an odd number of girls in this subset. Call the final subset $X$ and let the number of girls in $X$ be $g$ and the number of boys in $X$ be $b$. Notice that $$\mathbb{E}[|X|] = \mathbb{E}[g+b] = \mathbb{E}[g] + \mathbb{E}[b] = \frac{G}{2} + \mathbb{E}[b]$$ We now need to prove that $\mathbb{E}[b] \ge \frac{B}{2}$. Let $G_i$ be the set of boys that the $i$th boy likes. Notice there is a $\frac{1}{2}$ chance of each girl in $G_i$ also being in $X$. Therefore there is a $\frac{1}{2}$ chance of there being an odd number of girls in $G_i \cap X$. Therefore each boy has a $\frac{1}{2}$ chance of being in $X$. Therefore the conclusion readily follows.

This works right?

    Suppose there are m girls and n boys; randomly take a nonempty subset of girls, so that each boy has a probability of $\frac12$ of liking an odd number of girls in the subset, but since we exclude the empty set which does not satisfy the condition, each boy has >1/2 chance of liking an odd number of girls in this subset (since each boy likes at least one girl). This readily implies the expected group size is more than $(m + n)\frac12$, so there must be some group with more than half of the students.

Prepare yourself for a notational nightmare.

Consider taking a random subset of the girls, $S$, barring the empty set. Let $B$ and $G$ denote the sets of boys and girls. Now add all boys that like an odd number of girls in that subset. We wish to show over all such sets, there is at least one set which has a size greater than half of this school.

We could do this by calculating the expected value of the size.

Note for the girls we have an expected size strictly larger than $\frac{1}{2}|G|$, as we bar the empty subset.

Thus it suffices to show that over all the sets, the expected value of boys appearing is $\frac{1}{2}|B|$.

To do this consider a specific boy. Say he likes a set $Q$, of girls. Note that any given girl in $Q$ has a probability greater than $\frac{1}{2}$ of appearing in $S$, and thus there is also a $\frac{1}{2}$ chance of the boy liking an odd number of girls in $S$. To see this note that every girl added has a $\frac{1}{2}$ chance of flipping the parity of the number of girls he likes.

Thus as $\mathbb{E}[G \in S] > \frac{1}{2}|G|$ and $\mathbb{E}[B] = \frac{1}{2}|B|$ we can conclude the expected size of the set is greater than $\frac{1}{2}(|G| + |B|)$, and as such there exists a satisfactory set.

I think I messed this up

Let $g$ be the number of girls and $b$ be the number of boys.
Then we know that there are no restrictions on $b$, however $g \geq 1$.
Then the expected value of of $|S|$ is $\frac{1}{2}$. Then, let the set of girls that a boy likes be $C$. Then the probability that the number of members from $C$ that is in $S$ is odd is $> \frac{1}{2}$, because each boy likes at least one girl.
Then the expected value of the number of sets where each boy likes at least one girl is $> \frac{1}{2}$, thus one set $S$ exists that is at least $\frac{1}{2}$ as many people in the school, that satisfies the condition.

Consider the following construction of $S.$ Consider a random set of girls $G$, and choose the largest set of boys $B$ such that for every boy in $B$, he likes an odd number of girls in $G.$ \\

Note that $E[|S|] = E[|G|] + E[|B|].$ The expected size of $G$ is half the number of girls. Let an arbitrary boy have $n$ crushes. Then the probability he is in a $G$ is,
\begin{align*}
	\frac{1}{2^n} \left [\sum_{i = 0}^{\infty} \binom{n}{2i + 1} \right ] = \frac{1}{2}
\end{align*}
(well known or easily seen by binomial theorem). So the expected size of $|B|$ is half the number of boys. Hence $E[|S|]$ is half the number of students, so by PhP there exists a desired set $S.$

Let $b$ be the number of boys, and $g$ the number of girls. We will count number of pairs $(x, S)$ where $x$ is a boy, and $S$ is a subset of girls, such that $x$ likes an odd number of girls in $S$. Let $\ell$ be the number of girls he likes, then we must have $2^{\ell - 1} \cdot 2^{g - \ell} = 2^{g - 1}$ such $S$, because the $g - \ell$ girls he doesn't like don't affect anything, so we can just take any subset of them, and out of the girls he likes, since $\binom{\ell}{1} + \binom{\ell}{3} + \cdots = 2^{\ell - 1}$ for $\ell \ge 1$, we have the result. So, the number of such pairs $(x, S)$ is $b \cdot 2^{g - 1}$. Now, fix any subset $S$ of girls. The maximum size of boys we can choose without violating the odd condition is $$\sum_{i = 1}^{b} ((i, S) \; \text{is a valid pair}),$$ where $(K)$ denotes the truth of the statement $K$ ($1$ if it is true, $0$ otherwise). Summing this and the number of girls (just $|S|$) over all $S$, we have $$\sum_{S \in G} |S| + \sum_{i = 1}^{b} ((i, S) \; \text{is a valid pair}),$$ so we can manipulate into $$g \cdot 2^{g - 1} + b \cdot 2^{g - 1}$$ (as we knew that the second sum is $b \cdot 2^{g - 1}$, and the first sum is well-known to be $g \cdot 2^{g - 1}$). So, average value over all possible subsets is $\frac{g + b}{2},$ but recall that we also included the null set of girls in our sum above, so we can just divide by $2^g - 1$, since the null subset doesn't contribute anything (the set of boys you can choose at that point is null), so $\max \ge \frac{g + b}{2} + c,$ where $c$ is some small value, so $2 \cdot \max > g + b,$ so strictly more than half is possible, done.

ok whyyy do i have the worst sols ever

Choose a nonempty subset $G$ of girls at random. We will now consider the expected number of boys who like an odd number of girls in $G$. Consider some boy. If he was allowed to like no girls, the probability of him liking an odd number of girls in $G$ would be exactly $\frac12$. However, he is not allowed to like no girls, so the probability of him liking an odd number of girls in $G$ is strictly greater than $\frac12$. Therefore the expected number of boys is strictly greater than half of them. Since we pick a nonempty subset $G$ of girls at random, the expected number of girls in $G$ is strictly greater than half of all the girls. By Pigeonhole Principle, the result follows.


hello,

The polynomial  $ x^3\plus{}ax^2\plus{}bx\plus{}c$  have $ 3$ roots over $ ]0,2[$ .

Prove that: $ \minus{}2<a\plus{}b\plus{}c<0$

[hide]Let the roots be $ r_1$, $ r_2$, and $ r_3$. Then using Vieta's Formulas, $ a\plus{}b\plus{}c\equal{}\minus{}r_1r_2r_3\plus{}r_1r_2\plus{}r_2r_3\plus{}r_1r_3\minus{}r_1\minus{}r_2\minus{}r_3\equal{}\minus{}(r_1\minus{}1)(r_2\minus{}1)(r_3\minus{}1)\minus{}1$.  Each of $ r_1\minus{}1$, $ r_2\minus{}1$, and $ r_3\minus{}1$ are strictly between -1 and 1, so their product is strictly between -1 and 1, and subtracting 1, the result is strictly between -2 and 0.[/hide]

I'm sure it has been posted before. But I'll give a solution.

$ f(x)\equal{}x^3\plus{}ax^2\plus{}bx\plus{}c\equal{}(x\minus{}r_1)(x\minus{}r_2)(x\minus{}r_3)$. So $ 1\plus{}a\plus{}b\plus{}c\equal{}f(1)\equal{}(1\minus{}r_1)(1\minus{}r_2)(1\minus{}r_3)$. Since $ 0\le r_1,r_2,r_3\le 2$, then $ \minus{}1\le 1\minus{}r_1,1\minus{}r_2,1\minus{}r_3\le 1$, and hence $ \minus{}1\le(1\minus{}r_1)(1\minus{}r_2)(1\minus{}r_3)\le1$ thus $ a\plus{}b\plus{}c\equal{}f(1)\minus{}1\in(\minus{}2,0)$. Inequality is strict because the roots are distinct.


A point D lies inside the triangle ABC. Let $ A_1, B_1, C_1$ be the second intersection points of the lines AD, BD, and CD with the circumcircles of BDC, CDA, and ADB, respectively.
Prove that:
$ \frac {AD}{AA_1} \plus{} \frac {BD}{BB_1} \plus{} \frac {CD}{CC_1} \equal{} 1$

Let $ A_1B, A_1C$ cut the circles $ \odot(ABD), \odot(ACD)$ again at $ C_2, B_2.$ By Miquel theorem, the points $ A, C_2, B_2$ are collinear. From the circles $ \odot(ACD), \odot(BCD),$ we have $ \angle B_1B_2C \equal{} \angle BA_1C,$ which means $ B_1B_2 \parallel A_1B$ and similarly, $ C_1C_2 \parallel A_1C.$ Let $ B_2D, C_2D$ cut $ A_1C_2, A_1B_2$ at $ B_0, C_0,$ respectively. Then $ \frac {BD}{BB_1} \equal{} \frac {B_0D}{B_0B_2}$ and $ \frac {CD}{CC_1} \equal{} \frac {C_0D}{C_0C_2}.$ Since $ A_1A, B_2B_0, C_2C_0$ are concurrent cevians at $ D$ in the $ \triangle A_1B_2C_2,$ it follows that

$ \frac {AD}{AA_1} \plus{} \frac {BD}{BB_1} \plus{} \frac {CD}{CC_1} \equal{} \frac {AD}{AA_1} \plus{} \frac {B_0D}{B_0B_2} \plus{} \frac {C_0D}{C_0C_2} \equal{} 1$

Dear Mathlinkers,

http://jl.ayme.pagesperso-orange.fr/Docs/Orthique%20encyclopedie%209.pdf  p. 35-37.

Sincerely
Jean-Louis


function
modular arithmetic
number theory
prime factorization
number theory unsolved

Hi

I have the harmonic mean H(n) of the divisors of a positive integer n. I need to show that if n is perfect number, then H(n) must be an integer.

1/H(n)={1/τ(n)}Σ(1/d)

I have found that

H(n)=nτ(n)/σ(n)
H(n)=τ(n)/2

How can I conclude that this is an integer?

Thank you

You did must of the work...
Assume that $ n \equal{} \prod p_i^{a_i}$ is the prime factorization of n.
Now: τ$ (n) \equal{} \prod(a_i \plus{} 1)$. $ H(n)$ is not an integer iff $ \prod(a_i \plus{} 1) \equiv 1 \pmod 2$, or: $ a_i$ is even for all $ i$, i.e, $ n$ is a square.
Thus, we shall show that a square of an integer can't be perfect.
Let $ n \equal{} \prod_{i \equal{} 1}^{m} p_i^{2a_i}$. Assume that $ n$ is perfect, and WLOG $ p_1 \equal{} 2$ ($ a_1$ can be zero, but $ a_i > 0$ for $ i \neq 0$).
We have: $ 2\prod_{i \equal{} 1}^{m} p_i^{2a_i} \equal{} \prod_{i \equal{} 1}^{m} \frac {p_i^{2a_i \plus{} 1} \minus{} 1}{p_i \minus{} 1}$

Because $ \frac{x^{2n \plus{} 1} \minus{} 1}{x \minus{} 1} \equiv 1 \pmod 2$ for odd x, we have: RHS is odd, a contradiction. Hence a square can't be perfect, Q.E.D


[quote="Pascual2005"]Hola:

Los queria invitar a todos a que participen en este concurso que con mucho gusto promueve Mathlinks, la dificultad de los problemas es variada, para mas informacion vallan a contest,a rriba en el tab! :D[/quote]

Jeje, yo no puedo participar. Pero eso es por que yo ya estoy medio viejo para estas vainas. La verdad, si tenes menos de 20 anios, pues participa!!!


[quote="ashrafmod"]${\sqrt{17+8x-2x^{2}}+\sqrt{4+12 x-3 x^{2}}=x^{2}-4x+13}$[/quote]

[hide="hint"]${x^{2}-4x+13}=(17+8x-2x^{2})-(4+12 x-3 x^{2})$[/hide]

[hide="solution"]

So

$\sqrt{17+8x-2x^{2}}+\sqrt{4+12 x-3 x^{2}}=$

$(\sqrt{17+8x-2x^{2}}+\sqrt{4+12 x-3 x^{2}}\ )(\sqrt{17+8x-2x^{2}}-\sqrt{4+12 x-3 x^{2}}\ )$

Evidently there is no x, for which LHS=0, therefore we can cancel:

$\sqrt{17+8x-2x^{2}}-\sqrt{4+12 x-3 x^{2}}=1$

Replace $y=4x-x^{2}$ and have

$\sqrt{17+2y}=1+\sqrt{4+3y}$

Squaring obtain

$12-y=2\sqrt{4+3y}$

Again square with restriction $12-y\ge 0$ we have quadratic equation

$y^{2}-36y+128$ with roots $y_{1}=4 and y_{2}> 12$, so $y=4$

Now $4x-x^{2}=4$ gives

uniqe root $x=2$[/hide]

[hide="Oh, Heavens!  :rotfl: "]

Let $y=4x-x^{2}$ at the very start. Then we have

$\sqrt{17+2y}+\sqrt{4+3y}=13-y$ with evident root $y=4$

which is unique because LHS is encreasing and RHS is decreasing.[/hide]


How many of the numbers, $100,101,\ldots,999$, have three different digits in increasing order or in decreasing order?

$\text{(A)} \ 120 \qquad \text{(B)} \ 168 \qquad \text{(C)} \ 204 \qquad \text{(D)} \ 216 \qquad \text{(E)} \ 240$

I don't really ahve any better ideas than fast casework.  :( Oh well.

[hide]Let's study increasing first:

Suppose the first digit is one: there are 8C2 ways to choose the next two digits
first digit two: 7C2 ways,
and etc

For decreasing, everything as increasing. The only thing we have to consider differently is if the last digit is $0$. There are 9C2 ways that can occur.

Therefore, our answer is $9C2+2(8C2+\cdots+2C2)=204$
[/hide]

[hide]
Let's do increasing first.
It's a pattern, for 100s, you have 123 to 129, 134 to 139, etc. giving you the pattern $1+2+3+...7$ or $28$. For 200s, by same logic, you have $1+2+3+...6$ or $21$. This continues giving you $1+3+6+...28$ or $84$.
Now for decreasing, it's the exact same expect just 1 more because of the digit 0 giving you the final sequence of $1+3+6+...36$ or $120$.
Do $84 + 120$ which equals your answer, $204$.[/hide]

Another way:
In order to have the three numbers decreasing we can just pick a distinct set of three numbers and arrange them in decreasing order.  This can happen in $\ \binom{10}{3}$ ways.  The same is true for picking numbers in increasing order, but we must exlude those cases where $\ 0$ is the first digit.  So if $\ 0$ is the first digit then we can choose the other two in $\ \binom{9}{2}$ ways.  So our final answer is $\ 2 \binom{10}{3} - \binom{9}{2}=204$


In how many ways can 100 identical chairs be divided among 4 different rooms so that each room will have 10, 20, 30, 40 or 50 chairs.

[quote="unimpossible"]it's he same as how many partitions of 10 into ones. so [hide]13C3[/hide][/quote]

that is both incorrect logic and incorrect computation (It would be $ {12\binom3}$ rather than $ {13\binom3}$)

you are counting the case 10, 60, 20, 10, among many others, and this does not satisfy the condition

[quote="13375P34K43V312"]you are counting the case 10, 60, 20, 10, among many others, and this does not satisfy the condition[/quote]

oh yes sorry i didn't read the question carefully. :|

[hide]let it be 10 chairs into 4 rooms in either 1,2,3,4, or 5 chairs per room. give each room a chair. now, you have have 6 chairs left to split into 4 rooms.  so far you have 9C3 ways, using balls and urns. however, you have to subtract the number of ways a room could have more than 6 chairs, or in this case 5 extra chairs. there are 4 ways to give a room 4 extra chairs and another 4 ways to give the last one.

thus, the answer is 9C3-4*4=$ \boxed{68}$[/hide]

please correct my logic if i'm wrong. the answer doesn't seem right...

I don't know if you have discussed generating function, but it would help. The answer is 68, but I can't figure its solution yet. Maybe those who are good at combinatorics may want to help us.

@ 1337 - \binom works like \frac, so it would be \binom{12}{3}. {{12}\choose{3}} also works, but it's not used as commonly.


Let X be a complete metric space such that for every x in X, the singleton set {x} is not open. Prove that X is uncountable.

this may be one way to proceed.... :maybe:

consider x which belongs to X.
{x} is not open in X implies that the open ball B(x,1/n)
contains an element y not equal to x for all n = 1,2,3,....
so we can construct a sequence {x_n} from these elements ( ie , y's).
these form a cauchy sequence . as X is complete ,
x_n is convergent and it converges to x.
so x is a limit point.
as every point x is a limit point , X is a perfect set.
we also know that every perfect set is uncountable.
so X is uncountable....

Another solution uses Baire's theorem. $ X\setminus\{x\}$ is open ($ \{x\}$ is always closed) and dense (it isn't closed, because $ \{x\}$ isn't open).
But $ \emptyset\equal{}\bigcap_{x\in X} X\setminus\{x\}$ isn't dense. So Baire's theorem tells us, that this can't be a countable intersection. Hence $ X$ is uncountable.


real analysis
function
algebra
domain
real analysis unsolved

Define a function $ f: \mathbb{R}\times\mathbb{R}\to\mathbb{R}$ by $ f(x,\epsilon) \equal{} m(E\cap(I_{\epsilon} \plus{} x))$ where $ m$ is the usual lebesgue measure on $ \mathbb{R}$, $ m(E) > 0$, $ I_{\epsilon} \equal{} (0,\epsilon)$ and $ I \plus{} x \equal{} \{y \plus{} x: y\in I\}$. Is it true then that there always exist $ x_0$ and $ \epsilon_0$ such that $ f(x_0,\epsilon_0) \equal{} \epsilon_0$? This problem is related to exercise 30 in chapter 1 of Folland's real analysis book because the statement implies the solution to the problem. I appreciate any pointers you can give me.

[quote="Yury"]This statement is not true (of course, there exists a trivial solution $ \epsilon_0 \equal{} 0$). Let $ \phi$ be a bijection between $ \mathbb N$ and $ \mathbb Q$. Define
\[ E \equal{} {\mathbb R} \setminus \bigcup_{i\in {\mathbb N}} (\phi(i) \minus{} 2^{ \minus{} i}, \phi(i) \plus{} 2^{ \minus{} i}).
\]
Then $ m(E) \equal{} \infty$. However, for every $ a,b\in {\mathbb R}$ ($ a < b$), we have $ m([a,b]\cap E) < b \minus{} a$. Therefore, $ f(x_0, \epsilon_0) < \epsilon_0$.[/quote]

Excellent and I see why this works but letting $ I_{\epsilon} \equal{} \mathbb{R}$ gives us a solution even though $ I_{\epsilon}$ is not strictly in the domain of the function. So let me redefine the domain of the function from $ \mathbb{R}\times\mathbb{R}$ to $ \mathbb{R}\times S$ where $ S$ is the set of all intervals of $ \mathbb{R}$ including $ \mathbb{R}$ and any infinite ray. Is it still true then that a solution doesn't always exist? Although now I realize that this isn't the way to go about solving the problem in the book because even in this case we can find a set $ I$ such that the difference between $ m(E\cap I)$ and $ m(I)$ is as small as we wish it to be. Thanks for the help.

Just consider the set $ E\cap [0,10]$ (where $ E$ is the set I described in my previous post). Then again $ \mu([a,b] \cap (E \cap [0,10]))  \leq \mu([a,b] \cap E) < b\minus{}a$. But since $ \mu(E\cap [0,10]) < 10$, for every infinite interval $ I$ we have $ \mu(I\cap (E\cap[0,10])) < 10 <\mu(I)$.


HCSSiM
AMC
USA(J)MO
USAMO
email
AMC 12
AMC 12 A

Congratulations to the twelve HCSSiM alumns (unless I missed some) who qualified for the 2006 USAMO---including AoPSers s0mp, Sho, schulmannerism, jackb1115, and FermatPrime!

...and now that scores are posted, I'd like to know how y'all did!  Please PM me or send me an email letting me know (and also if you know how one of the non-AoPS-but-HCSSiM USAMO qualifiers did).

Wow---we have 15 HCSSiM alumns (and at least two applicants) who qualified for the 2007 USAMO.  Congratulations to all, but let me just name the AoPSers on that list: snorkack, smiley, FermatPrime, blerpiez, qqwref, and jackb1115.  (If the other nine have AoPS accounts, I don't know their usernames...including the alumn who earned a perfect score on the AMC12A!)

Wow!  Three HCSSiM teams participated in the iTest this year, and got 3rd place (team Yellow Pig), 8th place (team Yellow Pigs), and 42nd place (team Yay Petersen Graph! with a last-minute entry).  Congratulations!  Rankings of the teams went all the way to 169th.

WO!!! Lots of AoPS'ers!!  :roll:  :o  :P


hello to everybody........ :)
well i am arnav of class 11th,........joind mathlinks recently..........
my kvpy exam is on 2nd nov...........
well in this time i also have my academic exams(for which i am not actually tensed :D )
well i wanted help from all u guys.......
can ne one suggest me from where to study and crack my head for kvpy........... :?:  :)

tehre are lot many threads about KVPY in the [url=http://www.mathlinks.ro/index.php?f=513]indian forum[/url]
Please search there and if u have any otehr doubts please post them there


USAMTS AMC AIME geometry USA(J)MO USAMO algebra

Definitely.

If you want to see how to write a proof, you can view lots of threads on these forums where members write their solutions. Alternatively, you can look at solutions to old USAMTS problems. Writing a proof is basically explaining how you get your solution; it's not that hard. You could also read some books like Volume 1 or Volume 2; they're good.

About your scores, they're fine. You can improve a lot over the summer. I had 129 on the 10 last year and 4 on the AIME and I did "okay" on USAMTS...if I was a bit less lazy it would've been better but whatever.

USAMTS is a great program and you should definitely do it.

The USAMTS is a good place to learn to write a proof. Sure, you could learn how to write proofs in Geometry class, provided that your teacher does not use the pedantic statement-theorem T-bar method which nobody uses in real mathematics, but then your weakest attempts will graded for your report card. One of the purposes of the USAMTS is to let students master proofs at a more comfortable pace. If finding and proving all five solutions in a round is too fast a pace, then solve fewer of them.

We graders try to explain how to repair any flawed solution, though space limits us to about three sentences. Our goal is to see more perfect solutions in the next round (perfect solutions are easier to grade). More complete clarifications can be found by discussing solutions on this forum.

For the first round of the USAMTS, we almost always choose problems that require both an answer and a proof. This is deliberate, because we don't want to require beginners to do pure proofs. (Okay, Problem 5 of Round 1 this year was a pure proof, but that proof was mostly matching up similar terms in an expansion of an algebraic expression.) Finding the answer provides a framework to writing a clear proof: "This is how I found the answer and this is why no other answer can be found." By the fourth round, the students are practiced in writing proofs, so we can give problems that require nothing but a proof.

This website does provide guides to writing proofs, such as [url=http://www.artofproblemsolving.com/Resources/AoPS_R_A_HowWrite.php]How to Write a Solution[/url].

Erin Schram, USAMTS grader

It's always a good time to get into USAMTS.

It's not too hard. While you're thinking, just write down what you're doing. Like, let's say they asked you to solve "4*5-7+42/2 =?" with excruciating detail.

To write a proof, you'd talk how you think.

"Well, the first thing to do in order of operations is multiplication/division, so I calculated out 4*5 = 20 and 42/2 = 21. Then, I did the addition and subtraction of 20-7+21 = 34."

As you go along, the style of writing proof will improve. However, whether a proof is elegantly and fluently written, or excessively wordy and detailed, a correct proof is a correct proof.

It's great proof-writing practice. If you're afraid to start proofs now, doing proofs later on will be even harder.

A simple example is finding the sum of the angles in a triangle. If you didn't know, Would you rather see:

Its 180.

Or

Label the vertices A,B,C in clockwise order. Consider the line through A parallel to BC. Pick arbitrary points M,N, such that M is on the side of B (the right of A), and N is on the other side.

Thus, <A+<B+<C=<A+<BAN+<CAM (by parallels), which is a straight line, or 180.

I would say you should go for it. I got 133.5 on amc 10 last year and 4 on aime (in addition to chickening out of doing usamts), and this year was my first year to do usamts, and I am extremely glad I did it. I had a  pretty dim idea of how to write a proof at the beginning of round 1, but I did ok too. I would have no other place to practice writing proofs for competitions before USAMO if it weren't for USAMTS (though I have 5 % chance of making usamo this year..that another story).

You learn how to write proofs as you go, so don't think you need to "know" how to write a good proof before doing usamts, since I imagine most people don't know how beforehand.

[quote="high_flyer10"]I am wondering if I should do USAMTS next year. The thing is, I want to do it but I have absolutely no idea how to write a proof. I'm afraid that I would start USAMTS round 1 and then stop (like this year). I got a 120 on the AMC 10 and a 4 on the AIME this year. Should I attempt USAMTS next year? How on earth do you write a proof? I can't write a proof to save my life.[/quote]
You could probably get atleast silver if you tried a little bit

@ high_flyer10: A proof is a written essay stating why something is true. For example, if you wish to prove that the sum of the angles of a triangle totaled to 180 degrees, the following could be acceptable. (You might want to draw a diagram or two while writing the problem for clarification.

[hide="in here"]Take triangle $ ABC$, extend line segment $ BC$ infinitely through both sides, and draw line $ k$ through $ A$ such that it is parallel to line $ BC$.

Draw points $ D$ and $ E$ on line $ k$ such that they are on opposite sides of $ A$ and $ D$ is closer to $ B$. $ \angle DAB$ and $ \angle ABC$ are equal internal angles, as are $ \angle EAC$ and $ \angle ACB$. Now note that $ \angle ACB \plus{} \angle CAB \plus{} \angle ABC \equal{} \angle EAC \plus{} \angle CAB \plus{} \angle DAB \equal{} \angle EAD \equal{} 180^{\circ}$. Therefore the sum of the angles of a triangle is 180 degrees.[/hide]
The essay doesn't have to be long or wordy. It can even be one sentence;
"Taking Stewart's Theorem and rearranging the variables gives this result."
That is completely acceptable so long as it's true.

Actually people take the USAMTS to qualify for the AIME. I think you've got a decent shot at it.
The problems WILL be hard, but don't give up. I did, and I got a 0. Don't give up and you will get more than that. :)

EDIT: sorry i didn't see your proof, BOGTRO.

Also, I personally think USAMTS is like a good stepping stone to prepare for USAMO. Note that USAMO graders are MUCH MUCH stricter than USAMTS graders, so being able to get a feel for USAMTS should be beneficial for you so that you aren't totally shocked for USAMO.

USAMTS rules also deduct a point or two for flawed, messy, or unorganized solutions, so I personally do think it stresses proof-writing skill. (Meh, that made me think of Round 2 Problem #1 which I got a 4 but should have gotten a 5 if I weren't too lazy on my proof-writing organization, bleh)

Lastly, I want to say USAMTS problems are pretty challenging yet interesting. Just like USAMO, it challenges you to a higher level of thinking. And yet, USAMTS is free, with the exception of postage. And you can get good prizes, even if you don't think you can do well on USAMO/aka make MOP. Still, it's a good experience, so why not join USAMTS?

So, as you can probably see clearly, the consensus is that you should do USAMTS. End of question.  :)

As far as proof goes, the easiest way to understand is to compare with any question and answer you face in real life. If someone tells you a surprising news, you will automatically (and likely) ask why and where the person got the news. Then, this "someone" will go onto expand on the source of information and other relevant details. In some cases, you might even ask this "someone" to provide explanations for counterargument. That is, you may say, "Well I heard from my other friend that what you say is not true..." And so on.

The point of this is that as a human being, we emphasize one fact with another fact by usage of logic. We don't simply take a surprising news for granted; instead, we ask the processes in which the information came.

This is indeed what you do in proof. If you think slowly and make no assumption, you should be fine. A good proof-writer always asks himself/herself if the argument is logical. The concept of proof is evident to everyone; it's just that in mathematics, you need to build up these "facts" by studying, and that's where the books come in.

Guys, geometry proofs not good. Proof and solution are sort of equivalent.

For instance, find with proof the solutions to $ x^2\minus{}5x\plus{}5/2\equal{}0$.

Take the given polynomial: we would like to have some equation in the form $ a^2\minus{}b^2\equal{}0$, since these easily factor into $ (a\plus{}b)(a\minus{}b)\equal{}0$, leaving either $ a\minus{}b\equal{}0$ or $ a\plus{}b\equal{}0$.

Since $ x^2\minus{}5x\plus{}10\equal{}x^2\minus{}5x\plus{}25/4\plus{}15/4\equal{}(x\minus{}5/2)^2\minus{}15/4\equal{}0$, we have that $ (x\minus{}5/2\minus{}\sqrt{15/4})(x\minus{}5/2\plus{}\sqrt{15/4})\equal{}0$ by difference of squares. Thus either $ x\equal{}5/2\plus{}\sqrt{15/4}$ or $ x\equal{}5/2\minus{}\sqrt{15/4}$.

Not a good proof, but it is a solution: it explains your steps and should get a 5 in USAMTS. *I* think.

In my opinion, the USAMTS is the best Math Competition in America (not the hardest, but the best). It has the best questions, in that they are often open to interesting generalizations or point to some deeper concept. It allows students the greatest opportunity for growth by thinking for an extended period of time about the questions, and through the process of writing up their solutions. In addition, the feedback from the graders is invaluable.

Aside from research contests like the Siemens and Intel Science Competitions, the USAMTS is the closest contest to teaching students what it is like to do real mathematics. Success is only a secondary goal - the primary goal is growth and improvement.

[quote="mathemonster"]the quadratic formula may be used w/o proof in USAMTS  :wink:[/quote]

I am pretty sure he knows this.

anyway USAMTS is very good for improving your proof-writing and general rigor skills (even though I suppose their rigor requirement is not that... selective compared to USAMO and the like.) Most problems are pretty interesting. Some are computationally intensive. Either way, the point is to show your work and your thought process. Have a logical progression in your solution. Read other people's solutions or proofs to get a better idea of the language you should use.

after a while, you'll find solving the problem becomes harder than writing the proof. unless it's combinatorics T________T

[quote="Temperal"][quote="not_trig"]

after a while, you'll find solving the problem becomes harder than writing the proof. unless it's combinatorics T________T[/quote]

you mean vice versa?[/quote]

no; see "combinatorics." see USAMO 2007 #4. and 2008 #4.

Actually, proof and solution is a bit different. A proof should be just a line of deductions and facts that is easy to follow, but not necessarily motivated (I heard it was aesthetically appealing for a proof to be totally unmotivated). A good solution, on the other hand, should show enough motivation so that the reader know how one manage to find the solution. For example, it is very bad-style in a proof to say "if we want to prove A, we must prove B. Proof of B." but instead one should say "Proof of B. By B, A is true." But this would be fine for a solution.

[quote="timwu"]...I heard it was aesthetically appealing for a proof to be totally unmotivated... it is very bad-style in a proof to say "if we want to prove A, we must prove B. Proof of B." but instead one should say "Proof of B. By B, A is true." [/quote]

Where did you hear this from? I completely disagree with this.


8 chairs' 3/4 is 6 chairs.
2/3 of peop. is 6
6*3/2=9 peop. at least.
I dont know but no peop. and no chairs comes right to me,too.

[quote="G-UNIT"]$\frac{2}{3}$ of a group are sitting on $\frac{3}{4}$ of the chairs in the room.  At least how many people are there in the group?[/quote]

Let the number of people be [b]x[/b] , number of chair be [b]y[/b] , then

2x/3 = 3y/4  ---> 8x = 9y ---> x:y = 9:8

Least number of people = 9

[hide]The LCM of 2 and 3 is 6. so there are 6 people using 6 out of 8 chairs. There are at least 9 people.[/hide]

[hide]
i would do
$\frac{2}{3}x=\frac{3}{4}y$

$x=\frac{9}{8}y$

$\text{Now i'm stuck}$[/hide]

[hide]We want 2/3 of number of people to be a whole number. Also, $\frac{4}{3}\cdot\frac{2}{3}x = \frac{8}{9}x$ should also be a whole number. The smallest nubmer that satisfy this is the larger denominator of the two fractions or 9. [/hide]

[hide]

8 is the smallest number that $\frac{3}{4}$ of it is divisible by 3.
$\frac{2}{3}$; $\frac{6}{\frac{2}{3}} = 9$ So the least amount of people is $\framebox{9}$ [/hide]


For any three positive reals $a,b,c$, we have

$\sqrt{2}(ab^2+bc^2+ca^2)\ge ab\sqrt{b^2+c^2}+bc\sqrt{c^2+a^2}+ca\sqrt{a^2+b^2}$

A hint: divide by $abc$ and get a known ineqaulity.

It looks interesting! :lol:
Could you prove it in detail?? :D

[quote="socrates"] Could you prove it in detail?? :D[/quote]
Yes I do, but can you too ?! ::D  :D
$(\alpha> 1 )\&(\forall_k,x_k > 0)\&( \prod_{k=1}^n x_k=1) \Longrightarrow 2^\frac 1\alpha \sum_{k=1}^n x_k \geq \sum_{k=1}^n(1+x^\alpha_k)^\frac 1\alpha$
 :cool:

See also
http://www.mathlinks.ro/Forum/viewtopic.php?p=277125#p277125
where
[quote="harazi"]If $a_1...a_n=1$ then $\sqrt{\frac{a_1^2+1}{2}}+...+\sqrt{\frac{a_n^2+1}{2}}\leq a_1+...+a_n$.[/quote]

I am  wondering  which  one  is  stronger ?  Xstar's   ineq  or  this  one ?
http://www.mathlinks.ro/Forum/viewtopic.php?p=21704#p21704


Prove that
\[\mu^{*}(A \cup B)+\mu^{*}(A \cap B) \le \mu^{*}(A)+\mu^{*}(B),\]
where $\mu^{*}(\Omega)$ is the outer measure of $\Omega$:
\[\mu^{*}(\Omega) = \inf_{\Omega \subset \bigcup \Omega_{n}}\sum_{n}\mu(\Omega_{n}),\]
infimum being taken over all sequences (finite or not) of sets $\Omega_{n}$ belonging to a given ring of sets.

Choose an efficient covering $\Omega_{n}$ for $A$ and another $\Omega_{n}'$ for $B$. Let $E_{ij}=\Omega_{i}\cap \Omega_{j}'$,  $F_{ij}=\Omega_{i}\setminus\Omega_{j}'$, and $G_{ji}=\Omega_{j}'\setminus\Omega_{i}'$. The sets $E_{ij}$ cover $A\cap B$; the sets $E_{ij},F_{ij}, G_{ji}$ together cover $A\cup B$. Also,
\[2\sum_{ij}\mu(E_{ij})+\sum_{ij}\mu(F_{ij})+\sum_{ij}\mu(G_{ji}) =\sum_{i}\mu(\Omega_{i})+\sum_{j}\mu(\Omega_{j}')\]


geometry
3D geometry
modular arithmetic
number theory

Verify that if an integer is simultaneously a square and a cube (64=8^2=4^3), then it must be either of the form 7k or 7k+1.

[hide="solution"]
The wording of the problem suggests looking at numbers modulo 7, so we build a table:
x   $ x^2$   $ x^3$
0   0   0
1   1   1
2   4   1
3   2   6
4   2   1
5   4   6
6   1   6

From this we can see that any number cubed is either 0, 1, or 6 modulo 7.  For a number to be both a cube and a square, it must be the square of some cube.  0 squared is 0 mod 7, 1 squared is 1 mod 7, and 6 squared is also 1 mod 7, so any number that is both a square and a cube must be either 0 mod 7 or 1 mod 7, which is equivalent to the from stated in the problem.

[/hide]

[hide="Alternate approach"]A number is a square and a cube if and only if it is a sixth power.  Call our number $ a^6$.  If $ 7 | a$ then $ 7 | a^6$ and so $ a^6 \equal{} 7k$ for some integer $ k$.  If not, by Fermat's Little Theorem we have $ a^6 \equiv 1 \pmod 7$ and so $ a^6 \equal{} 7k \plus{} 1$ for some integer $ k$.  (Of course, you don't need FlT to do this -- you could simply check $ a^6$ for $ a$ in each equivalence class modulo 7.)[/hide]


geometry
algebra
polynomial
algorithm
combinatorics proposed
combinatorics

Is there any way to find the number of minimum colours required to colour a picture so that no two areas sharing a common border have the same colour?
Im sorry if i've posted this question on the wrong section , cz i don't know under which topis this goes

The four-color theorem tells you that four colors are always sufficient.
Hence, you may simply check all $ 4^n$ possible assignments of four colors to $ n$ regions.
Actually, the proof of the four-color theorem is algorithmic, and also yields a polynomial time algorithm for 4-coloring of planar graphs.

Deciding whether a planar graph can be colored with three colors is NP-complete.

Deciding whether a planar graph can be colored with two colors is straightforward.

[quote="lajanugen"]How do we decide if 3 colours a sufficient for a given picture?[/quote]

You may check all $ 3^n$ possible assignments of three colors to the $ n$ regions.
Since this problem is NP-complete, you should not expect to find a polynomial time algorithm for it.

Thankyou test20
Btw, what is "NP-complete"?


induction
superior algebra
superior algebra unsolved

Suppose $\forall 2\le k\le n\ L_{k}=\{(1\ k),(2\ k),\dots ,(k-1 \ k)\}$. Prove that each $a\in S_{n}$ has a unique representation in this form $a=a_{n}\dots a_{3}a_{2}$ where $a_{k}\in L_{k}$.

The identity permutation is in every $L_{k}$, isn't it?

If so, then it's pretty obvious what to do: $a(n) = a_{n}\ldots a_{2}(n) = a_{n}(n)$ (since $a_{k}$ sends $n$ into $n,$ for all $k \in \overline{2,n-1}$), so $a_{n}= \left( a(n) \ n \right)$; thus, we have reduced the problem to $n-1$, so we can use induction to finish it.


[quote="phan hong son"][i]Let[/i] $a,b,c,d \ge$ $0$[i],such that[/i] $a+b+c+d=4.$[i]prove that[/i]
\[\underset{\text{cycl}}\sum\sqrt{\frac{a^{4}+b^{4}+c^{4}}{(2+ab)(2+ac)(2+bc)}}\ge\frac{4}{3}\]
[/quote]

[b]Problem[/b] Prove that for any nonnegative real numbers $a,b,c,d$ satisfying $a+b+c+d=4,$
\[P=\sum \sqrt{\frac{a^{4}+b^{4}+c^{4}}{(2+ab)(2+bc)(2+ca)}}\ge \frac{4}{3}\]
[i][b]Proof[/b][/i]
By H\"{o}lder inequality, we have
\[P^{2}\left( \sum (2+ab)(2+bc)(2+ca)\right) \geq \left( \sum \sqrt[3]{a^{4}+b^{4}+c^{4}}\right)^{3}\]
Furthermore, using H\"{o}lder and Jensen inequality,
\[\sum \sqrt[3]{a^{4}+b^{4}+c^{4}}\geq \frac{1}{3}\sum (a+b+c)^{4/3}\ge \frac{4}{3}\left( \frac{\sum (a+b+c)}{4}\right)^{4/3}=4\sqrt[3]{3}\]
Hence, it remains to prove that
\[\sum (2+ab)(2+bc)(2+ca)\leq 108 \]
or
\[8\underset{\text{sym}}{\sum }ab+8\sum abc+\sum a^{2}b^{2}c^{2}-8abcd\le 76 \]
By Maclaurin inequality, we have
\[\sqrt[3]{\frac{\sum abc}{4}}\leq \sqrt{\frac{\underset{\text{sym}}{\sum }ab}{6}}\leq \frac{\sum a}{4}=1 \]
Hence,
\[\sum abc\leq 4,\underset{\text{sym}}{\sum }ab\leq 6 \]
Therefore
\[8\underset{\text{sym}}{\sum }ab+8\sum abc+\sum a^{2}b^{2}c^{2}-8abcd \\ =\left( \sum abc+\sum a^{2}b^{2}c^{2}\right)+\frac{54}{11}\left( \sum abc-\frac{44}{27}abcd\right)+8\underset{\text{sym}}{\sum }ab+\frac{34}{11}\sum abc \\ \leq \left( \sum abc+\sum a^{2}b^{2}c^{2}\right)+\frac{54}{11}\left( \sum abc-\frac{44}{27}abcd\right)+\frac{664}{11}\]
It remains to prove that
\[\sum abc+\sum a^{2}b^{2}c^{2}\leq 8\ (1) \]
\[\sum abc-\frac{44}{27}abcd\leq \frac{64}{27}\ (2) \]
But $(1)$ and $(2)$ are easy (you can prove them by yourself).
The inequality is proved.
Equality holds if and only if $a=b=c=d=1.$
:)


function
integration
calculus
real analysis
real analysis unsolved

Can anyone help me figure this out:

Let f_n, n = 1,2,3,... be a sequence of nonnegative continuous functions on R such that integrable on R of f_n <= 1/n^2. Let f = summation from n to infinity of f_n. Prove that f is integrable on R.

Under the usual hypotheses of measurability and integrability, if $\sum {\int {|f_{n}|}} <+\infty$, then $\sum {f_{n}}$ is integrable and its integral is the sum of the integrals. Use Lebesgue's bounded convergence theorem and Beppo-Levi (the monotonous convergence theorem).


Find an example of a bounded infinite subset of Q (rational numbers) that has no accumulation point in Q.

Such a set must have an accumulation point in $ \mathbb R\setminus \mathbb Q$. Like $ \sqrt{2}$ or something.


geometry
trigonometry
inequalities proposed
inequalities

if abc(a+b+c)=1 what is the minimum value of (a+b)(a+c).

Let $x=bc$ and so on, we have $xy+yz+zx=1$ and we have to find hte minimum of $\frac{yz}{x}+x+y+z=\frac{x^2+xy+yz+zx}{x}=\frac{x^2+1}{x}$, which is obviously 2.

Let $x=a+b,y=b+c,z=c+a$, then $x,y,z$ are sides of triangle. One the other hand $1=(a+b+c)abc=p(p-x)(p-y)(p-z)=S^2$($S$-area of this triangle), where $p=a+b+c$. But $(a+b)(a+c)=xz=\frac{2}{\sin \beta }\ge 2$($\beta$-angle between $x$ and $z$). So minimum is attaned (for example) with $\beta =90^o, x=2, z=1, y=\sqrt{5}$, and $a=\frac{3-\sqrt{5}}{2}, b=\frac{1+\sqrt{5}}{2}, c=\frac{-1+\sqrt{5}}{2}$.

With $x,y,z >0$ we have :$(x+y)(x+z)\geq 2\sqrt{xyz(x+y+z)}$.

it  is very simple !
A=(a+b)(a+c)=a^2+ac+ab+bc=a(a+b+c)+bc  so
A=a/abc+bc=1/bc+bc>2!