A group of persons is called [i]good[/i] if its members can be distributed to several rooms so that nobody is acquainted with any person in the same room
but it is possible to choose a person from each room so that all the chosen persons are acquainted with each other.

A group is called [i]perfect[/i] if it is good and every set of its members is also good.

A perfect group planned a party. However one of its members, Alice, brought here acquaintance Bob, who was not originally expected, and introduced him to all her other acquaintances. Prove that the new group is also perfect.

[i]Author: C. Berge[/i]

Here is my solution:

One has to show that all subsets of the new set are good. From the condition we already know that all the subsets without Bob are good. Now one hast to prove that all the subsets with Bob are good. In order to show that look at a good distribution of people of a set without Bob. If there are acquiantances of him in every room then he needs a new room. If there is a room without an acquiantance of him he goes into this room. Obviously the distribution in both cases is good.

A bit to easy in comparison to the others I think...

[quote="Max(i)"]
If there are acquiantances of him in every room then he needs a new room. [/quote]

Room only with Bob is very bad. :wink:  Because it's possible that Bob has acquiantance in any room, but now we cann't choose a person from each room and Bob so that all choosen persons are acquainted with each other. (because people that acquainted with Bob may be not acquainted with each other).

My solution is here:
It is obvious that good group is graph such that chromatic number of this graph is equate size of maximal clique. Obvious that all group without Bob is good, and all group with Bob, but without Alice is good too. (because we can exchange Bob with Alice and get a similar group withot Bob). So we need to look at groups with Bob and Alice. Lets $ G$ will be some of those groups. And let $ k$ be a size of maximal clique in group $ G$ without Bob. If in $ G$ size of maximal clique is bigger than $ k$, then we can paint $ G$ without Bob in $ k$ colours, and paint Bob in new colour. In that way we will get not more than $ k \plus{} 1$ colours in $ G$ and size of maximal clique in $ G$ at least $ k \plus{} 1$. So that's ok. If in $ G$ size of maximal clique is again $ k$, then there is no maximal clique with Alice in graph $ G$ without Bob. (else this clique with Bob will have size $ k \plus{} 1$). So we can paint $ G$ without Bob in $ k$ colours and then look at Alice colour. Let it be $ green$. There are $ green$ man in every clique with size $ k$. (because people in this clique have different colours and so there are all $ k$ colours in every maximal clique). Lets take all $ green$ people except Alice and turn they all out for some time. In our new graph $ G$ without Bob and those $ green$ people size of maximal clique lesser than $ k$. (Because in every maximal clique we turn out  at least one man). So we can colour $ G$ without Bob and $ green$ people in $ k \minus{} 1$ colours. Then we paint Bob and all $ green$ people in new colour and add them to our graph. Nobody from $ green$ people isn't acquainted with Bob and with each other (because in $ G$ without Bob they all and Alice have one colour). So this painting of $ G$ in $ k$ colours is correct. So again size of maximal clique is equate chromatic number.

[quote="limsk1"]I have a question!

Can Bob know anyone who is not acquianted with Alice?[/quote]

I think he can...

[quote="limsk1"]I have a question!

Can Bob know anyone who is not acquianted with Alice?[/quote]

NO! He can't.

I'm quite impressed that high schoolers were asked to (and probably did) solve this problem!

I like Akella's solution, and I'd like to restate it here in case anyone doesn't have the specific knowledge to follow it:

A [i]clique[/i] is a group of people who are pairwise connected (all mutual acquaintances). The [i]chromatic number[/i] of a graph (group of people) is the fewest number of colors required to color each person so that no two people who are acquainted have the same color.

A [i]maximum clique[/i] (not to be confused with [i]maximal clique[/i] -- any clique which is not a subset of any other clique) is a clique of maximum cardinality (of which there could be more than one). A crucial point is that the chromatic number of any graph must be at least as large as its maximum clique (because any clique requires that each member is colored differently).

From the problem statement, we can see that the chromatic number of a good group is [i]not larger than[/i] the the cardinality of its maximum clique: if the maximum clique (call it [i]C[/i]) has cardinality [i]k[/i], then each clique member requires his own room (with corresponding color), and if anyone required a color beyond that, he'd need a new room, but wouldn't be part of the maximum clique (as required by the problem statement).

This also means that [i]every maximum clique uses the same k colors as C[/i].

So, now we look at various cases for subsets [i]G[/i] of the new party:

* Bob is not in G: then G is good by assumption.
* Bob is in G but Alice is not: Bob can take the spot Alice would have had by assumption.
* Bob and Alice are both in G: Remove Bob for a moment and consider a good rooming scheme. Let Alice's room be green. If Alice is part of a maximum clique, then Bob can be placed in his own room. So suppose not. Then we can temporarily remove all the other green people from the graph, and the leftover people can be placed into k-1 rooms (because a green person is required to form a clique of size k). Now add back the green people + Bob into their own room. The maximal clique is again size k, meaning that it contains someone from the green room, so the scheme is again good.

Note that this follows easily from the strong perfect graph theorem.

https://en.wikipedia.org/wiki/Strong_perfect_graph_theorem

Assume after adding Bob there is a (hole/antihole) of odd length.  Then if this (hole/antihole) lacks Alice, it existed before as we can replace Bob with Alice.  Else it contains Alice.  If Bob and Alice are not adjacent, then if Bob has two neighbors C and S, then Alice knows C and S and so this can be used to make an odd (hole/antihole).  If Bob and Alice are adjacent in the cycle, then say Bob neighbors R while Alice neighbors T.  Then Bob knows T and Alice knows R, contradicting the fact that the induced graph is a hole.

Note that the letters stand for the surnames of the people who proved the strong perfect graph theorem.


[quote="mysmartmouth"]Do British people refer to themselves as "British", just like Americans refer to themselves as "Americans"?[/quote]

British People are very accurate wrt their origin. They would rather call themselves English, Scottish etc.

I would describe my nationality as British; but if asked where I'm from, I say England. "I'm from Britain" doesn't sound right!

I would describe my nationality as British too. I was born in Scotland but live in England so British seems most appropriate.

[quote="sludgethrower"]I would always call myself Scottish (even though I attend university in England)...and in fact many Scots are insulted when foreigners refer to them as being English.[/quote]

Admittedly, I would rather be called Scottish than English.

I'd agree- I'd say English. It sounds rather pretentious on our part when people abroad refer to Britain as 'Great' Britain; just a tad cringeworthy.


Bad title http://www.mathlinks.ro/Forum/viewtopic.php?t=144404 Locked!


Let $ s$ be the semiperimeter of $ \Delta ABC$. Prove that $ sin \frac{A}{2} \equal{} \sqrt{\frac{(s\minus{}b)(s\minus{}c)}{bc}}$


Let S be a convergent series.If we replaced the terms of that series (I mean if we sum the tems of series different order) is the new series convergent?What is the convergence point?Is it same with original series?

If the series $\sum_k a_k$ is [b]absolutely convergent[/b], i.e., if $\sum_k |a_k|<+\infty$, then any rearrangement of the terms results is a convergent series and the sum is the same as that of the original series. If the series converges but does not converge absolutely, it is possible to rearrange its terms so that the resulting series will converge to any prescribed real number or diverge.


Let $ a, b, c, n$ are positive integers and $ abc > n^3$. Prove that $ (a \plus{} 1)(b \plus{} 1)(c \plus{} 1) \geq (n \plus{} 1)^3 \plus{} n \plus{} 3$

we can not have $ \geq$ if the condition of the problem is $ >$

If $ abc \geq n^3$ , the inequality is not true  for $ a\equal{}b\equal{}c\equal{}n$

Why not? $ 5\ge 4$ is true as far as I know

But the inequality's wrong. Take $ a\equal{}b\equal{}n,c\equal{}n\plus{}x,x\rightarrow 0,x>0$

Then the ineq is $ (n\plus{}1)^2(n\plus{}1\plus{}x)\ge (n\plus{}1)^3\plus{}n\plus{}3$

$ (n^2\plus{}2n\plus{}1)x\ge n\plus{}3$

$ x\ge \frac{n\plus{}3}{n^2\plus{}2n\plus{}1}$.

This isn't necessarily true, for any $ n$, find $ x$ such that the last ineq doesn't hold, and that's it.

I just think that the equality case of the condition should be somehow connected with the equality case of the inequality.

[quote="Bugi"]Why not? $ 5\ge 4$ is true as far as I know

But the inequality's wrong. Take $ a \equal{} b \equal{} n,c \equal{} n \plus{} x,x\rightarrow 0,x > 0$

Then the ineq is $ (n \plus{} 1)^2(n \plus{} 1 \plus{} x)\ge (n \plus{} 1)^3 \plus{} n \plus{} 3$

$ (n^2 \plus{} 2n \plus{} 1)x\ge n \plus{} 3$

$ x\ge \frac {n \plus{} 3}{n^2 \plus{} 2n \plus{} 1}$.

This isn't necessarily true, for any $ n$, find $ x$ such that the last ineq doesn't hold, and that's it.[/quote]
Your counterexample does not work because if $ c \equal{} n \plus{} x,x\rightarrow 0,x > 0$ then $ c$ may be not an integer :!: .

Can you give any example of equality case ?

I've found $ ([a,b,c],n)\equal{}([2,1,1],1)$ or $ ([3,3,1],2)$ and permutations for $ [a,b,c]$, but are these all?

There are infinitely many equality cases. For example $ (a, b, c, n)\equal{}(7,11,13,10), (13,18,21,17), (21,27,31,26)$

Thanx - Now, I've found a family of equality cases


modular arithmetic
number theory unsolved
number theory

Prove that numbers of the form c^2+1 are not divisible by any primes of the form 4k+3

$ c^2 \equal{} \minus{} 1(mod p) \Rightarrow c^4 \equal{} 1(mod p) \Rightarrow 4|p \minus{} 1 or c^2 \equal{} 1$, contradiction,

$ \Rightarrow p \equal{} 1(mod 4)$,
here $ p$ is any prime.

$ c^2\plus{}1$ can be 1 or 2 mod 4.but rhs is 3 mod 4

assume $ p\equal{}4k\plus{}3,p|c^2\plus{}1$ so: $ 1\equiv c^{p\minus{}1}\equiv (c^2)^{(p\minus{}1)/2}\equiv (\minus{}1)^{2k\plus{}1}\equiv \minus{}1\pmod{p}$, contradiction. :D


I have heard that from now on, <10th graders' USAMO qualification will not be based mostly on their AIME scores. I know that before, the <10th graders had a more lenient index calculation. Is this still in effect?

Please read the selection rules for the USAMO in the Teachers' Manual
http://www.unl.edu/amc/d-publication/d1-pubarchive/2006-7pub/07-USAMO-TM/TM-USAMO,2007.pdf
page, 4, section II, and pay particular attention to part 4 at the top of the second column.

The selection rules will be the same this year as in 2007.  In a few days we will have the 2008 USAMO Teachers' Manual posted on the first page of our website.  Until then, you can rely on the 2007 USAMO Teachers' Manual for authoritative information, the 2008 version has only date changes and few typographical changes.

Steve Dunbar
MAA Director, American Mathematics Competitions


function
induction
limit
algebra proposed
algebra

Let $f: \mathbb R \to \mathbb R$ be a continuous function such that there exist numbers $a$ and $b$ with $ 0<a,b<\frac{1}{2}$ and
\[ f(f(x))\equal{}af(x)\plus{}bx, \quad \forall x \in \mathbb R.\]
Show that there exist $ k$ for which $ f(x)\equal{}kx$ for all $x \in \mathbb R$.

[quote="Victory.US"]let $ f: R \to R$ be continuous function such that: there exist $ 0 < a,b < \frac {1}{2}$ and
$ f(f(x)) = af(x) + bx$ ,$ \forall x \in R$

Show that there exist $ k$ what satisfy $ f(x) = kx, \forall k \in R$[/quote]

1) $ f(x)$ is bijective
Since $ b\neq 0$, we can write $ x = \frac 1b(f(f(x)) - af(x))$

A first consequence of this equation is that $ f(x)$ is injective, and so monotonous, since continuous.
A second consequence is that $ f(x)$ cant have a finite limit when $ x\to \pm\infty$ (else RHS would be finite and LHS not). So $ f(x)$, since continuous monotonous, is surjective and so bijective.
Q.E.D

2) Some infos on the roots of  $ x^2 - ax - b = 0$
Let then $ r_1 < 0 < r_2$ the two real roots of $ x^2 - ax - b = 0$ (remember $ a > 0$ and $ b > 0$)
$ r_2\geq 1$ would imply $ r_1\leq - \frac 12$ (since $ r_1 + r_2 = a < \frac 12$ and then $ - r_1r_2\geq \frac 12$, which is wrong since $ - r_1r_2 = b < \frac 12$. So $ r2 < 1$

$ r_1\leq - 1$ would imply $ r_2\geq\frac 12$ (since $ r_1 + r_2 = a < \frac 12$ and then $ - r_1r_2\geq \frac 12$, which is wrong since $ - r_1r_2 = b < \frac 12$. So $ r1 > - 1$

Last, since $ r_1 + r_2 = a > 0$, we get that $ |r_2| > |r_1|$
So : $ - 1 < r_1 < 0 < r_2 < 1$ and $ 1 > |r_2| > |r_1|$

3) main demo :
$ f(x)$ bijective implies that $ g(x) = f^{ - 1}(x)$ exists, is defined over $ \mathbb R$ and we have $ x = ag(x) + bg(g(x))$

Let then $ d = f(c)$ for some $ c\in\mathbb R$ and the sequences  $ u_n$ and $ v_n$ defined as :
$ u_0 = c$
$ u_1 = d$
$ u_{n + 2} = au_{n + 1} + bu_n$
$ v_0 = d$
$ v_1 = c$
$ v_{n + 2} = - \frac abv_{n + 1} + \frac 1b$

We clearly, with immediate induction, have $ u_{n + 1} = f(u_n)$ and $ v_{n + 1} = g(v_n)$ or again $ v_n = f(v_{n + 1})$

We also have $ u_n = \frac {(d - r_2c)r_1^n - (d - r_1c)r_2^n}{r_1 - r_2}$ and $ v_n = \frac {(d - r_2c)r_1^{1 - n} - (d - r_1c)r_2^{1 - n}}{r_1 - r_2}$

Since $ 1 > |r_2| > |r_1|$, we get that $ \lim_{n\to + \infty}u_n = 0$ and, since $ u_{n + 1} = f(u_n)$ and $ f(x)$ continuous, $ f(0) = 0$
So, since $ f(x)$ is a continuous monotonous bijection, $ \frac {f(x)}x$ has a constant sign over $ \mathbb R^*$ (positive if $ f(x)$ is increasing, negative if $ f(x)$ is decreasing).

But, since $ 1 > |r_2| > |r_1|$ :
If $ d - r_1c\neq 0$ $ \lim_{n\to + \infty}\frac {u_{n + 1}}{u_n} = r_2 > 0$

If $ d - r_2c\neq 0$ $ \lim_{n\to + \infty}\frac {v_{n + 1}}{v_n} = \frac 1{r_1} < 0$

And so, since the signs of ${ \frac {u_{n + 1}}{u_n} = \frac {f(u_n)}{u_n}}$ and $ \frac {v_{n + 1}}{v_n} = \frac {v_{n + 1}}{f(v_n)}$ must be the same, we conclude that :
Either $ d = r_1c$, either $ d = r_2c$

And so $ \forall x$, either $ f(x) = r_1x$, either $ f(x) = r_2x$

And, since $ f(x)$ is continuous and bijective :

Either $ f(x) = r_1x$ $ \forall x$
Either $ f(x) = r_2x$ $ \forall x$

Q.E.D.

thank you very much, pco for the last post   :)  :)


$ABCD$ is a quadrilateral with $AD=BC.$ If $\angle ADC$ is greater than $\angle BCD,$ prove that $AC>BD.$

I'm thinking Law of Cosines? (/Hinge thm)

$AC^{2}=AD^{2}+CD^{2}-2AD \cdot CD \cos{\angle{ADC}}$

$BD^{2}=BC^{2}+CD^{2}-2AD \cdot BC \cos{\angle{BCD}}$

Since $f(x)= \cos{x}$ is monotonically decreasing in $[0, \pi]$, so $AC>BD$.


Putnam
inequalities
geometry
college contests

Inequalities and Geometry don't appear much on the Putnam, right?

I definitely wouldn't say that. I've taken it three years in a row now and there have (to my memory) been inequalities and geometry on every test. It just isn't as explicit as most of the other Olympiads make it. They probably won't say prove this about this triangle. See B1 of this past year. They probably won't say prove this inequality, but look at A1 of this past year (it is both geometry and inequalities).

More examples are 2005 A4, A6, and B4; and
2004 A2, A6 (talk about inequalities), and B2.


number theory
least common multiple
inequalities

Order the following from smallest to largest: $ x \equal{} 2^{\frac {1}{2}}$, $ y\equal{}7^{\frac {1}{12}}$, $ z\equal{}9^{\frac {1}{15}}$.

That solution is great. Heres my approach.
$ x \equal{} 2^{\frac {1}{2}}$ ; $ y \equal{} 7^{\frac {1}{12}}$ ; $ z \equal{} 9^{\frac {1}{15}}$
[hide]I felt my way through this one really.
$ x, y$ seemed to be the easiest. I used an approximation for $ y$ to spit out a relation.
$ 8^{\frac {1}{3}} \equal{} 2$ ; $ 2^{\frac {1}{4}} < 2^{\frac {1}{2}}\Longrightarrow x > y$.

$ z$: My intuition tells me it's the smallest, so I'll go with that. I set up an inequality relating the bases/exponents of $ y$ and $ z$. Then I plugged in values to confirm or contradict my assertion that $ y > z$
[hide]$ (x \plus{} 2)^{\frac {1}{n \plus{} 3}} < x^{\frac {1}{n}}\Longrightarrow x \plus{} 2 < x^{(1 \plus{} \frac {3}{n})}$
x=7 [b];[/b] n=12
$ 9 < 7^{\frac {5}{4}}\Longrightarrow 9^4 < 7^5$
$ 9^4 \equal{} 81^2 \equal{} 80^2 \plus{} 160 \plus{} 1 \equal{} 6561$
$ 7^5 \equal{} 7(50 \minus{} 1)^2 \equal{} 7(2500 \minus{} 99) \equal{} 7(2401) \equal{} 16807$

$ 6561 < 16807$ [b]implies[/b] $ z < y$[/hide]
This solution clearly verifies the other.[/hide]
We have confirmed that $ \boxed{x > y > z}$

[b]EDIT :[/b]  :love: $ @$ t0ra


Solve this equation: $ sin2x\plus{}2tanx\minus{}3sinx.sin2x\plus{}sin3x\equal{}6cos^3x$

hello, by using the addition formulas we have $ 2\sin(x)\cos(x)^2\plus{}4\sin(x)\cos(x)^3\minus{}\sin(x)\cos(x)\plus{}2\sin(x)\minus{}6\cos(x)^2\equal{}0$. Substituting $ \tan\left(\frac{x}{2}\right)\equal{}t$ we have $ 3t^8\minus{}t^7\minus{}17t^5\minus{}6t^4\plus{}9t^3\minus{}7t\plus{}3\equal{}0$.
Sonnhard.

[quote="Dr Sonnhard Graubner"]hello, by using the addition formulas we have $ 2\sin(x)\cos(x)^2 \plus{} 4\sin(x)\cos(x)^3 \minus{} \sin(x)\cos(x) \plus{} 2\sin(x) \minus{} 6\cos(x)^2 \equal{} 0$. Substituting $ \tan\left(\frac {x}{2}\right) \equal{} t$ we have $ 3t^8 \minus{} t^7 \minus{} 17t^5 \minus{} 6t^4 \plus{} 9t^3 \minus{} 7t \plus{} 3 \equal{} 0$.
Sonnhard.[/quote]

[color=darkblue]Oh! How do you solve equation $ 3t^8 \minus{} t^7 \minus{} 17t^5 \minus{} 6t^4 \plus{} 9t^3 \minus{} 7t \plus{} 3 \equal{} 0$ [size=150]?[/size][/color]


Does exist infinitely many integers $n$ such that: $n|3^{n-1}-2^{n-1}$ ?

Related problem: [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=24475]Iran 2005[/url]

These problems are either impossible to solve, or they have extremely short solutions :).

Take $3^p-2^p$, where $p$ is a prime $\ne 2,3$. It works because $p|3^p-2^p-1$ (Fermat's Small Theorem), so $3^p-2^p|3^{3^p-2^p-1}-2^{3^p-2^p-1}$.

Short solution, grobber!
Other solutions with  $n=3^{2^k}-2^{2^k}$  and  $n=3^{3^k}-2^{3^k}$.


number theory
relatively prime
prime factorization

[quote="anirudh"]I need help on this problem:

[b]How many positive integers less than or equal to 250 are relatively prime with 250[/b][/quote]

I'm either too lazy to do it or know I'll be too slow.

What I would do is find the number of numbers that aren't relatively prime with 250. That's all numbers with 2 or 5 as a factor (since $250=5^3*2$)

[hide="hint"]start with noticing that any number that is divisible by 2 or 5 is not relatively prime to 250. [/hide]

i forgot what relatively prime meant  :(

[quote="anirudh"]i forgot what relatively prime meant  :([/quote]

Relatively prime means that two numbers don't share a common factor aside from 1.

For example, 5 and 6 are relatively prime, despite 6 not being a prime.

6's factors: 1,2,3,6
5's factors: 1,5

No overlap besides 1, so they're relatively prime.

If you want an easier method, try taking all 250 numbers and finding those that are NOT relativly prime.

[hide]for every ten numbers, there are 4 relatively prime numbers. Hence 4x25=100[/hide]

[hide]I think this is called the fe function. The formula to find out how many numbers below N are relatively prime to N would be: N(1-$1/p$)(1-$1/q$)(1-$1/r$) etc. etc. where p,q, and are are prime factors of N. In this problem, there are two factors: 2 and five. So you'd take 250(1-$1/5$)(1-$1/2$) = 250($4/5$)($1/2$) to get $100$

OR.

The factors of 250 are 2 and five. First find how many numbers below 250 share a common factors with 250. 250 can be prime factorized into 2's and 5's. the number of numbers 250 or lower that can be divided by 2 is 125 (250/2), and the number that can be divided by 5 is 50. The total is 175. Then subtract the ones that you counted twice, the ones that are divisible by 2 AND 5  (10). That number is 25. So 175-25 = 150. That's the number of numbers less than 250 that share AREN"T relatively prime to 250. 250-150 = $100$[/hide]

1.  Take the number and put it into prime factorization 2^1*5^3
2.  Take one less than each power  2^0=1 and 5^2 = 25
3.  Tale one less than each base  1 and 4
4.  Multiply the results together  1*25*1*4=100


In a mathematical contest, there were $ n\geq 4$ problems, each solved by exactly $ 4$ contestants, and for any two problems, there is exactly one student who solved both of them.

Assuming there were at least $ 4n$ contestants, find the minimum value of $ n$ for which there always exists a contestant who solved all problems.


calculus
integration
function
algebra
polynomial
quadratics
partial fractions

How can I integrate

(cy + d)/(ay + b) with respect to y

if a, b, c, d are constants and y is the only variable. Do I use partial fractions? Thanks

For $a\neq 0,$ we can rewrite as $\frac{cy+d}{ay+b}=\frac{1}{a}\left(c+\frac{ad-bc}{a}\cdot \frac{1}{y+\frac{b}{a}}\right)$

No. Partial fractions is a technique for pulling apart a rational function whose denominator has at least two different factors. We have only one factor here.

It is part of the larger "how to handle rational functons" picture. A rational function is a quotient of polynomials (and the polynomials themselves can be considered rational functions.)

Step 1: It this a proper fraction? (In a proper fraction, the degree of the numerator is strictly less than the degree of the denominator.) If not, employ long division to write the rational function as a polynomial plus a proper fraction.)

Step 2: Factor the denominator. (Alas, not an algorithm.)

Step 3: Employ partial fractions, if necessary.

In this problem, we don't need to go past step 1.

$\frac{cy+d}{ay+b}=\frac ca+\frac{ad-bc}{a(ay+b)}$

Now you can proceed to integrate.

Note: partial fractions is not a technique of integration. It is a technique of algebra that just happens to have some uses in integration.

[quote="Kent Merryfield"]
Note: partial fractions is not a technique of integration. It is a technique of algebra that just happens to have some uses in integration.[/quote]
I disagree... isn't an extensive treatment of partial fractions founded in complex analysis?

The only piece of partial fractions that complex analysis gets us is that every polynomial factors. Everything else is just a variation on polynomial interpolation, and the arguments we need are linear algebra.

We could build a theory of partial fractions based on general irreducible polynomials with no analysis at all. It would be applicable over any field.

I was defining the term "partial fractions" narrowly to mean step 3 in my post above - making the assumption that the denominator has already been factored. And as jmerry said, that is algebraic and can be done over any field.

Everything about the whole process is algorithmic and mechanical, with one exception: step 2, factoring the denominator. Yes, the Fundamental Theorem of Algebra assures us as a pure existence theorem that such factors exist (this applies to real polynomials being factored into linear and quadratic factors), but the Abel-Galois unsolvability results stand in the way of any algorithm.

One can find uses for the technique of partial fractions other than integration. The practical use of Laplace transforms to solve constant-coefficient linear ODE is one such use.

I did not see the original problem as falling into my narrow definition of partial fractions, since there was only a single factor in the denominator.


geometry
3D geometry
sphere
circumcircle
trigonometry
tetrahedron
number theory

The points $A, B$ and $C$ lie on the surface of a sphere with center $O$ and radius 20.  It is given that $AB=13, BC=14, CA=15,$ and that the distance from $O$ to triangle $ABC$ is $\frac{m\sqrt{n}}k,$ where $m, n,$ and $k$ are positive integers, $m$ and $k$ are relatively prime, and $n$ is not divisible by the square of any prime.  Find $m+n+k.$

[hide]
it is only necessary to find the distance from the center of the sphere to the center of the circumcircle of the triangle..
and the formula for the circumradius of a triangle is
$R = \frac{abc}{4A}$, where a, b, c are side lengths and A is the area of the triangle.
Heron's formula yields
$A = \sqrt{21(7)(6)(8)} = 84\\ R = \frac{(13)(14)(15)}{4(84)} = \frac{65}{8}\\$
Using pythagoras gives $\frac{15\sqrt{95}}{8}$ as the distance
$m=15, n=95, k=8,$ so $m+n+k=\boxed{118}$

[/hide]

[hide]You can calculate the circumradius of the triangle.  Area$=\sqrt{21*8*7*6}=84=\frac{1}{2}(13)15*\sin{B}=\frac{13*15*14}{4R} \implies R=\frac{13*15}{6*4}$, and we know our distance is $\sqrt{400-(\frac{65}{8})^2}$...it gives me that the distance is $\frac{15\sqrt{95}}{4}$[/hide]

[hide] The point on ABC on the altitude's base of tetrahedron ABCO is the circumcenter of ABC, because it lies on the intersections of perpendicular bisectors of AB, BC, and AC.

So by $R = \frac{abc}{4A}$, you find $R = \frac{65}{8}$. Just memorized that area of 13-14-15 is 84, from MC, I think. You can use Heron's to check.

And so $\sqrt{20^2 - \displaystyle\left(\frac{65}{8}\right)} = \frac{15\sqrt{95}}{8}$, and adding yields $118$.[/hide]

$R = \frac{abc}{4A}$

Could you post a proof?

$R = \frac{abc}{4K} \rightarrow K = \frac{abc}{4R} \rightarrow \frac{1}{2}ab \sin C = \frac{abc}{4R}$
$\sin C = \frac{c}{2R} \rightarrow \frac{c}{\sin C} = 2R$

The final statement is true by extended law of sines, thus the first statement is true.

Note: I used K to denote the area of a triangle.

sorry to revive old thread:
could somebody explain why in tetrahedron OABC, altitude from O passes through circumcenter of ABC?

[hide="Visually"]- Imagine the plane that contains triangle ABC.
- Now, slice the sphere with this plane.
- The cross section should be a circle.
- The circumcenter of ABC is the center of this cross-section circle, and is the closest point to the center.
+ Since the circumcenter is the point on this plane closest to the center of the sphere, the segment joining the circumcenter with the sphere's center is perpendicular to the plane.
+ Since the segment is perpendicular to the plane, it is the altitude.[/hide]

Of course, all that's really relevant are the "-" steps; the "+" steps show why it's the altitude, but that is only an easy way of stating the equivalent (and more relevant) fact, that the circumcenter is the closest point on the plane to the center of the sphere.

Let $ H$ be the foot of the altitude from $ O$ to the plane $ ABC$. Then triangles $ HOA$, $ HOB$, and $ HOC$ are congruent because of HL congruency with $ OH\equal{}OH\equal{}OH$ and $ OA\equal{}OB\equal{}OC$. So then $ AH\equal{}BH\equal{}CH$, so $ H$ is the circumcenter of triangle $ ABC$.

thanks.
as a follow-up questions regarding tetrahedra and the alitude from the vertex...
in general tetrahedron WXYZ, does the altitude from W always intersect triangle XYZ in its circumcircle.

From this problem I see why this is necessarily true when $ WX \equal{} WY \equal{} WZ$, but does it hold if the equality condition is dropped?

Definitely not.  For example, consider a tetrahedron with vertices W(0,0,0), X(x,0,0), Y(0,y,0), Z(0,0,z).  Obviously the altitude from Z to WXY intersects WXY at W, yet since WXY is right its circumcenter is the midpoint of XY (which is definitely not W unless the tetrahedron is degenerate).

Let the perpendicular line from $O$ hit $ABC$ at $O'$. We note that $O'$ is the circumcenter of $ABC$. It is well known that $R=\frac{abc}{4\cdot [ABC]}=\frac{13\cdot 14\cdot 15}{4\cdot 84}=\frac{65}{8}$ Hence, $OH=\sqrt{20^2-\left(\frac{65}{8}\right)^2}=\frac{15\sqrt{95}}{8}$. Thus, $m+n+k=118$ as desired.

why is it not the incenter instead of the circumcenter, it seems like it is the incenter that we are trying to find the distance to

Let $X$ be the foot of the line passing through $O$ and perpendicular to the plane containing $\triangle ABC$. Let $P$ be any point on the intersection of this plane and the sphere centered at $O$. By the Pythagorean theorem, we find $$XP=\sqrt{PO^2-OX^2}.$$ However, $PO$ is the radius of the sphere and $OX$ is a fixed distance, so this intersection is a locus of points that are a fixed distance from $X$ and contained in a plane. Hence it is a circle. Furthermore, this circle contains the vertices of $\triangle ABC$ and is thus the circumcircle of $\triangle ABC$ with circumcenter $X$. Call its circumradius $R$.

We apply Heron's formula to compute $$[ABC]=\sqrt{21(21-13)(21-14)(21-15)}=84.$$ Then, we can compute the circumradius with $$R=\frac{abc}{4[ABC]}=\frac{13\cdot14\cdot15}{4\cdot84}=\frac{65}{8}.$$ The distance from the $O$ to $\triangle ABC$ is given by $OX$, so we can finish with the Pythagorean theorem and compute
\begin{align*}
OX&=\sqrt{20^2-R^2} \\
&= \sqrt{20^2-\left(\frac{65}{8}\right)^2} \\
&= \frac{15\sqrt{95}}{8}.
\end{align*}
The answer is then $15+95+8=\boxed{118}$.

Let $P$ be the foot of the altitude from $O$ the plane containing $\triangle ABC.$ Since the cross section of the sphere is a circle, point $O$ is the circumcenter of $\triangle ABC.$ Since $R = \frac{abc}{4A}$, $R = \frac{65}{8}.$ Thus, $OP = \sqrt{20^2-R^2} = \frac{15\sqrt{95}}{8}.$ Therefore, the answer is $15 + 95 + 8,$ which is $\boxed{118}.$


find all functions $f$ such that
$f(x)\leq2^x$ and $f(x+y)\leq f(x)f(y)$   $ \forall  x \in R$

  :)


geometry
3D geometry
prism
analytic geometry

As the figure, the base of the triangular prism is an equilateral triangle with side length 2, the lateral surface is a square. Suppose the base is perpendicular to the lateral surface of the triangular prism .Now, the two medians of the equilateral $ \triangle ABC$ intersect at $ P$. The two diagonals of the square $ ABCD$ intersect at $ Q$, then how about the length of $ PQ$?

Coordinate geometry:

Set point $ B$ as the origin, set $ C$ to have coordinates $ (2, 0, 0)$, and $ E$ to have coordinates $ (0, 2, 0)$.

$ P$ therefore, has coordinates $ \left(1, 0, \frac {\sqrt {3}}{3}\right)$, and $ Q$ will have coordinates $ \left(\frac {1}{2}, 1, \frac {\sqrt {3}}{2}\right)$. (Do you see why these coordinates are valid?)

Then, by distance formula, we have $ PQ \equal{} \frac {2\sqrt{3}}{3}$.

EDIT> Note to self: $ 3 \times 4 \ne 30$

[quote="yanglunj"]we have $ PQ \equal{} \frac {\sqrt {30}}{3}$.[/quote]  With you until this point.  Check your arithmetic?

It's modestly quicker to note that if $ M$ is the midpoint of $ AB$ then $ PMQ$ is a right triangle.


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

Do not double post:
[url]http://www.artofproblemsolving.com/Forum/viewtopic.php?t=324641[/url]


number theory
relatively prime
number theory proposed

This problem started from a Korean olympiad problem. Prove that if  $ a_1,,a_n $ are positive integers, any two of them relatively prime and if $ A=(a_1+a_2++a_n)\cdot (\frac{1}{a_1}++\frac{1}{a_n}) $ is an integer, then $ A<n\cdot 2^{2^n} $. Anyway, this isnt that hard. But I dont have a proof for the following questions: a) do there exist infinitely many n for which there exist such numbers? Is the density of such numbers n zero?
b) for any such number n, can you a better upper bound?
[/i]

[quote="harazi"]a) do there exist infinitely many n for which there exist such numbers? Is the density of such numbers n zero? [/quote]

$(a_1,a_2,...,a_n) = (1,1,...,1)$ is always ok I think... so there is one for every $n$ :)

(and I really doubt if there are any besides the $(1,1,..,1)$ solution...)

[quote="Peter VDD"](and I really doubt if there are any besides the $(1,1,..,1)$ solution...)[/quote]

An example for $n=3$ would be $a_1=1,a_2=2,a_3=3$.

Thanks a lot for these trivial examples! Could you find others? I knew these and they don't interest me!

I think that for this problem there’s no satisfactory way to define “non-trivial, and here's why:

It’s easy to show that the condition is equivalent to $a_k|S=\sum_{i=1}^n a_i,\ \forall k\in\overline{1,n}$. Since the $a_i$s are coprime, this means that $\prod a_i|\sum a_i$, which, in turn, means that $\prod a_i\le \sum a_i$. For $n\ge 4$, it’s easy to show that in each such solution we must have at least two $1$s, so the numbers can’t be distinct.

On the other hand, we can find general forms of solutions with lots of $1$s, but they look more or less “trivial”: $(a_1,\ldots,a_{n-1},a_n)=(1,\ldots,1,n)$ for all $n$ and $(a_1,\ldots,a_{n-2},a_{n-1},a_n)=(1,\ldots,1,2,n)$ for odd $n$. We can also find solutions which have as many numbers $\ne 1$ as we want. Take $k$ pairwisely coprime numbers $1<a_{n-k+1}<\ldots<a_n$ and take $a_1=\ldots=a_{n-k}=1$. We need an $n$ s.t. $a_t|n-k+a_{n-k+1}+\ldots+a_n,\ \forall t\in\overline{n-k+1,n}$, but it’s obvious that we can find such an $n$ by employing the Chinese Remainder Theorem.

My question is, after all this nonsense (:D), what do you mean by “trivial” in this case?

I apologise, grobber, you are right. The problem is in fact trivial. Yet, there is one more question: what is the maximal value of that integer number from the problem. I showed that it is smaller than $ 2n^2 $ (I must have been idiot when writing n2^2^n ), but...


inequalities
trigonometry
inequalities unsolved

$x,y,z$ are reals. show that $sinx\cdot cosy+siny\cdot cosz+sinz\cdot cosx\le \frac{3}{2}$

That's easy we can assume $\sin x,\sin y,\sin z,\cos x,\cos y,\cos z$ is all positive.
So by AM-GM:
$\sin x\cos y+\sin y\cos z+\sin z\cos x\leq\frac{1}{2}(\sin^2x+\cos^2y+\sin^2y+\cos^2z+\sin^2z+\cos^2x)=\frac{3}{2}$.


Two players play the following game:
they have a bar of chocolate of dimension $ m\times n$ partitioned into squares $ 1\times 1$ (it is labeled $ (1,1)$ to $ (m,n)$ starting from left-bottom corner to right-upper corner )
A move consists in choosing a square (i.e. a $ (i,j)$ position) [b]with[/b] chocolate and taking all the chocolate from the squares $ (k,l)$ with $ k\ge i$ and $ l\ge j$.
The chocolate from the position $ (1,1)$ is poisoned.
A player loses if he takes the poisoned chocolate.
The players move alternatively.
Prove that the first player to move always has a win strategy.

This game is well-known, and usually shows up under the name of "Chomp".

Here is one web-page about chomp: http://www.win.tue.nl/~aeb/games/chomp.html


probability
combinatorics proposed
combinatorics

Let me remind you ,for the sake of clarity how we play at NIM. We place three piles of counters on a table. There are two players A and B and the player selects one of the piles and from it takes as many counters as he chooses;one , two,...the whole pile.A and B play alternately and the player who takes up the last counter wins (i.e. the player who can't move loses).
Now, assuming that:

a)each pile contains less than   $2^{n}$ counters,
b)no pile is zero (i.e. there are three piles),
c)both players know the theory,
d)the number in each pile at the beginning was determined by chance,

find $P(n)$ that is the probability (chance) that the second player should win

If you want you can also find the same probability but in the misère NIM i.e. same rules as NIM except that the player who takes the last counter loses.

Sorry. It's my mistake.
I didn't consider when XOR sum of two piles is zero.

I think its 0 or 1, since one of the player has winning strategy.

No.

[quote]c)both players know the theory, [/quote] so certainly one has the winning strategy and is bound to win but  the exercise asks you exactly to find that probability (or better  [quote]the probability (chance) that the second player should win [/quote]) and it's quite straightforward.


If $ a\plus{}b\plus{}c\equal{}0$ prove that

$ (\sum a^2)^3 \minus{}54a^2b^2c^2\equal{}2(a\minus{}b)^2(b\minus{}c)^2(c\minus{}a)^2$

Good work. :)

[quote="manlio"]If $ a \plus{} b \plus{} c \equal{} 0$ prove that

$ (\sum a^2)^3 \minus{} 54a^2b^2c^2 \equal{} 2(a \minus{} b)^2(b \minus{} c)^2(c \minus{} a)^2$

Good work. :)[/quote]

Let $ P(x)\equal{}(x^2\plus{}(x\plus{}c)^2\plus{}c^2)^3\minus{}54x^2(x\plus{}c)^2c^2$ a polynomial whose degree is 6
Let $ P'(x)\equal{}6(2x\plus{}c)((x^2\plus{}(x\plus{}c)^2\plus{}c^2)^2\minus{}18c^2x(x\plus{}c))$

It's easy to check that :
$ P(c)\equal{}P(\minus{}2c)\equal{}P(\minus{}\frac c2)\equal{}0$
$ P'(c)\equal{}P'(\minus{}2c)\equal{}P'(\minus{}\frac c2)\equal{}0$

So $ P(x)\equal{}a(x\minus{}c)^2(x\plus{}2c)^2(x\plus{}\frac c2)^2$. Comparing then high order coefficients, we get $ a\equal{}8$ and :

$ (x^2\plus{}(x\plus{}c)^2\plus{}c^2)^3\minus{}54x^2(x\plus{}c)^2c^2\equal{}2(x\minus{}c)^2(x\plus{}2c)^2(2x\plus{}c)^2$

Setting $ x\equal{}a\equal{}\minus{}b\minus{}c$ in this expression, we get the result.

[quote="manlio"]If $ a \plus{} b \plus{} c \equal{} 0$ prove that

$ (\sum a^2)^3 \minus{} 54a^2b^2c^2 \equal{} 2(a \minus{} b)^2(b \minus{} c)^2(c \minus{} a)^2$

Good work. :)[/quote]
It get's easy if you remember:
$ (a\minus{}b)^2(b\minus{}c)^2(c\minus{}a)^2 \equal{} 27(\minus{}(w^3\minus{}3uv^2\plus{}2u^3)^2\plus{}4(u^2\minus{}v^2)^3)$. When $ 3u\equal{}a\plus{}b\plus{}c,3v^2\equal{}ab\plus{}bc\plus{}ca,w^3\equal{}abc$. :P

[quote="Dimitris X"]From which algebra book did you find these interesting problems [b]manlio???[/b][/quote]

Sorry, but I don't remember the title of the book as I wrote out these problems on my notebook many years ago . Sorry.


number theory
prime numbers
number theory proposed

Let $p,q$ be positive prime numbers and suppose $q>5$. Prove that if $q \mid 2^{p}+3^{p}$, then $q>p$.

[i]Laurentiu Panaitopol[/i]


Find all natural numbers $x, y, z$ such that $x+2y+2z=xyz$

[hide]divide out by xyz, to get
$\frac{1}{yz}+\frac{2}{xz}+\frac{2}{xy}=1$
from here it seems pretty standard, but i don't remember how to do it...there is something like you show that the fractions are greater than something, move that over to the LHS, and the other fractions cannot be that high either, so and you get that x,y,z cannot be that high...anybody else know how to do this?[/hide]

[hide]so 1/yz+2/zx+2/xy=1

we can easy see that 1/3+2/6+2/6=1 (it is also the only solution)

yz=3
xz=6
xy=6

x=2*Sq(3), y=Sq(3), z= Sq(3)

And hoe dis it work actually LH ...[/hide]

[hide]
Let $a=yz$, $b=xz$, $c=xy$.

$\frac{1}{a}+\frac{2}{b}+\frac{2}{c}=1$

$\frac{bc + 2ac + 2ab}{abc} = 1$

$bc + 2ac + 2ab = abc$

Err okay nevermind.
[/hide]

[quote="José"]natural solutions[/quote]

Oops :oops:

$x + 2y + 2z = xyz$
$2y + 2z = xyz - x$
$2(y + z) = x(yz - 1)$

since theyre in ratio:
___
for natural numbres we can try letting $y + z = x$
so $2 = yz -1$ or $3 = yz$
y,z = 3,1 or 1,3
x = 4
which is a solution
___
if you let $2 = x$..

$yz - 1 = y + z$
$yz - y = z + 1$
$y(z - 1) = z + 1$
$y = (z + 1)/(z - 1)$
by inpection to produce natural solution for y , z can only be 2 or 3

so if so $z,y = 3,2 or 2,3$
which satisfies original equation
$2(2 + 3) = x(2*3 - 1)$ where $2 = x$ as stated earlier
___

and the final case where $x = yz - 1$
so $2 = y + z$
$2 - z = y$
$x = (2 - z)z - 1$
$-x = z^2 - 2z + 1$
$-x = (z - 1)^2$
$sqrt(-x) = z - 1$

therefore $x$ must be negative which is not a natural number so the natural solutions to this problem are:

x, y, z = (4, 3, 1),(4, 1, 3),(2,2,3),(2,3,2)

[quote="10000th User"]Agent, your solution is not complete. What about this triplet $(1,3,7)$? Certainly, $1+2\cdot3+2\cdot7=21=1\cdot3\cdot7$ :D[/quote]

doh! no idea how to get 1, 3, 7 lol would u mind showing :D

edit: i guess since they're in ratio you can have 1 be N times larger than another.. or something like that like 2N = x or something


geometry
geometric transformation
reflection
circumcircle
geometry proposed

Given triangle $ ABC$. Point $ O$ is the center of the excircle touching the side $ BC$. Point $ O_1$ is the reflection of $ O$ in $ BC$. Determine angle $ A$ if $ O_1$ lies on the circumcircle of $ ABC$.

Is this really trivial or am I wrong?

We have that $ < OBC \equal{} 90 \minus{} <\frac {B}{2}$, which implies that $ < BO_{1}O \equal{} <\frac {B}{2}$.Similarly, $ < CO_{1}B \equal{} \frac {C}{2}$

But $ O_{1}ABC$ is cyclic, then $ < BAC \equal{} < BO_{1}C$.
Hence, $ \frac {3}{2}(180 \minus{} < A) \equal{} 180$ and then $ < A \equal{} 60$.

Probably I am making some mistakes or misunderstanding the problem. I didn't get $ 60^{\circ}$ like [b]msecco[/b].
I got $ \angle A \equal{} 36^{\circ}$.
We have $ \angle OBC \equal{} 90^{\circ} \minus{} \frac B2$ and $ \angle OCB \equal{} 90^{\circ} \minus{} \frac C2$. Which implies $ \angle BOC \equal{} \frac B2 \plus{} \frac C2 \equal{} 90^{\circ} \minus{} \frac A2 \equal{} 2A \iff A \equal{} 36^{\circ}$.

I think that you misunderstood, dear friend.You didn't make mention of the point $ O_{1}$

Oups....sorry. :blush: I misunderstood. I thought that the problem asks for the case when $ O_1$ coincides with circumcenter. (not circumcircle).

we have $\angle BO_1C=\angle BAC=\angle BOC$,but $\angle BOC=\angle B/2+\angle C/2$,hence $\angle BAC=\angle B/2+\angle C/2$,so $\angle BAC=60$.


So please consider n>2  :blush:

Sorry I always forget about assumptions...


A circle passes through the points (-2, 0), (0, 2), and (8, 0). What are the coordinates of its center?

Let $A(-2,0),\ B(0,2),\ C(8,0).$ You are to find the intersection point of the perpendicular bisectors  $AB$ and $BC.$

[quote="ehehheehee"][hide]It is 3,-3?[/hide][/quote]

Yes, it is. :) Finding thei ntersection points of the perpendicular bisectors $AB$ and$AC$ leads to an easy solution.

I didn't do that though

I set up an equation

The point must be in between the -2,0 and the 08,0

so it is on the ilne x=3

then I set up an equation

25+x^2=9+(x+2)^2 the distance formula in relationship with either -2,0 and 8,0 with 0,2

x=3

so the point is 3 down from 3,0


geometry
geometric transformation
linear algebra
matrix
percent
vector
induction

How do you solve the following problem with a translation matrix?
Fifty percent of the population of a town lives in neighborhood A while Fifty percent live in neighborhood B. 35% of those who live in neighborhood A will move to B in one week while 28 percent of those who live in B will move to A in one week. What is the distribution the week after next, 21 weeks from now?

Thanks in Advance.

If you were in a stochastic processes course, talking about Markov chains, the usual conventions would represent the population as a row vector, multiplied on the right by a transition matrix. If you were in a typical linear algebra class, with this as an exercise illustrating matrix multiplication, then the usual conventions would represent the population as a column vector, multiplied on the left by a transition matrix.

I'm going to assume the latter; if in fact you mean the former, then take your own transposes.

Let the population at any given time be represented by a column vector. At time zero, that vector is $ x_0=\begin{bmatrix}0.5\\0.5\end{bmatrix}.$ (I just adopted the convention that the total population is $ 1.$ If you'd like to use a larger number for the total population, multiply accordingly.

We want to find a matrix $ T$ such that $ Tx_0=x_1,$ where $ x_$ is the population vector after a week.

The upper right entry of $ T$ multiplies the second entry of $ x_0$ and puts the result in the first entry of $ x_1.$ Hence, this represents people moving from B to A. Similarly the lower left entry of $ T$ would represent people moving from A to B.

So far, we have $ T=\begin{bmatrix}&.28\\.35&\end{bmatrix}$

Now, what about the main diagonal? Elements on the main diagonal represent people who don't move. $ 65\%$ of those in A don't move and $ 72\%$ of those in B don't move. That gives us

$ T=\begin{bmatrix}.65&.28\\.35&.72\end{bmatrix}.$

Now what happens in later weeks? Making some assumptions about independence that I suspect the proposers of the problem want us to make, we get that $ x_2=Tx_1=T^2x_0$ and by induction $ x_{21}=T^{21}x_0.$

Now, how can we compute $ T^{21}?$ We could just multiply it out. That may be worth doing as a pedagogical exercise - use a computer to help you. (I'd use a spreadsheet). Do the arithmetic approximately.

Assuming you do this approximate arithmetic, try answering these questions:

At each stage, what can you say about the sum of each column of $ T^k?$

Does it look like $ \lim_{k\to\infty}T^k$ exists?

If that limit exists, does it look like that limit might be a pretty good approximation of $ T^{21}?$

In the long run, is it even going to matter what $ x_0$ is?


Given $ n$ points arbitrarily in the plane $ P_{1},P_{2},\ldots,P_{n},$ among them no three points are collinear. Each of $ P_{i}$ ($1\le i\le n$) is colored red or blue arbitrarily. Let $ S$ be the set of triangles having $ \{P_{1},P_{2},\ldots,P_{n}\}$ as vertices, and having the following property: for any two segments $ P_{i}P_{j}$ and $ P_{u}P_{v},$ the number of triangles having $ P_{i}P_{j}$ as side and the number of triangles having $ P_{u}P_{v}$ as side are the same in $ S.$ Find the least $ n$ such that  in $ S$ there exist two triangles, the vertices of each triangle having the same color.

[quote=Stranger8][quote=hxy09]Merry Christmas!!!

We will show $ n_{min}\equal{}8$ here we go:

Suppose there are exactly $ k$ triangles containing a certain segment $ P_iP_j$ where $ K$ is independent from $ i,j$

Thus $ |S|\equal{}\frac{1}{3}k\binom{n}{2}$

Let's compute the number,call it $ x$,of triangles with vertices of two colors

Denote $ n_1,n_2$ the number of blue vertices and red vertices

For every triangle with vertices of two colors has exactly two sides whose vertices are of different colors

this yields $ x\equal{}\frac{1}{2}kn_1n_2$

$ \frac{1}{3}k\binom{n}{2}\minus{}\frac{1}{2}kn_1n_2\ge 2$ yields $ n\ge 8$

What we need now is just a counterexample for the case $ n\equal{}7$

We paint $ 1,2,3$ red,$ 4,5,6,7$ blue

and take a look at $ (456)(347)(167)(257)(236)(135)(124)$

We're done![/quote]

but you didn't show that if integer＄n＄does not satisfy the condition,then the integer which is smaller than ＄n＄ doesn't satisfy the condition,either.In fact,the case ＄n＄=6 are not so.easy to find a counterexample.[/quote]

?? how the latex isn't applied?


Let $ ABC$ be a triangle, $ D$ be the midpoint of $ BC$, $ E$ be a point on segment $ AC$ such that $ BE\equal{}2AD$ and $ F$ is the intersection point of $ AD$ with $ BE$. If $ \angle DAC\equal{}60^{\circ}$, find the measure of the angle $ FEA$.

[hide]Let $ G$ be the midpoint of $ BE$. $ DG$ is a midline of triangle $ BEC$, so $ \overline{DG} \parallel \overline{AC}$, so $ \triangle FGD \sim \triangle FEA$. Also, $ GE\equal{}\frac{1}{2}BE\equal{}AD$, which implies that $ AF\equal{}FE$. Thus, $ \angle AEF\equal{} \angle EAF \equal{} 60^\circ$.[/hide]

[hide]Let $ G$ be the point such that $ ABGC$ is a parallelogram, so $ AG \equal{} 2AD \equal{} BE$ and $ \angle AGB \equal{} 60$. Let the parallel through $ A$ to $ GC$ meet $ BG$ at $ H$. Then $ AHBE$ is a parallelogram, so $ AG \equal{} BE \equal{} AH$, so since $ \angle AGH \equal{} 60$, $ \triangle AGH$ is equilateral. Thus, $ \angle AHB \equal{} \angle AEF \equal{} 60$.[/hide]

@dgreenb801: Obviously, $ABGE$ is an isosceles trapezoid ($BG\parallel AE, AG=BE$), done.

Best regards,
sunken rock

Let$X$ be a point on the ray$AD$,such that:$XD=AD$ So$AC//PX$  $AX=BE$ So$ABEX$ is a isosceles trapezoid
So$\angle FEA=\angle FAE=\frac{\pi}{3}$

Sorry if this is any of the above posters' solutions:

Let $X$ be the midpoint of $BE$. Then, since $AD=XE$ and $XD$ is parallel to $AC$, $AEDX$ must be an isosceles trapezoid and $\triangle AEF$ is isosceles so $\angle FEA=60$.

I think the most natural solution hasn't been posted.

Let $G$ be the midpoint of $EC$. Then $DG = \frac{BE}{2} = AD$ and since $\angle DAG = \angle DAC = 60$ we have that $ADG$ is equilateral and therefore $\angle DGA = 60$. Since $FE \parallel DG$ we have $\angle FEA = \angle DGA = 60$ and we are done.


Let  be nonegative real numbers such that a>0,b>0,c>0 ,abc=8, prove that

[quote="xifan"]Let  be nonegative real numbers such that $ a > 0,b > 0,c > 0 ,abc \equal{} 8,$ prove that
\[ 1\leq\frac {1}{\sqrt {1 \plus{} a}} \plus{} \frac {1}{\sqrt {1 \plus{} b}} \plus{} \frac {1}{\sqrt {1 \plus{} c}}\leq2
\]
[/quote]
Let $ a \equal{} \frac {2x}{y},$ $ b \equal{} \frac {2y}{z}$ and $ c \equal{} \frac {2z}{x},$ where $ x,$ $ y$ and $ z$ are positive numbers.
$ LS.$ We need to prove that $ \sum_{cyc}\sqrt {\frac {x}{x \plus{} 2z}}\geq1.$
By Holder we obtain: $ \left(\sum_{cyc}\sqrt {\frac {x}{x \plus{} 2z}}\right)^2\sum_{cyc}x^2(x \plus{} 2z)\geq(x \plus{} y \plus{} z)^3.$
Id est, it remains to prove that $ (x \plus{} y \plus{} z)^3\geq\sum_{cyc}x^2(x \plus{} 2z),$ which is obvious.
For the proof of $ RS$ we can use a Contradiction method.

Hi arqady , how you use the Contradiction method ?
Thx.

if $x\geq y\geq z$ we have

$\sqrt{\frac{x}{x+2y}}+\sqrt{\frac{y}{y+2z}}+\sqrt{\frac{z}{z+2x}}>\sqrt{\frac{1}{3}}+\sqrt{\frac{1}{3}}+0>1.$

else if $x\geq z\geq y$ we have

$\sqrt{\frac{x}{x+2y}}+\sqrt{\frac{y}{y+2z}}+\sqrt{\frac{z}{z+2x}}$
$>\sqrt{\frac{x}{x+y+z}}+\sqrt{\frac{y}{x+y+z}}+\sqrt{\frac{z}{2(x+y+z)}}.$

Since

$\left(\sqrt{x}+\sqrt{y}+\sqrt{\frac{z}{2}}\right)^{2}>x+y+\frac{z}{2}+2\sqrt{\frac{xz}{2}}>x+y+z$,

we are done.


vector
geometry
parallelogram
inequalities
analytic geometry
combinatorics unsolved
combinatorics

Let $a,b,c,d$ are integers such that $(a,b)=(c,d)=1$ and $ad-bc=k>0$. Prove that there are exactly $k$ pairs $(x_{1},x_{2})$ of rational numbers with $0\leq x_{1},x_{2}<1$ for which both $ax_{1}+bx_{2},cx_{1}+dx_{2}$ are integers.

Hi, does anyone know how to do this problem? Please include motivation.  Thanks

Take the vectors $\left(\begin{array}{c}a\\ c\end{array}\right)$ and $\left(\begin{array}{c}b\\ d\end{array}\right)$.  The area of the parallelogram spanned between them is $ad-bc=k$.  So if we take the parallelogram $(0, 0), (a, c), (a+b, c+d), (b, d)$ and use Pick's theorem, we find that there are $k$ integer points $(x, y)$ in the parallelogram which are not on the edges connected to $(a+b, c+d)$.  This is true because we have $I+\frac{B}{2}-1=k$, and we're counting exactly this number of points: all interior points, exactly half the boundary points (those on the two nearer edges to $(0, 0)$) and excluding one of the mistakenly included corners.

Now every real point inside the parallelogram can be written as $x_1(a, c)+x_2(b, d)$ with $0\leq x_1, x_2\leq 1$.  Excluding the two far edges, the last inequality must be strict.  Writing the $k$ integer points we found as such, we have found $k$ pairs $(x_1, x_2)$ with the required conditions.  There can be no more, of course, because $(ax_1+bx_2, cx_1+dx_2)$ must be an integer point inside that parallelogram.

I'm not sure where the condition $(a, b)=(c, d)=1$ comes in.  If anyone has a contradiction when this condition doesn't hold, please post it.

I think it has something to do with the borders: when (a,c)=(b,d)=1, the borders have no lattice points but the vertices
EDIT: oops

No, that's true when $(a, c)=(b, d)=1$.  I thought that's what the point of the equalities was too at first, but the solution only works if the vectors are $(a, c)$ and $(b, d)$.  I'm just not sure where it could come into play.  All I can think of is that $(a, b)=(c, d)=1$ means that there's some linear combination of the vectors with a unit coordinate, but I'm not sure why that'd be important.  I even worked it out with $a=b=3, c=1, d=2$ and found $ad-bc=3$ pairs just like I should: $(0, 0), \left(\frac{1}{3},\frac{1}{3}\right), \left(\frac{2}{3}, \frac{2}{3}\right)$.  I guess it's there to make some other method of solution easier.


inequalities
trigonometry
geometry
circumcircle
geometric inequality
geometry solved

Let $ ABC $ be a triangle . $ M , N , P $ respectively lie on the segments $ BC ,CA, AB $ . Prove that :
  $ \frac{NP^2}{bc.sin^2A} + \frac{MP^2}{ac.sin^2B} + \frac{NM^2}{ab.sin^2C} \geq 1 $

I rewrite the problem with different notations, since I will later use the letter P for a different point:

[color=blue][b]Problem.[/b] Let ABC be a triangle, and let X, Y, Z be three points on the lines BC, CA, AB, respectively. Prove the inequality

$\frac{YZ^{2}}{bc\sin^{2}A}+\frac{ZX^{2}}{ca\sin^{2}B}+\frac{XY^{2}}{ab\sin^{2}C}\geq 1$.[/color]

[i]Solution.[/i] The following proof is written for the case of triangle ABC acute-angled and the points X, Y, Z lying inside the segments BC, CA, AB, but the other cases are considered analogously. (The inequality signs need not be reversed!)

Let the circumcircles of triangles AYZ and BZX meet at a point P (apart from Z). Then, the quadrilaterals AYPZ and BZPX are cyclic, so that $\measuredangle AYP=180^{\circ}-\measuredangle AZP$ and $\measuredangle BZP=180^{\circ}-\measuredangle BXP$. In other words, < AYP = < BZP and < BZP = < CXP. Hence, < CXP = < AYP; equivalently, $\measuredangle CXP=180^{\circ}-\measuredangle CYP$. Hence, the quadrilateral CXPY is cyclic, so that the point P must lie on the circumcircle of triangle CXY.

So thus we have obtained that the point P lies on the circumcircles of triangles AYZ, BZX and CXY and that < AYP = < BZP = < CXP. Denote < AYP = < BZP = < CXP = t.

Since the point P lies on the circumcircle of triangle AYZ, we have < AZY = < APY. Also, clearly, < YAZ = A. On the other hand, by the sine law in triangle AYZ, we find $\frac{YZ}{\sin\measuredangle YAZ}=\frac{AY}{\sin\measuredangle AZY}$. Hence, $\frac{YZ}{\sin A}=\frac{AY}{\sin\measuredangle APY}$. On the other hand, by the sine law in triangle APY, we have $\frac{AY}{\sin\measuredangle APY}=\frac{AP}{\sin\measuredangle AYP}$. Hence, $\frac{YZ}{\sin A}=\frac{AP}{\sin\measuredangle AYP}=\frac{AP}{\sin t}$. Hence, $\left(\frac{YZ}{\sin A}\right)^{2}=\left(\frac{AP}{\sin t}\right)^{2}=\frac{AP^{2}}{\sin^{2}t}$. Since the number $\sin^{2}t$ is nonnegative and $\leq 1$, this yields $\left(\frac{YZ}{\sin A}\right)^{2}\geq AP^{2}$, so that $\frac{YZ^{2}}{bc\sin^{2}A}=\frac{1}{bc}\cdot\left(\frac{YZ}{\sin A}\right)^{2}\geq\frac{1}{bc}\cdot AP^{2}=\frac{a\cdot AP^{2}}{abc}$. Similarly, $\frac{ZX^{2}}{ca\sin^{2}B}\geq\frac{b\cdot BP^{2}}{abc}$ and $\frac{XY^{2}}{ab\sin^{2}C}\geq\frac{c\cdot CP^{2}}{abc}$.

But by the "fairly general geometric inequality" from http://www.mathlinks.ro/Forum/viewtopic.php?t=15558 , applied to x = a, y = b and z = c, we have

$\left(a+b+c\right)\left(a\cdot AP^{2}+b\cdot BP^{2}+c\cdot CP^{2}\right)\geq bca^{2}+cab^{2}+abc^{2}$,

or, equivalently, $\left(a+b+c\right)\left(a\cdot AP^{2}+b\cdot BP^{2}+c\cdot CP^{2}\right)\geq\left(a+b+c\right)abc$, so that $a\cdot AP^{2}+b\cdot BP^{2}+c\cdot CP^{2}\geq abc$, and thus

$\frac{YZ^{2}}{bc\sin^{2}A}+\frac{ZX^{2}}{ca\sin^{2}B}+\frac{XY^{2}}{ab\sin^{2}C}\geq \frac{a\cdot AP^{2}}{abc}+\frac{b\cdot BP^{2}}{abc}+\frac{c\cdot CP^{2}}{abc}$
$=\frac{a\cdot AP^{2}+b\cdot BP^{2}+c\cdot CP^{2}}{abc}\geq\frac{abc}{abc}=1$,

qed.

  Darij


I don't know if this topic is in its proper category, but I have no clue how to prove this:

$\sum_{x=1}^{\infty}{\displaystyle \frac{1}{x^2}}=\displaystyle \frac{{\pi}^2}{6}$

Looks like calc to me.  Or some incredibly clever way to relate this with circles.

Here is a sight which gives 14 proofs, blahblahblah gave me the url when I asked the same question:
http://www.maths.ex.ac.uk/~rjc/etc/zeta2.pdf

But these do require calculus.

The simplest proof in my opinion is to take a fourier series of $f(x)=x^2$ on the interval $[-\pi,\pi]$, and then plug in the value $x=\pi$ and solve for the sum.

hehe. this a very famous series. wanna know how famous it was, john bernoulli once challeged the world to find the sum of $\sum \frac{1}{x^2}$ and Euler (my favorite mathematician proved it)
here is the proof:
let $P(x)=1-\frac{x^2}{3!}+\frac{x^4}{5!}-\frac{x^6}{7!}.....$
clearly $P(0)=1$. to find the roots of $P(x)$, note that for $x\not=0$:
${{P(x)=x[1-\frac{x^2}{3!}+\frac{x^4}{5!}-\frac{x^6}{7!}.....}{x}=x-\frac{x^3}{3!}+\frac{x^5}{5!}-\frac{x^7}{7!}.....}=\frac{\sin{x}}{x}$
so $P(x)=0 \rightarrow \sin{x}=0 \rightarrow x= (+-)k\pi$ for $k=1,2,3,...$ note that $x=0$ is not a solution. because $P(0)=1$
now if you factor $p(x)$ you get:
$P(x)= (1-\frac{x}{\pi})(1-\frac{x}{-\pi})(1-\frac{x}{2\pi})(1-\frac{x}{-2\pi})= [1-\frac{x^2}{\pi^2}][1-\frac{x^2}{4\pi^2}][1-\frac{x^2}{9\pi^2}]+....$
now look what happens when you expand the above equation:
you get
$1-[ (\frac{1}{\pi^2})+(\frac{1}{4\pi^2})+(\frac{1}{9\pi^2})+....]x^2+....$now set this equal to the original function for $P(x)$ you  get
$P(x)=1-\frac{x^2}{3!}+\frac{x^4}{5!}-\frac{x^6}{7!}.....= 1-[ (\frac{1}{\pi^2})+(\frac{1}{4\pi^2})+(\frac{1}{9\pi^2})+....]x^2+....$ now take a look at coefficient for the $x^2$ then set them equal to each other, you get:
$\frac{-1}{3!}=-(\frac{1}{\pi^2}+\frac{1}{4\pi^2}+\frac{1}{9\pi^2}+....)=\frac{-1}{\pi^2}(1+\frac{1}{4}+\frac{1}{9}+\frac{1}{16}+....) $
therefore:
$1+\frac{1}{4}+\frac{1}{9}+\frac{1}{16}+...=\frac{\pi^2}{6}$
so we are done :D

With this problem, I prefer methods that generalize to the sums of reciprocals of fourth powers, etc (and the above method does indeed generalize!)

I have a favorite method (which isn't on Robin Chapman's page) but it involves Laurent series, so it's not really appropriate to post.


What do you have against even numbers? How odd to favor only odd numbers...even the even will work?NO? :)

Yes, Gyan has a point there :)

\begin{eqnarray*}(k-3)(k-1)(k+1)(k+3)+16=(k^2-9)(k^2-1)+16=k^4-10k^2+25=(k^2-5)^2\end{eqnarray*} for any $k$.

Hence the question might be: Prove that $\frac{(n+6)!!}{(n-2)!!}+16$ is always a perfect square for natural $n$ :) (where $(-1)!!$ is defined as $1$)

Are german national olympiads this easy?

[quote="orl"]Prove that the sum of the product of 4 consecutive odd integers and the number 16 yields a square.[/quote]
Four consecutive odd/even numbers can be denoted $a, a+2, a+4, a+6$. We cleverly group the terms and use the $(x-y)(x+y)=x^2-y^2$ expansion to obtain \begin{align*}a(a+2)(a+4)(a+6)+16 & =(a^2+6a)(a^2+6a+8)+16\\ &=((a^2+6a+4)-4)((a^2+6a+4)+4)+16\\ &=(a^2+6a+4)^2-4^2+16\\ &=\boxed{(a^2+6a+4)^2}.\end{align*}

Similar question asked in Moscow Maths Olympiad 1941: Prove that 1 plus the product of 4 consecutive integers is the square of an integer.

[quote=judgefan99][quote=RedFireTruck][quote=judgefan99]It's a really slick question.[/quote]

is slick good or bad?

what does slick mean?[/quote]

it means good[/quote]

ok


In a particular sequence, each term after the first two terms is
the sum of the two preceding terms. If the first term is 20 and
the sixth term is 220, what is the value of the seventh term?

I have read the solution many times, but it kind of confuses me when I think of it in my head.[hide="Their Solution"]
In a particular sequence, each term after the
first two terms is the sum of the two
preceding terms. The first term is 20 and the
sixth term is 220. Let x2 = the second term,
x3 = the third term, etc.
x3 = 20 + x2
x4 = x3 + x2 = 20 + x2 + x2 = 20 +2x2
x5 = x4 + x3 = 20 +2x2 + 20 + x2 =40 + 3x2
x6 = 220 = x5 + x4 = 40 + 3x2 + 20 + 2x2
220 = 60 + 5x2
5x2 = 220 - 60 = 160
x2 = 32
x5 = 40 + 3x2 = 40 + 3 ´ 32 = 40 + 96
x5 = 136
x7 = x6 + x5 = 220 + 136 = 356 Ans.[/hide]

I kind of get it, but it makes me go crazy when I follow it :P !

I have attached the solutions manual so that you can see it in a better format (this is #8 on target)

Thank You,
-Jorian Hoover

Okay, let's say the second term is x. Then the 3rd term would be 20 + x. Then the 4th would be (20 + x) + x, or 20 + 2x. The 5th term would be (20 + 2x) + (20 + x), or 40 + 3x. The 6th term would be (40 + 3x) + (20 + 2x), or 60 + 5x. You know this is equal to 220, so x is 32. To get the 7th term you add up the 6th term, which is 220, and the 5th term. The 5th term is 40 + 3x, and when you plug in x you get 136. Now add up 220 and 136 to get 356 as the answer.

[quote="jhredsox"]ok, thank you.

there is no real easy way to give the solution due to the amount of x's, but ubemaya's made a lot more sense than the mathcounts one :)

-jorian[/quote]
What are you talking about, ubemaya's way takes just one minute tops!!! Besides, continue the pattern for a few more terms to find an interesting pattern, so you could do it even if it wanted 100 terms.
[hide="the interesting pattern for those too lazy to find it on their own"] Fibonacci[/hide]

ya, i know its fibonacci :P , my head just was going crazy when i saw so many variables in the mathcounts solution :D

-jorian


probability
expected value
binomial coefficients

A group of n married couples arrive at a dinner party and is seated around a circular table. The distance between a husband and wife is defined to be equal to the number of people sitting between them measured either clockwise or counter-clockwise, whichever gives the smaller result. Consider all possible arrangements of the 2n people.
what is the average number of couples, per arrangement, where both members are sitting side by side?

um...why did you even bother defining 'distance'?

anyway, pretty clearly, if n=1, we will have on average 1 married couple sitting together. now, let a_n be the number (on average) of married couples sitting together if we have n married couples. We investigate the relationship between a_(n+1) and a_n. Ok, not being discrimatory against gays or anything, let's assume the (n+1)th couple is a man and a woman, just to tell them apart. Okay. Let's place the woman first. She has, right now, 2n possible places to sit. The probability she breaks up a couple is a_n/2n. Ok. Just keep this in mind. Now we place the man. He has (2n+1) places to sit right now. The probability he sits next to his wife is 2/(2n+1). The probability he breaks up a couple if she has already broken up one is (a_n-1)/(2n+1). The probability he breaks up a couple is she has not broken up a couple is (a_n)/(2n+1). So now we look at the average change from a_(n+1) from a_n. Two couples will be broken up with probability (a_n-1)(a_n)/(2n+1)(2n). One couple will be broken up with probability [(a_n)/2n]*[(2n-a_n)/(2n+1)]+[(2n-a_n)/2n]*[(a_n-1)/(2n+1)]. No couples on average will be broken up with probability [a_n/2n]*[2/(2n+1)]+[(2n-a_n)/2n]*[(2n-a_n+1)/(2n+1)]. And one couple will be gained on average with probability [(2n-a_n)/2n]*[2/(2n+1)]. So we take the weighted averages of those and add it to a_n to get a recursive formula for a_(n+1) in terms of a_n, which we can then solve to get a closed form. But that would take an awful lot of multiplying and stuff. Probably a better way.

yeah there is a part (a) which i conviently left out which uses the distance.  Ravi is right, his answer matches with my computer simulation at least...

Ravi B wrote:I think a better way would be to [hide]figure out the probability that a particular husband and wife are sitting next to each other.  Then multiply by n.[/hide]

ok, the conventional way for expected value is E=Sum (x=1..n) f(x)*P(x)

ie the sum of probabilities of x couples sitting together times by x.   i do not understand why Ravi's approach works

[quote="bugzpodder"]

ok, the conventional way for expected value is E=Sum (x=1..n) f(x)*P(x)

ie the sum of probabilities of x couples sitting together times by x.   i do not understand why Ravi's approach works[/quote]

Number the couples 1 through n.
Look at SumA P(A)|A|  where A ranges over all subsets of {1, 2, ..., n} and P(A) is the probability that only the couples in A are sitting next to each other.
If you collect all the A's of the same size, you get the conventional formula:
Sum (x=1..n) f(x)*P(x).
However, if you split P(A)|A| into |A| copies of P(A), you can collect all the A's that include a given couple (say couple number 1), then you get Ravi's way.  This uses the fact that
SumA containing a P(A) = P(a).
Here P(a) is the probability that couple "a" is sitting together.  It also uses the fact that any couple is equally likely to sit together when the average is taken over all possible arrangements.

--Dan

Bugzpodder, my approach works because expected value is linear.  In particular, if X and Y are random variables, then E(X + Y) = E(X) + E(Y).  Note that this formula works whether or not X and Y are independent; that's why it is so valuable.

Let's apply this formula to your problem.  Let Xi be 1 if the ith couple is seated together.  Your problem is to compute E(sum of Xi).  By linearity, that expression is the same as the sum of E(Xi).  But E(Xi) is just the probability that the ith couple is seated together.

Now do you see why the approach works?  If so, you now have a wonderful tool for cracking problems about expected value.  For example, here is a classic problem.  Let's say that n people give their coats to a coat-check person.  At the end of the evening, the (drunk) coat-check person gives each of them a coat, but in a random way.  What is the average number of people who received the correct coat?  When I was a kid, I solved this problem in an long and ugly way, with binomial coefficients galore and induction.  It was years later before I learned the two-line proof that let's you solve the problem in about 10 seconds.  Do you see it?

i assume its probability of one times n again?  so (1/n)*n=1?

Yes!  I guess you solved it in one line, not two!


inequalities function calculus derivative

Let $f(x)=\sqrt{x^2+x+1}-\sqrt{x^2-x+1}$, show that $-1<f(x)<1$ for every $x \in\mathbb{R}$.

[quote="maokid7"]take the limit to $\infty$ and $-\infty$
to make the limit easy to find just multiply by 1 $\left(\frac{\sqrt{x^2+x+1}+\sqrt{x^2-x+1}}{\sqrt{x^2+x+1}+\sqrt{x^2-x+1}}\right)$

u will find that the limits are 1 and -1.
then to prove that the function has no larger values take the derivative and find all critical points and plug them back into $f(x)$ (you should find that the  derivative never equals 0)[/quote]

Truely it can be proved by saying that f(x) is nondecreasing and bounded from above by 1, and with  the fact that f(x) is odd, thus we have -1<f(x)<1.

But I was wondering how to give an elementary proof without calculus since I found it in a problem solving book for  high school students.

[quote="scorpius119"][hide]
Since $f(-x)=-f(x)$ and $f(0)=0$, the function needs to be considered only for positive $x$. Using conjugates, $f(x)=\frac{2x}{\sqrt{x^2+x+1}+\sqrt{x^2-x+1}}$.

When $x$ is positive, then $x=|x|=\sqrt{x^2}\Rightarrow f(x)=\frac{2}{\sqrt{1+\frac 1x +\frac{1}{x^2}}+\sqrt{1-\frac 1x +\frac{1}{x^2}}}$. Clearly this is positive.

This can be shown to be less than 1 because it is the reciprocal of an arithmetic mean. By AM-GM and taking reciprocals, $\frac{2}{\sqrt{1+\frac 1x +\frac{1}{x^2}}+\sqrt{1-\frac 1x +\frac{1}{x^2}}}\leq \frac{1}{\sqrt[4]{\left( 1+\frac 1x +\frac{1}{x^2}\right) \left( 1-\frac 1x +\frac{1}{x^2} \right)}}$

$=\frac{1}{\sqrt[4]{1+\frac{1}{x^2}+\frac{1}{x^4}}}<1$.

So $0<f(x)<1$ for positive $x$, $f(0)=0$, and $-1<f(x)<0$ for negative $x$. Therefore $-1<f(x)<1$ for all $x$.
[/hide][/quote]

Nice shot! :)

[quote="probability1.01"][hide="simony"]Do this geometrically. Let $A, B, C, D$ be points for which $\angle ABC = 120, \angle ABD = 60$, and $|AB| = x, |BC| = |BD| = 1$. Then $f(x) = |AD| - |AC| < |CD| = 1$.[/hide][/quote]

Marvelous! :coolspeak:


Hello all:

Question: Find the number of permutations of n in which i is not immediately followed by i+1.

Ex:  For n=4, 1324 would be good.  4231 would not.

This problem was asked in my combinatorics book, but only for n=6.  I was trying to set up a recurrence to generalize it for any n, but I'm getting stuck.

There might be a way to generalize it without recurrences, but it seemed like the most logical way to go.

Also, here is some extra info that I discovered that might help:

f(2)=1
f(3)=3
f(4)=11
f(5)=53
f(6)=310

Any ideas/hints/solutions/theorems would be great.  I got these numbers by enumerations (yea, it sucked).  As far as the recurrence, I got the following:

f(n)= (n-1)(f(n-1))+f(n-2)+....

Take the previous f(n-1) good ones.  Each have n-1 spots to insert the next number (n) into.
Now go back 2 steps and take the ones that were good in f(n-2) then made bad by inserting an (n-1) into a bad spot.  Now (n) can separate those two numbers making the permutation good again.

I'm having trouble with the rest.

If you break up each of the numbers with the above, you get:

f(2)=1
f(3)=3
f(4)=3*3+1+1 = 11
f(5)=4*11+3+6 = 53
f(6)=5*53+11+34 = 310

The trailing 1, 6, and 34 from f(4), f(5), f(6) I'm having trouble justifying.  Thanks!

http://www.artofproblemsolving.com/Forum/viewtopic.php?search_id=900102930&t=165833

When you have numerical data of this sort, a good place to look is always the [url=http://www.research.att.com/~njas/sequences/Seis.html]OEIS[/url] -- I found the thread I linked to above by searching for the sequence number ([url=http://www.research.att.com/~njas/sequences/A000255]A000255[/url]).  (You were close, but you made a computational error in generating 310 (should have been 309) -- if you'd had the correct value, you might have seen the pattern.)

Bah!  I was so close, and I had initially thought of something close to that, but the 310 threw me off completely.  Thank you so much for your help.

I was wondering if you had a better combinatorial proof/explanation.  I'm having trouble understanding why there are n-1*(an-1) choices if n+1 splits up 2 consecutive integers.

From any permutation of $ n \minus{} 1$ with no two consecutive letters, I can generate a permutation of $ n \plus{} 1$ with no two consecutive letters by choosing $ i$, replacing $ i \plus{} 1, i \plus{} 2, \ldots, n \minus{} 1$ with $ i \plus{} 2, i \plus{} 3, \ldots, n$ and inserting $ n \plus{} 1$ and $ i \plus{} 1$ immediately following $ i$.  For example, starting with 136245 I get the following 6 permutations, with italics for the inserted letters and bold for the shifted letters:
$ i \equal{} 1$ gives: 1[i]82[/i][b]47356[/b]
$ i \equal{} 2$ gives: 1[b]47[/b]2[i]83[/i][b]56[/b]
$ i \equal{} 3$ gives: 13[i]84[/i][b]7[/b]2[b]56[/b]
$ i \equal{} 4$ gives: 13[b]7[/b]24[i]85[/i][b]6[/b]
$ i \equal{} 5$ gives: 13[b]7[/b]245[i]86[/i]
$ i \equal{} 6$ gives: 136[i]87[/i]245
The inverse of this operation is what I described in the post I linked to.


Let $ABC$ be an equilateral triangle inscribed in circle $(O)$.Let $M$ be a point that moves on the minor arc of $(O)$.Let $CM$ intersects $AB$ at $E$,$AM$ meet $BC$ at $F$.Prove that $EF$ has a fixed point.

then you shouldnt post it in this forum
this forum is for:[b]An open question is a question that has no known solution up to this moment, and it is not known wheter the problem has one or not.[/b]
you should post it in [url]http://mathlinks.ro/Forum/index.php?f=46[/url] if its a [b]Problem you couldn't solve and to which you know that there is a solution (i.e. a problem from a contest, etc.) but you don't know it.[/b] or you should post it in [url]http://mathlinks.ro/Forum/index.php?f=47[/url] if its a [b]Problem that you have already solved and you are interested in second opinions or solutions.[/b]...


search
function
calculus
integration
number theory unsolved
number theory

What's the proof of [url=http://mathworld.wolfram.com/SchinzelsTheorem.html]Schinzel's Theorem[/url]
(I can't find any using search function)

But, in the link that you posted, there is the solution to your problem.  :)
You 've better read it more carefully. Moreover, this topic should be moved to the formulas and theorems forum.

Well, it tells something, but I still don't understand things like how $4(d_1-d_3)$ comes

Let me do the case when n=2k, and you'll try the other one.
Consider the circle C: $x^2+y^2=5^{k-1}$, then it has $4(d_1-d_3)$ solution in integers.
But since $5$ equals $1(mod 4)$, we conclude that $d_3 = 0$.
Moreover the number $5^{k-1}$ has $k$ divisors. So $d_1=k$. Finally  C has $4k$ solutions in integers.
Now, notice that if $(x,y)$ is an interger solution then also $(y,x)$ is a solution.
But since one of these numbers is even and the other odd, (why?)
we conclude that the number of integer solution of the equation $(2x-1)^2 +(2y)^2=5^{k-1}$ is $2k$ or $n$.
So we are done. I tried to write it very clearly, i hope you don't have any problem in understanding it.

Oh, thank you very much.
But actually what I don't understand is why the number of integral solutions $(x,y)$ to $x^2+y^2=n$ is equal to $4(d_1-d_3)$. How this comes? Is it well-known?

Yes, it is. This is not part of the proof you asked for.
But you will find an answer to http://mathworld.wolfram.com/SumofSquaresFunction.html .

I see.
Actually I'm too lazy to read the proof now. I'll just remember it  :)


symmetry
induction
number theory unsolved
number theory

Let $ n$ and $ k$ be positive integers. Prove that:
$ \displaystyle n| \sum_{d|n}\varphi \left(\frac nd\right) k^d$

Note: $ \varphi (n)$ is Euler's toitient function.

Let $ f(n,k)=\sum_{d|n}\phi (\frac nd )k^d$.
It is easy to chek, that $ n|f(n,k)$ for $ n=p^m$.
If $ n=n_1n_2, (n_1,n_2)=1$, then $ f(n_1n_2,k)=\sum_{d|n_1)\phi(\frac{n_1}{d} f(n_2,k^d)}$.
Therefore $ n_2|f(n_1n_2,k)$ and by symmetry $ n_1|f(n_1n_2,k)$. It give (by induction), that $ n|f(n,k) \ \forall n,k\in N$.

Hi... it's nice to see a non counting solution Rust.. i found this result while solving the problem of the necklaces  problem used bt Zetax in the link... i found the formula using the mobius inversion formula.. does anybody now an elementary solution to the problem of the necklaces?


Your hover board gets 120 $ km$ per $ cm^3$ of fuel. Hover board fuel costs $ \$8$ per $ cm^3$. How many dollars will it cost you to travel 2250 $ km$ on your hover board?

First, we must find how many $ cm^3$ of fuel we need.  To find that, we do $ \frac{2250}{120}\equal{}\frac{75}{4}$.  Knowing that it costs $ \$8$ per $ cm^3$ of fuel, we just multiply $ \frac{75}{4}$ by $ 8$.  This gives us our answer, $ \boxed {150}$


induction
search
calculus
integration
pigeonhole principle

What exactly is mathmatical induction? I seen this term so many times that my head is spinning, and I don't know what it means?

Maybe you guys are thinking I'm mentally challenged  :blush:

Using math to solve a problem pretty much.

Erm, iverson, mathematical induction is a tool used to solve math problems. I don't know how to use it efficiently, but here Silverfalcon quickly explains what it is and uses it in an example. You can probably find other sources by using the search feature of the forum or googling.

Check out the first problem he does and the proof.

[url=http://artofproblemsolving.com/Forum/viewtopic.php?highlight=mathematical+induction&t=28069]artofproblemsolving.com/Forum/viewtopic.php?highlight=mathematical+induction&t=28069[/url]

It is??? Everytime it's used, I thought it was just when someone uses math to solve a problem that's seemingly outside of Mathematics....boy was I wrong  :o

Yeah, Silverfalcon explains it very well.  It's one of three special proof techniques (that I know of, at least), namely induction, the pigeonhole principle, and proof by contradiction.

Induction is different from other proofs because it uses INDUCTIVE reasoning--you show it works for 1, and then you show that if it works for k, then it works for k+1.  So if it works for 1, it works for 2, so it works for 3, and 4, and 5, etc.  DEDUCTIVE reasoning is just when you try to show it works for all n directly.

[quote="dakyru"]4. [i]Mathematics.[/i] A two-part method of proving a theorem involving an integral parameter. First the theorem is verified for the smallest admissible value of the integer. Then it is proven that if the theorem is true for any value of the integer, it is true for the next greater value. The final proof contains the two parts.

Courtesy of dictionary.com   :)[/quote]

thanks dakyru ;)  :juggle:  :dry:

So, just to test induction, prove the following.

$1 + 2 + \ldots + n = \frac{n(n+1)}{2}$

Another:

$1^2 + 2^2 + \ldots + n^2 = \frac{n(2n+1)(n+1)}{6}$

Don't let bigger expressions fool you. The second is solved the same way.

1.
Statements proven by math induction all depend on an integer, say, n. It's convenient to talk about a statement P(n). For (1), P(1) says that $\frac{1(1+1)}{2}$  which is incidently true. Assume you want to prove that for some statement P, P(n) is true for all n starting with n = 1. The Principle (or Axiom) of Math Induction states that, to this end, one should accomplish just two steps:

   1. Prove that P(1) is true.
   2. Assume that P(k) is true for some k. Derive from here that P(k+1) is also true.

The idea of MI is that a finite number of steps may be needed to prove an infinite number of statements P(1), P(2), P(3), ....
We already saw that P(1) is true. Assume that, for an arbitrary k, P(k) is also true, i.e. 1 + 2 + ... + k = k(k+1)/2. Let's derive P(k+1) from this assumption. We have
$1+2+3+. . . . .+k+(k+1)$
$=(1+2+3+. . . . . +k)+(k+1)$
$=\frac{k(k+1)}{2}+\frac{2(k+1)}{2}$
$=\frac{k(k+1)+2(k+1)}{2}$
$=\frac{(k+1)(k+2)}{2}$
Which exactly means that P(k+1) holds. Therefore, P(n) is true for all n starting with 1.

2. The above example has illustrated the principles of mathematical induction. So this one would not be as detailed.
 For n=1, $1^2=\frac{1(2+1)(2)}{6}$ is true.
Assume P(n) is true. Derive P(n+1) from this assumption:
$1^2+2^2+3^2+. . . . . . .+n^2+(n+1)^2$
$= \frac{n(2n+1)(n+1)}{6}+(n+1)(n+1)$
$=\frac{(2n^2+n)(n+1)}{6}+\frac{6(n+1)(n+1)}{6}$
$=\frac{(2n^2+n+6n+6)(n+1)}{6}$
$=\frac{(2n^2+7n+6)(n+1)}{6}$
$=\frac{(2n+3)(n+2)(n+1)}{6}$
$=\frac{(n+1)[2(n+1)+1][(n+1)+1]}{6}$
This completes our induction step and the prove is thus completed.

Oh I believe I learned something like that (except much easier, I was still in fourth grade then). i guess I for got the term (slightly unfamiliar). :blush:

The idea is simple. First, we prove for most obvious case in which $p = 1$. (Let's say $p$ is the variable we used in problem). Then we assume that $p=k$ makes the statement true where $k$ is an arbitary number (arbitary in this case means random). From our assumption, we prove that $p=k+1$ work as well. QED

Now, how does that work?

First, we proved that it work for most basic case. Second, our use of assumption of $p=k$ and proving $p=k+1$ actually prove for all the numbers other than 1 since we can set $k$ to be any number we want. Note that I called the $k$ to be arbitary number.

I hope all my statements sound right. It's been since I used induction so.  :roll:


calculate $a$ and $b$ so as
$ \lim_{x \to 1}\left (\frac{a}{1-x^{m}}-\frac{b}{1-x^{n}}\right) = \frac{m-n}{2}$ , $m \neq n$ and $m,n \in \mathbb{N^{*}}$

[quote="pureblack2003"]calculate $a$ and $b$ so as
$\lim_{x \to 1}\left (\frac{a}{1-x^{m}}-\frac{b}{1-x^{n}}\right) = \frac{m-n}{2}$ , $m \neq n$ and $m,n \in \mathbb{N^{*}}$[/quote]
If I have not mistake You must solve this equation only:
$an=bm$
and
$m(m-1)b-n(n-1)a=(m-n)mn$


vector
function
topology
advanced fields
advanced fields unsolved

Prove that a compact metric space maps isometrically into a Banach space.

Consider the canonical embedding $ X \rightarrow X^{**}$. The map is linear and continuous, and if our metric space is compact, the image is also compact, thus closed, thus complete, thus Banach.

Why is the map linear? $ X$ is a compact metric space, not a vector space.

One might use $ X \to C^1(X,\mathbb{R})^*$?

C^1 is not defined for metric spaces...

There is an isometrical embedding $ M\to C_b(M)$ (Space of bounded, realvalued functions with the supremum norm) for all metric spaces M: Let $ f_x$ be the map $ y\mapsto d(x,y)$. This might not be bounded, but for a fixed $ x_0\in M$ the maps $ g_x: \equal{}f_x\minus{}f_{x_0}$ are. $ x\mapsto g_x$ is the desired embedding.


Well, if you are allowed to use a calculator, then I would guess and check to find the answer to be 36481.

isn't this a 92-93 nats target problem?
anyway...
[hide]
you realize that the square root of the number must be a 3 digit number that starts with a 1 or 3, 2 does not work because it won't be prime. and 4 is too big.
with a calc, numbers starting with 3 can be ruled out
then you can easily find the answer by guess and check[/hide]

[quote="davidli"]Find a five digit number for which all the following are true:
a. The number's square root is a prime palindrome
b. The number's first two digits express a perfect square.
c. The number's middle digit is a perfect square.
d. The number's last two digits express a perfect square.[/quote]
[hide]
use a calculator to square prime palindromes between 100 and 316
list of palindromes:
101
111
121
131
141
151
161
171
181
191
(200-299 palindromes are all even)
303
313
eliminate the ones that aren't obviously prime
left with:
101
131
151
181
191
313
square them all to find:
10201, 17161, 22801, 32761, 36481, 97969
$36481$ is the only one that fills the other requirements. (only 97969 and 36481 have a 1-digit square in middle, and only 36481 has squares around the square)
[/hide]


calculus
derivative
logarithms
calculus computations

f(x) = 8^(sin^2(3x))

I need help finding the derivatives of this function.  I tried using the rule

$f(x) = a^{x}$
$f'(x) = a^{x}(\ln a)$

Which would give me

f'(x) = 8^(sin^2(3x))(ln(8))

But this is not on the answers to chose from.  Any help with would be greatly appreciated.

You're forgetting the chain rule; our exponent isn't just $x$.


[quote="GameBot"]A 4'' by 6'' picture is enlarged to an 8'' by 10'' size. To the nearest whole percent, what percent increase in area does the enlargement represent?[/quote]

The 4" by 6" picture has an area of 24, while the 8" by 10" picture has an area of 80. Thus the percent increase in area is $ \frac{80 \minus{} 24}{24} \approx 233\%$.


[quote="joml88"]An inequality I can solve  :D I hope I'm right.

[hide="Solution"]
First, we use some results of AM GM:

\[\begin{eqnarray}
a^2b+b^2c+c^2a &\geq& 3abc\\
2(ab^2+bc^2+ca^2) &\geq& 6abc
\end{eqnarray}.\]

We subtract $(1)$ from $(2)$ and get

\[2(ab^2+bc^2+ca^2)\geq a^2b+b^2c+c^2a+3abc.\]

But the problem states that these are equal, so this means that

\[a^2b=b^2c=c^2a \ \ \text{and} \ \ ab^2=bc^2=ca^2.\]

Thus $a^2=bc, \ b^2=ac, \ \text{and} \ c^2=ab\Rightarrow b^3=c^3\Rightarrow b=c.$  And we can similarily show that $a=b$ (or $a=c$) and thus $a=b=c$ and the triangle is equilateral.[/hide][/quote]
can someone check when he subtract $(1)$ from $(2)$ because when you subtract, $(1)$ turns negative values and inequality reverses. it works if it is an equality but inequality...  :?
edit: i divided both sides of inequality by $abc$ and got
\[2\left(\frac{b}{c}+\frac{c}{a}+\frac{a}{b}\right)=\frac{a}{c}+\frac{b}{a}+\frac{c}{b}+3\]

Shoot...you're right.  My method is flawed. :mad:

[quote="DPopov"]Prove that if $a, b, c$ are the sides of a triangle and
\[2(ab^2+bc^2+ca^2)=a^2b+b^2c+c^2a+3abc\]
then the triangle is equilateral.[/quote]

Write
\[\sum_{cyc} ab^2-\sum_{cyc}a^2b=(a-b)(b-c)(c-a)\]
and
\[\sum_{cyc} ab^2-3abc=\sum_{cyc} ab(b-c)\]

We need only handle $a\geq b\geq c$ (otherwise it is trivial from the above)

If $a\geq b\geq c$, we will show that
\[(a-b)(b-c)(c-a)+ab(b-c)+bc(c-a)+ca(a-b)\geq 0\]

which is equivalent to showing

\[((a-b)(b-c)+bc)(c-a)+ab(b-c)+ca(a-b)\geq 0\]

Let $a=c+x+y$, $b=c+x$, so we need to show
\[-(yx+bc)(x+y)+aby+cax\geq 0\]

Expand to get $cx^2+x^3+cy^2+cyx-y^2x$.  By the triangle inequality, $y<c$, hence $cyx>y^2x$ and the inequality is proven.  Equality holds iff $x=y=0$, which means we have equality iff $a=b=c$

Since the case $a\geq c\geq b$ also gives equality iff $a=b=c$, we are done.

[quote="DPopov"]I divided by $abc$ as well and then added $2 \left(\frac{a}{c}+\frac{b}{a}+\frac{c}{b} \right)$ to both sides from which I obtained $\frac{a}{c}+\frac{b}{a}+\frac{c}{b} \geq 3$. But I don't really know where to go from there because that only gets you a lower bound.[/quote]
lower bound?  :huh:  where did you see the inequality sign in the first post anyway? :P

it should be $\frac{a}{c}+\frac{b}{a}+\frac{c}{b}=3$ which is clearly only true when $a=b=c$ QED

How did you get equality when $\frac{x}{y}+\frac{y}{x} \geq 2$ and since you have 3 pairs in the form of $\frac{m}{n}+\frac{n}{m}$ multiplied by 2 you end up with a 12 on the LHS which when you subtract 3 and divide by 3 from the RHS you end up with $\frac{a}{c}+\frac{b}{a}+\frac{c}{b} \geq 3$. Is there something wrong with my reasoning?

[quote="DPopov"]How did you get equality when $\frac{x}{y}+\frac{y}{x} \geq 2$?[/quote]
x=y.

Equality holds iff $x=y$ but this doesn't tell us anything at least I don't think because if $a>b>c$ the inequality may still hold.

where did you get the INequality sign in the first place? :P

How did you get EQUALITY.....it has to be an inequality because like I stated above $\frac{x}{y} +\frac{y}{x} \geq 2$ and not $\frac{x}{y}+\frac{y}{x}=2$ Maybe I am missing something?

[quote="DPopov"]Prove that if $a, b, c$ are the sides of a triangle and
\[2(ab^2+bc^2+ca^2)=a^2b+b^2c+c^2a+3abc\]
then the triangle is equilateral.[/quote]

here is where i get the equality sign :P

Ok....but where do you get the =3....because i used an inequality and here it is

\[2\left(\frac{b}{c}+\frac{c}{a}+\frac{a}{b}\right)=\frac{a}{c}+\frac{b}{a}+\frac{c}{b}+3\]
\[\Leftrightarrow 2\left(\frac{b}{c}+\frac{c}{a}+\frac{a}{b}\right)+2 \left(\frac{a}{c}+\frac{b}{a}+\frac{c}{b} \right)=\frac{a}{c}+\frac{b}{a}+\frac{c}{b}+3+2 \left(\frac{a}{c}+\frac{b}{a}+\frac{c}{b} \right)\]

Combining the terms on the LHS and using the fact that $\frac{x}{y}+\frac{y}{x} \geq 2$ we get

\[\frac{a}{c}+\frac{b}{a}+\frac{c}{b}+3+2 \left(\frac{a}{c}+\frac{b}{a}+\frac{c}{b} \right)=2\left(\frac{b}{c}+\frac{c}{a}+\frac{a}{b}\right)+2 \left(\frac{a}{c}+\frac{b}{a}+\frac{c}{b} \right) \geq 2(2+2+2)\]

Thus we get

\[\frac{a}{c}+\frac{b}{a}+\frac{c}{b}+3+2 \left(\frac{a}{c}+\frac{b}{a}+\frac{c}{b} \right) \geq 12\]
\[\Leftrightarrow 3 \left( \frac{a}{c}+\frac{b}{a}+\frac{c}{b} \right) \geq 9\]
\[\Leftrightarrow \frac{a}{c}+\frac{b}{a}+\frac{c}{b} \geq 3\]

And that is how I got the inequality :lol:

oops, sorry  :blush:
anyway, that inequality is always true, so you'll have to look for another way :P

i'm sorry, what are you doing here? What does your work imply?

I'm trying to find a solutin using that method above....dividing  by $abc$ and then expressing some inequalities...although I am not sure it will work

Let's make an effort to think big picture, as everyone should do when they try an inequality.

Is $LHS\geq RHS$ true for every $a,b,c$?  No, obviously not, take $a$ huge, $b=1$, $c$ very small.  This means that all of DPopov's work is down the drain.  Is it true when $a,b,c$ are sides of a triangle?  We'll see (I already proved the answer is yes)

Is it at least true for certain cyclic orderings of $a,b,c$?  YES.  If $a\geq c\geq b$, then
$(a-b)(b-c)(c-a)\geq 0$ and using $\sum a^2b\geq 3abc$, we see $LHS\geq RHS$.  Next!

Because it is cyclic, we may assume that $a$ is largest.  This means we only need to handle $a\geq b\geq c$.  Since the usual methods probably won't work here, we will try to brute force it by means of the substitution $a=c+x+y$, $b=c+x$, where $x,y\geq 0$.  The triangle condition implies that $y<c$ (or else $a\geq b+c$).  Factoring will make your life much, much easier here.

Expand.

Simplify.

Done.


For complex nos. z and w, prove that $|z|^2w - |w|^2z = z-w$, if and only if $z=w$ or $z\bar{w} = 1.$

No more comment than http://www.mathlinks.ro/Forum/viewtopic.php?t=89140 ...


[quote="Aragorn"]Two mothers met in the street.  They started talking about their children.  "I have three sons," said the first mother.  "How old are they?"  asked the second.

       "Well, it's easy to figure this out," replied the first mother.  "The product of their ages is equal to 36 and the sum of their ages is equal to the number of windows in the house across the street."

       The second mother thought for a while and said, "What you've told me is not sufficient to solve your problem."    "Oh, yes, the older one is red-haired," replied the first mother and the second solved the problem.

       What were the ages of the first mother's sons?[/quote]

all possible cases of the combinations of three sons' ages are:    (a*b*c=36)

a    b       c         sum
1　 1　  36　　  38
1　 2　  18　　  21
1　 3　  12　　  16
2　 3　  6　　　 11
1　 6　  6　　　 13
2　 2　  9　　　 13
3　 3　  4　　　 10

now, if sum are 38, 21, 16, 11, and 10, we can draw a conclusion with the corresponding a,b and c; but the second mother thought for a while and said, "What you've told me is not sufficient to solve your problem."

So, it is not the above sum; that is it is 13, but there are two cases: 1 6 6 and 2 2 9,
the second mother said:"the older one is red-haired", so,there is only one who is elder. That is 2 2 9.


Prove that a connected graph which has $ n$ vertices has at least $ n\minus{}1$ edges.

if you can remove an edge and still have it be connected then do it, repeat until it cannot be done anymore. What is left over afterwards must be a tree, for if there were a cycle then you could remove an edge from the cycle and it would still be connected.  Now you have a tree on n vertices, and it is well known that trees on  n vertices have n-1 edges (proof by induction works for that), so your orignal graph must have had at least n-1 edges.

[quote="nateharman1234"]it is well known that trees on  n vertices have n-1 edges[/quote]
This amounts to a reduction of the question to itself.

To see the requested result, [hide]I would just keep track of what happens to the number of connected components as you add edges to a graph on $ n$ vertices: initially, you have an empty graph so $ n$ components, and each time you add an edge you decrease the number of components by at most 1.[/hide]


If n is a positive divisor such that 2n has 28 positive divisors and 3n had 30 positive divisors, then how many positive divisors does 6n have?

(1996 AHSME #29)

Please post the first few solutions in spoiler to allow everyone to solve the problem without accidentally seeing someone else's.

[hide]The way I see it, we want to find factorizations of 28 and 30 such that 28=a*(b+1)*c and 30=a*b*(c+1). One such factorization is 28=1*7*4 and 30=1*6*5. Now we use that handy formula for the number of factors of a number n=p1^e1*p2^e2*p3*e3... is (e1+1)(e2+1)(e3+1)... Thus 2n has 7*4 factors, so 2n is 2^6*3^3, and 3n is 2^5*3^4, and 6n is 2^6*3^4, which has 35 factors. Unless I did something silly, there aren't any other values of n other than 2^5*3^3 which satisfy the condiiton of the problem.[/hide]

I'm pretty sure that's right.

For those of you who are mystified by the formula, it's this:

If a number has a prime factorization of A^a * B^b * C^c * D^d * ...

Then it has (a+1)(b+1)(c+1)(d+1)...total factors.

Spoiler:

[hide]We can use this property in reverse, too.

Since 2n has 28 factors,

(a+1)(b+1)(c+1)(d+1)... = 28.

We need to find numbers that multiply to 28, such as 4 and 7.  So a=6 and b=3.

Next, since 3n has 30 factors,

(a+1)(b+1)(c+1)(d+1)... = 30.

We could have several things multiply to 30, but to be as simple as possible, let's only use two (to be consistent with our last one, also).  So say 6 and 5.

So a=5, b=4.

Again, making it as simple as possible, let's set A and B as 2 and 3.  Oh, look! Since 2n = 2^6*3^3, n = 2^5*3^3.  This is consistent with the fact that 3n = 2^5*3^4, so we have verified that n must be 2^5*3^3.

Therefore, 6n = 2*3*n = 2^6 * 3^4.  So it has (6+1)(4+1) = 35 factors.  Answer.[/hide]

Quote:If n is a positive divisor such that 2n has 28 positive divisors and 3n had 30 positive divisors, then how many positive divisors does 6n have?

[hide]cool beans. well if you use that formula, its perdy easy from there. okay. so im guessing yall know that formula sphink, and have already read the solutions. but i want to know if my answer is right. so okay. well since a+1 times b+1 etc. are the number of factors. you know that (a+1)(b+1)..=28. after pondering a bit. i came to think that a=6 and b=3. for the bases, i used 2 because of 2n and 3n. so i used 2 and 3. so 2n=2^6 x 3:^3:. after pondering a bit also for 3n having 30 factors, i used a=5 and b=4. so 3n=2:^5:3:^4:. dividing by 3 for that equation n=2:^5:3:^3:. n equals the same thing for the other equation. were not done yet, because we have to find how many factors 6n has. so multiply n=2:^5:3:^3: by 6 (which is equal to 2 x 3) so 6n=2^6 x 3:^4:. so then 7 x 5=35. so 35 is the answer. i think ill go check my answer after i post this. mufasa.[/hide]

even if i helped just a tid bit. ill feel satisfied

Whoa there, I sense a lot of guesswork here. (a,b,c,...) for which abc... = 28 can be (1, 28), (28, 1), (2, 14), (14, 2), .. Same thing for abc... = 30. And how did you ever choose A, B, C, ... to be A=2, B=3. This all seems a bit too random for me.

[hide]well, of course we left out some stuff. but for the bases being 2 and 3. i used it because of the 2n and 3n part. so it would divide easaly. and notice i would say "after pondering for a bit". in finding what the exponents would be.[/hide]

[quote]but for the bases being 2 and 3. i used it because of the 2n and 3n part. so it would divide easaly[/quote]

Ok, I see now. But still...choosing the abc... = 28 and 30 seems a but on the random guessing side to me...

it was for me, at least. but notice once again that i said "after pondering for a bit". that means "after trying some cases and failing". lol. but its true

Well, since the thing with 30 factors and the thing with 28 factors have to be practically the same, except for one prime factor, you want them to be fairly close.  If you chose 28 and 1, you'd have to choose 30 and 1, which wouldn't work anyway.  So you mess around a little to get 4 and 7, 5 and 6, which are close to each other but not the same numbers.

It's sorta intuition.  You get used to it after a while.

Ok, well, I guess Ill take your word for it.

Don't take our words for it. Make sure you understand it. Otherwise you won't be able to solve a similar problem if it comes up in the future.

I was refering to the intuitive guessing.

You don't have to use any guesswork though. Did you read my solution?


geometry
circumcircle
geometric transformation
geometry proposed

[b][color=darkred]Let $ ABCD$ be a cyclic convex quadrilateral. Define the intersection $ E\in AC\cap BD$ and the points $ L\in (BC)$ ,

$ N\in (DA)$ so that $ m(\widehat {CLE}) \equal{} m(\widehat {DNE}) \equal{} \phi \le 90^{\circ}$ . Outside of $ ABCD$ construct the $ K$ - isosceles $ \triangle ABK$ and

inside of $ ABCD$ construct the $ M$ - isosceles $ \triangle CDM$ so that $ m(\widehat {AKB}) \equal{} m(\widehat {CMD}) \equal{} 2\phi$ . Prove that $ KM\perp LN$ .[/color][/b]

[color=darkblue][b][u]Particular case.[/u] If $ \phi \equal{} 90^{\circ}$ , then obtain the problem 5 (second day) for IMAC - 2008 (see[/b][/color] [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=210729][color=red][b]here[/b][/color][/url] [color=darkblue][b]or[/b][/color] [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=213068][color=red][b]here[/b][/color][/url] [color=darkblue][b]).[/b][/color]

[color=darkblue][b][u]Remark.[/u][/b] You can use the following remarkable lemmas :[/color]

[quote="Virgil Nicula"][color=darkred][b][u]Lemma 1.[/u][/b] Outside of $ \triangle ABC$ construct $ \triangle ABP$ , $ \triangle ACN$ , $ \triangle BCM$ so that $ \triangle ABP\sim\triangle ACN$ , $ m(\widehat {APB}) \equal{} \phi\ge 90^{\circ}$ ,

$ MB \equal{} MC$ and $ m(\widehat {BMC}) \equal{} 360^{\circ} \minus{} 2\phi$ . Prove that $ MP \equal{} MN$ and $ m(\widehat {PMN}) \equal{} 2\cdot m(\widehat {ABP})$ .[/color][/quote]

[quote="Virgil Nicula"][color=darkred][b][u]Lemma 1.[/u][/b] Outside of $ \triangle ABC$ construct $ \triangle ABP$ , $ \triangle ACN$  so that $ \triangle ABP\sim\triangle ACN$ and  $ m(\widehat {APB}) \equal{} \phi\le 90^{\circ}$ . Inside of $ \triangle ABC$

construct $ \triangle BMC$  so that $ MB \equal{} MC$ and $ m(\widehat {BMC}) \equal{} 2\phi$ . Prove that $ MP \equal{} MN$ and $ m(\widehat {PMN}) \equal{} 2\cdot m(\widehat {ABP})$ .[/color][/quote]

[color=red][b]Edit :[/b][/color] Sorry, now I mentioned where the triangles $ ABK$ , $ CDM$ are isosceles ! This problem - arrow type has many aplications and particular cases. Try they !

[quote="Virgil Nicula"][b][color=darkred]Let $ ABCD$ be a cyclic convex quadrilateral. Define the intersection $ E\in AC\cap BD$ and the points $ L\in (BC)$ ,

$ N\in (DA)$ so that $ m(\widehat {CLE}) \equal{} m(\widehat {DNE}) \equal{} \phi \le 90^{\circ}$ . Outside of $ ABCD$ construct the $ K$ - isosceles $ \triangle ABK$ and

inside of $ ABCD$ construct the $ M$ - isosceles $ \triangle CDM$ so that $ m(\widehat {AKB}) \equal{} m(\widehat {CMD}) \equal{} 2\phi$ . Prove that $ KM\perp LN$ .[/color][/b]
[/quote]
[hide="Solution"]
Let the circumcenters of $ \triangle ANE$ and $ \triangle BLE$ be $ P$ and $ Q$ respectively.  We have that the major angle of $ \angle APE$ is $ \angle APE \equal{} 2\angle ANE \equal{} 360 \minus{} 2\phi$.  Thus, $ \angle APE \equal{} 2\phi$.  Also, $ AP \equal{} PE$.  Since $ AK \equal{} KB$ and $ \angle AKB \equal{} 2\phi$, we have that $ \triangle AKB\sim \triangle APE$.  Thus, a spiral similarity maps $ \triangle APK\sim \triangle AEB$, from which we see that $ \frac {KP}{BE} \equal{} \frac {AK}{AB}$, so $ KP \equal{} \frac {BE\cdot AK}{AB}$.  Similarly, $ \triangle AKB\sim \triangle EQB$, so $ \frac {QL}{KA} \equal{} \frac {QB}{KB} \equal{} \frac {BE}{AB}$, so $ QL \equal{} \frac {BE\cdot AK}{AB} \equal{} KP$.  Similarly, $ PN \equal{} KQ$.  Now, the spiral similarities yield that $ \angle APK \equal{} \angle AEB \equal{} \angle BQK$.  Noting that $ \angle AEN \equal{} 180 \minus{} \angle NAE \minus{} \angle ANE\equal{} 180 \minus{} \angle BLE \minus{} \angle EBL \equal{} \angle BEL$, we have that $ \angle APN \equal{} 2\angle AEN \equal{} 2\angle BEL \equal{} \angle BQL$.  Thus,\[ \angle KPN \equal{} \angle APK \plus{} \angle APN \equal{} \angle BQL \plus{} \angle KQB \equal{} \angle KQL\]It follows that $ \triangle KPN\cong \triangle LQK$.  Thus, $ KL \equal{} KN$.  Similarly, $ MN \equal{} ML$, so $ KLMN$ is a kite, so $ KM\perp NL$. [/hide]

Yes, [b]The QuattoMaster 6000[/b], very nice your proof ! Thank you.