quadratics
function
algebra unsolved
algebra
inequalities

Let $n \geq 2, n \in \mathbb{N}$, $a,b,c,d \in \mathbb{N}$, $\frac{a}{b} + \frac{c}{d} < 1$ and $a + c \leq n,$ find the maximum value of $\frac{a}{b} + \frac{c}{d}$ for fixed $n.$

It is easy. Let $s=\frac{a}{b}+\frac{c}{d}=\frac{ad+bc}{bd}$.
If b=d then $s\le 1-\frac{1}{b}\le 1-\frac{1}{2n}$.
If $b\not =d$ then $s\le \frac{bd-1}{bd}=1-\frac{1}{bd}.$ From $a+c\le n$ we get $b,d\le 2n$.
 We have $\frac{n-1}{n}+\frac{1}{n+1}=1-\frac{1}{n(n+1)}$.

[quote="Rust"]
From $a+c\le n$ we get $b,d\le 2n$.
We have $\frac{n-1}{n}+\frac{1}{n+1}=1-\frac{1}{n(n+1)}$.[/quote]

I don't understand that, can you help me?

Let $s=\frac{a}{b}+\frac{c}{d}=\frac{ad+bc}{bd}<1$.
If b=d then $s=\frac{a+c}{b}$, maximum when $b=a+c+1$, because $a+c\le n$, $s\le 1-\frac{1}{n+1}$.
If $b\not =d$ then $s\le \frac{bd-1}{bd}=1-\frac{1}{bd}.$
If $b\ge n+1,c\ge n+1$, then $s\le 1-\frac{1}{n+1}$. Therefore if $s>1-\frac{1}{n+1}$ one of $b,d$ less than n+1. Let $b\le n$. If $d\le n$, then $s\le 1-\frac{1}{n^{2}}$. If $d>n+2$, then $s=1-\frac{b-a}{b}+\frac{c}{d}\le 1-\frac{b-a}{b}+\frac{n-a}{n+2}<1-\frac{1}{n(n+1)}$.
 We have $\frac{n-1}{n}+\frac{1}{n+1}=1-\frac{1}{n(n+1)}$. Therefore it give maximum s.

Not true unfortunately.
For n=5,for example, we have 2/9+3/4=35/36 > 29/30.
The exact answer is a bit complicated. The maximum equals 1-1/t where
t(3p)=4p^3+4p^2+3p+1
t(3p+1)=4p^3+8p^2+7p+2
t(3p+2)=4p^3+12p^2+14p+6

So t is not quadratic,but of third power wrt. n

can you give detail solution alexheinis?

I included the details in a pdf-file, I only had the solution in Dutch so I translated.
Bye.

Setting $b=a+x,d=c+y$ the problem gets easier, because we have
${a\over {a+x}}+{c\over {c+y}}<1\iff xy>ac$. We assume $a\le c$.
Keeping $\pi:=xy$ fixed, we will show that the form ${a\over {a+x}}+{c\over {c+y}}$
is maximal for
$x=\pi,y=1$. We have ${a\over {a+\pi}}+{c\over{c+1}}\ge
{a\over {a+x}}+{c\over {c+y}}\iff ay+cx\le a+c\pi$.
Using the convex function $f(x)=cx+{{a\pi}\over x}$ one sees that the maximum on $[1,\pi]$
is attained in one of the extremities and, in this case, when $x=\pi$.
Hence, if $xy=\pi$, then the form is at most ${a\over {a+\pi}}+{c\over {c+1}}$.
This form is maximal when $\pi=ac+1$, substitution yields $1-{1\over t}$, where
$t:=(ac+a+1)(c+1)$. We want to maximise $t$, it is increasing in $a,c$, hence we may assume $a+c=n$.
With $\gamma:=c+1,\sigma:=n+1$ we find $\gamma(a\gamma+1)$ and we consider
$g(x)=x+x^2(\sigma-x)$ on $[{\sigma\over 2},\sigma]$.
Then $g$ is concave on this interval with a maximum in $x={{\sigma+\sqrt{\sigma^2+3}}\over 3}$.
Notice ${{2\sigma}\over 3}<x<{{2\sigma+1}\over 3}$ and because we consider integers,
we split up with regards to $n$ modulo 3.
If $n=3p+1$ we have $\sigma=3p+2$ and $2p+1<x<2p+2$. We need to plug in $x=2p+1,2p+2$
and check which $x$ yields the bigger value. Similarly for the other cases modulo 3.
We find \[t(3p)=4p^3+4p^2+3p+1,t(3p+1)=4p^3+8p^2+7p+2,t(3p+2)=4p^3+12p^2+14p+6\]

Let $a,b,c,d \in \mathbb{N}$ and $\frac{a}{b}+\frac{c}{d}<1$. Prove that $$\frac{a}{b}+\frac{c}{d}<1-\frac{1}{(a+c)^3}.$$


Hi,
This may sound like an obvious question, but why do you want to go to college?

I think this is a very good question, and I think the answers will be interesting and thought-provoking.

a) I love knowledge.
b) College opens up all kinds of opportunites.  There are more job choices and more opportunities for internships etc.
Pi) I loved high school so much!  Seriously though, high school was a huge part of me-in particular cross country and math team.  In college, I still get to be a part of the cross country team.  After college I just wont have many options for running competitively with a group of people so close-knit.
3) It's an adventurous, CHALLENGING experience that I can't pass up.
$\omega$) It's been indoctrinated in me for almost as long as I've been alive that I will/should go to college.

[quote="joml88"]$\omega$) It's been indoctrinated in me for almost as long as I've been alive that I will/should go to college.[/quote]
This obviously does not apply to joml88, but I will say it anyway: [u]make sure this is not your only reason[/u].

For me, it's trying to help me figure out what the heck I want to do in life.

[quote="paladin8"][quote="neelnal"]College is overrated.

Garbage men in NY make $60,000 to$80,000 a year.[/quote]

If you want to be a garbage men, by all means, go ahead. Nobody is stopping you.

Why? To learn, of course, and expand my opportunities for getting a job doing something I love doing.[/quote]

i was kidding man. i wanna do a ph.d in math

I want to go to college because I know that I wont get anywhere without a college education.  I have all sorts of ideas and theories that I want to share in college, and hopefully turn the ideas into reality.  I want to show the world the impossible is indeed possible.  A solid college education will help me show my goal.

[hide] I definetely want to go to college.I'm thinking of going to BC and getting a bachelors degree. I'm currently in middle school and I am taking Geometry. How well do i have to do on my SATs to get a scolarship in BC?
[/hide]

I wanna go to get a good job and actually get a degree in something.  :rotfl:

Why do I want to go to college?

 I want to go to college because I will earn more money, meet people with similar interests, and be the recipient of higher education. I also want to go to college because I believe that it will make me more self confident, have greater knowledge of governance, be less likely to become a criminal, be emotionally and financially secure, and have a deeper understanding of human nature. It is not just for the money. A college education makes you a rounded person. It shapes your communication skills, expands your knowledge base, and exposes you to a whole new world of learning.

[quote="Iversonfan2007"][quote="neelnal"]College is overrated.

Garbage men in NY make $60,000 to$80,000 a year.[/quote]

what are you serious? WHOA, that's like 40K dollars more than the average us income[/quote]

Yea hahaa. Depends on the area of NYcity you pick the trash up in. It is because the demand for the job is very low due to the labor and dirtiness of the job.


I'm just curious: with respect to a 2D coordinate plane, does anyone know why on a 3D coordinate plane the x and y axes are moved around?

can you clarify what you mean by the $x$ and $y$ axes are moved around? When you "draw" a three dimensional space on a piece of paper... sometimes they're "moved around" to help with perspective and that allows you to "see"

i know that it is kind of confusing because the y-axis goes towards you in 2-d, but in 3-d, it runs parallel to you

How would simply moving the 3 axes around help one to see 3D on paper?  :? And to answer dangvh's question, when drawing a 2D coordinate plane, the x axis is horizontal and the y vertical (on the paper). However, on a 3D coordinate plane (drawn on the paper), the x axis is diagonal and y is horizontal. That's what I mean by "moving around".


probability
expected value
geometric series

We construct a base 2 number as follows. First we flip a coin. If we get tails, we write a $0$ and our number is complete. If instead we get heads we write a $1$ and then flip the coin again. If tails this time, our number is complete. If heads, we continue to the next digit. For the next digit we do the exact same thing, keeping in mind that we add the digit to the right of the number. If we continue this process, what is the expected base 10 value of our number?

I get 1. Is that the answer? If I'm right I'll post soln, but it's kinda long.

That's close to what I found, but not exactly what I have. One thing to make sure you read carefully: there is an intermediate flip between the flip that determines a digit and the flip that determines the next digit. A lot of people overlook that. But post your solution if you don't see an error (maybe i made one  ;) )

To clarify: we always stop after the first tails, but half of the time it adds a 0 at the end, and half of the time it doesn't?

[hide] I also got 1. The probability of getting $0$ is $\frac{1}{2}$ (with T), getting $1$ is $\frac{1}{4}$ (with HT), getting $10_2=2$ is $\frac{1}{8}$ (with HHT), etc. So the expected value is $\frac{1}{4}+\frac{2}{8}+\frac{3}{16}+...=\boxed{1}$. [/hide]

Yeah, lotrgreengrapes has the same solution as waht i got. Nicely explained.

Yeah, if we get tails on the very first flip then we stop. In general, half the time a tails will mean to end in a $0$ and half the time a tails will indicate that we don't move to the next digit.

Ok your series is correct for the first three values shown, but you incorrectly assumed that all the following terms would be of the form $\frac{k}{2^{k+1}}$. The possible numbers are $0$,$1$,$10$,$11$,$110$,$111$,$1110$,$1111$,... Notice that when we go from 2 digit numbers to 3 digit numbers we skip from $3$ to $6$. To be more precise, the values listed above are $0$,$1$,$2$,$3$,$6$,$7$,$14$,$15$,... in base 10.

It was a bit awkward, but that's what I thought you meant.  Thanks for the clarification.

I get [hide]4/3[/hide]

that's what i got yoober  :lol:
good job. post an explanation

Here's my whole solution (it arises very easily if you draw a tree of the outcomes):
First flip is 0,1 stay if 0, flip to stay or continue for 1 and so forth (bolded steps are where it stops, giving a final number).
[b]0[/b]         /1\
       /1\         [b]1[/b]
  [b]10[/b]      /11\
      /11\      [b]11[/b]
 [b]110[/b]    .../111\...
This gives $0*\frac12 + 1*\frac14 + 2*\frac18 + 3*\frac{1}{16} + 6*\frac{1}{32} + \cdots$. Looking at adjacent terms, they're the same so we get rid of every other term and multiply the sum by 2 giving $2(\frac14 + \frac{3}{16} + \frac{7}{64} + \cdots)$. We notice that the numerators are one less than powers of 2, and the denominators are powers of 4, so rewriting in summation notation to simplify things, it becomes $\displaystyle 2*\sum \frac{2^{n+1}-2^n}{4^{n+1}}$. Separating the fraction gives two geometric series which are easily evaluated: $\frac{2^{n+1}}{4^{n+1}} - \frac{2^n}{4^{n+1}} = (\frac12)^{n+1} - (\frac12)^{n+2}=1-\frac12=\frac12$. Now, multiplying the 2 which we took out before gives a final sum of $\boxed{1}$.

It looks like we got the same series, but summed them differently. Does anyone see an error that I made?

Hokkage, just check the way you wrote your sum.
You wrote $\sum \frac{2^{n+1}-2^n}{4^{n+1}}=\sum \frac{2^n}{4^{n+1}}$. However, you said "the numerators are one less than powers of 2" so it should be $\sum \frac{2^{n+1}-1}{4^{n+1}}$

That was a dumb mistake on my part  :blush:
I must have been tired or something.
Yes, in light of my obvious mistake I agree with the answer of $\frac{4}{3}$.


[quote="Silverfalcon"]I put Hyperlink on Word and made that to PDF by CutePDF. However, Hyperlink doesn't work. Any idea?[/quote]

What it is CutePDF?

CutePDF is a program that converts the regular document into PDF.

Anyone has an idea for this? Also, is there anyway that I can put hyperlink in PDF then? I know it's possible (duh) but I don't know how to do it whenever I convert regular documents into PDFs.


geometry
parallelogram
analytic geometry
geometry unsolved

Describe a construction of quadrilateral $ABCD$ given:

(i) the lengths of all four sides;

(ii) that $AB$ and $CD$ are parallel;

(iii) that $BC$ and $DA$ do not intersect.

Let AB=a, BC=b, CD=c and DA=d, w.l.o.g.  a<c (if a=c then ABCD is a parallelogram and the construction is easy). Construct a triangle BCX, where  BC=b, BX=d and CX=c-a, then take a point D on the ray CX such that CD=c. Draw the segment AB parallel to DC such that AB=a. Since AB and DX are parallel and have the same length, then ABXD is a parallelogram and AD=BX=d. Finally, is easy to see that the cuadrilateral ABCD fullfills the conditions.

$Tipe$

Answer of Reynaldo Gil Pons:
I do it by coordinate geometry.
Let $ AB \equal{} a$, $ BC \equal{} b$, $ CD \equal{} c$ and $ AD \equal{} d$.
Let $ A(\minus{}a;0)$, $ B(0;0)$, $ C(x_C;y_C)$ and $ D(x_D;x_D)$.
But $ y_C\equal{}y_D$ because $ AB$ is parallel to $ CD$.
As $ BC\equal{}b$, then:
$ b^2\equal{}x_C^2\plus{}y_C^2\hspace{1cm}(1)$
As $ AD\equal{}d$, then:
$ d^2\equal{}(x_D\plus{}a)^2\plus{}y_C^2\hspace{1cm}(2)$
As $ CD\equal{}c$, then:
$ c^2\equal{}(x_C\minus{}x_D)^2$
As $ AD$ and $ BC$ do not intersect:
$ c\equal{}x_C\minus{}x_D\hspace{1cm}(3)$
Replacing $ (3)$ on $ (1)$:
$ b^2\equal{}(x_D\plus{}c)^2\plus{}y_C^2\hspace{1cm}(4)$
Subtracting $ (4)$ from $ (2)$:
$ b^2\minus{}d^2\equal{}2x_D(c\minus{}a)\plus{}c^2\minus{}a^2$
And: $ x_D\equal{}\frac{b^2\minus{}d^2\minus{}c^2\plus{}a^2}{2(c\minus{}a)}$
Then we can calculate $ x_C$ and $ y_C$ in terms of $ a$, $ b$, $ c$, $ d$. However the problem is solved.


Evaluate $ \frac{1}{2\pi i} \oint \frac{1}{(z\plus{}2)(z\minus{}i)^{2}} \ dz$ around $ |z\minus{}1| \equal{} 2$.

This has two singularities at $ z_1\equal{} \minus{}2$ and $ z_2 \equal{} i$. $ z_1$ is on $ C$ which $ z_2$ is in $ C$. In the answer, it just works with the Extended Cauchy Integral Formula for $ z_2 \equal{} i$. What about $ z_1$? That is also a singularity, so why can't we just apply the regular Cauchy Integral Formula?

There is a difference between singularities inside the loop and singularities outside the loop.

but one singularity is [b]on[/b] the loop while the other singularity is [b]in[/b] the loop. Neither is outside the loop. So for the singularity which is [b]in[/b] the loop we use the Extended Cauchy Integral Formula. While for the singularity [b]on[/b] the loop, can we use the Cauchy Integral Formula?

And please keep this question in this section. Because no one visits the Complex Analysis section.

I'm not a moderator- but a moderator [b]will[/b] move this.

It's not on the loop. $ |1\minus{}(\minus{}2)|>2$.

Then how come when I draw it, it is on the loop? I have the circle centered at $ z_0 \equal{} 1$. Ok I get it.


I'd say go for the pure sciences degree.

[quote="satyam"]Is it a better idea to get a PhD in Math or to get a MS in financial engineering if you want to become a quant? Also, how long does it usually take to get those degrees and are there any exams that you need to pass in order to quality as a quant?
Any help will he appreciated.[/quote]

No specific exams to 'qualify' as a quant like there are for the actuaries.

PhD in math takes a lot longer than an MS in financial engineering.  I don't know much about the latter; it's a fairly new degree.  Also, it depends on where you want to work.  Hedge funds seem to go more for the folks with pure science degrees.  That said, they aim more at the people with applied knowledge (e.g. physics) than at the pure math people.

Whatever route you go, learn how to program.

[quote="maokid7"]so if i am a pure math major...that takes classes in physics and other applied fields and programming as well i should be fine right?[/quote]

If you do well in them, etc., then you should be ok.  Try to get an internship after your junior year, if not earlier.

do the top hedge fund managers tend to have math and science degrees rather than degrees in economics or finance as well, or is it mainly in the employees that they look for such people?


let the sequence $ a_n$:
$ a_1\equal{}1$ and $ a_2\equal{}7$ and $ a_{n\plus{}2}\equal{}1/a_n (a_{n\plus{}1}^2\minus{}1)$.
prove that $ 1\plus{}9a_{n\plus{}1}a_n$ is a square of integer.

It's easy to check the fomular $ a_{n\plus{}2}\equal{}7a_{n\plus{}1}\minus{}a_{n}$
Next, prove by induction $ 9a_{n}a_{n\plus{}1}\plus{}1\equal{}(a_n\plus{}a_{n\plus{}1})^2$

$ a_{n} \equal{} \frac{F_{4n}}{3}$ and $ 9 a_{n} a_{n\plus{}1} \plus{} 1 \equal{} (F_{4n\plus{}2})^2$
($ F_{n}$ is Fibonacci sequence)

you are right,hjen! :wink:
here is my full solution:
$ a_{n\plus{}2}\equal{}7a_{n\plus{}1}\minus{}a_{n}$ (->easy to see it)
we have:
$ a_{n\plus{}2}\minus{}3/2.a_{n\plus{}1}\equal{}3/2.a_{n\plus{}1}\minus{}a_{n}$
then we have:
$ a_{n\plus{}1}^2\minus{}3.a_{n}.a_{n\plus{}1}\plus{}a_{n}^2\equal{}a_{1}^2\minus{}3.a_{1}.a_{0}\plus{}a_{0}^2$
It is enough for every body! :oops:

[quote="Math pro"]\we have:
$ a_{n \plus{} 2} \minus{} 3/2.a_{n \plus{} 1} \equal{} 3/2.a_{n \plus{} 1} \minus{} a_{n}$
then we have:
$ a_{n \plus{} 1}^2 \minus{} 3.a_{n}.a_{n \plus{} 1} \plus{} a_{n}^2 \equal{} a_{1}^2 \minus{} 3.a_{1}.a_{0} \plus{} a_{0}^2$
It is enough for every body! :oops:[/quote]
Why ??.the proof whichis used Fibonaci sequence is nice and quite natural but but with yours ,i cant understand those lines


calculus
integration
derivative
real analysis
real analysis unsolved

Derivative of $ \sqrt{1+e^{x}+e^{2x}}$ is given by

$ \frac{d}{dx}\sqrt{1+e^{x}+e^{2x}}\; = \; \frac{\sqrt{1+e^{x}+e^{2x}}}{2}+\frac{e^{2x}-1}{2\sqrt{1+e^{x}+e^{2x}}}.$

So

\begin{eqnarray*}\int \sqrt{1+e^{x}+e^{2x}}\; dx & = & 2\sqrt{1+e^{x}+e^{2x}}-\int \frac{e^{2x}-1}{\sqrt{1+e^{x}+e^{2x}}}\; dx\\ & = & 2\sqrt{1+e^{x}+e^{2x}}-\int e^{\frac{x}{2}}\frac{e^{x}-e^{-x}}{\sqrt{e^{x}+e^{-x}+1}}\; dx\\ & = & 2\sqrt{1+e^{x}+e^{2x}}-\int 2e^{t}\frac{e^{2t}-e^{-2t}}{\sqrt{e^{2t}+e^{-2t}+1}}\; dt \quad \quad (x = 2t)\\ & = & 2\sqrt{1+e^{x}+e^{2x}}-\int \frac{8\sinh^{2}t \cosh t}{\sqrt{4\sinh^{2}t+3}}\; dt-\int \frac{8\sinh t \cosh^{2}t}{\sqrt{4 \cosh^{2}t-1}}\; dt\\ \end{eqnarray*}

Last two integrals can be computed using substitutions $ 2 \sinh t = \sqrt{3}\sinh u$ and $ 2 \cosh t = \cosh v$, respectively. But I will not proceed this calculation.

p.s. I tried to solve it using series expansion for more than 2 hours, only realizing that it just yields terribly messy formulas.


geometry
analytic geometry
geometry unsolved

Let $ P$ be an interior point of a triangle with sides $ a,b,c$ in which lines parallel to the sides of the triangle are traced. THe segments of the parallels delimited by the sides of the triangle have the same length. Find its value.

[hide="Answer"]
$ \frac{2abc}{ab\plus{}bc\plus{}ac}$
[/hide]

Let the desired segment be $ d$, and let the perpendiculars from $ P$ to the sides be $ n_a,n_b,n_c$ respectively. Then

$ {d\over a} \equal{} {h_a \minus{} n_a\over h_a} \equal{} 1 \minus{} {n_a\over h_a}$

Summing those up, we get $ d\left(\frac 1 a \plus{} \frac 1 b \plus{} \frac 1 c\right) \equal{} 3 \minus{} \left({n_a\over h_a} \plus{} {n_b\over h_b} \plus{} {n_c\over h_c}\right)$

The expression in the parentheses on the RHS is equal to $ 1$, which is easily proven if $ h_x$ is substituted by $ {2A\over x}$, where $ x\in\{a,b,c\}$ and $ A$ is the area of the triangle. After that, the result follows.

Let $(u:v:w)$ be the normalized  barycentric coordinates of $P$ WRT $\triangle ABC.$ Then lengths of the paralell sections from $P$ to $BC,CA,AB$ are given by

$d_a= a(1-u) \ \ , \ \ d_b=b(1-v) \ \ , \ \ d_c=c(1-w)$

Solving $a(1-u)=b(1-v)=c(1-w),$  together with $u+v+w=1$ gives

$P \equiv \left( \frac{1}{b}+\frac{1}{c}-\frac{1}{a}:\frac{1}{a}+\frac{1}{c}-\frac{1}{b}:\frac{1}{a}+\frac{1}{b}-\frac{1}{c} \right) \Longrightarrow$

$X_{192} \equiv 3 \cdot X_2-2 \cdot {X_1}^{-1} \equiv \left (\frac{1}{b}+\frac{1}{c}-\frac{1}{a}:\frac{1}{a}+\frac{1}{c}-\frac{1}{b}:\frac{1}{b}+\frac{1}{a}-\frac{1}{c} \right)$

Thanks a lot guys, that is very helpful.

luis, I am not accustomed to this notation you use but I would like to understand how you solved this problem.

Is this really a simple solution that I would understand if I understood the notation or does it involve more than basic concepts?


inequalities
induction
parameterization
combinatorics proposed
combinatorics

For a graph $G$, let $\nu(G)$ be the maximal number of edges s.t. no two of them have a common endpoint, and let $\rho(G)$ be the minimal number of edges to cover all the vertices (an edge covers a vertex if that vertex is one of the endpoints of the edge). If the simple undirected graph $G$ has $n$ vertices which are not isolated, show that $\nu(G)+\rho(G)=n$.

I'm sure you people will find this easy, but I thought it was a rather nice fact.

isn't it  just $v(G)=p(G)=\frac{n}{2}$ ? Anyway it's a nice fact

It's definitely not always like that (there are situations when they're not both $\frac n2$).. Had it been like that, it would have been really stupid of me to post it :D.

ok - I've posted it almost without being careful. But I think it is $v(G)=p(G)=\frac{n}{2}$ when $n\equiv0 \ (mod \ 2)$ and $v(G)=[\frac{n}{2}]$   $p(G)=[\frac{n}{2}] + 1$ when $n\equiv1 \ (mod \ 2)$

No Megus : Consider the graph with 4 vertices $A,B,C,D$ and edges $AB,AC,AD$.
Then $\nu (G) = 1$ and $p(G) = 3$.

Pierre.

Megus! You aren't realizing how much you wrong. ;)
$\nu(G)=n/2$ corresponds to complete matching in graph $G$. Why do you think Hall invented his theorem?  :)

Holy **** ! Now I'm realizing how wrong was I  :blush:  - eh - next time I'll think twice  :maybe:

[color=red][[b]Moderator edit:[/b] In this posting, $p$ means what grobber denoted by $\rho$ in the original post.][/color]

Let $G$ be a graph with $n$ vertices.
Let $\nu (G) = k$ and consider a maximal set $E$ of pairwise disjoint $k$ edges. Thus, these edges uses exactly $2k$ vertices from $G$. Since no vertex is isolated and from the maximality of $k$, it left $n-2k$ vertices, each of which are connected by an edge to at least one of the endpoint of an edge belonging to $E$. Thus, choosing one of these edges per vertex among the $n-2k$ and using the $k$ edges from $E$, we cover all the vertices. The minimality of $p(G)$ leads to $p(G) \leq (n-2k)+k = n-k$ so that $p(G)+ \nu (G) \leq n$.

Now, we prove the reverse inequality by induction on the number $a$ of edges in $G$.
Since no vertex is isolated, we have $a \geq [ \frac {n+1} 2]$.
If $a = [ \frac {n+1} 2]$ then for even $n$ it means that each vertex belongs to exactly one edge, so that $p(G) = a = \nu (G)$, so that $p(G) + \nu(G) = 2a = n$. And, for odd $n$, it means that each vertex except one, say $v$, belongs to exactly one edge and $v$ belongs to two edges. Thus, $p(G) = a = \frac {n+1} 2 $ and $\nu (G) = a-1$ so that $p(G) + \nu (G) = 2a-1 = n$. Therefore, we are done in the case where $a = [ \frac {n+1} 2]$.

Now assume the desired inequality holds for each graph with $n$ vertices (none isolated) and at most $a-1$ edges. Let $G$ be such a graph with $a$ edges.
Let $F$ be a set of $p(G)$ edges which cover each vertex from $G$.
- If $p(G) = a$ then we have to choose all the edges so as to cover all the vertices. Moreover, with the edges from $F$ we cannot form a cycle otherwise we could omit one edge from the cycle without losing the covering, which would contradicts the minimality of $p(G)$. It follows that $G$ is a forest, which means that each of its connex components is a tree (with at least two vertices in each component, since no vertex is isolated). If there are at least two components, then we may use the induction hypothesis on each of the components, and sum all the correspondant inequalities (clearly $p(G)$ (resp. $\nu (G)$) is the sum of the analog parameter for each component). If there is only one component, then $G$ itself is a tree, so that $a=n-1$. Since, we obviously have $\nu (G) \geq 1$, we are done again.
- If $p(G) < a$ then consider the graph $G'$ whith the same vertices than $G$ but only the edges from $F$. Since each vertex is covered, there is no isolated vertex. Then we may use the induction hypothesis to deduce that $p(G') + \nu (G') \geq n$.
But, from the minimality of $p(G)$ we have $p(G') = p(G)$, and clearly $\nu(G') \leq \nu(G)$ and the conclusion follows.
This ends the induction step.
Therefore $p(G) + \nu (G) \geq n$, and we are done.

Pierre.

P.S. Please, Grobber stop apologize when posting a graph problem ;)

Sorry for apologizing. :D:D

I seem to have done almost the same thing. Thanks for the solution.

:?  Oh...I was hoping that there was a direct proof of the equality (not using the two inequalities).

Pierre.

[quote]
then we may use the induction hypothesis on each of the components, and sum all the correspondant inequalities
[/quote]

Hmmm...to be rigourous, I have to use a double induction in the above proof :
First on $n$  : the case $n = 2$ is trivial, then we assume ($H_1$) that the inequality holds for all $i \leq n-1$.
Then, on $a$ as done above ($H_2$). The induction hypothesis in quote is then $H_1$. And the one used for $G'$ is $H_2$.

Pierre.

Well, the problem is much easier.

For any matching with $k$ edges, choose for the $n-2k$ unoccupied vertices some edge to cover them. This gives a covering with $k+(n-2k)=n-k$ edges, thus proving one inequality.

For any covering with $k$ edges, choose a maximal submatching(that means all edges of the matching are edges of the covering and no more edges from the covering may be added to give a matching); let it have $l$ edges. Then the $n-2l$ uncovered vertices all belong to some edge of the covering. Choosing for every uncovered vertex such an edge, no edge can be taken twice by the maximality of the matching. Thus $k\geq l+(n-2l)=n-l$ thus proving the other inequality.

Peter


Let $ A_0 A_1 ... A_{n\minus{}1}$ be a regular $ n$-gon inscribed in a circle with radius $ r$. Prove that for every point P of the circle and every natural number $ m<n$ we have:
$ \sum_{k\equal{}0}^{n\minus{}1} PA_k^{2m}\equal{}\binom{2m}{m}nr^{2m}$

Anyone can help me with this? Please try it.


algebra
polynomial
advanced fields
advanced fields theorems

What would constitute the easiest proof of this theorem ? I would like to have a look since I am using it (implicitely) to determine Galois groups of certain irreducible polynomials of $\mathbb{Q}[X]$.

I have read a proof which is a mixture of Artin's reciprocity law, Chebotarev's proof for the Frobenius conjecture, and Deuring's reduction to the cyclic case. The proof is quite a long, 15 pages, but rather elementary.


hallo,
Let $a, b \in N$ s.t. $\frac{a+1}{b}+\frac{b+1}{a} \in N$. Let $x=gcd(a, b)$. Prove:
\[ x^2 \le a+b. \]

 :)

[hide]Suppose that $gcd(a,b)=x$ then $a=a_1x$ , $b=b_1x$ where $gcd(a_1,b_1)=1$[/hide]

$ab \mid a^2 + b^2 + a + b = (a + b)^2 - 2ab + a + b$ $\Longrightarrow$ $ab \mid (a + b)(a + b + 1)$.
Let $a = xh$ and $b = xk$. Then $x^2hk \mid (a + b)(a + b + 1)$.
If $x = 1$ it's trivial. So suppose $x > 1$. Then $x^2 \mid a + b$ from which $x^2 \leq a + b$.


vector algebra polynomial integration calculus function derivative

Let V be the vector space of all polynomials over R with scalar product defined as:  $ \displaystyle \langle f(t); g(t) \rangle \equal{} \int_{0}^{1}{f(t)g(t)dt}$ Prove that the operator D defined as $ D(f) \equal{} \frac {df}{dt}$ has no adjoint operator

If $ D$ had an adjoint operator $ D^*$, we would have the following:

$ \langle f,g'\rangle \equal{} \langle D^*f,g\rangle.$

But we actually have this (by integration by parts):

$ \langle f,g'\rangle \equal{} \minus{}\langle f',g\rangle\plus{}f(1)g(1)\minus{}f(0)g(0).$

Let's be very particular: let $ f(x)\equal{}x.$ Then $ \langle x,g'\rangle \equal{}\minus{}\int_0^1g\plus{}g(1).$

So, hypothetically, if $ h\equal{}D^*(f)$ where $ f(x)\equal{}x,$ then for all $ g$

$ \int_0^1hg\equal{}\minus{}\int_0^1g\plus{}g(1),$ or $ \int_0^1(h\plus{}1)g\equal{}g(1).$

Now let $ g(x)\equal{}x^n.$ We have

$ \left|\int_0^1(h\plus{}1)g\right|^2\le\int_0^1(h\plus{}1)^2\cdot\int_0^1x^{2n}\equal{}
\frac1{2n\plus{}1}\int_0^1(h\plus{}1)^2.$

This can be made arbitrarily small by letting $ n$ be sufficiently large. But at the same time this had to be equal $ (g(1))^2\equal{}1.$ Since we can't do that, then there is no such (polynomial) function $ h$ and thus $ D^*$ can't be defined.

If the vector space were polynomials such that $ f(0)\equal{}f(1)\equal{}0,$ then the derivative operator would have an adjoint.


geometry
3D geometry
probability
sphere
rectangle
rotation
modular arithmetic

1. Three large cubes with sides 1m, 3 m, and 5m, are glued together at their faces. What is the least possible surface area of the resulting solid figure?

2. You are given six 2-meter wide walls to fully surround the lion, You are tasked to enclose him with the largest possible area without breaking the walls. What is the largest possible area?

3. Which positive integer becomes 57 times smaller when removing the leftmost digit?

4. Let A be the set of all integers from 23 to 99. If S is any six-element subset of A, how many possible values are there for the sum of the elements in S?

5. Mr. Lee awards extra credit to his students with quiz grades that are higher than the class mean. Given that 87 students take the same quiz, what is the largest number of students who can be awarded extra credit?

6. Tom randomly selects two distinct numbers from the set {1, 2, 3, 4, 5} and Steve randomly selects a number from the set {1, 2, 3,...., 9, 10}. What is the probability that Steve's number is larger than the sum of the two numbers selcted by Tom?

7. Two equal squares ABCD and DEFG have vertex D in common. The angle of CDG is 60. Find angle CFE.

8. The price of gum has skyrocketed in recent years. Each year for the last 7 years the price has increasedm and the new price is the sum of the prices of the two previous years. Last year, a piece of gum costs 60 cents. How much does a price of gum cost today?

9. A cylindrical barrel 50cm high with a radius of 18cm is filled with water up to 1cm from the brim.A solid sphere with radius 9cm is placed into the water so that the water level rises and some water spills out. If the sphere is half submerged underwater, how much water has spilled out?

10. Rectangle PQRS lies in plane with PQ=RS=2 and QR=SP=2. The rectangle is rotated 90 degrees about R, then rotated 90 degrees clockwise about the point that S moved after the first rotation. What is the length of the path travled by point P?

11. During a chicken-spaghetti day, people go to the restaurant to eat either chicken, spaghetti,or both chicken and spaghetti. If 1/3 of those who ate spaghetti also ate chicken, and 1/5 of those who ate chicken also ate spaghetti, what fraction of the people ate spaghetti only?

12. John can cross a river on his boat in 5 min. James can do it in 7 min. If they go back and forth from one side of the river to the other, and if they simultaneously cross the river, how many times would they meet in 35 min?

13. A, B, and C each had a bag of candies. A gave B candies equal to half of what C had. Then B gave C candies equal to half of what A now had. B ended up with 17 candies. A now had a number of candies equal to what C originally had, while C now had a number of candies equal to what A originally had. If there were 57 candies all in all, how many candies did C originally have?

14. Suppose that today, the last Friday of this month is on the 24th day of that month. The first day of the next month is a Thursday. What month is it now?

[quote="orangefronted"]
3. Which positive integer becomes 57 times smaller when removing the leftmost digit?[/quote]

[hide="Solution"]
=====
Let the resulting number after the leftmost digit is removed be $ n$. Clearly $ n\neq 1$, so $ 57n$ has at least three digits. Suppose $ 57n$ has exactly three digits. Then $ n \equiv 57n \pmod{100} \implies 56n \equiv 0 \pmod{100} \implies 14n \equiv 0 \pmod{25}$. Since $ (14,25)\equal{}1$, $ 25|n$. But for $ n\geq 25$, $ 57n$ has more than three digits. So suppose $ 57n$ has exactly four digits. Similar to above, we find $ 56n \equiv 0 \pmod{1000} \implies 7n \equiv 0 \pmod{125}$, so $ 125|n$. Trying $ n\equal{}125$, we find $ 57n\equal{}\boxed{7125}$, which works.
=====
[/hide]

14. Suppose that today, the last Friday of this month is on the 24th day of that month. The first day of the next month is a Thursday. What month is it now?

Today is the 24th, and the month ends in five days (Saturday-Wednesday is a five-day period).  Therefore, the month has a total of 29 days.  The only month with 29 days is $ \boxed{February}$ (during leap years).

Yes I think so.. They are not that simple though.

Thanks for the answers...12 more to go... :o  :o

1.the reduction of surface area can happen only when the surfaces of two different cubes touch. Between any two cube at maximum one surface of each cubes can touch each other, so the area reduction is at most twice the area of one of the surface of the smaller cube. So total area is at least 6*(25+9+1)-2*(1+1+9)=188. Obviously this can be achieved.

[hide="1"]the total surface area is $ 6\cdot 1^2 + 6\cdot 3^2 + 6\cdot 5^2 = 210 m^2$.  Now we wish to attach these cubes together to cover the most amount of surface area.  Gluing the 5m cube to the 3m cube covers $ 2 \cdot 3^2 = 18 m^2$ of surface area.  Now we can attach the 1m cube at any point.  We want to cover as many of its surfaces as possible, so we glue it in the corner of the 3m and 5m cube, covering an additional $ 4m^2$ of surface area.  Thus the minimum area is $ 210-18-4= 188$ square meters.[/hide]

[hide="2"]a regular shape always gives the greatest area for perimeter, for a given number of sides.  A circle gives the greatest area for its "perimeter" (circumference).

So we arrange the walls into a regular hexagon.  the area of a regular hexagon is the are of $ 6$ equilateral triangles with the same side length, so we have $ 6 \cdot \frac{(2)^2\sqrt{3}}{4} = 6\sqrt{3}$ square meters.[/hide]

[hide="4"]Claim: we can obtain any value between $ 153$ and $ 579$ for a sum of a six element subset.

Take the first 6 consecutive integers.  Then we have $ 23+24+25+26+27+28 = 153$.  We can then change the $ 28$ to $ 29$, $ 30$, $ 31$, $ 32$, and $ 33$.  Then we can take the set of consecutive integers starting with $ 24$, giving a sum one larger than we just had with $ 23+24+25+26+27+33$.  Continuing this process, we can get all the way up to $ 89+90+91+92+93+99$.  Then we can increase the penultimate number by 1, and then the 4th number by one, etc down to the first number, and then go back and increase the penultimate number again, and continue in this fashion until reaching $ 94+95+96+97+98+99 = 579$

So the sum of any 6 element subset in A can be any integer in $ [153,579]$ for a total of $ 579-153+1 = 427$ possible values.
[/hide]

[hide="5"]
The "optimal" case is when the distribution is skewed left so the mean is lower than the median.  The best way to drag the mean down is to have as many kids as possible get $ 0$'s on the quiz.  But at the same time we want as many as possible to beat the mean.

So suppose some people get 0's on the quiz.  If even one person got a zero, and the other $ 86$ students got the same score, then the mean is slightly lower than the score that these $ 86$ students got.  So the maximum number of students getting the extra credit is $ 86$.  Though this is possible, it is highly unlikely to actually happen.
[/hide]

[hide="6"]
Tom has the possible choices: (the sums are a set of chosen numbers)
$ 1+2=3$
$ 1+3 = 4$
$ 1+4=2+3=5$
$ 1+5=2+4=6$
$ 2+5=3+4=7$
$ 3+5=8$
$ 4+5=9$

So Tom has $ 10$ possible choices.  If Tom chooses a sum of $ n$, then steve has a $ 10-n$ ways of choosing a number larger than the sum of tom's numbers.  Let $ p(n)$ be the numbe of ways for Tom to chose a sum of $ n$.  Then the probability we want is:

$ \sum_{n=3}^{9}\frac{p(n)}{10}\cdot \frac{10-n}{10} = 1/10 \cdot 7/10 + 1/10 \cdot 6/10 + 2/10 \cdot 5/10 + 2/10\cdot 4/10 + 2/10 \cdot 3/10 + 1/10 \cdot 2/10 + 1/10 \cdot 1/10$
$ = \boxed{2/5}$
[/hide]

[hide="7"]
The squares are congruent, not equal.  Anyway, this tells us that they have the same side length.  $ \angle CDG \cong 60^\circ$ tells us that $ CG$ is the same length as the sides of the squares; thus, $ \triangle CDG$ is equilateral, so $ \angle CGD = 60^\circ$.  Now $ \angle DGF = 90^\circ$ so $ \angle CGF = 60+90 = 150^\circ$.  Since $ CG =FG$, $ \angle CFG = \angle GCF$.  Since the sum of the angles in a triangle is $ 180^\circ$, using $ \triangle CGF$ we see that $ \angle GFC = (180-150)/2 = 15^\circ$.  Now $ \angle GFE = \angle GFC + \angle CFE$.  $ \angle GFE=90^\circ$, so $ \angle CFE = 90-15 =  \boxed{75^\circ}$
[/hide]

[hide="8"]
Let the price of gum $ 8$ and $ 9$ years ago be $ x$.  Then the price of gum $ 7$ years ago was $ 2x$, $ 6$ years ago was $ 3x$, $ 5$ years ago was $ 5x$, $ 4$ years ago was $ 8x$, $ 3$ years ago was $ 13x$, $ 2$ years ago was $ 21x$, $ 1$ year ago was $ 34x$, and now is $ 55x$.  So we have $ 34x=60 \implies x=60/34$ and the price of gum is now $ 55\cdot60/34$ which is approximately $ 97$ cents.

I'm not totally sure about this... I'm not sure if I started off the problem correctly.  But either way we are finding $ 60$ time some ratio of the fibonacci numbers, and this ratio approaches $ \frac{1+\sqrt{5}}{2}$ quick enough that the gum price only changes a small fraction of a cent if we start from the wrong year.
[/hide]

[hide="9"]
First, we need to know how much volume half the sphere is.  The volume of a sphere is$ V=4/3 \pi r^3$, so we have $ 1/2 \cdot 4/3 \pi (9)^3 = 486 \pi$ cubic centimeters of space taken up.  This is no different than adding $ 54 \pi$ cubic centimeters of water to the barrel.  Now the barrel can hold an additional $ v=\pi r^2 h = \pi (18)^2 \cdot 1 = 324 \pi$ cubic centimeters of water.  Therefore, $ 486\pi-324\pi = 162\pi \approx 508.938$ mL of water spill out (1 cubic centimeter is 1 mL).
[/hide]

[hide="10"]
First of all, this rectangle is really a square.

The direction of the rotation does not matter.  In each rotation, $ P$ travels along an arc of a circle, whose radius is determined by the distance of $ P$ from the point we are rotating around, whose measure is the measure of the rotation.  Both rotations are $ \pi/2$ radians (90 degrees); $ PR = 2\sqrt{2}$ and $ PS = 2$.  The formula for arc length is $ s=r\theta$ with $ \theta$ in radians.  So $ P$ has moved $ 2\sqrt{2} \cdot \pi/2 + 2 \cdot \pi/2 = \pi (\sqrt{2}+1)$.
[/hide]

[hide="11"]
If the number of people who ate both is $ x$, then $ 4x$ ate only chicken and $ 2x$ ate only spaghetti, for a total of $ 7x$ people.  Therefore, $ \boxed{2/7}$ of the people only ate spaghetti.
[/hide]

what does "meet" mean in #12? do you mean end up on the same side of the river? because this clearly only happens at the beginning and at the end (they both cross an odd number of times).  Anyway I'll assume you mean "pass" when you say "meet".  Anyway, I'm not sure If I interpreted this correctly.
[hide="12"]

John would cross the river a total of $ 7$ times, and would meet Jack every time he crossed (except when they started together) for a total of $ 6$ meetings.
[/hide]

[hide="13"]
Let $ a$, $ b$, and $ c$ be the number of candies that A, B and C respectively start with.  Now lets keep score:

1st step: A gave B candies equal to half of what C had.
A: $ a-1/2 c$
B: $ b+1/2c$
C: $ c$

2nd step: B gave C candies equal to half of what A now had.
A: $ a-1/2 c$
B: $ b+1/2c - 1/2(a-1/2c)$
C: $ c + 1/2(a-1/2c)$

Now we have the system:
A: $ a-1/2 c  = c$
B: $ b+1/2c - 1/2a+1/4c= 17$
C: $ 3/4c + 1/2a = a$
$ a+b+c = 57$

from C we obtain $ 3/2c = a$
from A we obtain the same.
from B we obtain $ b-1/2a+3/4c = 17 \implies 4b-2a+3c = 68$.
$ 4b-2(3/2 c)+3c = 68 \implies 4b=68 \implies b=17$

Therefore $ a+b+c = 57 \implies a+c = 40$
$ 3/2c+c = 40 \implies 5/2 c=40$
$ c=\boxed{16}$
[/hide]

:)


well... $n^2+n=n(n+1)$

so we start with the base case, when $n=1$.
$1\cdot2 = 2$, so it is true.

Now, let's say it works for some number $k$. Then $k(k+1)$ is an even number
We need to prove that it also holds true for $n=k+1$. That means we need to prove that $(k+1)(k+2)$ is diivisble by 2.

Let's go back. $k(k+1) = k^2+k$
then $(k+1)(k+2) = k^2+3k+2 = (k^2+k)+(2k+2) = (k^2+k)+2(k+1)$

Since both $k^2+k$ and $2(k+1)$ are divisible by 2, we are done. QED.

jenybeny, I'd just like to add something.  reddevilz's solution is impeccable, but I'm not sure you understand exactly what mathematical induction is.

You said [quote]The method we were taught was by setting n=k and then assume true for n=k+1 .... but I can't figure this one out! [/quote]

No, you don't assume it's true for $n=k+1$

What you do is the following: First, you show it works for $n=1$.

Then, you assume it works for $n=k$ (called the INDUCTION HYPOTHESIS) and show it works for $n=k+1$

This works because you've shown it works for $n=1$ in step 1, so by step 2, it works for $n=2$.  Then, by step 2 again, it works for $n=3$.  And then, by step 2 again, it works for $n=4$ ad infinitum (is that the right expression, anyone?).

Thus, by going through just these two steps, you've shown it works for all natural numbers n.

[quote="bubala"]What you do is the following: First, you show it works for $n=1$. [/quote]

It is called the base case, and you dont have to use $1$. In some cases it might be easier to use other number, simply because of simplifying thingy.

o yea, and by the way, I dont think this belongs here. Probably Intermediate Section.

[quote="Peter VDD"][quote="xxreddevilzxx"]well... $n^2+n=n(n+1)$[/quote]You can stop there. Either n or n+1 is always even.[/quote]

Not if what is requested is a proof by induction, Peter.

It works for 1: 1(2) is even
Now assume that it works for n.  Then either n or n+1 has to be even.
Now let's see if it works for n+1.  The number in question is then (n+1)(n+2).
If n was originally even, then we now have n+2 again, which must be even because an even number was added.
If n+1 was originally even, then the new number is even still.

[quote="Jenybeny27"]I cannot figure out how to do this problem at all. I've been working on it, and for some reason I can't solve it.

Use mathematical induction to prove for n >= 1 and n an integer, n 2 +n is divisible by 2.

The method we were taught was by setting n=k and then assume true for n=k+1 .... but I can't figure this one out!

Please![/quote]

Well, to use induction, I guess you have to go far but I agree with Peter on general idea.

[hide="What I think.."]

Since $n^2+n = n(n+1)$ and no matter what $n$ is, $n+1$ and $n$ are in different parity and this means that one is even and other one is odd (doesn't matter which is which) so it's going to be divisible by 2.[/hide]


Consider O = {1, 3, 5, 7, . . .} the set of odd integers.  Define an operation ~ on O by the following rule:
a~b = the odd part of (a + b).  For example,
7~5 = the odd part of 12 = 3
3~11 = the odd part of 14 = 7
3~5 = the odd part of 8 = 1

1) Prove  a*(b~c) = (a*b)~(a*c)
2) Is ~ commutative?  That is, does a~b = b~a?
3) Is ~ associative?  That is, does a~(b~c) = (a~b)~c?
4) Consider any odd numbers a and b.  Prove that there exists an odd number x such that a~x = b.
5) Define f(x) = x~1.  Is it true that for any odd number x, if we continually apply f we will enventually get 1?
For example:  x = 9
f(9) = 5, f(5) = 3, f(3) = 1, done.
f(7) = 1, done.
f(97) = 49, f(49) = 25, f(25) = 13, f(13) = 7, f(7) = 1, done.
Will this always happen?

Sol'ns for 1 and 2; 3 forthcoming when I wake up.

[hide]Let D (n) represent the "odd part" - i.e. the greatest odd divisor of n. Then a ~ b = D (a + b).

Observe that if a = 2m * k where n :ge: 1, k is an positive integer (not necessarily odd), then D (a) = D (k).

Then,

1) Observe that a, b and c must all be odd in order for the question to make sense. (a * b) ~ (a * c) = D (a * (b + c)). Let b + c = 2m * k, k is odd. Then D (a * (b + c)) = D (ak * 2m) = D (ak) = ak.

a * (b ~ c) = a * D (b + c) = a * D (2m * k) = ak.

2) This is obvious (D (a + b) = D (b + a)).

To be continued...[/hide]

[hide]Yes. Since the answer is always odd and always less than x, the numbers will gradually converge on the least odd number, 1. There are no cycles of more than 1 number, since a cycle would involve the numbers involved increasing, and the greastest odd divisor is never greater than the number in question. The number will never repeat until 1 is reached, since that would require the greatest odd divisor of x+1 to be x. Only possible for 2.[/hide]

Solution  to 3 in spoiler:[hide] The case a=1 b=3 c=5 is a contradiction.

1~3=1

1~5=3

BUT

3~5=1

1~1=1

3 isn't 1.

So no.[/hide]

Solution to 4, also in spoiler:[hide]The problem is basically saying "If you have 2 odd numbers, a & b, is there always a number" (x) "that you can add to a to make b a's greatest odd divisor?" There will always be a number x to add to a so that a=2 (or 3 or whatever, until you get the greatest odd divisor) b. Then, b is a's greatest odd divisor.[/hide]


For the LHS, Since $ x_i$ is a permutation shouln't it be $ \ge 2004$ by AM-GM.


Unfortunately, there is big conflict between AIME I and NJ Science Olympiad State Competition.   What are you going to do if you plan to take AIME and you are in NJ Science Olympiad State Competition?

In theory, they should be the same level.

[quote="spse"]Do you think AIME II is harder than AIME I?[/quote]No -- they are intended to be the same level of difficulty.

They will average the same level of difficulty - the AMC makes up two essentially equal-difficulty tests, the AIME A and the AIME B, and flips a coin to determine which will be the I and II.

I highly suggest that you read the rules on AMC Pamphlet for this year and carry out the procedures for alternate testing so you do not end up missing the AIME! Good luck on both of exams.


abstract algebra
calculus
integration
calculus computations

We know that the Dirichlet kernel $ D_n(y) \equal{} \frac {1}{2\pi}\sum_{k \equal{} \minus{} n}^{n}e^{iky}$. The integral $ \int_{ \minus{} \pi}^{\pi}D_n(y)\ dy$ "should" be 1. But my calculations tell me that it is $ 0$.
Here what I did:
\[ \int_{ \minus{} \pi}^{\pi}D_n(y)\ dy \equal{} \int_{ \minus{} \pi}^{\pi}\frac {1}{2\pi}(\sum_{k \equal{} \minus{} n,k\neq 0}^{n}e^{iky})\ dy \equal{}
\]

\[ \frac {1}{2\pi}\sum_{k \equal{} \minus{} n,k\neq 0}^{n}([\frac {sin(ky)}{k}]_{ \minus{} \pi}^{\pi} \minus{} i[\frac {cos(ky)}{k}]_{ \minus{} \pi}^{\pi}) \equal{} 0
\]
What do I do wrong ?  :|

[quote="Amazigh"] Dirichlet kernel $ D_n(y) \equal{} \frac {1}{2\pi}\sum_{k \equal{} \minus{} n,k\neq 0}^{n}e^{iky}$. |[/quote]

Why did you remove the term $ k\equal{}0$ from the sum? As I recall, that term makes your integral $ 1$ :wink: .


[quote="Yongyi781"]First, calculate the velocity of the 6kg box just before it hits the ground. We have four forces: $ m_1g,m_2g,F_{T1} \equal{} m_2g,F_{T2} \equal{} m_1g$. Since $ m_1 \equal{} 6$ and $ m_2 \equal{} 2$, the net force on the 6kg box will be $ 4g$ down, and thus the 6kg box will accelerate at $ \frac 23 g\ \mathrm{m/s^2}$.

The velocity of the 6kg box just before it hits the ground is $ \sqrt {\frac 43 g} \equal{} \frac 23 \sqrt {3g}$ down because $ v^2 \equal{} 2ax,a \equal{} g,x \equal{} 1$. Therefore, the velocity of the 2kg box will also be $ \frac 23 \sqrt {3g}\ \mathrm{m/s}$ up. At this point, there will be no more tension in the string, so the only force acting on the 2kg box will be gravity, $ 2g\ \mathrm{m/s^2}$ down. (Also, the 2kg box is 2 meters in the air.) Now, we just use $ s \equal{} \minus{} \frac 12 gt^2 \plus{} v_0t \plus{} s_0$, plug and chug, we get the maximum height is $ s_0 \plus{} \frac 23$, and since $ s_0 \equal{} 2$, $ h_{max} \equal{} \boxed{\frac 53}$.[/quote]
I think your solution is wrong since we have the acceleration of the system, as well as of these two boxes, is 5(from these equations: T-m_1g=m1.a and m2.g-T=m2a. Adding them we get: a=(m2-m1).g/(m1+m2)=5). I also got the part of velocity of the 6kg box as well as the 2kg box but I can't manage to find the [b]2.5 above the ground[/b] as the answer given by the book. I just get from the equation: s=v0.t+1/2.at^2=1. I think it seems to contradict since when the 2kg box moves, it still moves even when the 6kg box touches the ground because of its inertial frame, so the distance it moves must be greater than that of 6kg box moves.

Nobody minds helping me with this problem? :(

as the 6 kg object has more masss ,  it will go downward

writing the equations for both the objects

(T-2g)=2a
and 6g-T=6a
we get 4g=8a
a=g/2

when the 6 kg block hits the groundit will stop but since the 2 kg block will have some velocity it will rise and tension will be zero
the 6 kg block stops when it travels a distance of 1 m
hence the 2 kg block also travels a distance of 1 m

hence final velocity of the 2kg block=sqrt(2*(g/2)*1)=sqrt(g)

note that it is now 2 m above the ground
now the 2kg block will rise without tension
let the maximum height attained be H
the sqrt(2gH)=sqrt(g)
H=1/2

hence total height =2+1/2=2.5
or H=

[hide="My Solution:"]
[quote="ghjk"]Two objects with masses 6.00 kg and 2.00 kg, respectively, hang 1.00m above the floor from the ends of a cord 4.00 m long passing over a frictionless pulley.Both objects start from rest. Find the maximum height reached by 2.00 kg-object[/quote]
Draw the FBD for each mass:
For $ 6kg:$
$ 60 \minus{} T \equal{} 6a$
$ (T \equal{} tension, \; a \equal{} acceleration \; of \; masses)$
For $ 2kg:$
$ 3T \minus{} 60 \equal{} 6a$
Solve linearly, get $ a \equal{} 5m/s^2$.
Now acceleration is applied till $ 6kg$ hits floor.
Then,
$ t \equal{} \sqrt {\frac {2}{5}}$
Max. height, $ H \equal{} \frac {v^2}{2g}$
$ v \equal{} at \equal{} \sqrt {10}$
Substituting, we get $ H \equal{} 0.5$
Therefore, max. height=$ \boxed {1m \plus{} 1m \plus{} 0.5m \equal{} 2.5m}$
[/hide]

[quote="aadil"]as the cord is massless the tension is uniform throught the cord .hence both the masses move with equal acceleration.on applying newtons second law we have 2 equations and  2 unknowns,tension and acceleration.
using kinematic equations we can find out the distance moved[/quote]
AND FINALLY, YOU GET $ 2.5m$!


$ x_n$ ($ n$ positive integer) is the solution of
$ x^{\frac{1}{n}}\equal{}\sqrt{1\minus{}x}$,
ascertain the nature of the series $ \sum_1^{\plus{}\infty}x_n$.

[hide="Hint"]Show that $ x_n > \frac {1}{n}$. It may be easier to do this using the inverse functions.[/hide]

[quote="Spasty"]$ x_n$ ($ n$ positive integer) is the solution of
$ x^{\frac {1}{n}} \equal{} \sqrt {1 \minus{} x}$,
ascertain the nature of the series $ \sum_1^{ \plus{} \infty}x_n$.[/quote]
easy:
$ x^{1/n}$~$ 1 \minus{} x/2$
then
$ x$~$ 1 \minus{} nx/2$
or
$ x_{n}$~$ \frac {2}{1 \plus{} n}$
therefore serie divergent


Can someone remind me what the formula is for the sum of an infinite geometric series????

Some other useful formulas would be great... :D

$\frac{a}{1-r}$ where $|r|<1$ and $a$ is the first term of the sequence

Well, just so you know, it is quite simple to find the formula if you forgot it.  Just do teh following.
$S_{\infty}=a+ar+ar^2+...+ar^{\infty}\\\implies S_{\infty}(r-1)=ar+ar^2+...+ar^{\infty}-a-ar-ar^2-...-ar^{\infty}=-a\\\implies S_{\infty}=\frac{a}{1-r}$

You coudl do the exact same to find the formula for $S_n=\frac{a(r^n-1)}{r-1}$
Masoud Zargar

boxedexe, be careful with your notation, infinity cannot be used like a number, i agree that is the correct idea, but the proof is more rigirous to say that the limit of the sum is $\frac{a_0}{1-r}$

Clearly, you are correct with the limit idea. :)

its a/ 1-r where a is the first term and r is the common ratio

 :alien:  :thumbup:


calculus
integration
real analysis
real analysis unsolved

Prove that

$\int_{0}^{\frac{\pi}{2}}\arccos(\frac{ \cos(x)}{1+2 \cos(x)})dx=\frac{5\pi^2}{24}$

----------------------------------------------------------------------------------

Here a proof, it use only material from MPSI/MP*
 http://www.dma.ens.fr/culturemath/contenu/dossiers.html#CoxeterInt

If you have another proof post it
thx


greatest common divisor
prime divisor
number theory
inequalities

For any positive integer $ n>1$, let $ P\left(n\right)$ denote the largest prime divisor of $ n$. Prove that there exist infinitely many positive integers $ n$ for which
\[ P\left(n\right)<P\left(n\plus{}1\right)<P\left(n\plus{}2\right).\]

In fact, I had seen it for the first time in a romanian selection test in 1984 I think. But I don't know to solve this extremely beautiful problem.

It is wonderful :) I adore it :)
I heard first of it last year, from one of my IMO team mates.
But he didn't have any idea of a solution; neither do I.
So ... a solution would be really really really appreciated.

:? I'm a bit confused ...

When you type n_k + 1 for example, do you mean nk + 1 or nk + 1?
...

[quote="grobber"]Let p>2 be a prime, and let n_k=p^(2^k)+1. We have P(n_k+1)=p.[/quote]

:?:?:? Why that? Am I missing something?

When I say a_k+1 I mean (a_k) + 1, not the (k+1)'th term of the sequence.

About that other thing, it's simple: I wrote + instead of -. I've edited it, so see if it makes sense now. Sorry! :D

Another idea...
Let p1, p2, ... be the sequence of prime numbers.
Let fn be the product of the first n primes: fn = p1p2...pn.
Take a positive integer k with...
*[i]P[/i](k) \leq pn, and
*kp1p2...pn + 1 = pn + 1m for some m.
Define m = kfn. Then we have
*[i]P[/i](m) = pn
*[i]P[/i](m + 1) = pn + 1 > pn
*[i]P[/i](m + 2) > pn + 1, since it's easy to check that none of p1, ..., pn + 1 divides m + 2.
So we should prove the existence of such a number k.
It's easy to prove that there is a "k" such that kp1p2...pn + 1 = pn + 1m for some m,
but how to prove that there exists such a k for which [i]P[/i](k) \leq pn?
Maybe I'm overlooking something obvious :D or maybe it's not tht obvious.

i tried this problem  for a long time. i  was kinda close in a way because i knew that the exponent  had to  be   power of two . but  choosing these numbers is very  clever,  how  can  that  natural to someone?

[quote="Arne"]Another idea...
Let $ p_1, p_2, \ldots$ be the sequence of prime numbers.
Let $ f_n$ be the product of the first $ n$ primes: $ f_n \equal{} p_1p_2...p_n$.
Take a positive integer k with...
$ P(k) \leq p_n,$ and
$ kp_1p_2...p_n \plus{} 1 \equal{} p_{n \plus{} 1}m$ for some $ m.$
Define $ m \equal{} kf_n.$ Then we have
$ P(m) \equal{} p_n$
$ P(m \plus{} 1) \equal{} p_{n \plus{} 1} > p_n$
$ P(m \plus{} 2) > p_{n \plus{} 1},$ since it's easy to check that none of $ p_1, ..., p_{n\plus{}1}$ divides $ m \plus{} 2.$
[/quote]
I think, this is wrong! Why do you think that between
$ p_{n}$ and $ p_{n \plus{} 1}$  is not another prime number?

can one say that there are infinite primes of the form $ 3^n \plus{} 2$ ?
if so , then
P($ 3^n$) = 3
$ 3^n \plus{} 1$ > P($ 3^n \plus{} 1$) > 3 , because $ 3^n \plus{} 1 \equal{} 2^s$ has only trivial solutions and $ 3^n \plus{} 1$ is not divisible by 3 and because its one less than a prime , it must have a divisor
P($ 3^n \plus{} 2$) = $ 3^n \plus{} 2$

to Grobber : you have to write : $ n_k\equal{}(p\minus{}1)(p\plus{}1)(n_1\plus{}2)(n_2\plus{}2)..(n_{k\minus{}1}\plus{}2)$ instead of : $ n_k\equal{}\left(p\minus{}1\right)\cdot\left(p\plus{}1\right)\cdot n_1\cdot n_2\cdot ...\cdot n_{k\minus{}1}$

Thats a very nice solution grobber. i love it

Had to throw in my 2 cents:

It is easy to see if n + 1 is the square of an odd prime, n will behave as needed.  We only need to show EITHER n + 1 is a square of an odd prime and n + 2 is forced in certain circumstances to follow the rest OR n + 2 be a square of an odd prime and show that P(n) < P(n + 1) for some specific situations.  I will try to unsuccessfully show the former.

But I am using Dirichlet's.  And from Dirichlet's we know there are infinitely many primes with the ones digit being 1 (i.e. the sequence 10k + 1 will hit infinitely many primes).  Call this prime p.  Note that P(p^2) = p.  Note further that $P(p^2 -1) = P(n)$ is less than HALF p + 1 as p + 1 and p - 1 are both even.

Eh, figured it might go somewhere.  Anyone with the rest of this proof?

[quote=grobber]It just so happens that i have a proof of this right in front of me. I'd love this to be mine, but it's copied word by word from a book:

[quote="problem"]For any positive integer $ n > 1$, let $ P\left(n\right)$ denote the largest prime which divides $ n$.
Prove that there exist infinitely many positive integers $ n$ for which

$ P\left(n\right) < P\left(n \plus{} 1\right) < P\left(n \plus{} 2\right)$.[/quote]

Let $ p>2$ be a prime, and let $ n_k\equal{}p^{2^k}\minus{}1$. We have $ P\left(n_k\plus{}1\right)\equal{}p$. We look at the sequence $ \left(n_k\plus{}2\right)\ \left\{k\geq 1\right\}$. We can see that any 2 distinct terms have 2 as their greatest common divisor, because for $ i<j$ we have $ \left(p^{2^j}\plus{}1\right)\minus{}2 \equal{} \left(p\minus{}1\right)\left(p\plus{}1\right)\left(p^2\plus{}1\right) ...\left(p^{2^i}\plus{}1\right) ...\left(p^{2^{j\minus{}1}}\plus{}1\right)$.

Since none of the terms of the sequence considered is divisible by 4, it means that the sequence $ P\left(n_k\plus{}2\right)$ contains arbitrarily large primes. Let $ k$ be the smallest integer for which $ P\left(n_k\plus{}2\right) > p$. Since $ n_k\equal{}\left(p\minus{}1\right)\cdot\left(p\plus{}1\right)\cdot n_1\cdot n_2\cdot ...\cdot n_{k\minus{}1}$ and all prime divisors of the number on the right are $ <p$, it means that $ P\left(n_k\right)<p\equal{}P\left(n_k\plus{}1\right)<P\left(n_k\plus{}2\right)$, and such a number $ n_k$ can be found for any prime $ p$.[/quote]

Why $p(n_k)<p$?

[quote=nmd27082001]
Why $p(n_k)<p$?[/quote]
Actually, the equation there is not quite correct and it should be $n_k=(p-1)(p+1)(n_1+1)(n_2+1)\dotsc (n_{k-1}+2)$ as the factors are of the form $p^{2^j}+1$, not $p^{2^j}-1$.
Clearly, all prime divisors of $p-1$ and $p+1$ are less than $p$. And by assumption $P(n_j+2) \le p$ for all $j<k$, hence all primes dividing one of the factors on the RHS are $\le p$, so $P(n_k) \le p$ but clearly $p$ itself does not divide $n_k$ either, so $P(n_k)<p$.


invariant
combinatorics unsolved
combinatorics

Grandson of a Baron Minhauzen states that in his country there exist $n\geq 3$ major cities , each two of which are connected with the airline in one direction. He also claims that from each city it is possible to arrive two any other with at most one change of the planes. For which values of $n\geq 3$ is it possible that the grandson of Barone Minhauzen claims the truth?

I can only prove that it works for odd $n$ up until now:

Label the cities $0,1,2,\ldots,n-1$, and draw an arc from $x$ to $y$ iff the smallest non-negative residue of $y-x$ modulo $n$ is odd. It's easy to prove that it works.

i think it works for all $n\geq 5$ and for $n=3$.(hopefully i haven't goofed up anywhere..)

basically if it works for $n$, then it is easy to see that it works for $n+2$ as well. just add $2$ new vertices to the vertex set $V$, call them $x,y$ and have directed edges from each vertex of $V$ to x and from $y$ to each vertex of $V$.finally add an edge from $x$ to $y$.now for  $x$ and $y$ clearly both trips are possible by paths of length $\leq 2$.for any $v\in V$, $v\rightarrow x$ is possible by definition.also, $x\rightarrow y\rightarrow v$ so the reverse is also possible. finally for any $v\in V, y\rightarrow v$ by definition and $v\rightarrow x\rightarrow y$ and so the claim holds.

since for $n=3$ the directed triangle works so for all odd n the above construction works.
for $n=6$ a grid is possible,so for all even $\geq 6$ it works again.
the grid for $n=6$ is:
  $(1,2),(1,3),(4,1),(5,1),(6,1),(3,2),(2,4),(2,5),(2,6),(4,3),(3,5),(6,3),(5,4),(4,6),(6,5)$.

Ahh, I see. I actually thought it didn't work for even $n$, and was too lazy to look for a construction for $6$ :(.

actually so did i! but i couldn't find any invariants,so tried to see why it wouldn't work for 6 and somehow fooling around  got that configuration.


symmetry
probability
articles
Euler
calculus
geometry
number theory

I didnt really want to make a new topic..but i couldnt really find a topic similiar to this one...and sorry if there is one where in this site....but I have been reading some wonderful ...truly wonderful books on te subject of mathematics. I have read The Milliennium Problems by Keith Devlin (who is a really good author) and I am currently reading Godel, Escher, Back by Douglas Hofstadler and although everytime I read it I only get 1/4 of what I am reading. so I end up reading each page 4 times to understand what he is trying to say.....i still love it...its really really good and I'm not even done with the book yet....I am acutally planning on reading more boks by Keith Devlin becuase his kind of books are what I am interested in....Logic...thoeries...and well I cant really explain it...I hope that reading these books might....but I am more interested in reading about thoreies than tryin to do themm....although godel, escher, bach's MU puzzle was actually really interesting for me to do it...and I am reading a logic book...Its really hard for me to explian exactly what i mean in words...I was wondering if anyone can recommend me to some other great and wonderful books that I might like and enjoy reading...THANKS

I agree Keith Devlin books are quite good. So are Ian Stewart books. I'll add more books to this reply through an edit tomorrow or the next day.

Have you read Music of the Primes?

Also, the various Simon Singh books are good for the mathematical layperson.

I like reading math biographies. Two that stand our are [i]The Man Who Loved Only Numbers[/i] and [i]The Man Who Knew Infinity[/i].

these books seems pretty interested..but can u provide a little summary and the author of the book so that i know a bit more about the book?

[quote="dts"]If you're looking for casual mathematics reading, I would recommend [i]The Colossal Book of Mathematics[/i] by Martin Gardner.  It has some very interesting chapters on topics as varied as Diophantine equations, symmetry, higher dimentions, probability, fractals, and paradoxes.  It even has a chapter about the book [i]Gdel, Escher, Bach[/i] that SLeon mentioned earlier.[/quote]

The other collections of Martin Gardner's articles are also good for casual reading.

[i]Countdown, the Art of Problem Solving, the Art and Craft of Problem Solving. [/i] and [i]Of Men and Numbers[/i] are good books...

"Prime Obssesion", by John Derbyshire is definately the most detailed math book for a lay-person that I've seen (In my opinion, it's much better than Music of the Primes and the Millenium Problems). It's also about the Riemman Hypothesis, and actually discusses and shows part of the derivation for the formula for primes less than a given number, the paths and efforts of those who are trying to prove the hypothesis, plus a healthy does of 19th century math history.

"Mathematical Mysteries", by Calvin C. Clawson is also a good all around cool and inspirational mainly number theory math book, with topics such as formulas for pi, the euler-mascheroni constant, ect.. Paraphrasing Amazon.com, "He delves into the heart of number theory to see and understand the exquisite relationships among natural numbers."

[quote="rrusczyk"]Also, the various Simon Singh books are good for the mathematical layperson.[/quote]

He speaks the truth.  Reading Fermat's Enigma is what really got me into math.

[quote="elston"]I think an interesting math book is Lapses in Mathematical Reasoning by Bradis, MInkovskii, and Kharchea  :)[/quote]

[quote="SLeon"]is that book going ot be soemthing that needs like a calcalus background to understand?[/quote]

No, that book has no calculus in it (as far as I can tell).  The most complicated things it has are geometry, logs, and trigonometry.  Some of the stuff in the earlier chapters just involve arithmetic...

THANKS FOR RECOMMANDING SIMON SINGH'S FERMAT'S ENGIMA...IT WAS REALLY REALLY GOOD... IM GLAD THAT I HAD THE CHANCE TO READ IT BECUASE IT [i]WAS [/i]BY FAR THE BEST BOOK I READ

My favorites are  books by George Gamow - Eg One, two three infinity and Mr. Tomkins in Wonderland.

Most of his other books are physics related but are fun.


Let L be a six digit (base ten) integer whose last digit is not 0, and let M be the number formed by moving this last digit to the front. For example, if L = 354268, then M = 835426. Find all possible L such that L = 3M. The sum of all the digits of all the possible L is:

a) 36
b) 72
c) 54
d) 48
e) None of these

[hide="answer"]
c) 54
[/hide]

How do you do this? Please explain to me like a absolute beginner because I forgot some of AoPS 1.  :blush:

We know the sum must be a multiple of 3, but this doesnt help us!
I would use case work for the first digits of L,M

OK I think I've got the answer.

[hide="Click to view hint"]
Suppose L = ABCDEF. Then M = FABCDE. Now let x = ABCDE and y = F.
Work on from there.

[hide="Click to view solution"]
L = 10x + y and M = 100000y + x.
Since L = 3M, we have the equation: 10x + y = 300000y + 3x.
So 7x = 299999y and hence x = 42857y.
Note that x is a one-digit number and y is a five-digit number.
Suppose x is 1. Then y is 42857.
Suppose x is 2. Then y is 85714.
Suppose x is 3 or bigger. Then y is 128571 or bigger, and isn't a five digit number anymore.
So L = 142857 or 285714
Adding the digits up gives $ \boxed{54}$.
[/hide]

[/hide]

Brilliant! Thank you so much smileyboi!

 :D

Nice:
Try multiplying 142857 by 1,2,3,4,5,6,7. What do you get?

Well, the number is basically 1/7, without the repeating part and multiplied by 1000000. So, you can figure out what it is by examining 1000000*1/7*n, where n=1,2,3,4,5,6,7 except that for n=7, the answer won't be 10000000, it'll be 1 less.

That's basically what I was saying since 285714 is the repeating part after the decimal in the expansion of $ 2*\frac{1}{7}$. It can be extended to each of the other $ n*\frac{1}{7}$, for n=1,2,3,4,5,6. The n=7 is an interesting case though.


In sistemul cartezian xOy se considera punctele coliniare $A_{i}(x_{i},y_{i}),i=1,4$,astfel incat sa existe matricile inversabile M din $M_{4}(C)$ in care primele doua linii sunt $(x_{1},x_{2},x_{3},x_{4})$ si $(y_{1},y_{2},y_{3},y_{4})$.Aratati ca suma elementelor matrici $M^{-1}$ nu depinde de matricea $M$ data.

Moubinool asked me to translate this in English.

In the plane $xOy$ consider the collinear points $A_i(x_i,y_i),\ i=\overline{1,4}$ s.t. there is at least an invertible matrix $M\in\mathcal M_4(\mathbb C)$ for which the first two lines are $(x_1,x_2,x_3,x_4)$ and $(y_1,y_2,y_3,y_4)$. Show that for all such invertible matrices $M$, the sum of the elements of $M^{-1}$ is the same.


The numbers 3, $ a$, $ b$, $ c$, $ d$, 38, $ \ldots$ form an arithmetic sequence. What is the value the sum $ b\plus{}c$?

b+c=a+d because you subtract the common difference from b and add the common difference to c. Doing this again, you find that b+c=3+38=[b]41[/b].

[quote="UberYoda"]Another way to do this problem would be to find $ b$ and $ c$. We can figure out the common difference between consecutive terms, which is $ 7$. The sequence is $ 3, 10, 17, 24, 31, 38$ and $ 17 \plus{} 24 \equal{} \boxed{41}$[/quote]
Aleph0's way is a more favorable approach considering the times pressure in a $45$ second limit--especially since you need to solve the problem before your opponent does.


Suppose $ a,b,c$ are three sides of triangle.

Prove that

$ \sqrt{a\plus{}b\minus{}c} \plus{}\sqrt{b\plus{}c\minus{}a} \le 2\sqrt{b}$

 :wallbash:

[hide]Let a = x+y, b = y+z, c = z+x. Then we get that this is equivalent to $ \sqrt{2y} \plus{} \sqrt{2z} \le 2\sqrt{y\plus{}z},$ which is true by QM-AM.[/hide]

Hi vinksman since both sides are positive first square them

Then cancelling commom terms and squaring again what u want to prove is
$ (a\plus{}b\minus{}c)(b\plus{}c\minus{}a)$<=$ b^2$

just direct expansion yields what u want to prove is

$ \minus{}(a\minus{}c)^2$ <=0
Which is obviously true

b = (b+a-c + b-a+c)/2.

so, setting b+a-c = x

                b-a+c = y,

the inequality is equivalent to

sqrt(x) + sqrt(y) <= 2sqrt((x+y)/2)

<=> x + y + 2sqrt(xy) <= 2(x+y) = x + y + (x+y)

<=> x + y => 2sqrt(xy)

which is true by AM-GM.

therefore, the original inequality is true.  :)


let $a,b,c,d \in [1,2]$
find min and max $A=\sum_{cyc}\frac{a}{b+cd}$

[hide="min"]We have: $c+d \ge cd$
so that $b+cd \le b+c+d$
$\Rightarrow \frac{a}{b+cd}\ge \frac{a}{b+c+d}$
$\Rightarrow LHS \ge \sum_{cyc}\frac{a}{b+c+d}\ge \frac{4}{3}$[/hide]

[hide]I think that max=2[/hide]


Find two consecutive integers with the property that the sums of their digits are each divisible by $2006$.

This number x is $x=y*10^k-1$, were $y\not=9(mod \ 10)$, and the sum digits y+1 divisible 2006, $2006|(9k-1)\Longrightarrow k=223+2006*m$. For example minimal number is $y=10^{223}-3, x=10^{446}-2*10^{223}-1$.

Well this is not from the german olympiad but from the german national contest (Bundeswettbewerb Mathematik).


function
calculus
integration
induction
real analysis
real analysis solved

Let be given a possitive integer n . Consider a continous function $ f(x):[0;n]-->R $ satisfying $ f(0)=f(n) $ . Prove that : there exist n couples of numbers $ a_i , b_i (i=1,2,..,n) $ belonging to $ [0;n] $ such that $ b_i-a_i $ are possitive integers and $ f(a_i) = f(b_i) $ for all $ i=1,2,..,n $

Infact we can find infinitely many such couples
 Let $c$ be a point in $(0,n)$ so that $f(c)$ is different than $f(0)$ and therefore $f(n)$
 ( If such $c$ does not exist then $f$ is constant and the conclusion holds trivially)
 Apply the Intermediate value property, we find $a_1 \in (0,c)$ ,$b_1\in (c,n)$ so that
 $f(a_1) = f(b_1) = \frac {f(c) + f(0)}{2}$.
 Now consider $(a_1,b_1)$ alone and follow the same procedure above we have $a_2,b_2$, then $a_3,b_3$....

dickchimney, I don't see that you have shown that $b_1-a_1$ is an integer. In fact, with that integral-difference condition, there are in general only finitely many such pairs of ponts.

In fact, to be assured of having $n$ such pairs of points, we must include $(0,n)$ as one of the pairs.

If $(a_i,b_i)$ is such a couple, can we also take $(b_i,a_i)$ as being one?

[quote="Kent Merryfield"]dickchimney, I don't see that you have shown that $b_1-a_1$ is an integer. In fact, with that integral-difference condition, there are in general only finitely many such pairs of ponts.

[/quote]

 Yep!! Thank you for that!! :blush:
 But it must be true that there exist $x$ so that $f(x)=f(x+1)$ where $x \in [0,n-1]$
 Otherwise we will have $g(x)=f(x)-f(x+1) > 0$ or $<0$ everwhere which leads to
 $f(0) > f(1) >...>f(n)$ or $f(0) < f(1) <... <f(n)$, contradiction.
 Once we have $f(x)=f(x+1)$ we can glue two points $x, x+1$ ( even if $x=0$ or $n-1$) together without affecting the hypothesis, especially the interger-diffrerence property!! Then we can process by induction, right?

I do not think it's that easy, man. I think there can be some integers $m<n$ for which there's no $x$ s.t. $f(x)=f(x+m)$. We can use your method to find such $x$'s for the case $m|n$ with no problems, but it doesn't look good if we want to find $n$ pairs.. :?

[Edit: I think I see what you mean now; I hadn't read it properly :); sorry about that  :blush: ]

[quote="grobber"] I think there can be some integers $m<n$ for which there's no $x$ s.t. $f(x)=f(x+m)$. [/quote]

 You're right!! But I did not prove that!!
 I process by induction on the length of the interval, (after the glueing thing, the length decreases by 1)
 Please check it again!! :D

[quote="grobber"] I hadn't read it properly :blush: ][/quote]

 No problem, that is the case of my first "proof" :blush:

Here's another approach.

For $k\in\{1,2,\dots\}$, let $g_k(x)=f(x+k)-f(x).$ We note that $g_n(0)=0.$ We count that as one of our solutions. What we now need is for there to be a total of at least $n-1$ roots of the collection of equations $g_k(x)=0$ for $1\le k\le n-1.$

Consider $f$ to be continuous and periodic of period $n.$ (That's what $f(0)=f(n)$ is good for.) Then define each $g_k$ to be continous and periodic. Each $g_k$ has average value zero.  Thus either $g_k$ is indentically zero (in which case we have infinitely many solutions) or it has at least one positive and at least one negative value in each period. Thus (by the Intermediate Value Theorem) for each $k,$, $1\le k \le n-1,$ there are at least two roots of $g_k(x)=0$ in $[0,n).$

This apparently gives us $2(n-1)$ solutions, but can we count them all?

If $g_k(x)=0$ for $0\le x \le n-k,$ then this is a solution on our list. But if $n-k<x<n$ then we can rewrite this as $g_{n-k}(x-n+k)=0$ and it counts as a root of $g_{n-k}(x)=0.$ Thus each solution we found does count as one of our solutions, but we may be counting the same solution twice (but no more than twice). Allowing for the double counting, we still have $(n-1)$ solutions, plus the one solution of $g_n(x)=0$ which we handle separately.

What Kent just proved is somewhat stronger than the desired result but I cannot state it clearly

[quote="romano"]dear Kent Merryfield , why can you write $ g_{n-k}(x-n+k)=0 $ where $ n-k\leq x\leq n $ ?[/quote]

 Let's see what is $ g_{n-k}(x-n+k) $
 By definition It it just $f(x)-f(x-n+k)$. We have
 $g_{n-k}(x-n+k)= f(x)-f(x-n+k)=f(x)-f(x+k)=-(f(x+k)-f(x)) =-(g_k(x))$
 So the former is zero iff the latter is zero !! That's all! :D

Thanks for covering that, dickchimney. By the way, the double counting always happens. There is a one-to-one correspondence between a root of $g_k$ in the "wrong" part of the interval and a root of $g_{n-k}$ in the "right" part of the interval, and vice versa. The only way to have more than the specified minimum number of solutions is to have some $g_k$ have more than two roots.

It took me a while to understand your solution in #5, but now that I do, I see that it is quite elegant. You are inducting on $n$, and your inductive hypothesis is that the whole theorem is true for $n-1.$

Thank u Kent! ;)
 What is your opinion Romano ? Is it solved ?

Yeah , nice solutions , Kent , Dickchimney !


probability
number theory
relatively prime

What is the probability that two integers picked at random are relatively prime?

The probability for two random numbers to be relatively prime is proven to be $P[\gcd(a,b)=1]=[\zeta (2)]^{-1}=\frac{6}{\pi^2}$, where $\zeta (s)=\sum_{k=1}^{\infty}\frac{1}{k^s}$.

Masoud Zargar

Yes, but I thought people might be interested in proving it for themselves.  From the proof should follow quickly (by generalization) that the probability that $n$ random numbers are relatively prime is $[\zeta(n)]^{-1}$.


In the arithmetic sequence $ 17, a, b, c, 41$, what is the value
of $ b$?

Since b is right in the middle, b is the average of 17 and 41, which is 29.

Since it is an arithmetic sequence, there is some common difference. Let's call it $ x$

17+2x=b
41-2x=b

Adding the two equations,

58=2b

29=b


probability
AMC
AIME
linear algebra
matrix

Hi, this is my first post on this forum!

This is the question:
"13.  A bug moves around a wire triangle. At each vertex it has 1/2 chance of moving towards each of the other two vertices. What is the probability that after crawling along 10 edges it reaches its starting point?"

I tried (unsuccessfully) to do it like this:

I label the three vertices S, A, and B with S being the starting point. I then let S(n), A(n), and B(n) be the number of ways to get back to S starting from S, A, and B respectively using n moves. From this we get the following equations:

S(n)=A(n-1)+B(n-1)
A(n)=B(n-1)+S(n-1)
B(n)=A(n-1)+S(n-1)

When you sub the last two equations into the first, you get one equation in terms of one variable.

S(n)=2S(n-2)+S(n-1)

Then I proceeded to solve for S(3) and S(4) to get the chain started. I got S(3)=2 and S(4)=4. However, this gave me a different answer for S(10) than the answer I found on this site:
http://www.kalva.demon.co.uk/aime/soln/answ03b.html

Did I mess something up in my work? I tried to find an error in my logic but I couldn't find one. Can someone help out?

Thanks for your time.

[hide="I do not like the Kalva solutions"]
let's set up a recursion

after 1 move, it's impossible to be back at S

after 2 moves, the probability is 1/2, because, after 1 move, the bug has a 1/2 chance of going back to the start

after 3 moves - the probability now that the bug is at the start is 1/2 (the probability that the bug was not at the start after 2 moves) times 1/2 (the probability that the bug goes to the start rather than the other vertex) - 1/4

after 4 - the probability now is (1-(1/4))(1/2)=3/8

you will find that if $p_{n}$ is the probability that the bug is at the start after $n$ moves, then $p_{n}=(1-p_{n-1})(\frac{1}{2})$

you do the math - I'm too tired.
[/hide]

clicking on the "Resources" icon in the top right corner of the forum index and then clicking "USA" under "National and Regional Competitions" takes you to a link where you can see all of the AIME problems, a majority of which have very nice-looking solutions.

sapphyre571, I just used your recursive formula to find the tenth move but it doesn't match the answer on the kalva site. Your equation gives 169/512.

But my question is to find the problem in my solution because I want to apply this method to future problems of this type (it seems versatile).

the adjacency matrix is:

0 1 1
1 0 1
1 1 0

taking this to the 10th power gives

342 341 341
341 342 341
341 341 342

the desired probability is 342/1024=171/512, so 683

Sorry I haven't learned matrices yet. But what I'm looking for is not an alternative solution. I'm looking for a problem with mine.

Is there an easy way to raise the adjacency matrix to large powers? (ie not multiplying it together lots of times)?

If you want to raise a matrix to a large power, diagonalization is the way to go. That matrix has eigenvalues $2,-1,-1$; the eigenvector for $2$ is $(1,1,1)^{T}$ and the eigenvectors for $-1$ are the orthogonal complement.
This is college-level math, and the AIME problem certainly has other solutions.

Ok sorry, but I took LinAlg last summer and I've forgotten most of it. What do I do once I know the eigenvector?

[hide]
Um...how about:

Probability of returning to point A after 1 step = 0
After 2 steps = 1/2 * (1-0) = 1/2
After 3 steps = 1/2 * (1-1/2) = 1/4
After 4 steps = 1/2 * (1-1/4) = 3/8
After 5 steps = 1/2 * (1-3/8) = 5/16
etc
After 10 steps = 1/2 * (1-85/256) = 171/512
edit: Sorry, someone already posted this method lol[/hide]


Why is the last statement on the attachment true? Shouldn't the intersection of f^-1 [B] be larger than the inverse image of the intersection, and why can we conclude that they are equal?

Let's see:

$ x\in f^{\minus{}1}\left[\bigcap_{\lambda} B_{\lambda}\right]$ iff $ f(x)\in \bigcap_{\lambda} B_{\lambda}$ iff $ f(x)\in B_{\lambda}$ for all $ \lambda.$

$ x\in \bigcap_{\lambda}f^{\minus{}1}[B_\lambda]$ iff $ x\in f^{\minus{}1}[B_\lambda]$ for all $ \lambda$ iff $ f(x)\in B_{\lambda}$ for all $ \lambda.$

They're the same.

Can you provide an example showing why it's different for forward images?

Suppose $ \exists a \in A_1$ and $ b \in A_\lambda \forall \lambda \neq 1$ s.t. $ f(a) \equal{} y, f(b) \equal{} y$.

Then, $ y \in \bigcap f[A_\lambda]$ but $ y \notin f[\bigcap A_\lambda]$


[quote="Γιώργος"]Αποδείξτε ότι $ \sum^{\infty}_{n \equal{} 1}\frac {ln2 \minus{} (\sum^{n}_{i \equal{} 1}\frac {1}{n \plus{} i})}{n} \equal{} \sum^{\infty}_{n \equal{} 1}\frac {\sum^{n}_{i \equal{} 1}\frac {1}{i}}{(2n \plus{} 1)(2n \plus{} 2)}$[/quote]

 Γιώργο ,
 τελείως φιλικά να πω τούτο :
 Αφού σε ενδιαφέρουν οι ολυμπιάδες , μην ανοίγεσαι σε πολλά μέτωπα. Αυτές οι ασκήσεις δεν αποτελούν θέματα για ολυμπιάδες.Δεν κάνουν όλες οι ασκήσεις του CRUX για ολυμπιάδες.Έτσι θα κερδίσεις χρόνο για να ασχοληθείς με τις shortlist και άλλα βασικά ολυμπιακά πεδία.Η ίδια προτροπή απευθύνεται και σε όλους , όσοι στοχεύετε στις ΙΜΟ.
Το σύνθημα του Gauss ήταν : Pauca sed matura = λίγα αλλά ώριμα ! Επιλέξτε λοιπόν τα κατάλληλα θέματα.
 Αυτές τις ασκήσεις βάλτες καλύτερα στο στικυ με  τους φοιτητές.Όχι γιατί εδώ βλάπτει , αλλά για να βλέπετε πιο πολύ ασκήσεις για ολυμπιάδες και όχι  ασκήσεις από τους άλλους κλάδους , όσο ωραίες και να είναι.
 Μια ζεστή γνώμη εξέφρασα και δε θέλω να την παρεξηγήσεις. Είμαι σίγουρος ότι θα την αξιοποιήσεις κατάλληλα και στο τέλος θα οφεληθείς. Αλλά ας  πουν και τα άλλα παιδιά τη γνώμη τους. Πιθανόν να κάνω λάθος.
  Μπάμπης

Τρια hints:
- Η σειρά $ \ln 2$.
- Catalan's identity.
- Εναλλαγή των συμβόλων άθροισης (λόγω απόλυτης σύγκλισης - σε ποιο μέλος, το αφήνω σε σένα).

Από εδώ και πέρα είναι εύκολο.


calculus
derivative
calculus computations

Find the derivative of
\[ y = (x^3 + 1)^{ - 4/3}.
\]
[hide="What I Did"]\begin{align*} y' & = - \frac {4}{3}(x^3 + 1)^{ - 7/3} \cdot (3x^2) \\
& = \frac { - 4x^2}{(x^3 + 1)^{7/3}} \end{align*}

Is that correct?  Is there a way to simplify the denominator, $ (x^3 + 1)^{7/3}$?[/hide]

Thanks in advance!

hello, your derivative is ok, you can simplify to $ y^' = \frac { - 4x^2}{(x^3 + 1)^2\sqrt [3]{x^3 + 1}}$.
Sonnhard.

[quote="Dr Sonnhard Graubner"]hello, your derivative is ok, you can simplify to $ y^' = \frac { - 4x^2}{(x^2 + 1)\sqrt [3]{x^2 + 1}}$.
Sonnhard.[/quote]

Ok, thanks!  (I'm going to assume that you meant $ y^' = \frac { - 4x^2}{(x^3 + 1)\sqrt [3]{x^3 + 1}}$.)

hello yes, this was a typo, it is $ y'(x)\equal{}\minus{}\frac{4x^2}{(x^3\plus{}1)^2\sqrt[3]{x^3\plus{}1}}$.
Sorry,Sonnhard.

[quote="Dr Sonnhard Graubner"]hello yes, this was a typo, it is $ y'(x) \equal{} \minus{} \frac {4x^2}{(x^3 \plus{} 1)^2\sqrt [3]{x^3 \plus{} 1}}$.
Sorry,Sonnhard.[/quote]
you could also solve it using logarithm.


inequalities
function
inequalities solved

Let k and n be \in N with 1 < k \leq n; x_1, x_2, x_3,... , x_k are k positive integers, whose sums equals its product.

a.) Prove:

x^n-1_1 + x^n-1_2 + ... + x^n-1_k \geq kn .

b.) Which additional sufficient and necessary properties must be satisfied for k,n and x_1, x_2, x_3,... , x_k in order to get equality:

x^n-1_1 + x^n-1_2 + ... + x^n-1_k = kn .

Suppose x1+...+xk=x1*x2*...*xk.
We apply Cochy's inequality:
x1+...+xk=x1*x2*...*xk\leq ((x1+...+xk)/k)^k ==>
x1*x2*...*xk=x1+...+xk\geq k^(k/k-1).

x1^(n-1)+...+xk^(n-1)\geq k(x1*x2*...*xk)^((n-1)/k)\geq k*k^((n-1)/(k-1))\geq kn since n\geq k and x^(1/(x-1)) is decreasing function for x\geq 2.

Equlity raises if
1) k=n -- from last inequality
2) x1=x2=...=xk -- from Cochy's enequality
But in such case x1*k=x1^k ==> k=x1^(k-1) ==> k=2, n=2, x1=x2=2

I feel some imperfection with this problem

myth try to use Cauchy instead of Cochy! - in rest everything looks fine :)


Solve the Clairaut equation:

$ x\equal{}tx'\minus{}f(x')$

And consider the equation with $ f(x)\equal{}\frac{x^2}{2}$. For which initial conditions will the equation have a solution?

The general solution of the Clairaut equation $ x \equal{} tx' \minus{} f(x')$ is $ x \equal{} Ct \minus{} f(C)$. There can also be a singular solution by excluding p from the two equations $ x \equal{} tp \minus{} f(p)$ and $ t \minus{} f'(p) \equal{} 0$. For $ f(x) \equal{} \frac{x^2}{2}$, and so $ f(x') \equal{} \frac{(x')^2}{2}$ we have as the general solution

$ x \equal{} Ct \minus{} \frac{C^2}{2}$.

To find a possible singular solution we eliminate p from $ x \equal{} tp \minus{} \frac{p^2}{2}$ and $ t \minus{} p \equal{} 0$, from which we obtain $ x \equal{} \frac{t^2}{2}$. This is indeed a singular solution of the original equation, as can be readly shown by substitution.


Let $n$ be a fixed positive integer. To any choice of real numbers satisfying \[0\le x_{i}\le 1,\quad i=1,2,\ldots, n,\] there corresponds the sum \[\sum_{1\le i<j\le n}|x_{i}-x_{j}|.\] Let $S(n)$ denote the largest possible value of this sum. Find $S(n)$.

[hide] Since the summation is symmetric, assume WLOG that $x_{1}\le x_{2}\le \cdots \le x_{n}$. Then we can rewrite the sum as

$\sum_{k=1}^{n-1}(n-k)|x_{k+1}-x_{k}| = \sum_{k=1}^{n-1}(n-k)a_{k}$

where $a_{k}$ are positive reals summing to $1$. Clearly, it makes the most sense for $a_{1}= 1$, from which we get $S(n) = n-1$.[/hide]

WLOG $x_1 \leq x_2 \leq x_3 \leq \cdots \leq x_n$. The sum is actually
$$ \sum_{k=1}^{n-1} k(n-k) (x_{k+1} - x_k) = \sum_{k=1}^n (2k-n-1)x_{k}$$
Hence we need $x_k=1$ for $2k-n-1 \geq 0$ and $x_k = 0$ otherwise. This gives the total as $\boxed{S(n) = \left \lfloor \frac{n}{2} \right \rfloor \left \lceil \frac{n}{2} \right \rceil}$.


arithmetic sequence
number theory unsolved
number theory

consider n is a natural number .prove that there exist a prime number like p that every one of these
numbers p-1,p+1,p+2 have atleast n different prime divisor.

Let $ \{ q_n \}$ be an enumeration of the primes with $ q_1 \equal{} 2$.  The system of congruences

$ x \equiv 1 \bmod q_1 q_2 ... q_n$
$ x \equiv \minus{} 1 \bmod q_{n \plus{} 1} q_{n \plus{} 2} ... q_{2n}$
$ x \equiv \minus{} 2 \bmod q_{2n \plus{} 1} q_{2n \plus{} 2} ... q_{3n}$

has a solution set $ x \equiv k \bmod q_1 q_2 ... q_{3n}$ with $ \gcd(k, q_1 q_2 ... q_{3n}) \equal{} 1$ by CRT.  This solution set is an arithmetic progression that contains a prime by Dirichlet's theorem.

This problem is in a class of similar problems where it is very difficult to explicitly describe the solution set but where, thanks to CRT, it is very easy to show that it exists.  A related question:  show that for any $ n$ there exist $ n$ consecutive positive integers, none of which can be written as the sum of two squares.  (Consider a system of congruences modulo primes congruent to $ 3 \bmod 4$.)


Let a;b;c;d be real numbers satisfying: $\large \frac{1}{2} \leq  a^2+b^2+c^2+d^2 \leq  1$.
Find the maximum and minimum of:
$\large Q = (a-2b+c)^2+(b-2c+d)^2+(b-2a)^2+(c-2d)^2$

hello, i think we have
$ \frac {1}{4}(7\minus{}3\sqrt{5})\le Q\le \frac{5}{2}(3\plus{}\sqrt{5})$.
Sonnhard.


Let a,b,c,d >0 such that $ a^3\plus{}b^3\equal{}c^3\plus{}d^3$ prove that    if $ ab \geq cd$ then $ a\plus{}b \geq c\plus{}d$

First condition $ \Rightarrow (a \plus{} b)(a^2 \minus{} ab \plus{} b^2) \equal{} (c \plus{} d)(c^2 \minus{} cd \plus{} d^2)$ let $ a \plus{} b \equal{} t$ and $ c \plus{} d \equal{} q$ if $ ab\geq cd$ then if $ t < q$ this implies that $ t(t^2 \minus{} 2ab) < q(q^2 \minus{} 2cd)$ contradiction then $ t\geq q$

Let a,b,c>0 such that a+b+c=1 Prove that
$ \sum\sqrt[3]{a\minus{}b\plus{}c^3} \leq 1$


[quote="13375P34K43V312"]A collection S of integers is defined by the following three rules (I) 2 is in S; (II) for every x in S, 3x and x+7 are also in S; (III) no integers except those defined by rules (I) and (II) are in S. What is the smallest integer greater than 2004 which is NOT in S?

This question prevented me from getting a 46 on the 2004 National Test, I still don't know how to do it...[/quote]
[hide="I love this question, really I do"]
Any number that =2/6/4/5/1/3 mod 7 is in the set. So, we need a number divisible by 7. 2009 is the smallest number that fits this description. So, our answer is 2009[/hide]
Is this good enough?

[quote="jhredsox"]I think the answer is[hide]2009

I know it involves using mod 7, in which you can never get a multiple of 7, therefore 2009 is the first multiple of 7 greater than 2004.[/hide]

-jorian[/quote]
Did you read my solution?
Hide yours.

[quote="jhredsox"]I did hide mine. No, I did not read your solution, hence i posted 30 seconds afterwards :wink:
-jorian[/quote]
Sorry, I'm stupid. Anyways, this took me about 2.5 minutes, that isn't too bad :) . The reason I asked did you read my solution is because I show why it works in more detail.

ya, c, u shouldn't feel stupid as i gave up, and cheated (don't ask how :rotfl: )
-jorian

This problem is interesting.  [hide="The key"] Every number of the form $2 \cdot 3^{k}$ is in this set for $k = 0, 1, 2, ...$.  Now,

$2 \equiv 2 \bmod 7$
$2 \cdot 3 \equiv 6 \bmod 7$
$2 \cdot 3^{2}\equiv 4 \bmod 7$
$2 \cdot 3^{3}\equiv 5 \bmod 7$
$2 \cdot 3^{4}\equiv 1 \bmod 7$
$2 \cdot 3^{5}\equiv 3 \bmod 7$
$2 \cdot 3^{6}\equiv 2 \bmod 7$

And so forth.  (This is a very interesting pattern!  Why does it give every non-zero remainder upon division by $7$?  Under what conditions does a similar pattern exist for, say, multiplication by $b \bmod p$?)

Since we can add $7$ to any element of the set to get more elements, after "some point" every number that is not divisible by $7$ is in the set.  Specifically, after $2 \cdot 3^{5}= 486 < 2004$.  [/hide]
Edit:  By the way, [b]bpms[/b], your original statement is slightly incorrect.  Since rule (II) only states $x \in S \implies x+7 \in S$ and not the reverse, we are missing many numbers $< 486$.

[quote="t0rajir0u"]
Edit:  By the way, [b]bpms[/b], your original statement is slightly incorrect.  Since rule (II) only states $x \in S \implies x+7 \in S$ and not the reverse[/quote]
Wait how is the reverse not implied? If x-7 is in the set, so is x.

$x-7 \implies x \neq x \implies x-7$. The standard falsity of converse.

t0rji0u's proposed extension is a pretty well known result related to Euler's totient theorem.

All I remember is, when I actually took the test in practice, I found a nifty way to do it quickly and got it right.

Here's my order of skill level:

worst: a random problem
middle: practice tests
best: real competition

Edit: Someone else already gave a really good explanation of how to do it, so I won't repeat. However, if you saw this problem and had no clue how to do it, I would recommend.

[hide]starting with two and adding 7 and multiplying by three systematically. For example, multiply $2$ by $3$ until multiplying it by $3$ would make it greater than 2009. Then add $7$ from then on to find a number to "rule out" e.g. $2*3^{6}= 1458$. 1458 is 2 mod 7, so obviously another number that is 2 mod 7, 2004, can be obtained. So you can rule out 2004. Then repeat by adding 7 and following the same operations you did above. Find numbers between 2002 and 2010 to see what numbers you can get. Pretty soon you'll have ruled out enough different numbers to realize that 2009 is the right answer. Although realizing the x is congruent to a (mod 7) thing is much better[/hide]

You could explicitly calculate ways to get the first few numbers greater than $2004$ until you can't get one anymore, but that seems harder to me, not easier.

The problem is essentially a modular problem.  Rather than avoiding the topic, why not try to learn some modular arithmetic?

[quote="asianhottie8293"]DOES ANYBODY HAVE A WAY WITHOUT MOD[/quote]
This question was a hard National-level question.  Very few students solved this question in the alotted time.

I think there are two approaches:

[hide="1.  Use logical reasoning"]
My intuition tells me the problem probably has something to do with multiples of 3 or with multiples of 7.

Think about the small numbers in the set:  2, 6, 18, 9, 16, 23, 13, 20, 27, 25.  We have multiples of 3.  We have multiples of 3, plus 1 (16, 13, 25).  And we have multiples of 3 minus 1 (23, 20).  Maybe it doesn't have anything to do with multiples of 3.

We also have lots of non-multiples of 7 in the set.  But in the first few items above, I don't see any multiples of 7.

So how would we get a multiple of 7 in the set?  If there's not already a multiple of 7 in the set, then adding 7 won't get us a multiple of 7.  And if there's not already a multiple of 7 in the set, then multiplying by 3 won't get us a multiple of 7.

So, there's no multiple of 7.  The smallest multiple of 7 greater than 2004 is 2009.[/hide]

[hide="2.  Take advantage of your calculator"]
Work fast and systematically:

2 is in the set.  So is 9, 16, ..., 2004, 2011, ...
2*3=6 is in the set.  So is 13, 20, ..., 2008, 2015, ....
6*3=18 is in the set.  So is 25, 32, ..., 2006, 2013, ...
18*3=54 is in the set.  So is 61, 68, ..., 2007, 2014, ...
54*3=162 is in the set.  So is 169, 176, ..., 2010, 2017, ...
162*3=486 is in the set.  So is 493, 500, ..., 2005, 2012, ...

So far, every number greater than 2004 is in the set, except 2009, 2016, ...

If you happen to try others, such as $9\times 3=27$:
9*3=27 is in the set.  So is 34, 41, ..., 2008, 2015, ...
Then, you'll find you are duplicating those you have already found to be in the set.  Hopefully, your intuition will get you back on track with the sequence shown above, before your time runs out.[/hide]

Basically, when you don't know what to do on a counting problem like this, try to look for a pattern (if you didn't finsih the other problem(s), do those instead then). You could have figured there was no 7, 14, etc. (it's using mods, but in a middle school fashion).

Jorian Hoover


How many different ways can change for 1 dollar be made using nickels, dimes, and/or quarters?

I've seen these problems a lot. Is there any quick way to do them?

Related, but uses half-dollars as well...[url]http://www.artofproblemsolving.com/Forum/viewtopic.php?search_id=2143529262&t=161837[/url]

There was a similar problem on the Maryland Math League last week or so. The only way I did these problems would be to systematically brute force; that is, make a careful list of every possible combination. Starting with say, 10 dimes, work down to 1 dime, and see how many combinations this would lead with other coins. This ensures you won't miss the "stray" combination when you're done.


Functional Analysis
topology
real analysis
real analysis unsolved

Does there exist an infinite dimensional Banach space X with a subset S such that each element of X is a finite linear combination of elements of S?

What did you really mean? :? You can just take $S=X$.

Suppose $X$ is an infinite dimesional Banach space.

Since $X$ is infinite dimensional, there exists an infinite linearly independent set. WLOG, we can choose this set to be $S=\{v_{k}: k\in \mathbb{N}\}$ in such a way that $\|v_{k}\|=1$ for each $k.$

Now consider the set of every sum $\sum_{k=1}^{\infty}a_{k}v_{k}$ for scalars such that $\sum_{k=1}^{\infty}|a_{k}|<\infty.$

Every such series converges, because its partial sums form a Cauchy sequence in $X$ and $X$ was presumed to be complete.

Every such series gives a point in the closure of the span of $S.$ What we need to show is that not every such series can itself be in the span of $S.$

Hmm... if we were working with a Schauder basis for $X,$ this would be easy, but I'm not quite sure how to finish it in general.

In other words, you'd want to know whether an infinite dimensional Banach space can have a countable Hamel basis (over its scalar field). No, it cannot:

Let $\{e_{n}\}_{n\ge 0}$ be such a basis for our Banach space $X$. Then our space is equal to $\bigcup_{n\ge 0}\langle e_{0},\ldots,e_{n}\rangle$, where $\langle\ldots\rangle$ denotes the linear span of whatever is between the brackets. Each $\langle e_{0},\ldots,e_{n}\rangle$, however, is a proper closed linear subspace of $X$, and hence a closed nowhere dense subset. By [url=http://mathworld.wolfram.com/BaireCategoryTheorem.html]Baire's theorem[/url], a complete metric space is not a countable union of such sets, and we have the desired contradiction.

I should have thought of Baire category. Thanks, grobber.

in this case your set is closure(span(S)) and this is infact equal to X.

think of L2[T]. it is certainly true that, because of fourier series (stone weierstrass etc) that if S={e^inx:n in N} then L2[T]=closure(span(S)).


topology
advanced fields
advanced fields unsolved

Let X and Y be normed spaces. How would you show that a linear mapping T: X-->Y
is continuous wrt the usual normed topologies iff it is continuous wrt the weak
topologies on X and Y.

Let $ f: X\to Y$ be linear.

One direction is easy:
Let $ f: X\to Y$ be continuous with respect to the norm topology. The sets of the form $ V\equal{}y_1'^{\minus{}1}(U_1)\cap\ldots\cap y_n'^{\minus{}1}(U_n)$ with open $ U_n$ and functionals $ y'\in Y'$ are a subbase for the weak topology on $ Y$. Since $ y'\circ f\in X'$ for each $ y'\in Y'$ the preimage $ f^{\minus{}1}(V)\equal{}(y_1'\circ f)^{\minus{}1}(U_1)\cap\ldots\cap(y_n'\circ f)^{\minus{}1}(U_n)$ are open in the weak topology on $ X$. So $ f$ is continuous with respect to the weak topologies on $ X$ and $ Y$.

Now consider the other case. $ f$ is linear it is continouos for the norm topologies iff it is bounded. So let $ A\subseteq X$ be a bounded set. We prove that $ f(A)$ is bounded. In normed spaces boundedness is equivalent to weak boundedness. So let $ y'\in Y'$ be arbitrary. $ y'\circ f$ is continouos with respect to the weak topology on $ X$ and so it is for the norm topology too (the weak topology is coarser than the norm topology). Hence $ y'\circ f\in X'$ and so $ y'(f(A))$ is bounded. Hence $ f(A)$ is weakly bounded in $ Y$ and therefore bounded. So $ f$ is bounded and continuous for the norm topologies.

Could you explain why the sets like $ V$ form a subbase for the weak topology? Also what do you mean by weakly bounded?

Many Thanks

These set are a base because of the definition of the weak topology. The weak topology is usually defined as coarsest topology on $ X$ s.t. all $ x'\in X'$ are still continuous. This means nothing else as that the weak topology is the initial topologie with respect to the maps $ x': X\to\mathbb{K}$. And the initial topology has this base.

"$ A\subseteq X$ is weakly bounded" means that $ x'(A)$ is bounded for each $ x'\in X'$.


How do I show that if $ a$ and $ b$ are positive integers, then there is a smallest positive integer of the form $ a\minus{}bk$ where $ k$ is $ Z$

If you have the well-ordering principle (can be proven by induction for $ \mathbb{Z}_ \plus{}$), then $ \{a \minus{} bk, k \in \mathbb{Z}\} \cap \mathbb{Z}_ \plus{}$ is a nonempty subset of $ \mathbb{Z}_ \plus{}$ and thus has a least element.


geometry
geometric transformation
reflection

i just want to know if Georgia Tech requires SAT subject tests?  i couldn't find it online.

and online it said "jan. sat scores may not be considered for admission" what exactly does this mean?

thanks

Thread retitled by moderator to reflect that "GT" is Georgia Tech.


ok, think about this...it is really not that bad, it is a very old puzzle...
Well, there are 2 roses infront of a rose, 2 roses in the back of a rose, one in front, one in the back...how many roses are there in all?  :?:

To clarify this, as I see it:

There are 2 roses in front of a rose and 2 roses behind a rose.
How many roses are there in all, if the fewest number of roses
are allowed?

ive said it before ill say it again
[hide]3?[/hide]

[quote="Cesario"]Way too easy, I think.
Three?  :)[/quote]

 :10:  wow, that was exactly what i thought, but it took so many people like a million guesses to get it right...lol. :rotfl:

[quote="box of rocks"]klutzycherry14,

no, you take the hit on this one.  Your statement of this OLD
problem was mucked up, and I gave you the chance to clarify
it after my post.  You never acknowledged that you hadn't presented it exactly right.

Your statement "...it took so many people like a million guesses
to get it right..." is beyond silly.[/quote]

im sorry, i should have realized that before...i just assumed that that since u said that and i had not contradicted it, everyone would assume that it was correct. and i admit that u were right in your assumption, so i apologize for that, and i was not referring to the people on here when i said the million people thing, i meant when i asked people like in person, like in my family/friends and stuff. so, i apologize for that...hope that is clear now... :oops: