induction
symmetry
modular arithmetic
combinatorial geometry
combinatorics unsolved
combinatorics

In a chess tournament $ 2n\plus{}3$ players take part. Every two play exactly one match. The schedule is such that no two matches are played at the same time, and each player, after taking part in a match, is free in at least $ n$ next (consecutive) matches. Prove that one of the players who play in the opening match will also play in the closing match.

This is one of the most beatiful problems I've ever seen. I've tried a solution. But it is extremely hard to express. Look at the attachments. Someone reply if it is understandable or not.

Edit: It contains some mistake. Will edit later.

Edit2: Corrected

I can't view the picture right now.

Anyway, is the solution really correct?

I know the solution is difficult to understand for my poor english or whatever. But if any one is interested, I will appreciate questions and will try to answar.

I have an idea.  :huh:

Totally we will have $ \frac{(2n\plus{}3)(2n\plus{}2)}{2}\equal{}(2n\plus{}3)(n\plus{}1)$ matches.

Suppose $ A$ and $ B$ play at the opening match, then we hope that the matches involving them will be held as soon as possible so that they will not forced to play the closing match.

Excluding the first match, $ A$ and $ B$ still need to play $ 2n\plus{}1$ matches.

After the first match, they will be free at the next $ n$ matches, and we can then arrange some other matches for them. But of course they cannot join the same match (as every two play exactly one), so $ A$ will be play the $ n\plus{}2$th match and $ B$ will play the $ n\plus{}3$th match, or reverse. And then they are going to rest for $ n$ matches and then immediately arrange $ 2$ other matches for them...(just ignore whether such arrangement is possible)

Then we need at least $ 1\plus{}(n\plus{}2)(2n\plus{}1)\equal{}2n^2\plus{}5n\plus{}3\equal{}(2n\plus{}3)(n\plus{}1)$ matches for $ A$ and $ B$ to finish their games, but this number is also the number of matches needed to be held... :blush:

[quote="lchserious"]Then we need at least $ 1 \plus{} (n \plus{} 2)(2n \plus{} 1) \equal{} 2n^2 \plus{} 5n \plus{} 3 \equal{} (2n \plus{} 3)(n \plus{} 1)$ matches for $ A$ and $ B$ to finish their games[/quote]
How do you get the period to be $ (n \plus{} 2)$ :?:

Consider this scenario:

[code]1   : A vs B
n+1 : A vs C
n+2 : B vs D
2n+2: A vs E
2n+3: B vs F
3n+3: A vs G
3n+4: A vs H[/code]
The period is $ n \plus{} 1$

I think the problem can't be solved by just considering the games of $ A$ and $ B$. You must take into account the accommodation of other players.

[hide="Regarding My Solution"]My English expression skill is not good, however, if anyone has [b]any[/b] question about my solution, I will try to explain.[/hide]

[quote="Akashnil"][quote="lchserious"]Then we need at least $ 1 \plus{} (n \plus{} 2)(2n \plus{} 1) \equal{} 2n^2 \plus{} 5n \plus{} 3 \equal{} (2n \plus{} 3)(n \plus{} 1)$ matches for $ A$ and $ B$ to finish their games[/quote]
How do you get the period to be $ (n \plus{} 2)$ :?:
[/quote]

Oh, I just forgot that $ B$ can have his match when $ A$ is taking his rest  :blush:  Sorry

It's been a while since he asked, but Akashnil's solution is right (and marvelous!).

Akashnil, could you please explain your solution in a better way? I am not able to clearly understnad everything that you wrote.

this problem is from a russian book called VSEROSIISKIE(the all russian)

Divide the $ (2n+3)(n+1) $ days into $ (2n+3) $ blocks of $ (n+1) $ days. Easy to see that if $ A,B $ play in i'th day then they will play in $ i+n+1 $ and $ i+n+2 $ th days. [b]Now we call it a move if the playing day of a player in a block changes its position in the next block[/b]. If a player has to play in the last block then he will have to skip a block.
[b]Lemma 1:-[/b]
A player can skip a block only when he reaches the end of a block.
[b]Lemma 2:-[/b]
If two players A,B have played a match and then they get separated. Then if A goes before B then B can never cross A.
[b]Lemma 3:-[/b]
If a player has to reach the last block then he will have to skip a block.

Now suppose, A,B played in the first day and A played in the $ (n+2) $th day and B on the $ (n+3) $ th day. So A can never cross B by Lemma 2. If B doesn't reach the last block then neither will A and if that happens then there will be at most $ 2n+1 $ players in the last block, which is impossible. So B will reach the last block. To reach the last block B will have to skip a block. So it will have to make at least $ n+1 $ moves. Since B has made $ n+1 $ moves already so at least $ n+1 $ players will be behind him in the last block. So at least $ \frac {n+1}{2} $ cells in the block will be before B's position(Because each cell can contain at most 2 players). After $ n+1 $ moves B will again come to the first place of a block but its position in the last block is after at least $ \frac {n+1}{2} $ cells. So it will have to make $ \frac {n+1}{2} $ more moves. So B will be at least $ \frac {n+1}{2}+\frac {n+1}{4} $ cells after in the last block. By the same reason it will have to make at least $ \frac {n+1}{4} $ moves again. So at last we will get that B will have to make at least $ n+1+\frac {n+1}{2}+\frac {n+1}{4}+.......... $ moves totally which means B will have to make at least $ 2n+2 $ moves. So we are done.

here is my solution:
$Lemma 1:$ If A and B play a match then one of them plays the next $n+1^{th}$ match and other the $n+2^{th}$.
$Proof$ : according to question no one can play a match before n matches of rest. So if some one plays after n+2 matches of rests then total 2*(n+2) that is 2n+4=(2n+2)+2 players play and thus there is one player two matches before n rest matches.

There are total $\binom{2n+3}{2}=(2n+3)(n+1)$ matches. So, we define a $round$ as $n+1$ consecutive matches starting from match one.
There are in all $2n+3$ rounds and a player plays only once in a round.
Let on one day one round be played in a hall having $n+1$ tables for match numbered from 1 to n+1.
th
We see that exactly one player does not play in one round.
Thus we define a $buffer$ as a table on which a single person not playing in the round sits. This table is placed after the n+1 th table.

Now Lemma 1 is equivalent to:
if A and B play on table $i$ then one of them plays on table $i$ and other on table $i+1$ the next day.
We say that one who wins goes to $i+1^{th}$ table.

$Lemma 2:$ If A wants to play on the table next to that of B then A has to defeat B (and of course play with B).  (proof: obvious by rephrased lemma 1)

Since each player plays 2n+2 matches that it 2n+2 rounds, he has to stay in buffer in exactly one round.
$Lemma 3:$ If A defeats B then B cannot cross the table of A.
Proof: Obvious from Lemma 2.

define one who has been to buffer table as buffered and similarly unbuffered is one who has not been to buffer table.

$Lemma 3.5:$ Only the player sitting on $n+1^{th}$ table can be buffered. (without proof)

$Lemma 4:$ A $"buffered"$ player cannot defeat an $"unbuffered"$ player.
$Proof:$ If buffered player B defeats A who has never been in buffer. Then A cant cross B and further B cant go in buffer again. Thus B can sit on atmost table number n+1 and thus A on at most table n. Thus A never reaches table n+1 and hence by lemma 3.5 never reaches buffer which is not possible as each player goes to buffer exactly once.

Another obvious thing is that one after crossing the buffer goes to table 1.

$Proof to Problem:$
Let the players be $A_1,A_2 ....A_2n+3$.
WLOG let $A_1$ defeat $A_2$. Then we'll show that $A_1$ also plays the last match .
That is it plays the last round on table numbered as n+1.
This is equivalent to showing that $ A_1$ wins all his matches.
If $A_1$ is on table $i$ then it is equivalent to show that $A_1$ has already played/defeated the winner of table $i-1$, because winner of $i-1$ comes to table$ i$ and thus if $A_1$ has already played him then he cannot sit on table $i$ and play the winner of table $i-1$, implying that he had won the match and moved to table $i+1$ and thus escaped the play with winner of table $i-1$ .
Case1: $A_1$ has not crossed the buffer.
in this case all the unbuffered players sitting on table numbered less then $A_1$ have been defeated by $A_1$. By lemma 4 we have the winner of table $i-1$ as an unbuffered player and hence we are done.

Case 2: $A_1$ has crossed the buffer.
Let f(A) denote the number of table on which A is playing.
then all the $A_j's$ having $f(A_j)<f(A_1)$ consists of following:
   1. Those who have been crossed by $A_1$ after being buffered, that is defeated
       by $A_1$ using Lemma 2).
   2. Those who crossed buffer after $A_1$ crossed it. Thus they were unbuffered
      while $A_1$ was in buffer. And thus like case 1 were already defeated by
      $A_1$.
Thus we see both the players sitting on table $i-1$ have been defeated by $A_1$ and we are done. :D

Since people have been complaining that the solutions above are hard to read, here are Akashnil's and kunalsinghal1994's solutions, reworded a bit.

[hide="Solution 1"](This is essentially Akashnil's solution.)

The key idea is to focus on how players $P,Q$ behave after (and also before, by symmetry) their match. In particular, their game sequence can't have two consecutive $Q$'s or $P$'s, or else one of $P,Q$ would have to sit out two rounds of $n+1$. Also, if we label the games of a round as $1,2,\ldots,n+1$, it's natural to give the non-player label $0$ (as in the previous round the non-player was in game $n+1$).

So basically, we want to compare the move sequences of players, and from above we have a very natural way to do this, organized by rounds: Take a $n+3\times 2n+3$ grid of dots in the Cartesian plane. The $k$th column corresponds to the $k$th round of $n+1$ matches, and the highest lowest dots in the $k$th column corresponds to the $0$th position (sitting out) in the $k$th round. Call the bottom/top rows the "river". A person either goes $+(1,0)$ (by losing) or $+(1,1)$ (by winning), and each player crosses the river exactly once. (In particular, the river dots all have exactly one person; all other $(n+1)(2n+3)$ land dots have exactly two people.) Most importantly, every two paths (which are continuous mod $n+2$) share exactly one dot.

Suppose the first game is $A,B$ and the last game is $A',B'$, where $A,B,A',B'$ are pairwise distinct. Clearly $A',B'$ start on distinct dots and $A,B$ end on distinct dots; WLOG suppose $B$'s first move is $+(1,1)$ ($B$ "beats" $A$) and $B'$'s last move is $+(1,1)$ ($B'$ "reverse-beats" $A'$). Since $B$ moves above $A$ after the first move, $B$ must cross the river strictly before $A$ does, and cannot end in the river. Thus $A$ ends below $B$ in the sense that the interval from $A$'s end to $B$'s end (mod $n+2$) does not contain $A'$ and $B'$'s end, and similarly $A'$ starts above $B'$.

Observe that the paths of $A,B$ form a "triangular region" $R$ mod $n+2$; let $R'$ be the region bounded by the paths of $A',B'$. We can easily check that the path of $A$ (and thus also $B$, by symmetry) cannot hit the interior of $R'$, and thus $R,R'$ only intersect on the border. But then the paths of $A,B'$ are disjoint, as are the paths of $B,A'$, contradiction.[/hide]

[hide="Solution 2"](This is essentially kunalsinghal1994's solution, and I believe close to what ThiagoSPinheiro intended.)

Again, we work in rounds of $n+1$ matches, and suppose the "winner" of each game plays $n+2$ games later and the "loser" plays $n+1$ games later. Let $X$ be the unused guy in round $1$, $A,B$ the first match with $B$ beating $A$. Observe that every player plays at most once each round and, because there are exactly $2n+3$ rounds of $n+1$, sits out exactly one round.

Go by contradiction and suppose $B$ first loses a match in round $k$ (in particular, he must have at least one match left).

[b]Case 1:[/b] $k\le n+1$. By definition, $k>1$, while by the minimality of $k$, $B$ plays position $k$ in round $k+1$ against, say, $Z$. Then $Z$ must not have played $B$ before, and hence must have played position $k-1$ in round $k$, $k-2$ in round $k-1$, etc., and position $1$ in round $2$. But this just means $Z\in\{A,X\}$, so $Z=X$. Yet $k\ge 2$, so $X$ must have beaten $A$ (otherwise $X$ cannot play position $2$ in round $3$), which is absurd: by discrete continuity, this prevents $A$ from being able to sit out, as $X$ has already sat out (and $A,X$ cannot play again).

[b]Case 2:[/b] $k\ge n+2$. By the previous case, we know $B$ wins his first $n+1$ games and thus sits out round $n+2$, so $k>n+2$. This time, $B$ plays position $k-(n+2)$ in round $k+1$ against a player $Z$, so $Z$ must have played position $k-1-(n+2)$ in round $k$, etc., and $0$ (i.e. sat out) in round $n+3$. Thus $Z$ must have played $n+1$ in round $n+2$, $n$ in round $n+1$, etc., down to $1$ in round $2$, so again we see that $Z=X$, and again that this prevents $A$ from being able to sit out.[/hide]

I find Solution 2 much more motivated, but Solution 1 is certainly very nice!

Really nice problem! Hopefully the following works (I took some hints for proving this from the above post; which is hopefully fine...)

[hide=" Solution"]
Label the players $P_1, P_2, \cdots , P_n$ and the games $G_1, G_2, \cdots , G_{(2n+3)(n+1)}$ in sequential order.

We divide the tournament into [i]rounds[/i]- where the first round is the set of the first $n+1$ games, the second round is the set of the second $n+1$ games, and so on. Notice that a player can play in at
most one round. Also, since there are $2n+2$ players in each round, there is exactly one player who doesn't play in the round- define that player to be the [i]loser[/i] of that round.

[b]Lemma:[/b] The losers of each round are pairwise distinct.
[i]Proof:[/i] Each player plays exactly $2n+2$ games, so each player must be the loser of at least one round. Since there are a total of $2n+3$ losers (counted with multiplicity), each player must be a loser exactly once; proving our claim. $\blacksquare$

For a particular player $P_j$ and a particular round $R_i$, we define the [i]index[/i] of $P_j$ in round $i$ to be the number of the game in that round in which $P_j$ plays (e.g. if $P_j$ plays in the fifth game of round 3, the index of $P_j$ in round 3 is 5) if $P_j$ is not the loser of round $i$ and $n+2$ if $P_j$ is the loser of round $i$.

[b]Lemma:[/b] If two players $P_i$ and $P_j$ play in a game $G_k$ ($k \leq (2n+3)(n+1) - (n+2)$), then one of them must play in game $G_{k+n+1}$ and the other in game $G_{k+n+2}$.
[i]Proof:[/i] Consider the games $G_{k+1}, G_{k+2}, \cdots , G_{k+n}$-each player can appear at most once in these games, so a total of $2n$ players are used. Hence, a total of $2n+2$ players are used up in the games $G_k, G_{k+1}, \cdots , G_{k+n},$ leaving only one player remaining. This player must play with one of $P_i$ and $P_j$ in game $G_{k+n+1},$ and the other player must play with a player from $G_{k+1}$ in $G_{k+n+2}$. $\blacksquare$

By the lemma, the index of a player in a particular round either increases by 1 (modulo $n+1$) in the next round or remains the same, and that of his last opponent remains same if the index of that player increases, and increases by 1 if the index of that player doesn't change.

We now make some trivial observations.
[list]

[*]If at a certain round, the index of a player $P_i$ is greater than that of a player $P_j$, until $P_i$ skips a round, as long as $P_i$ keeps changing its index, he cannot play a game with $P_j$. This is trivial. [/*]
[*]If a certain player is the loser of round $i,$ his index in round $i-1$ must have been $n+1$, and his index in round $i+1$ must be 1. This is because to skip $n+1$ consecutive games, by the lemma, the player has to play the game just before the first game and the game just after the last game.   [/*]
[*]Consider a game consisting of two players $P_i$ and $P_j$, and suppose that in the next round, the index of $P_i$ increases by 1 and the index of $P_j$ remains same. Then, starting from that round, until $P_i$ skips a round, the index of $P_i$ is always greater than the index of $P_j$. This is because at that round the index of $P_i$ is greater than the index of $P_j$, and for the index of $P_j$ to cross the index of $P_i$, it has to be equal to the index of $P_i$ at some round, which is not possible since $P_i$ and $P_j$ have already played against each other. As a consequence, $P_i$ skips a round before $P_j$ skips a round. [/*]
[/list]

Now, suppose the first two players are $P_1$ and $P_2$, and in the next round, the index of $P_1$ remains 1 while the index of $P_2$ is 2. The following claim finishes the problem.

[b]Claim:[/b] The index of $P_2$ must always increase by 1 $\pmod{n+1}$ in each round.
[i]Proof:[/i] Suppose $P_2$ is the loser of round $i$. It's fairly straightforward to prove that $P_2$ must change its index in all rounds until $i$- suppose otherwise, that in round $x$ ($x<i$), for the first time, $P_2$ doesn't change its index (i.e. its index in both round $x$ and $x+1$ are $x$). Suppose $P_2$ plays against $P_j$ in round $x+1$. The index of $P_j$ in round $x$ must be $x-1$ since that of $P_2$ is $x$. The index of $P_j$ in round $x-1$ must be $x-2$ since there are only two possible values for its index ($x-1$ and $x-2$) and that of $P_2$ is $x-1$. Inducting, we see that for all $k \geq 1$, the index of $P_j$ in $x-k$ is $x-k-1$. This means that in round 2, the index of $P_j$ is 1, so it must be the loser of round 1 (since the only other player whose index in round 2 was 1 is $P_1$ and $P_1$ and $P_2$ have already played before). This contradicts our first observation. This implies that until $P_2$ skips a round, he always changes his index. This consequently implies $i=n+2$. Now suppose $P_2$ keeps its index constant after he skips a round for the first time at round $k+n+2$, where he plays with $P_y$. Similar to the above argument, we see that the index of $P_y$ in round $k-x$ is $k-x-1$, similarly implying $P_y$ is the loser of round 1. This, again, is a contradiction, since for the index of $P_1$ to reach $n+2$ (i.e. for $P_1$ to skip a round, which it must), its index must at some round be equal to that of $P_y$, but they have already played in round 2. $\blacksquare$

The main proof is trivial from here. Since the index of $P_2$ always increases by 1, at the $2n+3$th round, his index must be $2n+2 \pmod{n+1} = n+1,$ i.e. $P_2$ plays the $n+1$th game of round $2n+3$, which is the last game of the tournament. $\blacksquare$ [/hide]

I think this is fairly similar to what is above, that is the key idea is player $2$ must always "move on".
Label the players $1,2,...,2n+3$. First we can make some simple observations.
(1) Among any $n+1$ matches, there are $2n+2$ unique players, this is obvious.
(2) Now consider match $k$ where $k\ge n+1$. Then there are $3$ choices for who can be in match $k$, the players of match $k-n$, and the only player who didn't play among the matches $k-n, k-n+1,...,k$.

Now divide the matches into intervals of size $n+1$. WLOG in the first interval $1$ plays $2$, $3$ plays $4$,..., $2n+1$ plays $2n+2$ Clearly in each interval all the players are unique by (1). Let the $i$th match in an interval be called "position $i$" and let the one player who does not play any matches be in position $n+2$. Position indices are taken modulo $n+2$  Using (2) we can determine that in the $j$-th interval where $j>1$, the $i$-th position will be one player from the $i$-th position and one player from the $i-1$-th position in the $j-1$-th interval for $i<n+2$, and for $i=n+2$ it will be a player from the $n+1$-th position in the $j-1$-th interval. We will call this important fact (3). There is also one more key idea which is:

(4) Every player will be in position $n+2$ exactly once, otherwise not all the players will play the same number of games.

Let's say that player $a$ beats player $b$ if in the match between players $a$ and $b$ is in position $i$ in some interval and player $a$ moves to position $i+1$. WLOG let $2$ beat $1$ in match $1$ in interval $1$. Clearly $2$ must eventually pass position $n+2$. If player $2$ wins all their games, they will be at position $n+1$, exactly, which will prove the problem statement.

Proof that player $2$ wins all their games: Let's call the people who player $2$ beat, "losers". Let's call a person who has reached position $n+2$ at some point, "safe". Consider the first time player $2$ loses. Suppose it is position $k$ before player $2$ has become safe. Then the player that player $2$ plays after losing must be a player player $2$ has not played yet, so it must be a safe player. Then that safe player must have beat player $1$, but this safe player will never reach position $n+2$ again by (4), so $1$ will not either, contradiction. Now suppose player $2$ loses for the first time after becoming safe, in position $i$. It is easy to see that the players in position $i-1$ must have played player $2$, but one of them must play player $2$ in the next interval. Contradiction.

[quote=ThiagoSPinheiro]Wow, this is certainly a beautiful problem. But it's kind of hard to explain. I haven't seen his solution but I will try to explain mine.

Firstly there will be $ (2n\plus{}3)(n\plus{}1)$ games to be played, divide them in $ 2n\plus{}3$ groups of $ n\plus{}1$ games each. Then each game will be named as a ordened pair $ (k;l), 1\leq k \leq n\plus{}1 ; 1 \leq l \leq 2n\plus{}3$ being $ k$ the position of the game in his $ n\plus{}1$ group and $ l$ the group this game is in. So $ (1;1)$ is the first match and $ (n\plus{}1;2n\plus{}3)$ is the last one.

Each group has $ n\plus{}1$ matches so it's impossible for a player to play two matches in one group, so there will be $ 2n\plus{}2$ diferent players in each group, leaving only one per group without playing. As each player has to play $ 2n\plus{}2$ matches and there are $ 2n\plus{}3$ groups, each player will not play in exactly one group and in each group exactly one player will not play.

Let's now analyze the last match of a group, $ (n\plus{}1;l)$, in the next group the two players that played this match need to wait $ n$ matches to play again, so they have only two options: playing $ (n\plus{}1;l\plus{}1)$ or else not playing in the $ l\plus{}1$ group. But they can't both play the same match again and neither can they both not play any match at all in this group. This implies that one of them won't play in the $ l\plus{}1$ group and the other will play the $ (n\plus{}1;l\plus{}1)$ match. With the same argument we see that those that played the $ (n;l)$ match will be divided in the way that one will play $ (n;l\plus{}1)$ and the other the $ (n\plus{}1;l\plus{}1)$. By induction we concluded that those that played the $ (k;l), k<n\plus{}1$ will divide and play the $ (k;l\plus{}1)$ and the $ (k\plus{}1;l\plus{}1)$. This implies that the one that did not participate in the $ l$th group will play $ (1;l\plus{}1)$.

So we see that at most a player can advance one place inside the groups after each match. In order that someone from the first match end up playing the last one he will need to play in every position up to the last, then skip a group play in the first position again, and so play in every position again to be able to play in the last. To do this at least $ n\plus{}1\plus{}1\plus{}n\plus{}1\equal{}2n\plus{}3$ groups will be needed, but that's exactly the number of groups there are so the one that plays $ (1;1)$ and $ (2;2)$ will never play in the same position two groups in a row.

This means that to solve the problem we need only to show that one of the participants of the first match will always play $ n\plus{}2$ matches after his previous. In other words that player will never fall in a situation that he plays the games $ (k;l)$ and then $ (k;l\plus{}1)$. That will be called player $ 2$, the other participant of the first match will be called player $ 1$ and the player that did not participate in the first group will be called player $ 3$.

Let's suppose that eventually player $ 2$ will play $ (k;k)$ and $ (k;k\plus{}1)$ his opponent on match $ (k;k\plus{}1)$ will be player $ 3$, since the only players that can reach him on $ (k;k\plus{}1)$ are those that he has already played against and player $ 3$, since someone from the $ (n\plus{}1;1)$ match would take up to the $ k\plus{}2$th group to reach the $ k$th position.

Now we need to show that player $ 3$ will play $ (1;2)$ and $ (1;3)$ not being able then to reach player $ 2$ if he eventually stops, making it impossible for him to ever stop advancing inside the groups. If player $ 3$ doesn't play $ (1;3)$ player $ 1$ will play it. But player $ 1$ needs to eventualy gets to position $ (n\plus{}1;l)$ and he can not play anymore against player $ 3$, but now player $ 3$ who can't leave any group anymore has a higher position than player $ 1$, so player $ 1$ won't be able to leave a group without playing against player $ 3$ again, making this situation impossible!

And that solves the problem =]

Can anyone understand what I meant?[/quote]
Yes I understand I have told this solution to my classmates but no one understand but I think it is very beautiful thank you.

 :D

[hide = Solution]
First, label the games $G_1, G_2, \dots$. Also, number the players $P_1, P_2, \dots$.

By the $n-$game free condition,  any consecutive block of $n+1$ games will involve $2n+2$ distinct players ($\star$). This motivates us to break the games into intervals:
\[S_1 = \{G_1, G_2, \dots, G_{n+1}\}\]
\[S_2 = \{G_{2}, G_{3}, \dots, G_{n+2}\}\]
and so on.

Each interval $S_i$ involves $2n+2$ distinct players, so we are motivated to define $A_i$ to be the index of the player who doesn't play in $S_i$.

CLAIM: the game $G_{j+n+1}$ involves $A_j$ and one of the players from $G_j$.

PROOF: we observe that by applying $\star$ to interval $S_j$, these 3 players (who are $A_j$ and the pair from $G_j$) are the \textit{only} players that may participate in the game. Clearly, $G_{j+n+1} \neq G_j$, so $A_j$ must participate.

Now, for any game $G_j$ involving $x$ and $y$ such that $x \in G_{j+n+1}$, we define $g_j = x$. (To repeat some terminology from above solution, we say that $x$ "wins" the game.)

WLOG, let the first game be
\[G_1 = (1, 2).\]

We see that, by CLAIM, $G_{n+1}$ will contain $P_{A_1}$ and one of $\{P_1,P_2\}$. WLOG, let
\[G_{n+1} = (2,A_1).\]

Now, we will prove that, for any game $G_q$ that $P_2$ plays in, $g_q = 2.$ (So we say that 2 wins all his games.)

Let us partition the games into intervals of length $n+1$:
\[B_1 = G_1, G_2, \dots, G_{n+1}\]
\[B_2 = G_{n+2}, G_{n+3}, \dots, G_{2n+2}\]
etc.

Let $k$ be the index for which $B_k$ does not involve $P_2$. The last game $G$ of $B_{k-1}$ then involved $P_2$, and $g = 2$ ($P_2$ won.)

Then, let's say say there existed game $G_j$, involving $P_2$ and $P_x$, such that $g_j = x$, so $x$ moves to a game that is indexed 1 $\pmod{n+1}$.

    If the game happened before $G$:

    Since $P_2$ ends up behind $P_1$, and $x$ ends up behind $P_2$, we must have a game in which $x$ plays $1$, and $x$ wins. But then, after the game $G_j$, we can never have $A_i = 1.$ We could never have $A_i = 1$ before the interval either -- so there does not exist $i$ such that $A_i = 1.$ This forces $P_1$ to play more than $2n+2$ games, which is a contradiction.

    If the game happened after $G$:

    Consider game $G_{j-1} = (y,z)$. We see that, since $P_2$ has been "absent" in an interval, $P_2$ must have played $P_x$ and $P_y$ previously.

    However, we need $P_2$ to play one of $x$ and $y$ in the next $B$ interval, which is then impossible since the same game cannot occur twice.

From here, we conclude that if $P_2$ plays in game $k$, he must play in game $k+n+2$. Thus, he plays in all the games $G_j$ such that
\[j \equiv 1 \pmod {n+2}.\]

Since $\dbinom{2n+3}{2} \equiv 1 \pmod {n+2},$ we have $P_2$ playing in the last game, so we are (at last) done.

[/hide]

Let $G_1, G_2, \ldots , G_{T}$ be the games in order from first to last, where $T = (2n+3)(n+1)$ denotes total number of games, Let $B_i$ for each $i$ denote the block of games $G_i, G_{i+1}, \ldots , G_{i + n}$. In each block, no player may play twice, so the $n+1$ games allow for exactly $2n+2$ players. For each block $B_i$, let $C_i$ be unique player who does not play.

Note that for each game $G_{k +(n+1)}$, the two players must be $C_k$ and one of the two players in $G_k$ since the $2n$ players in $G_{k+1}, G_{k+2}, \ldots , G_{k+n}$ all cannot play within $n$ days, and the game $G_k$ cannot happen again. So for each game $G_i$, one of its players carries on to game $G_{i + (n + 1)}$ and competes with the guy who didn't play in $G_i, G_{i+1}, \ldots , G_{i + n}$. The player who does not carry on must overshoot to game $G_{i + \ell}$ where $\ell > n+1$. In the overshoot case, the player is $C_{k+1}$, and hence must play with someone from $G_{k+1}$ in $G_{i + n + 2}$, so $\ell$ is necessarily $n + 2$.

Now, say people $P_1$ and $P_2$ compete in $G_1$, and WLOG $P_1$ overshoots on to $G_{n+3}$ to play against $A_1$. We will show that $P_1$ always overshoots, and thus plays in all games $G_m$ with $m \equiv 1 \pmod {n+2}$. Nicely enough, $T \equiv 1 \pmod {n+2}$ hence this actually finishes. Divide all games into the blocks $X_1 = B_1, X_2 = B_{1 + (n+1)}, \ldots , X_{2n+3} = \ldots, B_{1 + (2n+2)(n+1)}$. Of which there are $2n+3$ total, and thus $1$ block $P_1$ did not play in.

FTSoC $P_1$ carries on at least once, the first time from game $G_j$ in $X_{\ell}$ against opponent $P'$ who overshoots to $G_{j + n + 2}$. Whenever he carries on, his game position modulo $n+1$ is unchanged, and if he overshoots, it is increased by $1$. [list]
[*] If $\ell \leq n+1$, then $P_1$'s modulo value has never surpassed $n+1$, so he has competed in game $i$ of each block $X_{i+1}$ so far with an exception of having competed in game $\ell$ of block $X_{\ell + 1}$. Say he plays $Q$ in his game in block $X_{\ell + 1}$. Say for each block $X_i$ up to $i = \ell + 1$, person $Q$ has played in the $a_i$th game. Since $P_1, Q$ have not played before, $a_i < i$ always for $i \leq \ell$. Furthermore $a_i$ is nondecreasing, and these restrictions are enough to tell us that $a_i = i-1$ for all $i \in [2, \ell]$ and $a_1 = 1$. So either $Q = P_2$ or $Q$ was the guy who didnt play in $X_1$. Clearly $Q = P_2$ is not possible as $P_1, P_2$ cannot play again. So $Q = G$, where $G$ is the guy who ghosted $X_1$. $G$ must have played in game $i-1$ in every block $X_i$ with $i \geq 2$ then, meaning $G, P_2$ played in the first game of $X_2$. Since $G$ advanced by $1$ modulo $n+1$ every block thereafter, he must have always overshot, and thus $P_2$ carried on from $X_2$ to $X_3$. Since $G, P_2$ cannot play again, $P_2$ modulo value in each block is strictly less than $G$'s, but $G$'s modulo value can never surpass $n+1$ since he can never skip another block, thus $P_2$ can never skip a block at all, impossible.

[*] If $\ell > n+1$, then $P_1$ has already skipped a block specifically block $X_{n+2}$, having overshot every block before, and must play in every block thereafter. Say he plays $Q$ in block $X_{\ell + 1}$. Similarly to above, we find that $Q$ must have played in game $i - 1$ in each block $i$, hence ghosting in $X_{n+3}$. Analyzing further down, we find that $Q$ must have played in the first match of $X_2$, and thus must either be $P_1$ or have ghosted $X_1$. But $Q$ could not have ghosted both $X_{n+3}$ and $X_1$, and also could not have played $P_1$ twice, impossible.  [/list]
So indeed, $P_1$ always overshoots, so his games' positions are always $i$ is always $1 \pmod {n+2}$. There are $2n+2$ of those from $1$ to $T$, so $P_1$ must play in all of those games. One of those games is $G_T$, where $P_1$ must play in. $\blacksquare$

Solved with [b]nukelauncher[/b].

Split the tournament into \(2n+3\) [i]days[/i] of \(n+1\) games each. Then each day, one player has a [i]bye[/i], and the remaining players each play in exactly one game. Since each player plays the same number of games, each player has a bye on exactly one day.

First notice that no player may be free for at least \(n+2\) consecutive games. Otherwise, at most \(2n+2\) people participate in the next \(n+2\) games, and since the middle \(n\) games must be played by \(2n\) distinct people, the first and last of these \(n+2\) games must be played by the same two people, contradiction.

Therefore after each game (except on the last day), one player takes \(n\) games off and the other takes \(n+1\) games off. Let the player taking \(n\) days off be the [i]loser[/i] of that match, and the player taking \(n+1\) days off be the [i]winner[/i].

On each day, let a player's [i]index[/i] be \(i\) if he is playing in the \(i\)th game of a day, or 0 if he has a bye. Then between days, a player's index either stays the same or increments modulo \(n+2\).

Let the players of the first match be \(A\) and \(B\), and assume \(B\) wins.

[color=red][b]Claim:[/b][/color]      \(B\) always wins.

[i]Proof.[/i]      Assume \(B\) first loses on day \(k\), and that \(B\) plays \(X\) on day \(k+1\).     Then \(X\) must have won every prior game,     else \(B\) and \(X\) would have played before.     In particular, \(X\) took a bye on the first day, and beat \(A\) on the second day.

Since \(X\) already took a bye, \(X\) may not take another bye, so his index is always positive thereafter.     Moreover since \(A\) and \(X\) already played, \(A\)'s index is always strictly less than \(X\)'s index.     In particular, \(A\) may never take a bye, contradiction. \(\blacksquare\)

Thus, \(B\) plays in game number \(1+(2n+1)(n+2)=\binom{2n+3}2\), as desired.

[hide=Temple of Worship to v4913] Suppose this is a 1v1 geometry tournament instead of chess. The key idea is to think of people (and a goddess) running in one direction in $\mathbb{Z}_{n+2}$ (or a circle with $n+2$ points) in a way that preserves continuity.

By the problem condition, if players $A,B$ plays game $x$ then exactly one of $A,B$ plays on game $x+n+1$ and the other plays game $x+n+2$. In this case, suppose $A$ defeats $B$.

Suppose the tournament has $2n+3$ days. On each day, $n+1$ games are played. Also, because v4913 is a geo goddess, she plays and defeats the person who is not played with another player. She basically chases the players. If a player loses, he stays on the same board, and the distance between her and the player decreases by 1, and if a player wins, he moves up a board (board $x \rightarrow$ board $x-1$) and nothing happens to the distance between her and the player.

Let $f_k(t)\colon \{1,\cdots,2n+3\} \rightarrow \mathbb{Z}_{n+2}$ denotes the board player $k$ is on on day $t$. Let $g_k(t)$ denote the time when player $k$ plays his $t$th game. Suppose player $1$ defeats $2$ on day 1. Furthermore, set $f_k(1)=\lfloor \frac{k-1}{2} \rfloor$ for $1\le k\le 2n+3$. The problem is equivalent to proving $2$ will lose all his games because if he plays $2n+3$ games, then his last game can at most the $1+(2n+1)(n+2) = (2n+3)(n+1)$'th game, with equality holding if and ony if he loses every game.

First of all, v4913 needs at least $n+1$ days to catch up with players $1$ and $2$, which implies $1$ must lose at least $n+1$ games, or win at most $n+1$ games.

Assume for contradiction $2$ does not lose all his games. Let $t$ be the earliest day in which player $2$ wins a game. If $a_t$ is the player $p_2$ defeats, for all $t'> t$, $g_{1}(t')<g_{2}(t')<g_{a_t}(t')$. Since $2$ loses all his games, for all $t'<t, g_1(t') < g_{a_t}(t')$. Before time $t$, player $a_t$ must run his way up to board $0$ to play $2$, while $1$ leaves board $0$ for board $n+1$.

If $1$ and $a_t$ has not played before, $1$ needs to catch up with $a_t$, and run a full circle (i.e. win $n+2$ games), which means $1$ has played $2n+3$ games.

After $2$ beats him, $2$ still has games to play, and $2$ has never met the next person $X$ before. This means $X$ has also lost all his games, and has been standing still at board $n+1$ since the tournament started, so $X$ is player $2n+3$. At this point, $1$ and $a_t$ has ran the circle at least once, so $2$ is already defeated by v4913. Since $X$ lost all his games, $X$ has been defeated by v4913 twice, contradiction! [/hide]

I was requested to explain my solution better, so here we go again! :blush:

[hide="Another rewrite"]Define $f_p(i)$ to be the index of the $i$'th match played by the player $p$, in the global schedule.

1) $f_p(i)\in [1, (n+1)(2n+3)]$ for $i\in [1, 2n+2]$
2) $f_p(i+1)-f_p(i) \in [n+1, n+2]$
3) For each $p\neq q$, there is a unique pair $(i, j)$ such that, $f_p(i) = f_q(j)$

Define $g_p(i) = f_p(i) - (i-1) (n+1)$
1) $g_p(i)\in [1, 2(n+1)]$ for $i\in [1, 2n+2]$
2) $g_p(i+1)-g_p(i) \in [0, 1]$
3) For each $p\neq q$, there is at most one $i$ such that, $g_p(i) = g_q(i)$

Define $h_{pq}(i) = g_p(i) - g_q(i)$
1) $h_{pq}(i+1) - h_{pq}(i)\in [-1, 1]$
2) If $h_{pq}(i) > 0$ and $h_{pq}(j) < 0$, then there exists $k\in (i, j)$ such that $h_{pq}(k)=0$
3) $h_{pq}(i) = 0$ for at most one $i$.

If $h_{pq}(1) \ge 0$ and $h_{pq}(2n+2) \ge 0$, then $h_{pq}(i) \ge 0$ for all $i$.
We define $p$ beats $q$ iff this is true. This is equivalent to $g_p(i) \ge g_q(i)$ for all $i$
Suppose first game of the tournament is played by $p_1, p_2$ and last game of the tournament is played by $q_1, q_2$ distinct from $p1, p2$
$g_{p_1}(1) = g_{p_2} (1) = 1 < g_{q_1}(1)$
$g_{q_1}(2n+2) = 2n+2 > g_{p_1}(2n+2) > g_{p_2}(2n+2)$ (WLOG)

$p_1$ beats $p_2$ and $q_1$ beats $p_1$.
$g_{q_1}(i) \ge g_{p_1}(i) > g_{p_2}(i)$ for all i > 1. Hence $g_{q_1}(i) \neq g_{p_2}(i)$ for all $i$, contradiction.[/hide]

Truly amazing, potentially my favorite olympiad problem of all time, I can't really remember a problem better than this (note: I have not done 2020 C8 which gets a lot of praise as well). A problem of sheer brilliance, an incredibly cool statement, and many equally interesting solutions, all with more or less the same underlying idea which I will try and explain. It is also remarkable that Akashnil wrote up an explanation for his decade-old solution while I'm typing this on the thread.

My solution is no different from the many above, so I will focus more on the motivation and the write-up will be lengthy but in reality is the same as that of, for example, TheUltimate123. The final very short write-up does not convey even the tiniest fraction of how beautiful this problem truly is.

Firstly, I think anybody who has solved this problem will agree that they almost just stumbled upon the solution; in hindsight, it felt completely natural but in reality, it was never clear how close I was to the solution.

Number the players such that the first match is played between $(1,2)$, the second match between $(3,4)$, \cdots, the $n$-th match between $(2n-1,2n)$, the $n+1$-th match between $(2n+1,2n+2)$, and without loss of generality, the $n+2$-th match between $(1,2n+3)$.

Let us start with two natural observations which one notices by simply trying to play with the given structure, nothing out of the box.
[list]
[*] There are ${2n+3 \choose 2} = \frac{(2n+3)(2n+2)}{2} = (n+1)(2n+3)$ matches in the tournament.
[*] Among any $n+1$ consecutive games, there will be $2n+2$ different competitors
[/list]

The first one is clear, any pair of the $2n+3$ players play exactly one match and the second one follows by the fact that after any player plays a match, they must rest for at least $n$ matches, and this condition would not be satisfied if there were a repetition of players within a sequence of $n+1$ matches.

This makes it natural to group the matches in $n+1$ in the most obvious way, taking $2n+3$ consecutive groups of $n+1$, let us call these the rounds. Each player plays $2n+2$ matches which means that for each player there will be exactly one round wherein they are absent.

Now, trying to play with small cases such as $n \in \{1,2\}$, we have the following important and easy claim.

$\textbf{Claim:}$
For any player, the rest between their consecutive games is either $n$ games or $n+1$ games.
$\textbf{Proof}$
Assume for the sake of contradiction that there are $n+2$ consecutive games where player $i$ has no matches. Then notice that the set of players (no repetitions) of the first and last $n+1$ matches of this set of $n+2$ consecutive games contain all the players, in particular, the first and final matches must be between the same pair, a contradiction, as desired. $\blacksquare$

Now, it is natural to define $f_i(j)$ to be difference in the match numbers between the $j$-th and $j+1$-th matches of the $i$-th player for $i \in \{1, \cdots, 2n+3\}$ and $j \in \{1, \cdots, 2n+1\}$ and try to globally restrict some things using the fact that $f_i(j) \in \{n+1,n+2\}$, for example we know that $\sum_{k=1}^{2n+1} f_i(k) \leq {2n+3 \choose 2}-1$ but this at first sight is useless. However, it actually leads to a wonderful observation. The equality can only hold if the starting player only makes jumps of length $n+2$! (exclamation mark not factorial) This means that for the problem to be true the equality must hold for one of the starting players, in particular, the player which takes a break of length $n+1$ at first must only take breaks of length $n+1$, i.e, $f_2(k) = n+2$ for all $k \in \{1, \cdots, 2n+1\}$ must hold.

This is now one of the most crucial parts of the problem, this shift in perspective is really important but also in my opinion quite motivated; one can see that if we go back to our notion of rounds, we can consider the position within the round that a player plays.

For $i \in \{1, \cdots, 2n+3\}$, define $g_i(j) \in \{1, \cdots, n+2\}$ be the position at which the $i$-th player plays a match in round $j \in \{1, \cdots, 2n+3\}$ such that $g_i(j) = n+2$ for some unique $j \in \{1, \cdots, 2n+3\}$ for each $i \in \{1, \cdots, 2n+3\}$ where $j$ is the number of the round where player $i$ does not play.

Now, the main observation that follows from $\textbf{Claim}$ is that either $g_i(j) = n+1, g_i(j+1) = 0$ or $g_i(j+1)-g_i(j) \in \{0,1\}$, that is, if we consider this circle of numbers $0, \cdots, n+1$, each player moves continuously, clockwise along it, and moreover, if $g_{i_1}(j) = g_{i_2}(j)$, then $\{0,1\}  = \{g_{i_1}(j+1)-g_{i_1}(j), g_{i_2}(j+1)-g_{i_2}(j)\}$, and if $g_i(j) = n+2$, then $g_i(j+1) = 1$.

What this means can be visualized as follows:
If a round is represented in the following manner (can also be put on a circle but due to the asymmetry I do not think it is necessary), for example for $n=2$,

$(1,2), (3,4), (5,6), 7$
Then, the next round will be of the following form:
$(1,7), (2,3), (4,5), 6$, there will be one element selected from each position and said element will move forward with the final element going back to the first position.

Moreover, each player will have to reach the final position at some point because they must have exactly one round where they do not play.

Now, the magical part of the problem; after trying for a while to characterize types of sequences of moves that we can make in this set-up, the idea to focus on solely the first two elements for a moment dawns on us. Indeed, our conclusion is only concerning the first two elements, so let us see how they behave.

Our intuition is that if $2$ ever stays in the same position after a round, the person that moves on will be disconnected from the first player because we know that $2$ has to always be ahead of $1$ in the cycle, because it moved on to the second position after the first round and any two players play exactly one match. This means that player $1$ will have to meet with the player that moved on against $2$ after this player has completed a full cycle and wasted enough time to ensure that $1$ is never able to reach the $n+2$-th position and not play in a round.

$\textbf{Lemma 2:}$
$g_2(i+1) = g_2(i)+1$ for all $i \in \{1, \cdots, n+1\}$
$\textbf{Proof)}$
Firstly, notice that $n+2 \geq g_2(i+1) \geq g_2(i) \geq 1$ for all $i \in \{1, \cdots, n+2\}$ because we know that $g_2(i+1) \leq g_2(i)+1$ for all $i$ and $g_2(1) = 1$.

Assume for the sake of contradiction that $g_2(m+1) = g_2(m)$ for some $m \in \{2, \cdots, n+1\}$, in particular let $m$ be the minimal such integer.

Notice that $g_2(i) > g_1(i)$ for all $i \in \{2, \cdots, n+1\}$ because the two players move continuously within the positions and $g_2(1) = g_1(1)$ means that we can apply a discrete version of the Intermediate Value Theorem to get that $g_2(i) = g_1(i)$ for some $i > 1$ if $g_2(j) \leq g_1(j)$ for some $j \in \{2, \cdots, n+2\}$, in particular it is not possible for $g_2(i) = g_1(i)$ because then players $1,2$ will have played more than one match.

Now, let $k$ be the number of the player that player $2$ plays against in the $m$-th round and notice that player $k$ satisfies $g_k(i) > g_2(i)$ for all $1 \leq i < m$ and $g_k(m) = g_2(m)$ and for $m+1 \leq i \leq n+2$, $g_2(i) < g_k(i)$.
This means that $g_2(i) \leq g_k(i)$ for all $i \in \{1, \cdots, n+2\}$ and therefore $g_1(i) < g_2(i) < g_k(i)$ for all $i \in \{1, \cdots, n+2\}$.

Moreover, we know that the $k$-th player must play against player $1$ meaning that there exists some $i \in \{n+3, \cdots, 2n+3\}$ such that $g_1(i) = g_k(i)$. Let this index $i$ be $m_2$.

Now, we will use all this notation to finish in an elegant way, the notation was just to present the intuition in a rigorous way.

Give the second player a red ribbon in the beginning. Let us assume that when player $2$ meets player $k$, she passes it onto player $k$ who later on passes it to player $1$ when they meet.

Now, let us track the movement of the red ribbon; we know that it started in the first position and completed one full cycle before meeting player $1$ at some point and then player $1$ also reached the $n+2$-th position, moreover, the ribbon moved at most one spot in our cycle at each step, meaning that there must have been $2 \cdot (n+2) = 2n+4$ rounds, a contradiction. This contradiction means that $g_2(i+1) = g_2(i)+1$ for all $i \in \{1, \cdots, n+1\}$. $\blacksquare$

Now, $\textbf{Lemma 2}$ means that $g_2(n+2) = n+2$.

To finish, consider the same tournament but where the matches are played in the exact opposite order. Let $p,q$ be the two players in the first match of this tournament and notice that either $g_p(n+2) = (2n+3)-(n+1) = n+2$ or $g_q(n+2) = (2n+3)-(n+1) = n+2$ by $\textbf{Lemma 2}$, applied to this tournament, without loss of generality $g_p(n+2) = n+2$, then $g_p(n+2) = g_2(n+2) = n+2$, however, at each round $j$, we have exactly one player $i$ such that $g_i(j) = n+2$. This means that $p=2$ and consequently player $2$ must have played in the last match of the tournament. $\blacksquare$ $\blacksquare$

Does this work? Not sure.

It is not hard to prove that, after a match, one player plays again in $n+1$ matches, and the other plays again in $n+2$ matches. Call the former player the [i]loser[/i], and the latter the [i]winner[/i]. We don't care about the last couple matches where neither player plays again. If a match isn't the first match of either player involved, one must be coming off a win, and the other off a loss, since players don't play twice. Finally, by the time the winner of the first game plays their second match, everyone else has played once.

Observe that there are $\tbinom{2n+3}{2}=(n+1)(2n+3)$ total games. Since this equals $1+(2n+1)(n+2)$, this implies that nobody except for the players in the first game can win all their matches; also, the problem is equivalent to showing that the winner of the first match goes on to win all of their games (except possibly their last, where their result stops mattering).

Suppose that the winner of the first match doesn't win all their games. Consider the player $P$ who starts with the longest winstreak, which contains at least one win: by our assumption, they eventually lose a game and then play another: say the $k$-th overall. The other participant $Q$ in match $k$ must have won in match $k-(n+2)$, since match $k$ cannot be their first match. $P$ won in match $k-(2n+3)$ to get to match $k-(n+1)$ (where they first lose); to get to match $k-(n+2)$, $Q$ either won in match $k-(2n+4)$ or lost in match $k-(2n+3)$, but the latter is impossible since they meet in match $k$. Thus $Q$ won in match $k-(2n+4)$. Repeating this argument, it follows that $Q$ in fact won every match up to $k$, and all of these matches came directly before some match of $P$.

If $P$ doesn't play in the first match overall, then $Q$'s first match must have come directly before the first match of $P$, since otherwise it comes too late. But then we find that $Q$ has a starting winstreak that's at least one game longer than $P$'s: contradiction. Otherwise, $Q$ is the player who first plays in match $n+2$ and it's winstreak is exactly the same length as $P$'s. But then we can repeat this by looking at $Q$'s winstreak (giving it the role of $Q$) and find that the player who wins in match $n+1$ has a longer winstreak: contradiction. $\blacksquare$

[b]Remark:[/b] I think one of the key steps in this problem might be introducing the idea of "winning" and "losing", even though we haven't done anything mathematical to the problem. I think it makes everything much easier to think about. Didn't come up with it myself.


geometry
geometric transformation
reflection
articles
rotation
inequalities

I was working through the beginning chapters of my Chemistry book, and this exercise came up:

$ \text{Perform the following mathematical operations and express the result to the correct number of significant figures.}
\linebreak
\linebreak
\frac{2.526}{3.1}+\frac{0.470}{0.623}+\frac{80.705}{0.4326}$

I know for multiplication/division, you would use the least number of significant figures. For addition/subtraction, you would use the least number of digits. But how about for this problem, with both addition and division?

Every time you perform an operation, you apply the rule for that operation.  Any votes on where in the forum this thread belongs?

bleh. if there were a general science forum, I'd say that, but how about chemistry.

Okay, but the book also said that you shouldn't round or do anything like that until the VERY end of the problem. I thought that was how you would do it too, but the book stresses that a lot. And when I tried it that way, I got an answer of 188.164, which rounds to 188.2. The book's answer is 188.1.

Sorry about the forum, I wasn't sure which forum to post in either.  :|

$ \frac {80.705}{0.4326}\equal{}186.6$ with 4 significant figures, so anything past the tenths place will theoretically be nonsignificant. The other divisions will yield significant figures to beyond the tenths:
$ \frac {2.526}{3.1}\equal{}0.81$ and $ \frac {0.470}{0.623}\equal{}0.754$
You can calculate with as many decimal places as the calculator will allow, then round $ 188.127...$ to $ 188.1$
Of course, the whole silly thing is often unreasonable, as in:
$ \frac {101}{103}\equal{}0.981$
How did we get a result showing about a 0.1% relative error out of two values with a 1% uncertainty? However, rigid rules are accepted, whether reasonable or not.

well so there exist more refined uncertainty calculations for that

sigfigs are really just a first (useful) approximation to careful tracking of uncertainties ?

I agree with Mystic on significant digits are the first approximation to deal with uncertainty.

KMST calculated the divisions correctly, but the rounding for multiplication/division should always be done after the calculation and the rounding for addition/subtraction should always be done before calculation.  I don't think your book's rule is right.  If you had a large number of intermediate results, the amounts you are adding to unknown digits (in the hundredths place) would affect the tenths digit and beyond.  If you think of the place past the least significant digit as an unknown, you can't logically get any meaningful final conclusion as to the value of an unknown by adding/subtracting.

186.6     can be thought of as    186.6?  with the ? meaning an unknown value                         186.6
   0.81                                      0.81?                                                                                0.8
   0.754                                    0.754?                                                                               0.8
---------                                 ----------                                                                            ------
188.164  round to 188.2            186.1???  or 186.1 (if don't round before calculation)                188.2
                                                                      (but just eliminate the unknown place)

The last calculation should be correct.

I stand by my prior result of 188.1, based on
http://www.chem.sc.edu/faculty/morgan/resources/sigfigs/sigfigs7.html
(and everything I've read before, and everything that makes sense to me). I do not see a reasonable way to get 188.2 as a result.
Calculated independently, each quotient would be rounded to a different number of decimal places, based on the uncertainty derived from the number of decimal places in each given number. Calculated independently, the first quotient would be rounded to 0.82, the second to 0.754, and the third to 186.6, based on significant figures in the given numbers. But since more calculations follow, we don't round yet.
For a series of calculations, we keep in mind the uncertainty we want the final result to reflect, but we do not round until all calculations are done.
In computing the whole sum, I calculated all three quotients and their sum using as many digits as the computer would give me. The result was $ 188.12727....$. After that, I rounded it to $ 188.1$, because that was the last decimal place I was certain about.

Leaving the rounding to the end isn't what the site you cited suggested, unless you are doing linear regression, which had nothing to do with the problem.

It is improper to suggest adding something to a place, such as the hundredths place, that is uncertain generates a definite answer.

For example, if you started with 210 cows, to two significant digits, with no knowledge of the units place. Then someone gives you 1 cow, your technique would tell you that you had precisely 211 cows.  By adding one cow you have eliminated  the average uncertainty of five cows.

It still isn't correct.

Suppose I had 210 cows to two significant digits.  Then someone gave me 1 cow.  Then someone gave me 1 cow.  Then someone gave me 1 cow.  Then someone gave me 1 cow.  Then someone gave me 1 cow.  Then someone gave me 1 cow.  Then someone gave me 1 cow.  Then someone gave me 1 cow.  Then someone gave me 1 cow.  Then someone gave me 1 cow.  Are you arguing that, to 2 significant digits, I still have only 210 cows?

[quote="wizard2378"]Leaving the rounding to the end isn't what the site you cited suggested,  ....[/quote]The site I gave as a reference (a prof. at U. South Carolina) stated
"In a long calculation involving mixed operations, carry as many digits as possible through the entire set of calculations and then round the final result appropriately."

A boy visiting a natural history museum with his dad says "That dinosaur skeleton is five million and one years old."
"How do you know?" asks the father.
"Because I heard the museum lady said it was five million years old when I was here with my school last year."

Again, I didn't say that this technique is perfect.  I do know that it is the rounding consistently required by the government in turning in calculation as to amounts of chemicals.

You are welcome to come up with whatever methods you want and some teachers, including professors in highly rated colleges have different methods that they personally prefer.

Any method has its shortcomings, if I were teaching a class that emphasized a shortcoming of a particular method, I might change the method to apply appropriately to the specifics I was teaching.

"The first division should result in 3 significant figures. The last division should result in 2 significant figures. The three numbers added together should result in a number that is rounded off to the last common significant digit occurring furthest to the right; in this case, the final result should be rounded with 1 digit after the decimal."  This is the part of the cited article that doesn't say to use all the digits in the calculator until the end.

(This technique does make grading and finding errors, if one wants to comment on individual answers easier.  Students can also get through more examples and this probably looks better on standardized testing of the teacher's ability to teach.)

Without wanting to start additional concern, I note in passing that the warning is against rounding in the middle of what is a single logical calculation, even though it is composed of many individual additions, multiplications and divisions.  Proper data error treatment for curve fitting is not done with the technique of significant digits, it is done separately from the curve fitting.

I would handle the cow example with a one step advance to the significant digits treatment, grouping all things that I was adding in groups according to the least significant digit, combine them, then add to the term with the next greatest least significant digit.  If I got ten individual cows (more than 5 - or five if even) then I would go to 210, otherwise stay at 200.

The major flaw that this technique is used to eliminate isn't one that is the focus of the discussion.  One can't eyeball a water flow in the middle of a rain event as about 5 gallons per minute, use the inspection sheet on a half hour rotation for the start time and end time for the rainwater flow report the amount of water that flowed through a rainwater ditch as 4,328 gallons.

Could anyone explain why would people stipulate rules for significant figures (eg for addition, multiplication, etc) the ways they are?

Well, the only completely accurate way to do it (assuming that the decimal rounding of every initial number was done correctly), is to say that the result is between
\[ \frac{2.5255}{3.15}\plus{}\frac{0.4695}{0.6235}\plus{}\frac{80.7045}{0.43265}\approx 188.09005\dots\]
and
\[ \frac{2.5265}{3.05}\plus{}\frac{0.4705}{0.6225}\plus{}\frac{80.7055}{0.43255}\approx 188.16492\dots\]
which means that after rounding to the first decimal place it can be both $ 188.1$ and $ 188.2$, or, in other words, $ 188$ is where the significant digits end.

All the "rounding rules" are invented for those who have trouble with the concept of two-sided inequalities and are "rules of thumb" rather than universal recipes. The one that tells you to postpone rounding to the end is based on the idea that the answer that you get this way is, at least, always feasible though it may be not very clear what the precise interval of uncertainty is (to determine the latter with reasonable precision for long expressions, you need to think in terms of absolute and relative errors rather than in terms of "significant digits").


Let (a x b x c) + (a + b + c) = 341 be an equation where a, b and c
are consecutive positive integers. What is the value of a?

 :help:

[quote="FullMetalNaruto"]Let $ abc \plus{} a \plus{} b \plus{} c \equal{} 341$ be an equation where $ a, b$ and $ c$ are consecutive positive integers. What is the value of $ a$?[/quote]

Let $ b$ be the middle number, without loss of generality, to get $ (b\minus{}1)(b)(b\plus{}1)\plus{}(b\minus{}1)\plus{}b\plus{}(b\plus{}1)\equal{}341 \Rightarrow
b(b^{2}\plus{}2)\equal{}341$. This equation has no integer solutions...

are you sure that the question is right?

If they are indeed consecutive, (a,b,c)=(5,6,7) is

$ 5\cdot6\cdot7\plus{}5\plus{}6\plus{}7\equal{}210\plus{}18\equal{}228$, which is too low, but (6,7,8) is

$ 6\cdot7\cdot8\plus{}6\plus{}7\plus{}8\equal{}338\plus{}21\equal{}359$, which is too high.

(abc)/(a+b+c)=341

if a,b,c are consecutive integers, what is a?

I'm pretty sure [i]that's[/i] the right question.

[quote="FullMetalNaruto"]
Given $ \frac{abc}{a\plus{}b\plus{}c}\equal{}341$

If $ a,b,c$ are consecutive integers, what is $ a$?
[/quote]
[hide="Solution"]
Without loss of generality, let $ b$ be the middle number.

Then, $ \frac{(b\minus{}1)(b)(b\plus{}1)}{(b\minus{}1)\plus{}b\plus{}(b\plus{}1)}\equal{}341 \Rightarrow (b\minus{}1)(b\plus{}1)\equal{}1023 \Rightarrow$

         $ (b\minus{}32)(b\plus{}32)\equal{}0 \Rightarrow b\equal{}32$.

Presuming $ a$ is the smallest integer (never explicitly stated), $ a\equal{}b\minus{}1\equal{}\boxed{31}$.
[/hide]

[hide="Or be lazy... like me!"]$ \frac{(b\minus{}1)b(b\plus{}1)}{(b\minus{}1)\plus{}b\plus{}(b\plus{}1)} \equal{} 341 \implies \frac{b(b\minus{}1)(b\plus{}1)}{3b} \equal{} 31 \times 11 \implies$

$ (b\minus{}1)(b\plus{}1) \equal{} 31 \times 33$

From here, it's pretty easy to realize that $ b$ is $ 32$.[/hide]


Let a,b,c be positive real numbers with \[ \mathop a\nolimits^{\frac{3}{2}}  \plus{} \mathop b\nolimits^{\frac{3}{2}}  \plus{} \mathop c\nolimits^{\frac{3}{2}}  \equal{} 3
\]
prove that
\[ \mathop {\left( {a \plus{} b} \right)}\nolimits^3  \plus{} \mathop {\left( {b \plus{} c} \right)}\nolimits^3  \plus{} \mathop {\left( {c \plus{} a} \right)}\nolimits^3  \le 24
\]

[quote="csbonny"]Let a,b,c be positive real numbers with
\[ \mathop a\nolimits^{\frac {3}{2}} \plus{} \mathop b\nolimits^{\frac {3}{2}} \plus{} \mathop c\nolimits^{\frac {3}{2}} \equal{} 3
\]
prove that
\[ \mathop {\left( {a \plus{} b} \right)}\nolimits^3 \plus{} \mathop {\left( {b \plus{} c} \right)}\nolimits^3 \plus{} \mathop {\left( {c \plus{} a} \right)}\nolimits^3 \le 24
\]
[/quote]
Let $ a \equal{} x^2,$ $ b \equal{} y^2$ and $ c \equal{} z^2,$ where $ x,$ $ y$ and $ z$ are positive numbers. Then
$ \mathop {\left( {a \plus{} b} \right)}\nolimits^3 \plus{} \mathop {\left( {b \plus{} c} \right)}\nolimits^3 \plus{} \mathop {\left( {c \plus{} a} \right)}\nolimits^3 \le 24\Leftrightarrow8(x^3 \plus{} y^3 \plus{} z^3)^2\geq3\sum_{cyc}(x^2 \plus{} y^2)^3\Leftrightarrow$
$ \Leftrightarrow\sum_{cyc}(2x^6 \minus{} 9x^4y^2 \minus{} 9x^4z^2 \plus{} 16x^3y^3)\geq0\Leftrightarrow\sum_{cyc}(x \minus{} y)^4(x^2 \plus{} 4xy \plus{} y^2)\geq0.$


In an isosceles trapezoid, the bases equal 2 and 14 and the lateral sides equal 10. Find the length of the circumradius of of the trapezoid.

The diagnols are equal. put ptolemy's theorem to find out the diagnol. use the following relation on any one of the 4 triangles obtained
$ Area\equal{} \frac {abc}{4R}$


inequalities
number theory
prime factorization

Hi Guys

Can someone tell me what is a optimal solution and can someone give me an example of a optimal solution.

heres what i got so far.

Optimal solution: In the context of the Optimizer, the optimal solution is the one with the lowest cost or highest return from among the set of scenarios analyzed by the Optimizer. Optimal solution  which only uses a minimum possible number of moves.

That's correct. In a mathematical context, if you have a bunch of inequalities, such as

$ x \geq 40$
$ y < 400+x$
$ x+y < 1000$

and a third inequality such as $ C = 5x+4y$, the most optimized answer would be to have the highest (or lowest) value of $ x$ and $ y$ possible satisfying the conditions, such as to maximize (or minimize) the value of C.

Hi Prime factorization

Thanks for the example but I find that example to hard to understand.

Ive just started my course im doing maths computing so far Ive learnt the travling sales man problem sudoku problems.

Could you please give me an example with the op to do with problems similer like i have learnt please.

Thanks Alot

Steve

Ok then. I'll make it nice and simple I suppose.

Jimmy Neutron wants to have a party, so he's going to need lots of food. He will need to buy at least 30 pineapples and 20 blueberries. The total amount of fruit purchased cannot exceed 100. If Jimmy Neutron loses 5 cents for every pineapple purchased and 2 cents for every blueberry purchased, what is the least amount of money he could lose while still being able to hold a party?

I'm sorry if the problem's really cheesy, I can find exam questions based on this topic if that helps.

Hi Prime factorization

[quote]I'm sorry if the problem's really cheesy, I can find exam questions based on this topic if that helps.[/quote]

If you dnt mind could you post a exam question based on this topic and please explain the answer to the problem. Its just hard looking for a true example of Optimal solution I really want a gud simple example soo I can understand it properly soo I can know what it is :(

Check the link here [url]http://ltm.swlauriersb.qc.ca/Subjects_Courses/Mathematics/FinalExams/pdfExams/536/S5685362003.pdf[/url] try numbers 11 and  16 on pages 23 and 25. The document also contains an answer guide for the long answer questions. If you're still having trouble, feel free to ask any questions.

The answer to question 11 is not given but the answer to question 16 is on page 8.

Hi Prime factorization

Thanks for your help. Looked at those examples and understand OP alot better :roll:


As the title says, if I dont have math in my schedule this year, is that going to make me look bad on college applications? My math teacher urged me to take some math.

I didn't have any math my senior year.  I tried to take a class at the local college, but the schedule just wouldn't work.  I'd suggest taking one if you can, but it shouldn't kill your application if you don't (explaining why you didn't take a math in your application would help even more).

You should have a good explanation for not taking math, and a good math background before you take the year off. But if, for example, you worked really hard on your English and your other subjects after getting ahead of most of your age mates in math, that shouldn't be a big problem.

i finished calc bc and am doing stat on my own.
thanks


What is the sum of the reciprocals of the distinct positive factors of 8? Express your answer as a mixed number.


Hey everyone. I just had a couple of questions regarding circuits. I would appreciate any feedback or hints or whatever. Thank you in advance.

3) The potential difference between the plates of a leaky (meaning that charge leaks from one plate to the other) 2.0 µF capacitor drops to one-fourth its initial value in 2.6 s. What is the equivalent resistance between the capacitor plates?

Thanks again!

[quote]2) In Fig.2 below, R1 = 150 W, R2 = R3 = 60.1 W, R4 = 84.1 W, and the ideal battery has emf ε = 6.0 V. (a) What is the equivalent resistance? What is i in (b) resistance 1, (c) resistance 2, (d) resistance 3, and (e) resistance 4?[/quote]
[img]http://photo-origin.tickle.com/image/75/0/2/O/75021065O375327223.jpg[/img]

a)$\large R=R_1+R'=R_1+\frac{1}{\frac{1}{R_2}+\frac{1}{R_3}+\frac{1}{R_4}}$

b)$\large I=I_1=\frac{\varepsilon}{R}$

c)$\large I_2=\frac{IR'}{R_2}$

d)$\large I_3=\frac{IR'}{R_3}$

e)$\large I_4=\frac{IR'}{R_4}$

[quote]4) (a) In Fig. 4 below, what value must R have if the current in the circuit is to be 1.4 mA? Take ε1 = 1.5 V, ε2 = 3.2 V, and r1 = r2 = 3.9 W. (b) What is the rate at which thermal energy appears in R? [/quote]
[img]http://photo-origin.tickle.com/image/75/0/2/O/75021077O638597842.jpg[/img]
[color=blue]
a)$\large I=\frac{\varepsilon_2-\varepsilon_1}{r_1+r_2+R}\Longrightarrow R=r_1+r_2-\frac{\varepsilon_2-\varepsilon_1}{I}$

b)$P=I^2R$[/color]

Thank you very much. I had a similar answer, I just made a stupid arithmetic mistake.

Does anyone know how to solve problems 1 or 3?? I'd appreciate any help. Thanks.

3) The potential difference between the plates of a leaky (meaning that charge leaks from one plate to the other) 2.0 µF capacitor drops to one-fourth its initial value in 2.6 s. What is the equivalent resistance between the capacitor plates?

[b]I'm still not sure how to solve numbers 3. I would appreciate any help. I have a basic idea, but i'm not sure where to go with it. Thanks.[/b]

Let $V_B = 92.8\ \text V$ be the battery voltage, $V_L = 67.4\ \text V$ the lamp breakdown voltage, $Q(t), V(t)$ charge and voltage on the capacitor as functions of time t. Choose time origin at an arbitrary lamp flash. Let $t_F = 0.25\ \text{sec}$ be the time interval to the next flash. The current $I(t)$ through the resistor R as a function of time is $I(t) = \frac{\text dQ}{\text dt}$. The voltage on the capacitor is

$V(t) = \frac{Q(t)}{C} = V_B - IR = V_B - \frac{\text dQ}{\text dt}\ R$

This is a simple 1st order differential equation for the charge Q(t):

$\frac{\text dQ}{\text dt} + \frac{Q}{RC} = \frac{V_B}{R}$

Since $Q(t) = CV_B = \text {const}$ obviously is a particular solution (because then $\frac{\text dQ}{\text dt} = 0$), the general solution is

$Q(t) = CV_B + K \exp\left(-\frac{t}{RC}\right)$

where K is an arbitrary constant. Since we have Q(t) = 0 at t = 0, $K = -CV_B$ and

$Q(t) = CV_B \left[1 - \exp\left(-\frac{t}{RC}\right)\right]$

$V(t) = \frac{Q(t)}{C} = V_B \left[1 - \exp\left(-\frac{t}{RC}\right)\right]$

Substituting $V(t) = V_L$ and $t = t_F$ for the next flash, we get an equation for R:

$V_L = V_B \left[1 - \exp\left(-\frac{t_F}{RC}\right)\right]$

$R = \frac{t_F}{C \ln \frac{V_B}{V_B - V_L}}$

Thanks for your help. I got caught up with what to do with the time, but that was smart how you set tf to 0.25 seconds. I really appreciate your help.

Do you (or anyone else) by any chance know how to answer this question as well?

3) The potential difference between the plates of a leaky (meaning that charge leaks from one plate to the other) 2.0 µF capacitor drops to one-fourth its initial value in 2.6 s. What is the equivalent resistance between the capacitor plates?

First, please do not delete problems once the solutions are posted. Second, you should be able to solve problem 3, it is very similar to (and a little bit simpler than) problem 1. At least try to post a solution. If not correct, someone will point out the errors.

The reason I havent posted a solution is because I do not know how to post them with subscripts and superscripts and fraction bars, etc. etc. I am new to the boards.

Also, I was unaware that questions should not be deleted once they are answered. Sorry.

But yea, when you post the solutions I just compare it to what I have written down and see if they differ.

Thanks, sorry for the misunderstanding.

Read this post: [url=http://www.mathlinks.ro/Forum/viewtopic.php?t=5261]www.mathlinks.ro/Forum/viewtopic.php?t=5261[/url] and download the pdf LATEX help attachment. Then try to post some arbitrary math expressions, such as fractions, variables with indices, or equations, in the [url=http://www.mathlinks.ro/Forum/index.php?f=224]Test Forum[/url]. You can also "spy" on other people's single line equations by double-clicking them, pasting them into your posts and enclosing between the dollar signs.

If you keep posting problems that look like homework without any work shown, you may get the benefit of doubt a few more times, but eventually people will stop replying.

The leaky capacitor with capacitance C can be replaced by an ideal capacitor of the same capacitance and some resistor R in parallel. The voltage on the capacitor and resistor are the same, hence,

$V = \frac{Q}{C} = IR$

But $I = -\frac{\text dQ}{\text dt}$. The negative sign is used to express the fact that the charge on the capacitor is decreasing, while the current flows from the positive to the negative plate through the parallel resistor. Therefore,

$\frac{Q}{C} = -\frac{\text dQ}{\text dt}\ R$

$\frac{\text dQ}{\text dt} + \frac{Q}{RC} = 0$

This is a homogenous 1st order differential equation with constant coefficients, with a general solution

$Q(t) = K \exp\left(-\frac{t}{RC}\right)$

where K is an arbitrary constant. Since at the time t = 0, $Q_0 = Q(0) = CV(0) = CV_0$, where $V_0 = V(0)$ is the initial voltage on the capacitor, $K = Q_0 = CV_0$ and

$Q(t) = CV_0 \exp\left(-\frac{t}{RC}\right)$

$V(t) = \frac{Q(t)}{C} = V_0 \exp\left(-\frac{t}{RC}\right)$

At the time $t_1 = 2.6\ \text{sec}$, the initial voltage $V_0$ drops to $V_1 = V(t_1)$ such that $\frac{V_1}{V_0} = \frac 1 4$

$\frac{V_1}{V_0} = \exp\left(-\frac{t_1}{RC}\right) = \frac 1 4$

which gives an equation for the resistance R:

$R = \frac{t_1}{C \ln 4} = \frac{t_1}{2C \ln 2}$

Thanks..

Not all of the questions which I post to begin with are HW problems. Like I said I am new to this board and just trying to learn physics and compare what I have written down to what someone else may think. When I am assigned HW, my teachers even say we can compare answers with others, so that is what I am doing.

I will download that program you sent me and see how it is.

Even if I was fooling myself and had no idea what was going on, I would be screwed come the day of the test - so I assure you that I do indeed work out the problems, I just have trouble finnishing them. However, I feel that the more problems you practice, the better you will do in the future.

So thank you for your help, and I am sorry for the missconfusion.


trigonometry
analytic geometry
geometry
circumcircle

[quote="Mark1"]Hi.  I have the following trig question, that I hope someone can assist me with.

When graphed using polar coordinates, the center of a regular nonagon is at the origin and one vertex is at (6, 0 degrees) or (6, 0 radians).

I want to find the polar coordinates of the other vertices in both degrees and radians.

You will need polar coordinate graph paper.

Thank you.[/quote]
You won't need polar graph paper at all.
Draw the circumcircle, with radius $6$ and center $(0,0)$ (as given). Then, since it is regular, it will hit the nonagon [i]regularly[/i] nine times after going through $2\pi$. Thus each vertex's angle can be written as $\frac{360^\circ k}{9}=40^\circ k$, with $k = 0,1,2...8$ All points will have the radius of the circumcenter, $6$.

Thank you, Cinco.  Brilliant you are.

 :)

[quote="Mark1"]Thank you, Cinco.  Brilliant you are.

 :)[/quote]

No prob :)


ceiling function
combinatorics proposed
combinatorics

Determine the largest positive integer $ N$ such that for every way putting all numbers from 1 to 400 into a $ 20 x 20$ table (1 number per cell) one can always find row or a column having two numbers with difference not less than $ N$.

let $ d$ be the largest difference between two entries in the same row or column. if $ a, b$ are any two entries of the array, then by considering the differences of each of $ a$ and $ b$ and the entry $ c$ at the intersection of the column through $ a$ and the row through $ b$ we get that $ |a \minus{} b| \leq 2d$. letting $ a \equal{} 1, b \equal{} 400$ shows that we can guarantee $ d \geq \lceil 399/2 \rceil \equal{} 200$.

OK This proves that $ N\geq 200$ Please, can anybody construct table with these properties such that difference between any two numbers in same column or row is less than 201.

[quote="madshiet"]Привет!
Все-таки непонятно нам, как вы пришли к этой точке в этом и применения веб-сайтов. Вы, как писать о себе недостаточно, чтобы мы, которые умирают от удивительно, что ли, кто вы, не может узнать о вас. Вы пользующиеся с народом? Это уже смешно? Эй вы знаете, я пришел на ваш веб-сайт, поскольку я был поиска некоторые программы для покупки бесплатно или дешево, но после этого я увидел здесь скандал, я преодолев мое мнение мечты? Растите деятельности.[/quote]
На каком языке ты говоришь?Если ты не знаешь русский,то и писать на нем не надо,а то получается какая-то чушь(без обид),и если решился использовать русский то пиши на нем либо через pm либо в national forum.

Please can you write in English (go to national forum if you want to write in Russian)

Can anybody finish this problem.

I told him to go to national forum. :wink:


inequalities
trigonometry
inequalities unsolved

Let $a,b,c$ are positive reals so that $a+b+c=abc$.Prove that:
$\frac{\sqrt{2a^2+b^2}}{ab}+\frac{\sqrt{2b^2+c^2}}{bc}+\frac{\sqrt{2c^2+a^2}}{ca}\geq\sqrt{3}$

Oke, it's really easy.
We have, from $a+b+c=abc\Rightarrow\frac{1}{ab}+frac{1}{bc}+\frac{1}{ca)=1$.
Rewrite inequality as following:
$\sqrt{\frac{2}{a^2}+\frac{1}{b^2}}+\sqrt{\frac{2}{b^2}+\frac{1}{c^2}}+\sqrt{\frac{2}{c^2}+\frac{1}{a^2}}\geq\sqrt{3}$

Oke, it's really easy.
We have, from $a+b+c=abc \Rightarrow\frac{1}{ab}+\frac{1}{bc}+\frac{1}{ca}=1$.
Rewrite inequality as following:
$\sqrt{\frac{2}{a^2}+\frac{1}{b^2}}+\sqrt{\frac{2}{b^2}+\frac{1}{c^2}}+\sqrt{\frac{2}{c^2}+\frac{1}{a^2}}\geq\sqrt{3}$
On the other hand:
$\sqrt{\frac{2}{a^2}+\frac{1}{b^2}}+\sqrt{\frac{2}{b^2}+\frac{1}{c^2}}+\sqrt{\frac{2}{c^2}+\frac{1}{a^2}}\geq\sqrt{\sqrt{2}.\left(\frac{1}{a}+\frac{1}{b}+\frac{1}{c}\right)^2+\left(\frac{1}{a}+\frac{1}{b}+\frac{1}{c}\right)^2}$
$\geq\sqrt{(\sqrt{2}+1).3\left(\frac{1}{ab}+\frac{1}{bc}+\frac{1}{ca}\right)}>\sqrt{3}$

$\sum_{cyc} \frac{\sqrt{2a^2 + b}}{ab} =\sum_{cyc}\sqrt{\frac{1}{b^2} + \frac{1}{b^2} + \frac{1}{a^2}} \ge (*) \sum_{cyc} \frac{\frac{1}{b} +\frac{1}{b} + \frac{1}{a}}{\sqrt3}= \sqrt 3 \cdot (\frac{1}{a} + \frac{1}{b} + \frac{1}{c})$

$(*)$ Cuadratic Mean $\ge$ AM

Now from the condition $a+b+c=abc$ we can make the substitution $a=\tan{\alpha}$ , $b=\tan {\beta}$ and $c=\tan {\gamma}$. For $\alpha , \beta \text{and} \gamma$ the angles of an acute  triangle.
Now we got that:
$\sqrt 3 \cdot (\frac{1}{a} + \frac{1}{b} + \frac{1}{c}) = \sqrt 3 \cdot \left(\cot{\alpha} + \cot{\beta} + \cot {\gamma}\right) \ge (**) \sqrt 3\cdot 3 \cdot {\cot {\frac{\alpha + \beta + \gamma}{3}}} = 3 >\sqrt 3$

(**) is Jensen's inequality.

QED ;)

A similar problem, http://mathlinks.ro/Forum/viewtopic.php?t=88771


Why is this a thread? How did it get that meaning?

I don't see what you are trying to say with your answer.


Prove that cos11+ cos83+ cos155+ cos227+ cos299=0,where angles are measured in degrees

Let $ w \equal{} \cos 11 \plus{} i \sin 11$, and let $ z$ be the fifth root of unity. The problem is equivalent to showing that $ \text{Re}(w \plus{} wz \plus{} wz^2 \plus{} wz^3 \plus{} wz^4) \equal{} 0$, which is obvious since $ 1 \plus{} z \plus{} z^2 \plus{} z^3 \plus{} z^4 \equal{} 0$.

Rewrite it as: (cos11+cos299)+(cos83+cos227)+cos155 and then use (cosA+cosB=...)


Find all solution of natural number $ (a,b)$ such that $ 6a(12a\plus{}1)\equal{}b(b\plus{}1)$.

there isnt any solution in natural numbers,i think

Anni: try $ a\equal{}58$, $ b\equal{}492$.  Aadil: if that is the condition, then I wasted alot of time on this problem.

Well, the subject of the topic states that $ \gcd (a,b)\equal{}1$ after all.
The author should have clarified the problem clearly.

Btw, how did you find that solution, joeislittle? :o  :huh:

[quote="dyd"]Find all solution of natural number $ (a,b)$ such that $ 6a(12a \plus{} 1) \equal{} b(b \plus{} 1)$.[/quote]

$ b\equal{}\frac{\minus{}1 \pm \sqrt{(12a)^2\plus{}(12a\plus{}1)^2}}{2}$

So for $ a$ there exists integer $ b$ satisfies the equation

$ \Leftrightarrow 12a\equal{}2mn, 12a\plus{}1\equal{}m^2\minus{}n^2$ (Pythagoras Triples)

Mod $ 3$ and then $ 4$ we get $ 6|n$ $ \Leftrightarrow n\equal{}6k$, for an integer $ k$

So the equation $ \Leftrightarrow (m\minus{}6k)^2\minus{}72k^2\equal{}1$, which is Pell's equation.

The fundamental solution $ \begin{cases} m\minus{}6k\equal{}17 \\ k\equal{}2 \end{cases}$

gives $ a\equal{}mk\equal{}58$ and $ b\equal{}492$, which is the solution given by [b]joeislittle[/b].
And there are infinitely many such solutions.

If $ \gcd(a,b)\equal{}1$ is provided, then $ a|b\plus{}1$ and $ 8a< b\plus{}1 < 10a$, which gives $ b\plus{}1\equal{}9a$

But $ b\plus{}1\equal{}9a \Rightarrow 6a(12a\plus{}1)\equal{}(9a\minus{}1)(9a) \Leftrightarrow 15a\equal{}9a^2 \Leftrightarrow 5\equal{}3a$, contradiction.
So there are no such solution if $ \gcd(a,b)\equal{}1$ is provided.

I'm sorry for the unclarity.. The subject actually refers to $ (6a,12a\plus{}1)$ and $ (b,b\plus{}1)$ anyway :blush:
And yeah, my solution is also based on Pell..

If you're interested, this problem is compiled when I was working on this problem :

Find all prime $ p$ such that these equations simultaneously have solution in natural numbers :
$ 7p \equal{} 8x^2 \minus{} 1$ and $ p^2 \equal{} 2y^2 \minus{} 1$

Sorry if this is a repost.

[hide]The only solution is p=41. An elementary proof can be given as follows:
 p^2-7p=2(2x+y)(y-2x) {1}. For p=2,3,5,7 we can easily see that we don't get any solution. So p>7 and p^2-7p>0. Thus, we get y>2x. But: p^2=2y^2-1>y^2. So p>y and y-2x<y<p. So p cannot divide y-2x, but neither 2. From {1} we get that p divides y+2x<2y<2p. So we must have y+2x=p and the problem is now less than trivial. [/hide]

[quote="panos_lo"]An elementary proof can be given as follows..[/quote]

yeah,, this original problem doesn't need Pell at all (even Pell can't help anything, I think). Motivated by [b]stephencheng[/b]'s solution, I've create another problem which is a special case from this problem (which I can't solve it by myself):

Find all natural $ k$ such that there exist relativelye prime natural numbers $ a,b$ satisfy

\[ ka(2ka\plus{}1)\equal{}b(b\plus{}1)\]

[quote="dyd"]Find all natural $ k$ such that there exist relativelye prime natural numbers $ a,b$ satisfy
\[ ka(2ka \plus{} 1) \equal{} b(b \plus{} 1)
\]
[/quote]

$ a|b\plus{}1 \Rightarrow b\plus{}1\equal{}xa$ for some positive integer $ x$.

So the equation $ \Leftrightarrow ka(2ka\plus{}1)\equal{}xa(xa\minus{}1)$
$ \Leftrightarrow k\plus{}x\equal{}(x^2\minus{}2k^2)a$
$ \Rightarrow$ Sufficent and necessary condition for existance of solutions is  $ (x^2\minus{}2k^2)|k\plus{}x$

$ \Leftrightarrow (x^2\minus{}2k^2)|\gcd(x^2\minus{}2k^2,k\plus{}x)\equal{}\gcd(k^2,k\plus{}x)\equal{}\gcd(x^2,k\plus{}x)$

So $ (x^2\minus{}2k^2)| \gcd(k^2,x^2)\equal{}[\gcd(k,x)]^2$

Now let $ m\equal{}\gcd(k,x)$ and $ x\equal{}mx_1, k\equal{}mk_1$ it becomes:

$ x_1^2\minus{}2k_1^2\equal{}1$

And the sufficient and necessary condition becomes $ m^2(x_1^2\minus{}2k_1^2)|\gcd(m^2k_1^2,m(k_1\plus{}x_1))$
$ \Leftrightarrow m|\gcd(mk_1^2,k_1\plus{}x_1) \Leftrightarrow m|k_1\plus{}x_1$

So the possible $ k$s are $ mk_1$, where $ k_1$ is any solution of the Pell's equation $ x_1^2\minus{}2k_1^2\equal{}1$

and $ m$ is any positive factor of the respective $ (x_1\plus{}k_1)$.

[quote="stephencheng"]
Now let $ m \equal{} \gcd(k,x)$ and $ x \equal{} mx_1, k \equal{} mk_1$ it becomes:

$ x_1^2 \minus{} 2k_1^2 \equal{} 1$[/quote]

Sorry but I can't see how you get it.. Can you give me the details?

[quote="dyd"][quote="stephencheng"]
So $ (x^{2}\minus{}2k^{2})|[\gcd(k,x)]^{2}$
Now let $ m \equal{} \gcd(k,x)$ and $ x \equal{} mx_1, k \equal{} mk_1$ it becomes:

$ x_1^2 \minus{} 2k_1^2 \equal{} 1$[/quote]

Sorry but I can't see how you get it.. Can you give me the details?[/quote]

$ (x^{2}\minus{}2k^{2})|[\gcd(k,x)]^{2}$
$ \Leftrightarrow (m^2x_1^2\minus{}2m^2k_1^2)|m^2 \Leftrightarrow (x_1^2\minus{}2k_1^2)|1$

with $ x^2\minus{}2k^2>0$ gives $ x_1^2\minus{}2k_1^2\equal{}1$


The Vikings raid one of 20 coastal cities in Scotland at random every month. A lord has recently gained control of six of these cities. One month, he receives word from two that they have not been raided. What is the probability that none of his six cities were raided that month?

Let the probability be a/b.  Find a*b.

There are 14 cities that are not his, so the probability that none of his cities were raided is $ \frac{14}{20} \cdot \frac{13}{19} \equal{} \frac{91}{190}$. Thus the answer is $ 91 \times 190 \equal{} \boxed{17290}$.

Not true.

$ (14*13)/(18*17)$

13923.

Note that he knows that 2 were not raided.

So then the odds are 14/18=7/9 so 63. There are 18 left and they have an equal chance of raiding each one.


[quote="the game"]So the problem is now to prove
 $a/(b+c)+b/(a+c)+c/(a+b)\geq 3/2$
But how do i do it?[/quote]
For example:
$\frac{a}{b+c}+\frac{b}{a+c}+\frac{c}{a+b}=\frac{a^{2}}{ab+ac}+\frac{b^{2}}{ab+bc}+\frac{c^{2}}{ac+bc}\geq$
$\geq\frac{(a+b+c)^{2}}{ab+ac+ab+bc+ac+bc}\geq\frac{3}{2}.$ :wink:

[quote="the game"]So the problem is now to prove
 $a/(b+c)+b/(a+c)+c/(a+b)\geq 3/2$
But how do i do it?[/quote]

its called nesbitt's inequality and its a well known one. you can find the proof in most inequality books.


I saw these relationships listed in my math book:

$ \mathrm{arccsc}\, x \equal{} \arcsin(1/x) \\
\mathrm{arcsec}\, x \equal{} \arccos(1/x) \\
\mathrm{arccot}\,x \equal{} \frac{\pi}{2}\minus{}\arctan x$

Can someone verify these?

Thanks.

Undo the inverses. They become common identities.

For example, take the

csc of both sides for #1

sec of both sides for #2

cot of both sides for #3

You know that sin=1/csc, so...

Or am I failing at trig again, and this doesn't help?

[quote="tornado.adv4"]What do you do once you have x = csc (arsin (1/x) )?
Is there an identity for that?[/quote]
Draw the unit circle and the appropriate right triangle for that and you'll see it immediately :)
Set $ arcsin(1/x)\equal{}\theta$ and this means that $ sin(\theta)\equal{}1/x$. Recall that sin is opposite/hypotenuse. Then if you draw a right triangle, labeling one of those angles(other than the right angle) as theta, label the opposite leg 1 and the hypotenuse as x. This means the leg adjacent to theta is $ \sqrt{x^{2}\minus{}1}$. Therefore $ csc(arcsin(1/x))\equal{}csc(\theta)$. Since csc x is 1/sin x, that means csc is hypotenuse/opposite, which means $ csc(\theta)\equal{}x$.

Thanks!
But how do you do it for arccot x = pi/2 - arctan x?

Take $ \tan$ of both sides.

$ \frac{1}{\cot(\arccos x)}=\frac{1}{x}=\tan\left(\frac{\pi}{2}-\arctan x\right)=\frac{\tan\frac{\pi}{2}+x}{1+x\tan\frac{\pi}{2}}$

That last thing is... well, $ \frac{\infty}{\infty}$, so I suppose you'd take the limit.

$ \lim_{\theta\to\frac{\pi}{2}}\frac{\tan \theta+x}{1+x\tan\theta}=\lim_{\theta\to\frac{\pi}{2}}\frac{\sec^2\theta}{x\sec^2\theta}=\frac{1}{x}$.

Sorry for the L'Hopital's; someone probably has a better way.

Using L'Hopital's here probably means there is another way to simplify it. Notice that you could also take the sin, cos, and tan for the 3 problems, respectively.

Haha, there's an obvious non-L'Hopital's solution that I somehow missed.

$ \lim_{\theta\to\frac{\pi}{2}}\frac{\tan\theta\plus{}x}{1\plus{}x\tan\theta}\cdot\frac{\cot\theta}{\cot\theta}\equal{}\lim_{\theta\to\frac{\pi}{2}}\frac{1\plus{}x\cot \theta}{\cot\theta\plus{}x}\equal{}\frac{1}{x}$


[hide]The probability that you don't roll a 4 or 5 the first time is $\frac 23$. Same for the second time. ${\frac 23 * \frac 23 = \boxed{\frac 49}}$[/hide]

[quote="236factorial"]I roll a dice twice. What is the probability I will not roll a 4 or 5? Express your answer as a common fraction.[/quote]

[hide]
The probability that I will roll a 4 or 5 on the first roll is #{1,2,3,5,6}/#{1,2,3,4,5,6}=4/6.
Same thing for the second roll, so we get (4/6)^2=4/9.
[/hide]

[hide]The probability of not getting a 4 or 5 in a roll is $\frac23$  (4 out of the 6 numbers aren't 4 or 5).  That means that the probability of not getting a 4 or 5 in 2 rolls is $\frac23^2=\frac49$[/hide]

[hide]This is a problem that i might be able to answer!!!! :D  :D
Assuming that there are 6 numbers on the dice, the probability of rolling a 4 or a 5 is 2/3.  So 6/6-2/3=4/6=2/3.  since you are rolling 2 dice you do: 2/3*2/3 which is $\boxed{\frac{4}{9}}$[/hide]

[hide]
There is a $\frac{2}{3}$ of a chance for both rolls.
So, the answer is $\frac{2}{3}^2=\boxed{\frac{4}{9}}$[/hide]


Starting from the numbers$ 1, \frac{1}{2},\frac{1}{3},.........,\frac{1}{100}$
 the following operation is performed until only one number remains: Choose two numbers, say a and b, and replace them with a + b + ab. Determine the remaining number.

If we amalgamate $n$ numbers $a_1,a_2,\cdots,a_n$ by this method, it is easy to confirm (by induction) that we get $\displaystyle\prod_{i=1}^n(a_i+1) - 1$.

Since this is independent of the order of the $a_i$, we may assume that we amalgamate the numbers in increasing order (i.e. $1$ with $2$, the result of this with $3$ etc.).  But since the product $\displaystyle\prod_{i=1}^n\frac{n+1}{n}$ telescopes to $n+1$, with $n=100$ we get $\displaystyle\prod_{i=1}^{100}(\frac{1}{i}+1) - 1=101-1=100$.

What is this?
$\displaystyle\prod_{i=1}^n(a_i+1) - 1$.

[quote="cyberjoe"][tex]\prod_{i=1}^n(a_i+1) - 1=(a_1+1)(a_2+1)...(a_n+1)-1[/tex][/quote]
I know very well this I  mean what is the expression of this.Do you understand me?