It seems that IMO'2008 will be huge...
Currently there are 87 registered countries ( http://www.imo-2008.es/participants.php ).

And countries like Costa Rica, Cuba, Georgia, India, Kazakhstan, Latvia, Macedonia,
Moldova, Romania, Slovakia, Turkmenistan, Vietnam are not registered yet.

And North-Korea will participate again! Good!

I guess that is good that they are fostering more international participation and love of math.

India is definitely going to be there this year :). We hope that this time will lead to a significant improvement over the average performances of the last few years!

89 and growing. (Slovakia and Latvia joined the fun.) I think 93 (the record from last year) is at least going to be equaled (India, Moldova, Romania, Vietnam are not on the list yet), if not broken.

Well, you know that not all countries (and regions) registered for the competition usually appear on IMO. That's why we'll have to wait the opening ceremony to say the official number of teams competing. ;)

Yeah... I guess I know. So, are you coming to IMO as an observer, hsiljak? (You wrote: "(...)we'll have to wait the opening ceremony(...)")

No, no, I haven't planned a trip to Spain this year :) I did use the term "We'll", but that still doesn't mean I'll go :) Just a figure of speech.

Well, to be honest - I expected that. Just wanted to be sure.

[quote="test20"]It seems that IMO'2008 will be huge...
Currently there are 87 registered countries ( http://www.imo-2008.es/participants.php ).

And countries like Costa Rica, Cuba, Georgia, India, Kazakhstan, Latvia, Macedonia,
Moldova, Romania, Slovakia, Turkmenistan, Vietnam are not registered yet.[/quote]

Now there are 93 registered countries:  http://www.imo-official.org/year_reg.aspx

Costa Rica, Georgia, Latvia, Romania, Slovakia, Turkmenistan have been
registered in the meantime.

Cuba, India, Kazakhstan, Macedonia, Moldova, Vietnam are still missing.
It would be strange to have an IMO without India, Kazakhstan, Macedonia, Moldova,
or Vietnam.
And Cuba does not always participate with a full team of six students, but has
participated at every IMO since 1971, except for 1975 and 2006.

So all in all, Spain may end up with 99 participating countries.

[quote="test20"]Now there are 93 registered countries:  http://www.imo-official.org/year_reg.aspx
[/quote]
And now they are up to 96 countries.
India and Macedonia have registered, and it looks as if Benin will participate
for the first time in an IMO!

Cuba, Kazakhstan, Moldova, Vietnam are still missing.
I wonder whether this might mean that Kazakhstan has run into problems
with organizing IMO'2010.

test20: You seem to be from Cuba (the little flag under your name). Will Cuba participate this year?

If so, the number of 100 will probably get reached as I'm sure Vietnam, Moldova and Kazakhstan will participate. I couldn't imagine what would need to happen in order for them not to participate.

[quote="hsiljak"][quote="test20"]
Cuba, Kazakhstan, Moldova, Vietnam are still missing.
[/quote]
Well, some countries do their TSTs first, and then confirm the participation together with the registration of participants ;)[/quote]

Yes, different countries have different ways of doing their TSTs.

But: The registration deadline for leaders, deputy leaders and observers of
*ALL* participating countries is April 30, and does not depend on the local TSTs:
http://www.imo-2008.es/deadlines.html

[quote="test20"]And now they are up to 96 countries.
India and Macedonia have registered, and it looks as if Benin will participate
for the first time in an IMO![/quote]

As of today, there are 99 registered countries.
Cuba and Kazakhstan have not been registered.

And among the registered countries, there are eleven countries that still
have neither registered team leaders nor deputy leaders nor contestants:
---Benin
---Bosnia and Herzegovina
---Bolivia
---Chile
---Guatemala
---Iceland
---Saudi Arabia
---El Salvador
---Turkmenistan
---Uruguay
---Vietnam

* Benin will send an observer-A. Is this their first appearance at an IMO?
* Guatemala has not shown up in 2006 and 2007. Does anybody know about them?
* Uruguay particpated every year from 1997-2006, but did not come to IMO'2007.
Will they participate in Spain?
* Bolivia, Bosnia and Herzegovina, Chile, El Salvador, Iceland, Saudi Arabia,
Turkmenistan, and Vietnam are regular IMO-countries, and they all were present
at  IMO'2007. They are probably just sloppy in international communications, or
perhaps they want to make the life of the Spanish organizers more exciting.

El Salvador will participate for sure :) Our TST was held about one week ago, so I guess our country's leaders and contestants will be registered all at the same time.

[quote="Jutaro"]El Salvador will participate for sure.[/quote]
Good to know!

In the meantime, also Kazakhstan has registered.
And for the first time, there will be a team from the United Arab Emirates at an IMO!!

IMO'2008 might be the first IMO with contestants from 100 different countries!!!

Currently, there are 102 registered countries.
Two of these registered countries will not send a team, but only an observer (Benin
and Syria; it's their first appearance at an IMO; in 2009 they may send a team).
Furthermore Cuba is not registered yet, but will participate for sure.
All in all, this yields a total of 101 countries with teams.

Out of these 101 countries, there are only five countries that still have neither
registered team leaders nor deputy leaders nor contestants:
---Cuba
---Guatemala
---El Salvador
---Turkmenistan
---Vietnam

Cuba has a team and will participate for sure.
El Salvador has a team and will participate for sure.
Guatemala has participated at some IMOs, but neither in 2006 nor in 2007.
Turkmenistan has participated at every IMO since 2001.
Vietnam has participated at every IMO since 1982.

A cautiously optimistic prediction would be to have the 96 actively registered countries
plus Cuba, El Salvador, Turkmenistan, Vietnam.

This makes 100 countries.

[quote="test20"]IMO'2008 might be the first IMO with contestants from 100 different countries!!![/quote]

Currently, there are 104 registered countries.
For three of them (Benin, Syria, Mauritania) it is the first appearance at IMO.
Hence, they only send an oberver but no contestants.

Among the remaining 101 countries, 96 have registered contestants.
Only five countries did not register their contestants by the very last (extended) deadline.
--Cuba
--Mozambique
--Romania
--Turkmenistan
--USA

Cuba, Romania, USA have a team.
I guess they are playing some kind of political game, and keep their student data
secret from the Spanish IMO organisation (although I do not understand the
motivation for this; how can they get an advantage out of this?)
Romania and USA have also registered observers, but did not settle the
corresponding fees by the deadline. Very strange.

What about Mozambique and Turkmenistan?
If there would be just one contestant from one of these countries, Spain would
have contestants from 100 different countries.

I will go by this calculation:
104 countries are registered.
98 countries have registered team leaders. Panama has no registered leader, but it does have 2 registered contestants. That's 99.
If you are certain that Cuba will participate, we reach 100. With Turkmenistan, the number could rise to 101.

[quote="test20"]I guess they are playing some kind of political game, and keep their student data
secret from the Spanish IMO organisation (although I do not understand the
motivation for this; how can they get an advantage out of this?)
[/quote]There is no "political game". The teams haven't been selected for either Romania or USA. There are still 2 TSTs to go for both countries until the final 6 are selected.

Yes , it couldn't be a political game . The is no reason for something like this .

BTW , Could someone post please the first TST of Romania ? And someone the TST's from USA ?

[b]We've got 100![/b]

99 countries have registered their team leaders + Panama which has registered 2 contestants, but not a team leader.

[quote="mornik"]Are we certain that Cuba will participate? If so, why are there no registered participants 3 weeks before IMO? What about Mauritania and Mozambique (Mozambique has registered their team leader, though)?[/quote]

Currently, there are 104 registered countries.
For three of them (Benin, Syria, Mauritania) it is the first appearance at IMO.
Hence, they will only send an oberver but no contestants.

Among the remaining 101 countries, 98 have registered contestants and registered leaders.
Only three countries did not fully register their participants:
--Cuba (nobody registered at all)
--Mozambique (only 1 registered team leader)
--Panama (only 2 registered contestants)

Cuba has a team (one contestant, one team leader), but they are horribly unreliable in their communications.
Mozambique and Panama are totally unclear.

Thanks. You are sure that Cuba will participate, though?

Finally also Cuba has registered a participant and a team leader!

All in all, there are 104 registered countries.
For three of them (Benin, Syria, Mauritania) it is the first appearance at IMO.
Hence, they will only send an observer but no contestants.

Among the remaining 101 countries, now 99 have registered contestants and registered leaders.
Only two countries did not fully register their participants:
--Mozambique (only 1 registered team leader)
--Panama (only 2 registered contestants)

Does anybody have any information about Panama or Mozambique?
If one of them indeed sends contestants, then IMO'2008 would be the
first IMO to have contestants from 100 different countries!

[quote="michaj"][quote="test20"]Finally also Cuba has registered a participant and a team leader!
[/quote]

However, the Cuban contestant seems to be a bit too old for the IMO ;)

http://www.imo-official.org/year_reg_team.aspx?code=CUB[/quote]

And you have special eyes that can detect ones age ? :maybe:

I think there was also an (Israeli? I'm also not sure.) contestant who was 0 years old. I can't find it now, it was probably changed anyway.

[quote="hsiljak"]Originally, there was a typo in the page: it said 1817 years old (or 1718, I'm not sure). That's why michaj made this comment (right, michaj?).[/quote]

Yep, 1817 years it was. An admirable age for a contestant indeed :)


For the positive integer n let 4^n+2^n+1 be a prime. Prove that n is represented as n = 3^k with k being a positive integer.

It is easy to see, that if k is not 3l, with l -- integer, than
x^{2k}+x^k+1 devided by x^2+x+1

Another easy way : if n = 3k+1 then 4 n + 2 n  + 1 = 0 mod[7] and is greater than 7.
If n = 3k+2, then 4 n + 2 n  + 1 = 21 = 0 mod[7] and is greater than 7.

Pierre.

But what will yuo do if n=3^s k, where k=3m \pm 1

Sorry, I misread the text (3k is not 3^k)...

Pierre.


What is considered a good time complexity for IOI problems?   O(10^6), O(10^7) or what?

I don't believe there is such a rule.. it all depends on the task and the time limit given. And by the way, O(10^6) , O(10^7) is equivalent to O(1)  :P

Remember New Jersy style guidlines. The relevent portion is [quote]n is usually small[/quote]. A O(1) algorithm with large overhead will not outpreform a O(n) algorithm with next-to-no overhead for small .

[quote="richard"]I'm sorry, I didn't make myself understood. What I mean is: in order for a program whose running time depends on a variable n (n<=10) to run in 1 second, should we aim for an algorithm of O(n^6), O(n^7) or what?[/quote]

I think you can assume that n <= 10 usually means there's an O(2^n) or O(3^n) algorithm.. I don't think I've ever seen a programming problem for which the official solution was O(n^6) or O(n^7). :)


Suppose that $ m\equiv 1\pmod{b}$.
What integer between $ 1$ and $ m\minus{}1$ is equal to $ b^{\minus{}1}\pmod{m}$?

Let $ m\minus{}1\equal{}kb$ (for some integer $ k$, by the given condition).  Then it's obvious that the answer is $ m\minus{}k$, because $ kb\equiv\minus{}1\mod{m}$.


Mr. and Mrs. Adams recently attended a party at which there were three other couples. Various handshakes took place. No one shook hands with his or her own spouse, no one shook hands with the same person twice and no one shook his or her own hand. After the handshaking was done, Mr. Adams asked each person, including his own wife, how many hands they had shaken. Each gave a different answer. How many hands did Mrs. Adams shake?

[hide]Let's see...
A B C D are the Mr.'s
Aa Bb Cc Dd are the Mrs.'

If the handshake happens in order:
A) B C D Bb Cb Db (means A with B, A with C, A with D, etc.)
B) C D Ab Cb Db
C) D Ab Bb Db
D) Ab Bb Cb
Ab) Bb Cb Db
Bb) Cb Db
Cb) Db
Db) 0

I am not sure why D) and Ab) have to turn to the same number of people for handshakes...
Each person seems to have to shake hands with other six eventually. But it didn't state in the problem that each person have to shake hands with everyone else...
[/hide]

one question about solution..

[hide=".....??"]but if A DID shake hands with B, then wouldn't B say i shook hands with A, C, D, Aa, Cc, Dd???
so technically, everybody shook hands 6 times.... and the total number of handshakes in the room SHOULD be 18... (if i'm not mistaken)...[/hide]

Not everyone has to shake hands with everyone else.  That would trivialize the problem.

We can generalize this. Let there be $ n$ couples.
Each person handshook $ 0,1,..,2n\minus{}3,2n\minus{}2$ persons.
Suppose someone handshake $ 2n\minus{}2$ persons, then this persons husband/wife shakes hands with $ 0$ persons.
Suppose someone handshake $ 2n\minus{}3$ persons, then this persons husband/wife shakes hands with $ 1$ person.
And so on..
So the handshake becomes $ 2n\minus{}2\minus{}r$ persons for say wife and $ r$ persons for husband.
Since each person gave different answer, Mr.Adams and Mrs. Adams shook hands with equal number of hands, i.e. $ r\equal{}\frac{2n\minus{}2}{2}\equal{}n\minus{}1$.
Hence Mrs.Adams shook hands with $ n\minus{}1$ in this case.
In our case $ 2$ persons.

[quote="dran"]
Since each person gave different answer, Mr.Adams and Mrs. Adams shook hands with equal number of hands, i.e. $ r \equal{} \frac {2n \minus{} 2}{2} \equal{} n \minus{} 1$.[/quote]

I got everything else but lost on the above reasoning. Explanation please?

[quote="jeez123"]
I got everything else but lost on the above reasoning. Explanation please?[/quote]

Since $ 2n\minus{}2$ is even, there exist number of handshakes which are equal for both the wife and the husband of some couple.
The problem supposes that 'Each gave a different answer'. This means that Mrs.Adam and Mr.Adam handshook equal number of handshakes.
$ 2n\minus{}2\minus{}r$=(number of handshakes of say wife) equals to $ r$=(number of handshakes with husband) when $ r \equal{} \frac {2n \minus{} 2}{2} \equal{} n \minus{} 1$.

[quote="dran"]
Suppose someone handshake $ 2n \minus{} 2$ persons,[b] then this persons husband/wife shakes hands with $ 0$ persons[/b].
Suppose someone handshake $ 2n \minus{} 3$ persons, [b]then this persons husband/wife shakes hands with $ 1$ person[/b].
And so on..
.[/quote]

I am almost there, please be patient!

Why does the person's husband/wife shook can only shook hands with $ 1$ persons when his/her spouse shook $ 2n\minus{}3$, and so forth?

Thanks so much!

Huh?
How is it 2?

Here is a way in which she shakes with 3:

B.) A C D a c d
C.) A B D a d
D.) A B C a
a.) B C D
b.)
c.) B
d.) B C

[quote="jeez123"]
Why does the person's husband/wife shook can only shook hands with $ 1$ persons when his/her spouse shook $ 2n \minus{} 3$, and so forth?[/quote]

Suppose you shake hands with $ 2n \minus{} 2$ persons. Then you have shaken hand with people who have shaken $ 1,...,2n \minus{} 3$ hands. Your wife/husband can then have handshaked $ 0$ or $ 2n \minus{} 2$ persons (since you didn't shake your wife/husband). But all people shake different number of handshakes. Thus your wife/husband shakes hand with $ 0$ people.

Remove this couple from the counting and the number of handshakes. Apply same argument for $ 2n \minus{} 3,2n \minus{} 4,...$ and so on.

OH!

So the keyword here is that everyone hand-shook different numbers of people. Since there are $ 2n\minus{}2$ people besides the couple in a room, we have to find out [b]how[/b] every husband and wife pair hand shake (2n - 2, 0) (2n - 3, 1) (2n - 4, 2) so that everyone hand-shook with different number of people. Every husband and wife's combined number of handshake is $ 2n\minus{}2$.

Thank you for your explanations!

[hide="super ownage"]
The only possible numbers of hands that people shook are 0,1,2,3,4,5, and 6.
Each person can shake with everyone except him/herself and his/her spouse.
But we need to fit these numbers to 8 people, so by pigeonhole 2 people shook the same number of hands.

Let us suppose WLOG B shook hands 6 times.  (We will see why we can do this later.)  That means b shook hands 0 times, because if the 0 shaker was any of the other people, we could reach a contradiction.
Then let us suppose C shook hands 5 times.  That means c shook hands 1 time, because if the 1 shaker was A, a, D, or d, then he would have had to shake C and B.
Etc.
So 6 is "paired" with 0, 5 is "paired" with 1, 4 is "paired" with 2, and 3 is "paired" with 3.

Because Mr. Adams is the "leftover" in the pigeonholes, then he must have value 3, and that means Mrs. Adams shook 3 times, no matter how we originally named the numbers.

Clearly we can do this for [b]any[/b] even number of people.
[/hide]

[quote="CircleSquared"]That means b shook hands 0 times, because if the 0 shaker was any of the other people, we could reach a [b]contradiction[/b].[/quote]

The "Pigeon Hole Principle" is exactly what I needed to sort myself out. Though, could you go on about the contradiction part?
Thanks!

B shook hands with everyone but his spouse.
That means each person except b had to have shaken at least 1 time.
So if anyone but b shook hands 0 times, we reach a contradiction.

:jump: I understood the whole thing now. I am super happy! Thanks!

[quote="CircleSquared"][quote="nateharman1234"]Metamathematical solution:

[hide] If he instead asked each person how many peoples hands they didn't shake, each person would still give a different answer. So it is essentially the same problem, only since the original problem was solvable so must this one and the answer must be the same, so the wife must have shaken as many hands as she didn't shake. The answer follows.[/hide][/quote]

This is somewhat abusive of the original problem, and would never pass on an proof exam such as the USAMO.  How is it a mathematical solution?[/quote]

I said it was a metamathematical solution, in that I go outside of mathematics by assuming that a unique solution exists, and then by that assumption I determine what it must be.  Indeed it would not pass for a proof on USAMO, I just posted it as an interesting way to think about it.

How do you know the problem is solvable again?  :D


In $\triangle ABC$, $O$ is the circumcenter and $H$ the orthocenter. $D$ is a point of $BC$ that $OD$ is perpendicular to $BC$. Show that $AH = 2OD$

It's a known theorem.
Nevertheless is a good idea for Intermediate Topics.....
Have fun!!! :)

[hide="hint"]Extend $BO$ and  Parallelograms... [/hide]

This problem was posted by me several days ago ( right in this forum).  :)
My proof is: Construct the circumcircle. And let the intersection of CO and the circle be E. Then we can show that AHBE is a parallelogram. Hence AH=BE. Because OD $\perp$ BC, EB $\perp$ BC, and CD=BD, so BE=2OD, hence we can imply AH=2OD.

[quote="indybar"]how to prove the parallelogram?[/quote]

The quadrilateral AHBE is a parallelogram since $AH\perp BC$, $BE\perp BC$, $BH\perp CA$ and $AE\perp CA$.

For another proof of the theorem in question, see http://www.mathlinks.ro/Forum/viewtopic.php?t=24870 post #4 Theorem 3 (of course, since O is the circumcenter of triangle ABC, the point D, lying on BC and satisfying $OD\perp BC$, must be the midpoint of the segment BC).

  darij


integration
trigonometry
calculus
calculus computations

Compute $ \int \frac{1}{\sin^4x \plus{} \cos^4x}\,dx$.

[hide]
We have the identity
\[ \sin^4 x\plus{}\cos ^4 x\equal{}(\sin^2 x\plus{}\cos^2 x)^2\minus{}2\sin^2 x\cos^2 x\equal{}1\minus{}\frac{1}{2}\sin^2 2x\equal{}\frac{3\plus{}\cos 4x}{4}\]
Now make the substitution $ u\equal{}\tan 2x$. We then have $ \cos 4x\equal{}\frac{1\minus{}u^2}{1\plus{}u^2}$ and $ \frac{du}{dx}\equal{}2(1\plus{}u^2)$, so that our integral is equal to
\[ \int \frac{4}{3\plus{}\frac{1\minus{}u^2}{1\plus{}u^2}}\cdot \frac{du}{2(1\plus{}u^2)}\equal{}\int \frac{du}{2\plus{}u^2}\]
Now use $ \int_0^y \frac{dt}{1\plus{}t^2}\equal{}\arctan y$ to get
\[ \int \frac{du}{2\plus{}u^2}\equal{}\frac{1}{2}\int \frac{du}{1\plus{}\left( u/\sqrt{2}\right)^2}\equal{}\frac{\arctan \frac{u}{\sqrt{2}}}{\sqrt{2}}\plus{}C\]
\[ \equal{}\frac{\arctan \frac{\tan 2x}{\sqrt{2}}}{\sqrt{2}}\plus{}C\]
Specifically, $ \int_0^x \frac{dx}{\sin^4 x\plus{}\cos^4 x}\equal{}\frac{\arctan \frac{\tan 2x}{\sqrt{2}}}{\sqrt{2}}$.
[/hide]

[quote="Carcul"]Compute $ \int \frac {1}{\sin^4x \plus{} \cos^4x}\ \mathrm {dx}$.[/quote]

$ I\equiv\int \frac {1}{\sin^4x \plus{} \cos^4x}\ \mathrm {dx}\equal{}$ $ \int \frac {\left(\sin^2x\plus{}\cos^2x\right)^2}{\sin^4x \plus{} \cos^4x}\ \mathrm {dx}\equal{}$ $ \int\frac {\tan^2x\plus{}1}{\tan^4x\plus{}1}\cdot\left(\tan x\right)'\ \mathrm {dx}\equal{}$ $ F\left(\tan x\right)\plus{}\mathcal C$, where $ F(t)\equal{}\int\frac {t^2\plus{}1}{t^4\plus{}1}\ \mathrm {dt}\equal{}$ $ \int\frac {\left(t\minus{}\frac 1t\right)'}{\left(t\minus{}\frac 1t\right)^2\plus{}2}\ \mathrm {dt}\equal{}$ $ \frac {1}{\sqrt 2}\arctan\frac {t^2\minus{}1}{t\sqrt 2}\plus{}\mathcal C$. Therefore, $ I\equal{}\frac {1}{\sqrt 2}\arctan\frac {\tan^2\minus{}1}{\sqrt 2\tan x}\plus{}\mathcal C\equal{}$ $ \minus{}\frac {1}{\sqrt 2}\arctan\frac {\sqrt 2}{\tan 2x}\plus{}\mathcal C$, i.e. $ \boxed {I\equal{}\frac {1}{\sqrt 2}\arctan\frac {\tan 2x}{\sqrt 2}\plus{}\mathcal C}$ because $ \arctan x\plus{}\arctan \frac 1x\equal{}\frac {\pi}{2}\cdot\mathrm {sign\ x}\ .$

Yes, that's another approach. We could also use directly the substitution tan x = t.


Find all polynomials P(x) with integer coefficients such that the set {P(n) | $ n\in Z$} contains the fibonacci sequence.

It's from the first stage of Polish MO, please lock this.


function
real analysis
real analysis unsolved

Hello!:)
Let $A,\ B \subset X$ and let $\alpha , \beta \in R$. What is a necessary and sufficient condition for $\alpha* \chi_A + \beta* \chi_B$ being measurable?
($\chi_A$ - characteristic function $A$)
Thaks for help!

Three possibilities:

$A$ and $B$ are both measurable

OR

$\alpha=\beta$ and $A\cup B$ is measurable

OR

$\alpha=\beta=0.$

Not exactly.
The right conditions:

$(A$ is measurable or $\alpha=0)$ and $(B$ is measurable or $\beta=0)$
or
$\alpha=\beta$ and both $A\cup B$ and $A\cap B$ are measurable
or
$\alpha=-\beta$ and both $A\setminus (A\cap B)$ and $B\setminus (A\cap B)$ are measurable.


1.If x is a real number not less than 1, which is larger: √(x+1) - √x or √x - √(x-1)?

2.Find 1*1! + 2*2! + ... + n*n!

3.What is the remainder on dividing 6^83 + 8^83 by 49?

4. A nice number equals the product of its proper divisors (positive divisors excluding 1 and the number itself). Find the sum of the first 10 nice numbers.

1. [hide]We compare their reciprocals instead.

(:sqrt:(x + 1) - :sqrt:x)-1 = :sqrt:(x + 1) + :sqrt:x

(:sqrt:x - :sqrt:(x - 1))-1 = :sqrt:x + :sqrt:(x - 1)

So (:sqrt:(x + 1) - :sqrt:x)-1 > (:sqrt:x - :sqrt:(x - 1))-1. Thus :sqrt:(x + 1) - :sqrt:x < :sqrt:x - :sqrt:(x - 1).[/hide]

2. [hide]1 * 1! + 2 * 2! + ... + n * n!

= (2 - 1) * 1! + (3 - 1) * 2! + ... + (n + 1 - 1) * n!

= 2 * 1! - 1! + 3 * 2! - 2! + ... + (n + 1) * n! - n!

= 2! - 1! + 3! - 2! + ... + (n + 1)! - n!

= (n + 1)! - 1.[/hide]

3. [hide]683 + 883

= (7 - 1)83 + (7 + 1)83

= ((83, 0) * 783 - (83, 1) * 782 + ... - (83, 81) * 72 + (83, 82) * 7 - (83, 83) * 1) + ((83, 0) * 783 + (83, 1) * 782 + ... +(83, 81) * 72 + (83, 82) * 7 + (83, 83) * 1)

Note that the binomial coefficients are not important here. Then, all the even-powered terms cancel out, so we're left with: (I'll leave out the binomial coefficients except where necessary)

2 (783 + 781 + ... + 73 + (83, 82) * 7)

All terms except the last one are divisible by 49. So this expression  :equiv: 2 * (83, 82) * 7 = 2 * 83 * 7 = 35 (mod 49)[/hide].

4. [hide]I claim that a nice number has exactly 2 proper divisors. To prove this, consider a number n with proper divisors d1, d2, d3, ..., dk. It is obvious that da * dk - a + 1 = n. If k > 2, then the product of the proper divisors > n; if k = 1, the sole proper divisor < n.

Thus k = 2.

n's prime expansion = p1a1 * p2a2 * ... * pmam.

The number of divisors (proper or otherwise) is given by

(a1 + 1)(a2 + 1) ... (am + 1).

Now this obviously equals 4 (2 proper divisors, the number 1, and n itself), so there are only two possibilities:

1) a1 = a2 = 1

2) a1 = 3

This means that n is either the product of two distinct primes, or is the third power of some prime. We list some numbers from each case:

1) 2 * 3 = 6, 2 * 5 = 10, 2 * 7 = 14, 2 * 11 = 22, 2 * 13 = 26, 3 * 5 = 15, 3 * 7 = 21, 3 * 11 = 33;

2) 23 = 8, 33 = 27.

So the 10 smallest ones are 6, 8, 10, 14, 15, 21, 22, 26, 27, 33. They sum to 182.[/hide]

[hide]

3.  use binomial theorem.  (7-1)^83 will have terms that are divisible by 49 except for the last 2, which are 83c1*7*1 +83C0*-1, which is  41 mod 49, and (7+1)^83, which will give 83c1*7+83C0*1, which is 43  mod49.  So the sum is 84, which is 35 mod 49.[/hide]


im new in mathlinks please, can somebody post some problems?


Can you prove

$ \sum_{k\equal{}0}^n {n\choose k}\, x\, (x\plus{}ak)^{k\minus{}1}\, (y\minus{}ak)^{n\minus{}k}\equal{}(x\plus{}y)^n$

hello, for the proof see here
http://www.combinatorics.org/Volume_3/PDF/v3i2r16.pdf
Sonnhard.

Thanks for the link.
I reproduced this computer-generated proof. I can only confirm that this is a valid proof.
It does the trick but it gives me no clue how to derive this proof.
I'm sure Abel had another method to derive his formula.


geometry
3D geometry
sphere
geometry unsolved

In $3$-dimensional space there is given a point $O$ and a finite set $A$ of segments with the sum of lengths equal to $1988$. Prove that there exists a plane disjoint from $A$ such that the distance from it to $O$ does not exceed $574$.

[quote="orl"]In 3-dimensional space there is given a point $O$ and a finite set $A$ of segments with the sum of lengths equal to 1988. Prove that there exists a plane disjoint from $A$ such that the distance from it to $O$ does not exceed 574.[/quote]

Observe that $574>\frac{1988}{\sqrt{12}}$.W.L.O.G., we let $O$ be $(0,0,0)$ For every plane cuts through the sphere $x^2+y^2+z^2=(\frac{1988}{\sqrt{12}})^2$, then it must also cut some of the segments. We will prove it by contradiction, that means the sum of the segments must be larger than $1988$.

Consider every plane that parallel to one of $x=0$, $y=0$, $z=0$. For every segment, let its ends are $(x_1,y_1,z_1)$ and $(x_2,y_2,z_2)$. Then it covers $(x_2-x_1)$ length of plane which is parallel to $x=0$. Similarly, it covers $(y_2-y_1)$ length of plane which is parallel to $y=0$ and covers $(z_2-z_1)$ length of plane which is parallel to $z=0$. Note that the length of segment $m$ is $\sqrt{(x_2-x_1)^2+(y_2-y_1)^2+(z_2-z_1)^2}$. Then the total lengths of plane being covered is $\le \sqrt{3m}$ by $QM\ge AM$. As there are totally $3*\frac{1988}{\sqrt{3}}$ length of plane being covered. We have $m\ge 1988$.
As $574>\frac{1988}{\sqrt{12}}$, there must be a plane disjoint from all the segments such that the distance from it to $O$ does not exceed $\frac{1988}{\sqrt{12}}$.


geometry circumcircle conics ellipse incenter ratio parallelogram

A quadrilateral $ABCD$ is inscribed in a circle with center $O$. A point $P$ is given on the plane. Let $K$, $L$, $M$, $N$ be the circumcenters of triangles $ABP$, $BCP$, $CDP$, $DPA$, respectively. Prove that the midpoints of the segments $KM$, $LN$, $OP$ are collinear.

This is a really nice problem :!:

The lines NK, KL, LM, MN are perpendicular bisectors of the segments AP, BP, CP, DP. Let perpendiculars n, k, l, m to AP, BP, CP, DP at A, B, C, D meet at to $K' \equiv n \cap k,$ $L' \equiv k \cap l,$ $M' \equiv l \cap m,$ $L' \equiv m \cap n,$ forming a quadrilateral K'L'M'N' centrally similar to KLMN with the similarity center P and similarity coefficient 2. In this similarity, the midpoints U, V of KM, LN go into the midpoints U', V' of K'M', L'N' and the midpoint Z of OP into O. Thus we have to show that O lies on the Newton line U'V' of the quadrilateral K'L'M'N'.

Let the opposite sides K'L', M'N' meet at S, WLOG on the opposite side of L'M' than K', N',  and let the opposite sides L'M', N'K' meet at T, WLOG on the opposite side of K'L' than M', N'. Let $E \in N'K',\ F \in K'L',\ G \in L'M',\ H \in M'N'$ be the other intersections of (O) with the side lines of the quadrilateral K'L'M'N'. (O) is the circumcircle of the pedal triangle $\triangle ACD$ of the triangle $\triangle N'TM'$ with respect to P. Consequently, the 3 normals to $N'T \equiv N'K',\ TM' \equiv L'M', M'N'$ at E, G, H concur at the isogonal conjugate Q of the point P with respect to the $\triangle N'TM'$ and O is the midpoint of PQ. Likewise, (O) is the circumcircle of the pedal triangle $\triangle BDA$ of the triangle $\triangle K'SN'$ with respect to P. Consequently, the 3 normals to $K'S \equiv K'L',\ SN' \equiv M'N',\ N'K'$ at F, H, E concur at the isogonal conjugate Q' of the point P with respect to the $\triangle K'SN'$ and O is the midpoint of PQ'. Thus the points $Q \equiv Q'$ are identical and all 4 normals to N'K', K'L', L'M', M'N' at E, F, G, H concur at Q.

Since the angles $\angle PAK',\ \angle PBL',\ \angle PCM',\ \angle PDN'$ and the angles $\angle QEK',\ \angle QFL',\ \angle QGM',\ \angle QHN'$ are all right, the lines $N'K' \equiv AE,\ K'L' \equiv BF,\ L'M' \equiv CG,\ M'N' \equiv DH$ are all tangents of an ellipse $\mathcal E$ with the focal points P, Q and pedal circle (O). Thus the quadrilateral K'L'M'N' is tangential to the ellipse $\mathcal E$ with the center O. Using a parallel projection, project the ellipse $\mathcal E$ into the circle (O). The quadrilateral K'L'M'N' tangential to the ellipse $\mathcal E$ goes into a quadrilateral K''L''M''N'' tangential to the circle (O), the Newton line U'V' of K'L'M'N' goes into the Newton line U''V'' of K''L''M''N'', while the line PQ and the midpoint O of the segment PQ stay in place. Since the Newton line U''V'' of the tangential quadrilateral K''L''M''N'' passes through its incenter O and O stays in place in our parallel projection, the Newton line U'V' of the original quadrilateral K'L'M'N' also passes through O.

Why the projection of ellipse $\mathcal E$ into the circle (O) projects the Newton line U'V' of K'L'M'N' into the Newton line U''V'' of K''L''M''N''??? :huuh:

Because parallel projection transforms lines into lines and it preserves ratios of segment lengths on the same line. Therefore, midpoints U', V' of the diagonals K'M', L'N' of K'L'M'N' are projected to the midpoints U'', V'' of the diagonals K''M'', L''N'' of K''L''M''N''.

[quote="nxxx"]Why does parallel projection preserve ratios of segments on the line?[/quote]

 You can simply use Thales Thoerem.

  [b]Segments on lines between parallel lines are proportional. [/b]

Can you explain it :?:
I don't know how to use Thales Theorem in this problem... :blush:

Suppose a line $l$ with points $A,\ B,\ C \in l$ in a plane $\mathcal P$ is transformed by a parallel projection into a line $l'$ with points $A',\ B',\ C' \in l'$ in a plane $\mathcal P'.$ If the two planes $\mathcal P \parallel \mathcal P'$ are parallel, then every figure in $\mathcal P$ is congruent to the projected figure in $\mathcal P',$ and A'B' = AB, B'C' = BC. If the planes $\mathcal P,\ \mathcal P'$ are not parallel, they intersect in a line $k,$ which stays in place in the parallel projection. If $l \parallel k,$ then $l' \parallel k,$ ABB'A',  BCC'B' are parallelograms, and again A'B' = AB, B'C' = BC. If $l$ is not parallel to $k,$ they intersect at a point P, which stays in place, and $P \equiv l \cap l'.$ The lines $AA' \parallel BB' \parallel CC'$ are parallel (rays of the parallel projection), the triangles $\triangle PAA' \sim \triangle PBB' \sim \triangle PCC'$ are similar, having equal angles, and $\frac{PA'}{PA}= \frac{PB'}{PB}= \frac{PC'}{PC}.$ If follows that $\frac{AB}{BC}= \frac{A'B'}{B'C'}.$ Isn't it simple?

[quote="yetti"]

Since the angles $ \angle PAK',\ \angle PBL',\ \angle PCM',\ \angle PDN'$ and the angles $ \angle QEK',\ \angle QFL',\ \angle QGM',\ \angle QHN'$ are all right, the lines $ N'K' \equiv AE,\ K'L' \equiv BF,\ L'M' \equiv CG,\ M'N' \equiv DH$ are all tangents of an ellipse $ \mathcal E$ with the focal points P, Q and pedal circle (O). Thus the quadrilateral K'L'M'N' is tangential to the ellipse $ \mathcal E$ with the center O. [/quote]
    Why you have M'N'P'K' are tangents of an ellipse with the focal P;Q and pedal circle (O)

[quote="hoangclub"]Why you have M'N'P'K' are tangents of an ellipse with the focal P;Q and pedal circle (O)[/quote]

Let (O) be a circle with radius a, centered at the coordinate origin O, with equation $ x^2 \plus{} y^2 \equal{} a^2.$ Let P be arbitrary point inside the circle (O), WLOG on the positive x-axis, so that $ p \equal{} OP < a.$ Let a line through P with arbitrary slope m, with equation $ y \equal{} m(x \minus{} p),$ meet the circle (O) at points A, A'. Substituting the line equation into the circle equation leads to a quadratic equation for the x-coordinate of A:

$ x^2 \plus{} m^2(x \minus{} p)^2 \equal{} a^2$

with solution

$ x_{A} \equal{} \frac {pm^2 \pm \sqrt {D}}{1 \plus{} m^2},\ \ D \equal{} a^2(1 \plus{} m^2) \minus{} p^2m^2$

A line through the point A and perpendicular to PA has equation

$ y \minus{} y_{A} \equal{} y \minus{} m(x_{A} \minus{} p) \equal{} \minus{} \frac {1}{m} (x \minus{} x_{A})$

Substituting for $ x_{A}$ and squaring yields

$ my \plus{} x \equal{} x_A(m^2 \plus{} 1) \minus{} pm^2 \equal{} \pm \sqrt {D}$

$ F(x, y, m) \equal{} (my \plus{} x)^2 \minus{} D \equal{} m^2(y^2 \minus{} a^2 \plus{} p^2) \plus{} 2mxy \plus{} x^2 \minus{} a^2 \equal{} 0$

This is equation of a family of lines dependent on the arbitrary parameter m. Equation of their envelope is obtained by eliminating m from the equations $ F(x, y, m) \equal{} 0$ and

$ \frac {\partial F}{\partial m} \equal{} 2m (y^2 \minus{} a^2 \plus{} p^2) \plus{} 2xy \equal{} 0$

The 2nd equation gives $ m \equal{} \minus{} \frac {xy}{y^2 \minus{} a^2 \plus{} p^2}.$ Substituting this to the 1st equation, the envelope equation comes out as

$ (x^2 \minus{} a^2)(y^2 \minus{} a^2 \plus{} p^2) \minus{} x^2y^2 \equal{} 0,\ \ \ \frac {x^2}{a^2} \plus{} \frac {y^2}{a^2 \minus{} p^2} \equal{} 1$

which is equation of an ellipse $ \mathcal E$ with center O, semimajor axis a, and focus P. Conversely, locus of the feet of normals from the ellipse focus P to ellipse tangents is the circle (O).


An eight by eight square has a 2 by 2 square in the middle (where nothing goes in). There are 12 pieces, how do you fit all of the pieces in? (I have really quick "pictures" of these). I'm sorry if the pieces and board are not proportionate. You are allowed to flip the pieces, you may not reuse the pieces. The black spot on the board is where no pieces may go into. (for example I can't put a part of piece on/in it)

The best way to do this is to make an actual board with pieces and solve it form there.  This is just an puzzle, not a math problem.

Is the problem asking whether it is [i]possible[/i] to fit all pieces in? Or is it definitely possible?

It's possible that all the pieces fit it, I've counted before. And yes I have tried with a real board, almost like a bazillion times...  :|  :mad: It's really getting me fustrated.  Any easier ways to "solve" it other than trying so many times? Oh and also, we have to put the pieces on the way it fits.

Just counting doesn't ensure it.  For example, can you put a 2x2 square on a 1x4 board?  They both have 4 squares...

Some things to get you started.  Obviously the first piece (the plus sign) cannot go into a corner.  Otherwise it would block off a square.  Is it possible to place the plus sign one spot over from the corner?  Which spots can you put the plus sign in, and if you put it in those spots, which pieces must you use around it?

What other pieces have areas "restricted?"  In other words, there are certain spots that each piece is not allowed to go, otherwise it would block off a square from the other pieces.

Using this logic, the answer should come in maybe 20 minutes of playing with it since you start significantly reducing the amount of options that are available.

I have a puzzle exactly like this, with the same pieces but the board is different(W, H, and Y).  By any chance, are you just asking this on AoPS so you can solve it and get some thing( my parents told me they'd buy anything if I could solve it, sadly, i was really close but haven't yet)

For these puzzles, they'll take a lot of time, but sadly, i don't think there is an easier way other than to use common sense.

This should kinda belong in the games forum...not sure...

Well anyway, I don't need anymore help  :D  I finished it this afternoon after finishing exactly half of it and then going on  :D


geometry
trigonometry
limit
calculus
calculus computations

limt    x--------infinity

        [(x+a)(x+b)(x+c)(x+d) ]^1/4   -  x

2. (sinx)/x<1 and (tanx/x)>1 prove it

3.  limit r---infinity

    product (r^3-8)/(r^3+8)

                    r=1 to infinity

Hello
Sorry but Do u mean $ \frac {{(x \plus{} a)(x \plus{} b)(x \plus{} c)(x \plus{} d)}^{1/4}}{x}$?
if so [hide="solution"]
Take $ x^4$ common from num.Answer is 1.
[/hide]
Solution.

Hello
Kindly start using Latex.
In question 3 are u asking to find  $ lim_{r\to\infty}\frac{r^3\minus{}8}{r^3\plus{}8}$?
Thank u.

Problem 3 is probably meant to be $ \prod_{n\equal{}3}^{\infty}\frac{n^3\minus{}8}{n^3\plus{}8}$.

[quote="Carcul"]Problem 3 is probably meant to be $ \prod_{n \equal{} 3}^{\infty}\frac {n^3 \minus{} 8}{n^3 \plus{} 8}$.[/quote]
If that's the case then just see that $ n^3 \minus{} 8 \equal{} (n\minus{}2)(n\plus{}1\plus{}\sqrt{3}i)(n\plus{}1\minus{}\sqrt{3}i)$ and $ n^3 \plus{} 8 \equal{} (n\plus{}2)(n\minus{}1\plus{}\sqrt{3}i)(n\minus{}1\minus{}\sqrt{3}i)$.

Then, if i didn't make any mistakes, we have: $ \prod_{n \equal{} 3}^{m}\frac {n^3 \minus{} 8}{n^3 \plus{} 8} \equal{} \frac{2}{7} \cdot \frac{m^4\plus{}2m^3\plus{}7m^2\plus{}6m\plus{}12}{m^4\plus{}2m^3\minus{}m^2\minus{}2m}$. So the result should be $ \frac{2}{7}$. :)

[quote="kabi"]Hello

First of all $ \frac {tan(x)}{x} > 1$.Kindly edit it.
[hide="2"]
Consider a sector $ OAP$ of unit circle with center $ O$.Draw a perpendicular$ PM$ from $ P$ to $ OA$.Extend $ P$ to $ B$ such that angle $ BAM$ is right angle.
$ OA = OP = 1 unit$
$ AB = OAtanx$
$ area of triangle OAP$=$ \frac {1}{2}OA*OPsinx$
$ area of sector OAP$=$ \frac {x}{2\pi}\pir^2$
$ area of triangle OAB$=$ \frac {1}{2}OA*AB$
$ area of triangle OAP < area of sector OAP < area of OAB$
$ sinx < x < tanx$
$ \frac {sinx}{x} < 1 < \frac {tanx}{x}$
[/hide]
Thank u.[/quote]
sir pl explain the method i am not getting

1) $ \dfrac{1}{4}(a+ b + c + d)$

Informally:
[hide]
\begin{align*}
\sqrt[4]{(x+a)(x+b)(x+c)(x+d)} - x
&=& \left(\sqrt[4]{(x+a)(x+b)(x+c)(x+d)} - x\right) \times
\dfrac{\sqrt[4]{(x+a)(x+b)(x+c)(x+d)} + x}
{\sqrt[4]{(x+a)(x+b)(x+c)(x+d)} + x}
\\&=&
\dfrac{\sqrt{(x+a)(x+b)(x+c)(x+d)} - x^2}
{\sqrt[4]{(x+a)(x+b)(x+c)(x+d)} + x}
\times \dfrac{\sqrt{(x+a)(x+b)(x+c)(x+d)} + x^2}
{\sqrt{(x+a)(x+b)(x+c)(x+d)} + x^2}
\\&=&
\dfrac{(x+a)(x+b)(x+c)(x+d) - x^4}
{\left(\sqrt[4]{(x+a)(x+b)(x+c)(x+d)} + x\right)\left(\sqrt{(x+a)(x+b)(x+c)
(x+d)} + x^2\right)}
\end{align*}

Consider the highest powers of $ x$ in the numerator and denominator, which is 3.

Coefficient of $ x^3$ in the numerator is $ (a + b + c + d)$.

and in the denominator, for large (positive) $ x$,
\begin{align*}
\left(\sqrt[4]{(x+a)(x+b)(x+c)(x+d)} + x\right)\left(\sqrt{(x+a)(x+b)(x+c)(x+d)} + x^2\right)
&\approx& \left(\sqrt[4]{x^4} + x\right)\left(\sqrt{x^4} + x^2\right)
\\&=& \left(x + x\right)\left(x^2 + x^2\right)
\\&=& 4x^3
\end{align*}

[/hide]

[quote="kabi"][quote="MUN"]
sir pl explain the method i am not getting[/quote]
Hello
I remember Dr had given a pdf with d same proof.It is much clear.
or
check this::
http://www.artofproblemsolving.com/Forum/viewtopic.php?t=242582
Hope ur doubt will be clear this time.
Thank u.[/quote]
thanks kabi
i want to meet u

The statement $ \frac{\tan x}{x} > 1$ is wrong, unless some specific interval is given.

[quote="MUN"]limt    x--------infinity

[(x+a)(x+b)(x+c)(x+d) ]^1/4   -  x

[/quote]
$ \lim_{x \to \infty} [(x\plus{}a)(x\plus{}b)(x\plus{}c)(x\plus{}d) ]^{\frac{1}{4}} \minus{} x$

Is this the question???
Or is it:
$ \lim_{x \to \infty} \frac{[(x\plus{}a)(x\plus{}b)(x\plus{}c)(x\plus{}d) ]^{\frac{1}{4}}}{x}$

[quote="Rajiv"][quote="MUN"]limt    x--------infinity

[(x+a)(x+b)(x+c)(x+d) ]^1/4   -  x

[/quote]
$ \lim_{x \to \infty} [(x \plus{} a)(x \plus{} b)(x \plus{} c)(x \plus{} d) ]^{\frac {1}{4}} \minus{} x$

Is this the question???
Or is it:
$ \lim_{x \to \infty} \frac {[(x \plus{} a)(x \plus{} b)(x \plus{} c)(x \plus{} d) ]^{\frac {1}{4}}}{x}$[/quote]
first one

I was wondering if writing $ \lim_{x \to \infty} [(x \plus{} a)(x \plus{} b)(x \plus{} c)(x \plus{} d) ]^{\frac {1}{4}} \minus{} x$ (please do not laugh if this is wrong :D ) as:

$ \Large \lim_{x \to \infty} \frac {\sqrt [4] {\left(\frac {1}{x} \plus{} \frac {a}{x^2}\right) \left(\frac {1}{x} \plus{} \frac {b}{x^2}\right) \left(\frac {1}{x} \plus{} \frac {c}{x^2}\right) \left(\frac {1}{x} \plus{} \frac {d}{x^2}\right)} \minus{} \frac {1}{x^3}}{\frac {1}{x^4}}$ could help get an indeterminable form of $ \left( \frac {0}{0} \right)$ so as to be able to use $ \mathfrak {L'Hopital's}.$
Then applying the $ \mathfrak {L'Hopital's}$, we get the numerator as : $ \lim_{x \to \infty} \frac {(\cdots) \plus{} \frac {3}{x^4}}{\frac { \minus{} 4}{x^5}}$ where the $ (\cdots)$ is some ugly term which ultimately equates to $ 0$ as $ x$ is in the denominator of all these terms. Hence we get finally $ \lim_{x \to \infty} \left(\frac {\minus{}3}{4} \right)x$ and hence we can pretty [b]neatly[/b] conclude the value of  $ \lim_{x \to \infty} [(x \plus{} a)(x \plus{} b)(x \plus{} c)(x \plus{} d) ]^{\frac {1}{4}} \minus{} x \equal{} \color{red}{\lim _{x \to \infty} \frac { \minus{}3x}{4} \equal{} \minus{} \infty}$

[hide]Did some one out there get $ 4x^3$??? More or less, we have got the same answer, the only noticeable difference being that in the sign... :D [/hide]

[hide="Solution to 1"]
Substitute $ x \equal{} \frac{1}{h}$ which transforms the limit into:

Let $ f(x) \equal{} [(1\plus{}ax)(1\plus{}bx)(1\plus{}cx)(1\plus{}dx)]^{\frac{1}{4}}$

$ \lim_{h\to 0^{\plus{}}} \frac{f(0 \plus{} h) \minus{} f(0)}{h}$

$ \equal{} f'(0) \equal{} \frac{1}{4}(a\plus{}b\plus{}c\plus{}d)$

[/hide]


vreau sa aud pareri de la cei care au fost clasa a XII-a. cat de banale vi s-au parut ?  :P am zis la misto, ca toata lumea zice : vaaai, ce simple ce banaleee subiectele de judeteanaa vaiii. si la nationala, 3 pt  :blush: felicitari icx pt autodepasire ( asta e si scopul ascuns al olimpiadei, dincolo de orgoliile prostesti de 2 lei ) si capul sus mychrom, ca esti tanar si mai ai multe astfel de ocazii. persevereaza, si nu te lasa afectat de shobolanismele unora cum m-am lasat eu  :roll:

[quote]Nu ma duc la nationala, adevarul este ca nici nu-mi permiteam sa ma gandesc la asa ceva, in ultima luna chiar m-am autodepasit (cu 1000%) si sunt multumit de mine.[/quote]

Si eu sunt in aceeasi situatie, cred.Oricum ma simt foarte multumit  :cool: .Felicitari!  :)

Subiectele au fost destul de accesibile, ca sa zic, la 7a ,
totusi nu am rezolvat prima problema care se pare ca era cea mai usoara  :huh: .
Bafta tuturor celor care merg la nationala si la internationala  !

PS:In incinta scolii unde s-a tinut olimpiada se amplasasera niste
 domni care vindeau culegeri de matematica pentru olimpiada  (loc strategic  :D ).
Am cumparat cateva , deci tot m-am ales cu ceva  :P .

Cum vi s-au parut subiectele la a IX-a ? .. Eu zic ca au fost palpabile... in comparatie cu unele subiiecte din anii anteriori ?

mychrom, eu sunt a IX-a :)

Eram atat de ofticat ca am stat toata saptamana acasa ca sa fac geometrie incat am profitat de standul celor de la GIL din curtea liceului si mi-am luat cartea lui V. Nicula, "Geometrie plana (sintetica etc)". Nu mai ratez io sansa asta la anu' :P Hai, felicitari si bafta in continuare celor care au trecut ;) Ceilalti, la treaba pt ONM 2008 :P

@turcas intr-adevar, mi s-au parut [u]un pic[/u] mai accesibile

bine subliniat "un pic" . :)) Mi-am luat si eu aceeasi carte ... avand in vedere ca stau mai prost cu geometria :) ... Si pe mine m-a macinat problma 2 , sper sa ma pun la punct cat de cat cu geometria , pana la faza urmatoare :)

[quote="icx"]Ideile mi-au venit mult mai repede decat la locala (faza pe sector), am fost multumit de subiecte, nici foarte usoare, nici foarte grele. Noroc cu functiile alea si problema 4, ca geometria aia de la 2, mama ei, m-a tocat marunt. :D Nu ma duc la nationala, adevarul este ca nici nu-mi permiteam sa ma gandesc la asa ceva, in ultima luna chiar m-am autodepasit (cu 1000%) si sunt multumit de mine.[/quote]

pai cu 3 probleme, eu zic ca treci lejer.

Si cu 2 probleme poti sa te califici, dar nu stiu ce sa zic despre punctajele de la celelalte 3 probleme care mi-au ramas, clar nu iau 21 puncte (ca nu-mi faceam griji asa).

Tu ce-ai facut pohoatza?

Btw cred ca te-am vazut azi pe acolo :P

nu stiu ce sa zic, astept rezultatele, caci am o solutie sa zic eu "dubioasa" la subiectul 1, sa vedem.

oricum eu anul asta, cred ca o sa se mearga de la 14, cel putin la a 9a, daca nu mai putin, dar din cate am auzit eu, parca asa ceva nu se putea.

am aflat niste rezultate din valcea, si am inteles ca la a 9a, cea mai mare nota a fost 6, deci sa fim optimisti.

Ma intreb daca se vor posta pe site-ul [url=http://www.cnih.ro]CN "Iulia Hasdeu"[/url], cum au facut si cu faza pe sector :maybe: Daca pana maine pe la pranz nu apar pe net, o sa ma duc acolo...

[quote="maky"]
edit : in legatura cu link`ul prezentat mai sus, prefer sa am reactia "no comment". eventual poate primesc o cutie noua de vopsea drept cadou  :maybe:[/quote]

 :D

[quote="mychrom"][quote="spix"][quote]http://forum.portal.edu.ro/index.php?showtopic=42605 [/quote]

Cea mai tare discutie de forum pe care am vazut-o, ma amuza de fiecare data cand o citesc  :play_ball:[/quote]

mai e una haioasa, cu "fraude in olimpiada de matematica" sau ceva de genu' asta.[/quote]
este cu adevarat amuzanta dar as prefera sa nu fie deloc.Cei neavizati care intra pe acel forum pot crede ca acele lucruri sunt adevarate si imaginea unor oameni de valoare si a olimpiadei in general va avea de suferit.

on-topic: mai are cineva rezultate de la alte judete? ce asteptari aveti de la ON din acest an?

exista o pozitie oficiala a factorilor de decizie cu privire la elevii calificati la onm 2007?

Pot sa va spun ceva rezultate din Satu Mare :
a X-a: Tataran Alexandru 21p
a XI-a: eu 26p
a XII-a: Gavrus Cristian 26p
            Marginean Vlad 17p
ma astept ca subiectele de la ONM sa fie mult mai dificile,in special la anliza, la judeteana s-au dat doar siruri.

Sabin , nu sti cumva ce punctaj a avut loc I la a IX-a din Satu Mare ?

sunt curios de rezultatele din slatina/olt de la clasa a 8a, daca poate sa le puna cineva, primele locuri. [maky stie dc  :D ]

la a IX-a parca a castigat andra cu 20-21.

La a 9a locu 1 9p   :blush:  dar nu m-as mira sa il duca la ONM ,n-ar fi prima oara  :P

nu va mai agitati atata....:)....lasati oricum antionala anu asta e in vacantza....cand is apstele..asha ca mai bine mergeti la stropit..:)).....oricum abia astept si eu sa ajung al pitesti sal vizitez...ca nam fost inca..:D.....

nationala a fost mereu in vacantza....
oricum.. si eu abia astept sa ajung la piteshti(in sf nu mai zic ploieshti) \:D/


Bonjour,

je suis à la recherche d'un plugin pour ajouter Asymptote sur un forum et un wiki.

Le wiki n'est pas du même type que AoPSWiki... mais je me dis que je saurais peut-être adapter le code qui est utilisé sur AoPSWiki...

donc si quelqu'un le connait... et s'il consent à partager ce savoir précieux, je le remercie d'avance.

Gaétan M.

Pour commencer à utiliser Asymptote, vous devez d'abord télécharger et l'installer. Pour afficher les images au format eps que vous produisez, vous aurez également besoin de télécharger une visionneuse eps comme GSview. (GSview est très pratique car il permet d'afficher les fichiers EPS et PDF, et avec Ghostscript, Asymptote pouvez facilement imprimer les images au format pdf ainsi.)
[modifier] Asymptote

      Pour télécharger et installer Asymptote sur votre machine Windows:
Aller à la FileCluster et cliquez sur le Miroir 1 Lien externe à droite. Cela vous amènera à SourceForge, qui vous aidera à télécharger asymptote-2.15-setup.exe.
Une fois le téléchargement terminé, accédez à D: \ downloads \ Asymptote, ou partout où vous avez enregistré le fichier, puis double-cliquez sur le fichier exe (asymptote-2.15-setup.exe).. Cela va ouvrir une fenêtre de l'installateur, où vous pouvez choisir le dossier dans lequel sera installé Asymptote (ou simplement utiliser la valeur par défaut C: \ Program Files Asymptote \), puis choisissez si vous souhaitez avoir des raccourcis ajoutés sur le bureau et le menu Démarrer. Lorsque vous avez terminé, cliquez sur Installer.
Asymptote est prêt à démarrer la production d'images, mais vous avez encore besoin d'un moyen de voir ces images. (REMARQUE:.. Si vous avez déjà un visualiseur capable d'afficher les fichiers EPS et PDF, vous n'avez pas besoin de télécharger le fichier ci-dessous.)

Ceci est l'edition anglais. Je regrette, mais mon français n'est pas très bon. En haut est l'edition de Google Translate. J'espère que ça t'aide.

     To begin using Asymptote, you must first download and install it. To view the eps-format images you produce, you will also need to download an eps viewer such as GSview. (GSview is convenient because it can display both eps and pdf files, and with GhostScript installed, Asymptote can easily output the images in pdf format as well.)
[edit] Asymptote

     To download and install Asymptote on your Windows machine:
Go to FileCluster and click on the External Mirror 1 link on the right. This will bring you to SourceForge, which will help you download asymptote-2.15-setup.exe.
When the download is complete, browse to D:\downloads\Asymptote, or wherever you saved the file, and double-click on the .exe file (asymptote-2.15-setup.exe). This will open an installer window, where you can choose the folder that Asymptote will be installed to (or simply use the default C:\Program Files\Asymptote), and choose whether you wish to have shortcuts added to the desktop and start menu. When you have finished, click Install.
Asymptote is ready to start producing images, but you still need a way to view these images. (NOTE: if you already have a previewer capable of viewing .eps and .pdf files, you do not need to download the file below.)

Aussi, tu dois télécharger "GSView" d'ici: http://downloads.ghostscript.com/public/gs907w32.exe
Le plugin est d'ici: http://iweb.dl.sourceforge.net/project/asymptote/2.21/asymptote-2.21-setup.exe


Find the total number of different integer values the function \[f(x) = \lfloor x\rfloor+\lfloor 2x\rfloor+\left\lfloor \frac{5x}{3}\right\rfloor+\lfloor 3x\rfloor+\lfloor 4x\rfloor\] takes for real numbers $x$ with $0 \leq x \leq 100$.

The link doesn't work...can you post the solution?


function
modular arithmetic
algebra unsolved
algebra

Determine all functions $ f$ mapping the set of positive integers to the set of non-negative integers satisfying the following conditions:
(1) $ f(mn) \equal{} f(m)\plus{}f(n)$,
(2) $ f(2008) \equal{} 0$, and
(3) $ f(n) \equal{} 0$ for all $ n \equiv 39\pmod {2008}$.

[quote="April"]Determine all functions $ f$ mapping the set of positive integers to the set of non-negative integers satisfying the following conditions:
(1) $ f(mn) \equal{} f(m) \plus{} f(n)$,
(2) $ f(2008) \equal{} 0$, and
(3) $ f(n) \equal{} 0$ for all $ n \equiv 39\pmod {2008}$.[/quote]

$ f(n) \ge 0$ for all $ n$ then if $ 2008 \equal{} mn$ then $ 0 \equal{} f(2008) \equal{} f(n) \plus{} f(m)$ then $ f(n) \equal{} 0$ for any divisor of $ 2008$

$ (m,2008) \equal{} 1$ then exists $ a$ such $ am \equiv 1 \pmod {2008}$ then
for $ n \equal{} 39a$ we have $ nm \equiv 39 \pmod {2008}$ then
$ 0 \equal{} f(nm) \equal{} f(n) \plus{} f(m)$ then $ f(m) \equal{} 0$ for any integer $ m$ coprime with $ 2008$

If $ (m,2008) \equal{} d$ then $ m \equal{} da$, $ (a,2008) \equal{} 1$ and $ d|2008$
$ f(m) \equal{} f(da) \equal{} f(d) \plus{} f(a) \equal{} 0 \plus{} 0 \equal{} 0$
then $ f(n) \equal{} 0$ for all $ n$

Same argument for any natural number instead of $ 2008$ and for any nonzero instead of $ 39$.

Consider a prime $p$ such that $(p,2008)=1$
Now consider the set $2008k+39$ such that $0\leq k\leq (p-1)$
By php we'll get $p$ divides one of them that implies $f(p)=0$
Now as $f(2008)=0$ so $f(p)=0$ for all prime $p$.
Now easily we can see $f(n)=0$ for all $n$.


function
limit
real analysis
real analysis unsolved

f and g are two periodic functions, and $ \lim_{x\to \plus{} \infty}[f(x) \minus{} g(x)] \equal{} 0$. Prove: f=g.

Proof. Let f's period is $ T_1$, g's $ T_2$. Let $ T_1,T_2 > 0$, then for definite $ x$, we have
$ f(x) \minus{} g(x) \equal{} \lim_{x\to \plus{} \infty}[f(x) \minus{} g(x)]$
$ \equal{} \lim_{n\to \plus{} \infty}\{[f(x \plus{} n T_1) \minus{} g(x \plus{} n T_1)]$
$ \plus{} [g(x \plus{} nT_1 \plus{} nT_2) \minus{} f(x \plus{} nT_1 \plus{} nT_2)]$
$ \plus{} [f(x \plus{} nT_2) \minus{} g(x \plus{} nT_2)]\}$
$ \equal{} 0 \plus{} 0 \plus{} 0 \equal{} 0.$

So , for $ \forall x$, we have $ f(x) \equal{} g(x)$.

Question: why here we can make $ f(x) \minus{} g(x) \equal{} \lim_{x\to \plus{} \infty}[f(x) \minus{} g(x)]$? thanks

[quote="zhoraster"][quote="water2011"]
 $ \lim_{n\to \plus{} \infty}[f(x) \minus{} g(x)] \equal{} 0$
[/quote]
It should read $ \lim_{\mathbf{x}\to \plus{} \infty}[f(x) \minus{} g(x)] \equal{} 0$, otherwise there's nothing to prove.
[quote]
Question: why here we can make $ f(x) \minus{} g(x) \equal{} \lim_{n\to \plus{} \infty}[f(x) \minus{} g(x)]$? thanks[/quote]
Why can we write $ \lim_{n\to\infty} c \equal{} c$, where $ c$ is a constant?[/quote]

It is my typo. I have modified it . Thanks


This expression is OK in the Forum, but when I try to make it into a PDF via TeXnicCentre, it becomes mess. I don't know how to fix it...... Can anyone help me with it?
$ x_{i}^{k}= \begin{cases}0,\text{if}~x_{i}^{(k-1)}=x_{i+1}^{(k)},i=1,2,\cdots,n \\ 1 ,\text{if}~x_{i}^{(k-1)}\neq x_{i+1}^{(k)},i=1,2,\cdots,n \end{cases}$

I had the same problem with equation erray.

Put it in the Center exactly like this:

\$ x_{i}^{k}=
\begin{cases}0,\text{if}~x_{i}^{(k-1)}=x_{i+1}^{(k)},i=1,2,\cdots,n \\
1 ,\text{if}~x_{i}^{(k-1)}\neq x_{i+1}^{(k)},i=1,2,\cdots,n
\end{cases} \$

Where \$=dollar sign

I have done what you said, but it still doesn't work...... :maybe:

Eh? I put it in TeXnicCenter, it comes out fine...  :huh:  :maybe:

[quote="stevem"]The cases environment only works if you load the amsmath package. This package is loaded on this forum which is why it works here.[/quote]
Thanks for the information. But where can I find the Amsmath Package? It is not in the LaTeX Packeges Manager.... ...

Edit: I have fixed it. Thanks for all the help above!


Only if you buy the solutions manual. You could also ask it on the forum, where people will help you.

[quote="Lilac"][size=150]Does anyone know where to find solutions for the problems in here:[/size]

[u]http://www.artofproblemsolving.com/Books/Excerpts.pdf[/u]?

I'm having a bit of trouble (esp. with the harder problems) and would appreciate if anyone knows where to find the solutions...[/quote]
Just so you know, there are hints in the back of the book too.
and as izzy mentioned, the solutions manual. But don't use that all of the time

Thanks for the help, everybody...I'll probably buy the Intro to Probability book.

Sorry about being downright clueless ;)


function
calculus
derivative
real analysis
integration
real analysis unsolved

Hi,

I'm wondering if there exists a continuous fonction f:[0,1]->R such that

$ |f(x)\minus{}f(y)| \geq  |x\minus{}y|^{1/2}$

thanks

Note that such a function would have to be nowhere differentiable.

Brownian motion displays this behavior on average, but not as a worst case.

In fact, as a worst case - you can't do this. There is no such function.

Step 1: Such an $ f$ would have to be monotone. If it were not, then (by the IVT) there would be points $ x\ne y$ such that $ f(x)\equal{}f(y),$ which would violate the hypothesis.

Step 2. WLOG, assume that $ f$ is increasing.

$ f(1)\minus{}f(0)\equal{}\sum_{k\equal{}1}^n\left[f\left(\frac kn\right)\minus{}f\left(\frac{k\minus{}1}n\right)\right]\ge\sum_{k\equal{}1}^n\sqrt{\frac1n}\equal{}\sqrt{n}.$

That cannot hold as $ n\to\infty,$ so we cannot construct such a function.

Aclually, such function does not exist for every $ \alpha<1$. There is very beautiful rezult by Lebesque that every monotone function is differentiable a.e. This gives a contradiction( with Kent's observation) :)

The concrete estimation I gave - the telescoping sum on a partition - would work in the same way for any $ \alpha<1,$ giving rise to the estimate $ f(1)\minus{}f(0)\ge n^{1\minus{}\alpha}.$ But leshik's observation - that monotone functions can't be nowhere differentiable - is also a good point.

Thanks for the solution.

And now, do you think there's a continous fonction $ f : R\minus{}> R^2$ such that

$ \parallel{}f(x)\minus{}f(y)\parallel{} \geq \sqrt{|x\minus{}y|}$

?

[quote="leshik"]There is very beautiful rezult by Lebesque that every monotone function is differentiable a.e.[/quote]
leshik refers to the [url=http://en.wikipedia.org/wiki/Lebesgue_differentiation_theorem]Lebesgue Differentiation Theorem[/url], which helps with the Lebesgue integral analogue to the Fundamental Theorem of Calculus.

you can drop the assumption that $ f$ is continuous, and this is still a good exercice. It has already been discussed on the forum ...

Are you speaking about the continuous function $ f: R \rightarrow R^2$ such that
\[ \parallel{}f(x) \minus{} f(y)\parallel{} \geq \sqrt {|x \minus{} y|}\]
where $ \parallel{}\cdot\parallel{}$ is a norm on $ R^2$
?

Where has it been discussed on the forum ?

thanks


A group consist of $ n$ tourists. Among  every $ 3$ of them there are $ 2$ of which are not familiar.For every partition of the tourists in 2 buses,you can find  2 tourists that are in the same bus and are familiar with each other.Prove that a tourist familiar to at most $ \frac{2n}{5}$ tourists.

[hide="An idea"]Turn this into a graph.  Let each tourist be represented by a vertex, and let two vertices be connected by an edge if and only if their respective tourists are familiar.

The first condition is equivalent to saying that there are no cycles of length 3.

The second condition is equivalent to saying that the graph is nonbipartite.  This is equivalent to saying there's a cycle of odd length.

So there exists a cycle of odd length greater than or equal to 5.[/hide]

I don't know if this helps though...

[hide="Ignore this"]It's false.  Consider a graph whose vertices are $ a, b, c, d, e, a_{1}, a_{2},\ldots, a_{n\minus{}5}$ such that we have edges $ \{a,b\},\{b,c\},\{c,d\},\{d,e\},\{e,a\}$ and $ \{a,a_{i}\}$ for all $ i$.  This graph has no triangles and is not bipartite, but $ \deg(a) \equal{} n\minus{}3$ which certainly can be larger than $ \frac{2n}{5}$ for large enough $ n$.

One alternative possible statement is that the [i]average[/i] vertex can't have degree larger than $ \frac{2n}{5}$.  Then this is a Turan-type result.[/hide]

Wait, I've misunderstood the question: we almost certainly are supposed to prove that there exists a tourist who knows at most $ \frac{2n}{5}$ tourists.  Or, in other words, show that a graph in which every vertex has degree greater than $ \frac{2n}{5}$ either contains a triangle or is bipartite.

This was an interesting problem.  Suppose the opposite, i.e., lets assume that the degree of every vertex is more than $ \frac{2n}{5}$.  Because $ G$ is bipartite, like K81o7 said, it must contain a cycle of odd length.  Let $ C_{2k\plus{}1}$ be the cycle of minimial length.  We know $ k\ge 2$ because $ G$ is triangle-free, and now I will make an argument by contradiction with this odd cycle.

Suppose that the smallest odd cycle has length greater than or equal to $ 5$.  Let the vertices of $ C$ be $ \{v_{1},v_{2},\dots, v_{2k\plus{}1}\}$ where $ v_{i}$ is connected to $ v_{i\plus{}1}$ (cyclic notation is used).  Notice that if we consider the induced subgraph of the vertices of $ C$, no edges besides the $ 2k\plus{}1$ explained above can exist, since this would yield a smaller odd cycle.  Now, because the length of the cycle is at least $ 5$ and each vertex is connected to exactly two others, each vertex in the cycle must be connected to more than $ \frac{2}{5}$ of the vertices outside the cycle.  Because of this fact and the fact that $ G$ cannot contain any triangles, it is easy to see that $ v_{i}$ and $ v_{i\plus{}2}$ must both be connected to more than one-fifth of the vertices outside the cycle.  But because the cycle is at least length $ 5$, we know that there at least $ 5$ of these pairs $ (v_{i}, v_{i\plus{}2})$, and thus there are two pairs of vertices in the cycle $ (v_{i}, v_{i\plus{}2})$ and $ (v_{j},v_{j\plus{}2})$ that are all connected to some point $ x\in V$ outside the cycle.  This leaves three different cases:

Case I: $ v_{i}, v_{i\plus{}1}, v_{i\plus{}2}, v_{i\plus{}3}$ are all connected to $ x$.

The fact that this is a contradiction is trivial, since there are $ 3$ triangles admitted.

Case II: $ v_{i}, v_{i\plus{}2}, v_{i\plus{}4}$ are all connected to $ x$.

In this instance simply consider the new cycle $ v_{i}, x, v_{i\plus{}4},\dots, v_{i\minus{}1}$.  This is still an odd cycle, and yet it is shorter in length by $ 2$.  But since $ C$ was the shortest odd cycle, we have a contradiction.

Case III: $ v_{i}, v_{i\plus{}2}, v_{i\plus{}j\plus{}2}, v_{i\plus{}j\plus{}4}$ are all connected to $ x$.

In this last and final case, we know that either the length from $ v_{i}$ to $ v_{i\plus{}j\plus{}4}$ or the length from $ v_{i\plus{}2}$ to $ v_{i\plus{}j\plus{}2}$ must be odd.  Then we simply join $ x$ and create a new odd cycle like in Case II, arriving at a contradiction.

Hence, repeating the above argument, we either arrive at a graph with a triangle, or we simply receive an odd cycle of smaller length.  Either way, once we obtain an odd cycle of length $ 5$, either Case I or Case II must occur, and this will produce a triangle, which is the desired contradiction.  Hence we are finished.

It is worth noting that this result is best possible, for if we suppose $ n\equal{}5k$, then consider the $ k$ disjoint 5-cycles $ P_{1},P_{2},\dots, P_{k}$ such that $ P_{i}\equal{}\{v_{i,1}, v_{i,2},\dots, v_{i,5}\}$.  Then if the only edges in this graph are the ones in the cycles (i.e. $ v_{i,j}$ is connected to $ v_{i,j\plus{}1}$) and the edges between $ v_{i,j}$ and $ v_{k,j\pm 1}$, then each vertex will have degree $ 2k$, the graph will triangle-free and not be bipartite.

This problem implores a greater generalization:  Given a graph $ G$ that is not $ k$-partite and does not contain a $ m$-clique, what is the greatest degree that the smallest vertex of all possible graphs can have?

[quote="zgorkster"]This problem implores a greater generalization:  Given a graph $ G$ that is not $ k$-partite and does not contain a $ m$-clique, what is the greatest degree that the smallest vertex of all possible graphs can have?[/quote]

"Has girth $ m$" (i.e., does not contain any cycles of size smaller than $ m$) seems to me the more natural generalization.  I suspect asymptotic results for this type of question are known.


algorithm
search
geometry
function
analytic geometry
email

This thread is for discussion of the USACO November 2006 contest. Discuss results, algorithms, etc., and perhaps we can compile solutions for all $9$ problems while we're waiting on the analysis. I've managed to get together solutions for the gold problems from the USACO discussion forum, but I don't have any silver or bronze solutions yet, so they would be much appreciated (or expansions on the gold solutions would also be cool).

[hide="block"]
At each node, keep track of the two shortest distances to that node found so far. Then proceed with a Dijkstra-like algorithm in which you expand the closest unexpanded node so far (or if the second-shortest path to an already expanded node is the minimal distance, expand that one provided you haven't already). A heap is necessary to run within the time limits.
[/hide]
[hide="cowfood"]
There are two solutions, you can either just do a straight-up memoization where you recurse to the right, and this is, though slightly counterintuitively, pretty fast because the number of possible configurations is actually bounded above by like either the 12th Fibonacci or Tribonacci number, so the state space for memoization is rather small. However, it is a bit difficult to code because you need a bitmask of size 144 to memoize.

The second solution involves using a bitmask of the previous row, and constructing a dynamic programming algorithm with that as the state, and you can use various bit-trickery to make it fairly easy to code.
[/hide]
[hide="plank"]
Instead of cutting apart a board, merge the target planks together until you are left with the original board (then merging boards of length $a$ and $b$ costs $a+b$). Merge the two smallest, and repeat until there is only one left. A heap lets you get O(NlogN).
[/hide]
[hide="badhair"]We need a solution for this one still.[/hide] *solution needed*

[hide="bigsq"]We need a solution for this one still.[/hide] *solution needed*

[hide="rndnum"]We need a solution for this one still.[/hide] *solution needed*

[hide="brand3"]We need a solution for this one still.[/hide] *solution needed*

[hide="scrbl"]
All we need is a way of comparing the input rack with a given word from the dictionary. The easiest way is to sort the input letters (not including #s, but we need to know how many there are), and sort each dictionary word as we read it. Start by looking at the first characters A and B (input/dictionary respectively). If B matches A, go forward in both words; if B>A go forward in the first word; if B<A then we use up one wildcard, and go forward in the second word. Then we just need to check if we used too many wildcards or not.
[/hide]
Thanks to TripleM for this solution!

[hide="cowtag"]We need a solution for this one still.[/hide] *solution needed*

scrbl:
[hide]All we need is a way of comparing the input rack with a given word from the dictionary. The easiest way is to sort the input letters (not including #s, but we need to know how many there are), and sort each dictionary word as we read it. Start by looking at the first characters A and B (input/dictionary respectively). If B matches A, go forward in both words; if B>A go forward in the first word; if B<A then we use up one wildcard, and go forward in the second word. Then we just need to check if we used too many wildcards or not.[/hide]

My result:
[code]
block       *  *  *  *  *  *  *  *  *  t
cowfood     *  *  *  *  *  *  *  *  *  *
plank       *  *  *  *  *  *  *  *  *  *
[/code]

What about you?

I didn't participate, which is why I'm doing them all now ;)
cowtag:
[hide]This is just a simple simulation, since 1000^2 is easily small enough. Start with all cows unseen; step through the cows one at a time (looping back to 1 etc), find the closest unseen cow, and mark it as seen. The last unseen cow is the winner.[/hide]
badhair:
[hide]Start off with an empty list which will represent the longest decreasing subsequence found so far. Read the input one by one - while the end of our list is <= our next value, remove it. Now the size of the list is the number of cows who can see the current cow, so add that to the total, put this current value on the end of the list, and repeat. This works fast enough as it is since the size of the list cannot get too big; you could possibly speed it up a little by doing a binary search for where the next value should go if you really wanted.[/hide]
bigsq:
[hide]A brute force should work, with a tiny bit of pruning. Loop over all possible pairs of Js in the grid. Assume those are two adjacent vertices of a square, and check whether there are either two Js or a J and a * in the other two corners. If so, update the best square found so far.
That would time out, because there could be up to 10000*10000 pairs of Js, approximately. However, with any large number of Js, you are going to have lots of squares. So, suppose the first J in a pair is at (a,b). Rather than search the whole grid for another J, only look at locations which are far enough away to provide a bigger square. Thus something like:
[code]for a from 1 to n
for b from 1 to n
for c from 1 to n {
    for d = 1; while (a-b)*(a-b)+(c-d)*(c-d)<bestarea and d<=n; d++) {
        test();
    }
    for d = n; while (a-b)*(a-b)+(c-d)*(c-d)<bestarea and d>0; d--) {
        test();
    }
}[/code]
That works in 0.2 seconds on the worst test case for me.[/hide]
rndnum:
[hide]Let f(n,x) be how many numbers from 1 to n have x more zeroes than ones. Split those numbers into three groups: {1},{even numbers},{odd numbers}. Those last two groups can be calculated recursively by taking off the last digit and accounting for that with the 'x'. That gives us the recurrence f(n,x) = f([n/2],x-1) + f([(n-1)/2],x+1) + (1 more if x is -1). Since there aren't too many values for x (somewhere between -31 and 31 at worst) and there will only be approximately a logarithmic number of 'n's, we can do this with memoization, storing previous results in a map. You can then calculate the answer as (sum for x>=0 f(end,x)) - (sum for x>=0 f(start-1,x)).That gives me a worst case of 0.008s in C++.[/hide]

badhair

[hide]
Another way of phrasing this problem is: for each cow, find the number of cows that can see it.

Now, process the cows in order, and keep a stack of cows that still have the potential to see other cows (in other words, a stack of cows whose lines of vision haven't been blocked by a taller cow yet).

If the cow you are processing is shorter than the cow on top of the stack, push the current cow on to the stack.
Otherwise, if it's taller or equal, pop off cows until the current cow shortest than the cow on top of the stack. For each cow you pop off, add the size of the stack to the total, because the size of the stack represents the number of cows that can see the cow you just popped off.
[/hide]

I've edited in solutions to all silver problems above. That just leaves me with one bronze which is stumping me for some reason..

brand3 is stumping me too. I can't get the last three test cases done under a second and can't think of a better way to do it other than recursively going through the possibilities.

Well, I may have only gotten gotten half the test cases for badhair, but my solution was only one line off from being perfect (makes me sad :()

[hide="here is the outline of the solution that is similar to the analysis now up"]

First, keep an array of the heights and a boolean array of which cows can currently see. Also keep a number keeping track of how many can see so you don't have to count the array every time.

Loop through the cows. If a cow is the first cow or shorter than the previous cow, then do nothing, add the number of cows that can see to the sum, then toggle the cow's position in the array because it can now see (also add one to the number seeing).

If a cow is taller than the previous cow, loop back through the cows until you find one that is taller than the current cow, decrease the number seeing by the number of cows that were blocked and add the number of cows that can still see, then the current cow becomes seeing and the number is incremented.

If a cow is the same height as the previous cow, then only the previous cow stops seeing, so toggle that and add the number remaining (adding the number was the one line I missed), then add the current cow to the number seeing and the array.

When you finish the loop, your sum will be the sum requested (the sum of the number of cows the ith cow can see is the same as the sum of the number of cows that can see the ith cow).

Also, if you wish:
[hide="full fixed java code of badhair solution outlined above"]
It's slightly less compact than the one in the analysis but it works
[code]
import java.io.*;
import java.util.*;

class badhair {
	public static void main(String[] args) throws IOException {
		BufferedReader f = new BufferedReader(new FileReader("badhair.in"));
		int N = Integer.parseInt(f.readLine());
		int[] heights = new int[N];
		int working = 0;
		boolean[] work = new boolean[N];
		for(int i = 0; i<N; i++){
			heights[i]=Integer.parseInt(f.readLine());
		}
		int[] num = new int[N];
		long sum = 0;
		work[0] = true;
		working = 1;
		for(int i = 1; i<N; i++){
			if(heights[i]<heights[i-1]){
				sum+=working;
			} else {
				if(heights[i]==heights[i-1]){
					work[i-1]=false;
					working--;
					sum+=working;
				} else {
					for(int j = i-1; j>-1; j--){
						if(heights[j]<=heights[i]){
							if(work[j]){
							 	working--;
								work[j]=false;
							}
						} else {
							sum+=working;
							break;
						}
					}
				}
			}
			working++;
			work[i]=true;
		}
		PrintWriter out = new PrintWriter("badhair.out");
		out.println(sum);
		out.close();
	}
}
[/code]

[/hide]
[/hide]

[quote="TripleM"]Ah. Well, I just tried it and it passes in 0.916 in C++. So I guess theres no smarter way of doing it (I assumed 22 million was a bit large..)
Thus:
brand3:
[hide]If you use java, give up. Otherwise, just recursively run through all possibilities and stop once you've hit the last one you need.[/hide][/quote]

remember that java gets 2x the runtime

As for bigsq, my current solution (fixed to prevent wrong answers and bad exit statuses giving me only 6 test cases) is looping through all the Js ignoring pairs that can't give smaller areas, but on something like an 80x80 square filled with Js and one empty slot, you're not going to finish in time. Interesting that bigsq is the only one of the nine problems without an analysis up.

also: my results
[code]
            1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
badhair     *  *  *  *  x  x  x  *  x  x
bigsq       *  *  x  e  *  *  e  e  e  *  *  e  e  e  e
rndnum      *  x  x  x  x  t  t  t  t  t

[/code]

My five missed badhairs were because of the missing line I explained above (they had consecutive cows with the same height). The wrong answer on bigsq was because my program said OOH! you can go 9 up and 1 right from this J to another J and 9 left and 1 down from the same J to another J! That's a right angle! (draw it and you see it isn't). The bad exit statuses are array out of bounds, mostly - possibly a string index out of bounds which means I essentially didn't include the upper bounds of x<N and y<N in the answer I submitted (but interestingly I found that the checks were in the program on my computer and I stopped editing them 20+ minutes before the end of my 3 hours). With my edited programs I get all 10 on badhair and miss 5 on bigsq due to time.

Weird formatting....when I edited in my code it hid everything. Anyone got a guess as to why it happened?

[quote="TripleM"][quote="Hamster1800"]
remember that java gets 2x the runtime[/quote]
Yeah, but the input/output will most likely be far too slow (anything that comes close to running out of time in C++ in the training problems is guaranteed to run out of time in java even with a longer time limit; believe me, I know.)

[quote]As for bigsq, my current solution (fixed to prevent wrong answers and bad exit statuses giving me only 6 test cases) is looping through all the Js ignoring pairs that can't give smaller areas, but on something like an 80x80 square filled with Js and one empty slot, you're not going to finish in time. Interesting that bigsq is the only one of the nine problems without an analysis up.[/quote]
My program solves an 80x80 square with one empty slot instantly (0.03 seconds or so), so I guess it depends on your implementation.
Heres mine, if you want to see it:
[hide][code]
#include <fstream>
using namespace std;
char grid[100][100];
int N;
int type(int i, int j) {
    if (i<0 || j<0 || i>=N || j>=N || grid[i][j]=='B') return -1;
    if (grid[i][j]=='*') return 0;
    return 1;
}
int main() {
    ofstream fout ("bigsq.out");
    ifstream fin ("bigsq.in");
    fin >> N;
    for (int i=0; i<N; i++)
    for (int j=0; j<N; j++) fin >> grid[i][j];
    int best = 0;
    for (int i=0; i<N; i++)
    for (int j=0; j<N; j++) {
        if (grid[i][j]!='J') continue;
        for (int k=0; k<N; k++) {
            for (int l=0; (k-i)*(k-i)+(j-l)*(j-l)>best && l<N; l++) {
                if (grid[k][l]!='J') continue;
                int x = type(i+j-l,j+k-i);
                int y = type(j+k-l,l+k-i);
                if (x!=-1 && y!=-1 && (x==1 || y==1)) {
                    best>?=(k-i)*(k-i)+(l-j)*(l-j);
                }
            }
            for (int l=N-1; (k-i)*(k-i)+(j-l)*(j-l)>best && l>=0; l--) {
                if (grid[k][l]!='J') continue;
                int x = type(i+j-l,j+k-i);
                int y = type(j+k-l,l+k-i);
                if (x!=-1 && y!=-1 && (x==1 || y==1)) {
                    best>?=(k-i)*(k-i)+(l-j)*(l-j);
                }
            }

        }
    }
    fout << best << endl;
    return 0;
}[/code][/hide][/quote]

I'm not quite perfect at reading C++ code, but as I see it, you're looping through the points rather than the Js as I did, so when you get to (0,0) and (80,0), your program essentially terminates. Is this correct? Also, since you're looping through the points. What would be the worst case scenario? the bottom right three being Js and nothing else?

Also, could you explain the function of >?= please? I couldn't find it in a web search and it was used in the solution to the hungry cows (OCT06) problem, which I want to know how to do.

Lastly, the brand3 analysis was in java. So obviously if you're working in java, don't give up ;)

[quote="syboy"]hi
can i go to silver division with this result?
            1  2  3  4  5  6  7  8  9 10
brand3       *  *  *  *  *  *  *  *  t  t
cowtag      *  *  *  *  *  *  *  *  *  *
scrbl          *  *  *  *  *  *  *  *  *  *
if i can , how i do it?
 :?:[/quote]

You will probably automatically be invited. I think you get an email about it, but then in the next competition you will have access to the Silver problems instead.

syboy: You will either get an e-mail, or be listed in the results as being allowed to move up to silver or something. If you don't get any e-mail, but the contest results seem to indicate that you should be in silver, just send an e-mail to the Head Coach (Rob Kolstad), making sure to put USACO in the header, and he will probably take care of it. Your score is almost certainly high enough to move up to silver.

As for the >?= operator, as mentioned, a>?=b basically sets a to be the max of a and b, and a<?=b sets it to be the min of the two. It's deprecated but still commonly used because it is easier to type than writing out the min function. I think it is a deprecated form of the turnary operator a=a>b?a:b; which isn't nearly as convenient to type.

mahbub: What country are you from?

Did anyone actually code up the heap for the blocks problem?

[quote="TripleM"]I am looping through the Js. Let me add a few comments:
[code]    for (int i=0; i<N; i++)
    for (int j=0; j<N; j++) {
        if (grid[i][j]!='J') continue;
[/code]
This loops through all points (i,j) which contain a J.
[code]      for (int k=0; k<N; k++) {[/code]
For each x coordinate of the next point:
[code]
            for (int l=0; (k-i)*(k-i)+(j-l)*(j-l)>best && l<N; l++) {[/code]Start looking at the y coordinates from 0 upwards which are far enough away
[code]                if (grid[k][l]!='J') continue;[/code]And make sure its actually a J.

We then do the same thing for y coordinates on the 'other' side (starting at N-1 and going backwards). This means we skip out looking at all the points in the middle which are too close.

Thus, in pseudocode; for every J, and every other J which is far enough away, check to see if those two help form a square.

Oh, and as for >?=, its some deprecated operator that probably isn't meant to be used, but I like it. a >? b returns the maximum of a and b, so a >?= b is just like saying a = max(a,b).[/quote]

Ah. There's the difference. We're both looping through the Js, but you loop through the Js much more efficiently (I kept an array of the J positions and looped through that in a very slow manner whereas you go through each point checking if it's a J). I really don't feel like coding a new solution from scratch, but I might port your code to java sometime to see if it runs in time. Also, thanks for explaining what >?= does.

Syboy: I've got the same opinion as everyone else. With only missing two test cases, you probably have a good chance of being invited to silver. If you really want to be invited and aren't, then send an email asking.

[quote="JSteinhardt"]
mahbub: What country are you from?
[/quote]

I am from Bangladesh. Small country in south Asia.

[quote="JSteinhardt"]
Did anyone actually code up the heap for the blocks problem?
[/quote]

In STL there is priority queue. but it works as max heap. but in problem we need min heap. so i inserted the number a as -a. and when popping, i just negated it  :lol:  So we actually dont need to implement heap if u r using C++.

That is a clever way to use the C++ heap. I am curious, though, as to why the solution times out even with a heap. Can you explain?

may be there is some mistake in your code.

you know, STL priority queue is much slower than self implimented heap. as STL heap got AC so implemented heap also should get AC.

I missed the qualification round.. so i had to start from bronze.. i submitted 2 and got all ok. but brand3 really hurt me, statement told that it can be upto 22,000,000 ; and i thought.. wow.. may be i need to use dp to find the first element to print... and i just left the contest right then.. in analysis mode, i wrote a simple backtracking with little pruning and that gets all tests okay, and the max was not 22,000,000 the max was 12,000,000 .. I was really heart broken... I still am heart broken...

And you know the funny thing about cowtag.. if you write a nice soln with linked list - okay - you'll get all test case okay.. even if you write a nasty for loop ( 0..n )continuous going until there is nothing left, it will also get all test case okay..  :(

The basic rule is: if its bronze, there must be an 'easy' solution ;) I did exactly the same with brand3 for a while, but then realised everything I was trying was far too hard for bronze; lets try brute force.

Be careful with that though, while usually this is true, if you are worried about the time limit you might want to at least optimize a little and write tight inner loops.

Also, I recall at least three times when a bronze problem was dynamic programming.

I didn't do the qualification round either, so I also had to start with bronze. Unfortunately I had to leave in the middle of the contest, but I probably wasn't going to do good on it anyway, probably because I just started learning Java the few days before the contest (I don't normally use any of the languages you have to submit USACO answers in :() and also because I got confused on brand3, trying to figure out how to do an unknown number of nested for loops. Eventually I just did some weird recursion thing...

Yeah recursion would be the idea.

Or you can be like McCutchen and use templates.

But that requires C++.

Then again C++ is far better than JAVA.


For an even positive integer $n$, let $S$ denote the set of natural numbers $a$, $1<a<n$ for which $a^{a-1}-1$ is divisible by $n$. If $S=\{n-1\}$, prove that $n=2p$ for some prime number $p$.


While watching a parade I saw some clowns and horses. I counted
30 legs and 10 heads. How many horses did I see in the parade?

clowns:$ x$
horses:$ y$

$ \left\{\begin{array}{l}
x\plus{}y\equal{}10 \\
2x\plus{}4y\equal{}30
\end{array}\right.
\iff
\left\{\begin{array}{l}
x\equal{}5 \\
y\equal{}5
\end{array}\right.$

Thus, $ \boxed{5}$　horses.

Or, assume that it is all clowns.  Then there are $ 20$ legs.  We need to substitute horses for clowns and each substitution adds $ 2$ legs, so $ \frac{10}{2}\equal{}\boxed{5}$.


um...why is that in this forum?  :maybe:

[quote="tcjy"]okay, so this is how to write in color:
the code is (b)(color=some sort of color wether its darkred, blue, or yellow) typing (/color)(/b) and change the ()s to []'s
it looks like this: [b][color=blue]Hi[/color][/b][/quote]

or the alternative is to highlight the text and click the bolded B next to the thing that says Message body and then rehighlight it and scroll down on the Font colour thingy. saves you a heck of a lotta typing :dry:

[quote="tcjy"]I was not sure where to put it :D so I chose the fun factory. After all, if you're not sure where to put it, put it in the fun factory :rotfl:[/quote]

LOL. true dat XD


See [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?p=961590#961590]this[/url].

You guys are now the home team.

Let's see if it helps or hurts! I'll miss the bus ride to Penn State for the team building aspect of it. And I'll miss the Creamery! :-)

Tom

O_O oh no!!!! is this for real? that would mean that about 95% of the ARML traditions are going down the drain. although it should make things more.....interesting.

what arml traditions are there? sit in a hot, musty, uncomfortable plane for 4 hours >?

Actually, for us, it's riding a bus for about a day to Penn State.  Also, there's a "traditional" visit to a certain small food court in the middle of nowhere along the way, where most Georgia ARML members are fond of sending pennies by the hundred down a device which the mall calls a "hyperbolic funnel".  (The other members of the team and the coaches fail to understand this behavior.)  It is also a tradition to go to a certain restaurant afterward, to get yelled at by Penn State staff for getting frisbees in odd places, to stay in a certain hotel on the way, to pull all-nighters playing ultimate frisbee at said hotel on the way back, to eat at Cracker Barrel on the way up, to practice in the hotel rooms the night before we get there, to complain about the freshman dorms we get at Penn State, etc., etc., etc.

[quote="Elemennop"]i got one question

why are you playin ultimate frisbeE??[/quote]

Dude, in general, about half our customs are down the drain. In addition, it's no more fun, because the number of people at UGA is probably going to be quite small (< 600... probably <300).

With our group, injuries during Ultimate Frisbee are the custom! :-)

So, does *anybody* from GA want to go to the GA ARML site? If we pay more, can we go to Penn State?

Yeah, I want to go to UGA and I'll tell you why. As a very successful ARML team, I belive that we have the obligation to help other, less successful, teams, especially in the south. Having a southern location will allow other southern teams more of a chance to compete. It will also allow us to take more than 2 teams if we so choose.

I'm really going to miss going to Penn State and the ride up. (Not necessarily the ride back! :-) But this is probably better for ARML and the southern teams in the long run.

Ruby had a great suggestion today however. We could leave on Thursday, take a bus to Virginia, and return to UGA on Friday! At least we would get the bus practice time on the way up!  :D

That would be fun indeed... but then we'd stay up all Thursday night :|.

I feel sad about having to miss that bus ride...there was a bunch of team-building on the way up to Penn State... though I guess what's done is done.

[quote="captcha000"]lol that would certainly be interesting....and why would they pick georgia over say...a team from the south that has won recently (as in last year)[/quote]

Noo that would be bad. As it is, we might still be able to go to Penn State... Personally, I think it should have been in Texas. I mean if they added a site (which they shouldn't have done).

We should be able to choose where we go for the competition. That way we may be able to keep traditions.

[quote="Xantos C. Guin"]If all of us were willing to pay for the additional cost, then we might convince the coaches to going to Penn State. Another alternative is for all of us to refuse to participate unless we go to Penn State. But, we'll probably give in before they do, especially since there are plenty of people who would still go even if it is only to UGA so that isn't a good idea.[/quote]

Lol, but they won't win probably even top 10... anyways... it'll look really corny if Georgia doesn't go to UGA while about 5 other states which are farther away go to UGA.  :D

who cares how it looks? you guys should do wahtever you want t odo

Hmmm guys. We are basically the hosts. It would be really strange for the hosts to go somewhere else!

i hate to sound cliche / corny, but of course uga will be no fun with a negative attitude. i may be biased because I've only gone to penn state once and played no ultimate, but i think uga may hold new opportunities...

[quote="Criticalline1859"]...or maybe you are biased because you won UGA?[/quote]
 :lol:
arml at uga really doesn't have much to do with the uga tournament except that they are at the same place (and i don't really believe that uga gives me good luck).


calculus
integration
floor function
algebra
function
domain
calculus computations

\[ \int\limits_{ \minus{} 2}^2 {\left[ {x^2  \minus{} 1} \right]dx}
\]

$ {\left[ x \right]}$=greatest integer less than equal to $ x$

To do this integral, we should break it into peices over which the integrand is constant.

$ x^2\minus{}1$ ranges from $ 3$ to $ \minus{}1$ over the interval.

$ x^2\minus{}1\equal{}3 \implies x\equal{} \pm 2$
$ x^2\minus{}1\equal{}2 \implies x \equal{} \pm \sqrt{3}$
$ x^2\minus{}1\equal{}1 \implies x\equal{} \pm \sqrt{2}$
$ x^2\minus{}1\equal{}0 \implies x\equal{} \pm 1$
$ x^2\minus{}1\equal{}\minus{}1 \implies x\equal{}0$

So $ \lfloor x^2\minus{}1 \rfloor$ is $ 2$ for $ x \in (\minus{}2,\minus{}\sqrt{3}) \cup (\sqrt{3},2)$, $ 1$ for $ x \in (\minus{}\sqrt{3},\minus{}\sqrt{2})\cup(\sqrt{2},\sqrt{3})$, $ 0$ for $ x \in (\minus{}\sqrt{2},\minus{}1)\cup(1, \sqrt{2})$ and $ \minus{}1$ for $ (\minus{}1,1)$.  Putting this all together,

$ \int_{\minus{}2}^2 \lfloor x^2\minus{}1 \rfloor dx \equal{} 2[2(2\minus{}\sqrt{3})]\plus{}1[2(\sqrt{3}\minus{}\sqrt{2})]\minus{}1(2)$
$ \equal{} 8\minus{}4\sqrt{3} \plus{} 2\sqrt{3}\minus{}2\sqrt{2}\minus{}2 \equal{} 6\minus{}2\sqrt{3}\minus{}2\sqrt{2}$

First question to ask on seeing a symmetric domain, $ \int_{\minus{}a}^af(x)\,dx:$

Is the function being integrated even, odd or neither? And if neither, can the decomposition into even and odd parts be accomplished painlessly?

In this case, the function, $ \lfloor x^2\minus{}1\rfloor,$ is even. It's even because it's some arbitrary thing (the floor function) done to an even function. The the thing we do with the integral of an even function is "fold it over." Write what we want as
\[ 2\int_0^2\lfloor x^2\minus{}1\rfloor\,dx\]
The rest proceeds as facis has done, only with the "fold-over," we don't need as many cases.


MR.SEIBOLD HAS 6 DAUGHTERS.

EACH DAUGHTER IS 4 YEARS OLDER THAN THE YOUNGEST SISTER.

THE OLDEST DAUGHTER IS 3TIMES AS OLD THAN HER YOUNGER SISTER.

HOW OLD IS EACH OF THE THE DAUGHTER.

I AM NOT GETTING IT HOW TO DO. :huh:

Solution: I think you mean "THE OLDEST DAUGHTER IS 3 TIMES AS OLD AS HER [b]YOUNGEST[/b] SISTER"
So if we use algebra to do this, it'll be like this:
Youngest daughter's age: $ x$
Second daughter's age: $ x\plus{}4$
Third daughter's age: $ x\plus{}8$
Fourth daughter's age: $ x\plus{}12$
Fifth daughter's age: $ x\plus{}16$
Oldest daughter's age: $ x\plus{}20$

Since it states that the oldest daughter's age is 3 times the youngest daughter's age, we can set up an equation: $ 3x\equal{}x\plus{}20$ So by using simple algebra, we isolate the $ x$, (Subtract $ x$ from both sides) and we get $ 2x\equal{}20$ Now we divide both sides by $ 2$ and we get $ x\equal{}10$!!!!
So our ages would be"
$ 10$
$ 14$
$ 18$
$ 22$
$ 26$
$ 30$

Hope this helped.  :lol:

we have x is the youngest one. And x+20 as the oldest.
x+20=3x
20=2x
x=10
10, 14, 18, 22, 26, 30 are the ages of the sisters


geometry
circumcircle
geometric transformation
reflection
incenter
perpendicular bisector
geometry unsolved

Circumcircle $ (N)$ of $ \triangle FM_aM_b$ is the 9-point circle of $ \triangle ABC.$ Construct this circumcircle. $ M_c \in (N)$ is the unknown midpoint of $ AB.$ Then $ \overline {FM_a} + \overline {FM_b} + \overline {FM_c} = \pm \frac {r}{IO} [(b - c) + (c - a) + (a - b)] = 0.$ This is sum of directed segments and it has to be decided, which ones have to be taken positive / negative. For a proof, see
[url]http://www.mathlinks.ro/viewtopic.php?t=100242[/url],
[url]http://www.mathlinks.ro/viewtopic.php?t=85415[/url], etc.

Construct 2 concentric circles $ \mathcal F_1, \mathcal F_2$ with common center $ F$ and with radii $ r_1 = |FM_a - FM_b|$ and $ r_2 = FM_a + FM_b.$ WLOG, suppose $ FM_a < FM_b,$ as in your sketch. Draw circle with center $ F$ and radius $ FM_a,$ intersecting the ray $ \overrightarrow{FM_b}$ at $ P_1$ and the opposite ray at $ P_2.$ Reflect $ P_1, P_2$ in the perpendicular bisector of $ FM_b$ into $ Q_1, Q_2.$ Then $ FQ_1, FQ_2$ are radii of the circles $ \mathcal F_1, \mathcal F_2.$

The smaller circle $ \mathcal F_1$ always intersects $ (N)$ at 2 points; select the one on the larger of the arcs $ FM_a, FM_b$ of $ (N)$ and label it $ M_c.$ The larger circle $ \mathcal F_2$ may or may not intersect $ (N)$ at 2 points; if it does, label them $ M_c', M_c''.$ Apart from special cases (such as isosceles $ \triangle ABC$), this yields either one solution $ M_c$ or 3 solutions $ M_c, M_c', M_c''.$ Consider only one, say $ M_c.$ $ \triangle M_aM_bM_c$ is medial triangle of $ \triangle ABC.$ Parallels to $ M_bM_c, M_cM_a, M_aM_b$ through $ M_a, M_b, M_c,$ respectively, pairwise intersect at $ A, B, C.$

As a check, construct incenter $ I$ of the $ \triangle ABC$ and make sure it falls on the segment $ NF.$


group theory
abstract algebra
superior algebra
superior algebra unsolved

I think this has been solved twice (at least :)) on the forum.

[quote="eugene"]If H is a subgroup of finite index in a group G, then H contains a subgroup N which is of finite index and normal in G.[/quote]

What does "finite index" mean?

The set of left cosets of $H$ has finitely many elements.

P.S. I know you know what it means, liyi, because I've seen you use it :). The index of $H$ in $G$ is $[G:H]$ (you used this notation in some problems you have recently posted).

Hmm. Thanks for your reply. Now I know what it refers to... I didn't know that because I'm reading a Chinese book and I don't match the terms in different languages.

grobber... could you please give me the link of that proof? thx :) or a hint

[url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=22796]Here's something[/url], although it's not fully detailed there. There are other threads, I think.

Aww well I remember this problem very well. I have been posting it for the last few days but without answers.Only I get the reply that this problem has already been discussed before.Can anyone here give me the link of the proof.

[url]http://www.artofproblemsolving.com/Forum/viewtopic.php?highlight=beautiful&t=19724[/url]. Are we all happy now? :)

Thanks a lot, grobber.That was very illuminating.