floor function
induction
combinatorics proposed
combinatorics
boolean lattice method

Let $ S$ be a set with $ n$ elements, and $ F$ be a family of subsets of $ S$ with $ 2^{n\minus{}1}$ elements, such that for each $ A,B,C\in F$, $ A\cap B\cap C$ is not empty. Prove that the intersection of all of the elements of $ F$ is not empty.

Let $ [n] \equal{} 1,\dots,n$ and $ P([n])$ denote the power set of $ [n]$. A subset $ S$ of $ P([n])$ is said to be good if for any $ A,B,C \in P([n]),\quad A\cap B\cap C$ is non empty. If $ A\in S$ then $ [n]\backslash A \notin S$. I shall prove that a good subset of $ P([n])$ of size $ 2^{n \minus{} 1}$ must contain a singleton. This is equivalent to prove that $ A_1\cap A_2 \dots A_{2^{n \minus{} 1}}$ is non empty where $ A_i$ are elements of a good subset of $ P([n])$.

Let us on contrary assume that there exists a good subset of $ S$ of $ P([n])$ of size $ 2^{n \minus{} 1}$ and without a singleton. $ S$ contains all the subsets (of $ P([n])$) of cardinality $ n \minus{} 1$. Consider the fact
$ \{1,2,\dots,n \minus{} 2,n \minus{} 1\}\cap\{1,2,\dots,n \minus{} 2,n\}\cap\{n \minus{} 1,n\} \equal{} \emptyset$
We can pair up every two subsets of size $ n \minus{} 1$ to conclude that $ S$ does not contain any subset of size $ n \minus{} 2$.( We can indeed go on to prove that if $ S$ contains all subsets of size $ r > \lfloor \frac {n}{2}\rfloor$ then it does not contain any subset of size $ n \minus{} r$) This would imply that $ S$ contains subsets of size $ n \minus{} 2$.

(i)	When $ n$ is odd.
$ S$ contains all subsets of size $ r > \lfloor \frac {n}{2}\rfloor$. Though $ S$ contains $ 2^{n \minus{} 1}$ elements it is not good because
$ \{1,2,\dots,\frac {n \plus{} 1}{2}\}\cap \{\frac {n \plus{} 1}{2},\dots,n\}\cap \{1,2\dots,\frac {n \minus{} 1}{2},\frac {n \plus{} 3}{2}\} \equal{} \emptyset$

(ii)	When $ n$ is even.
$ S$ contains all subsets of size $ > \lfloor \frac {n}{2}\rfloor$, $ |S| < 2^{n \minus{} 1}$.

Therefore the assumption is false and a subset $ S$ with $ |S| \equal{} 2^{n \minus{} 1}$ contains a singleton.

very nice proof Srikanth! (you have a typo at line 7, should be doesnt contain subsets of size 2) and also in the even case $ S$ may also contain subsets of size $ \frac{n}{2}$ but it is easily ruled out by similar arguments.

I have a new solution:

If X is one of the subsets, the complementar of X can not be in this family. So if X is not in the family => the complementar of X is in the family. ( because in total there are 2^n subsets and we have 2 ^(n-1) subsets => we must have one of this 2 subsets : x or complementar of x )
Let be A and B in the family. Because the complementar of the intersection of A and B can not be in the family (because it's intersection with A and B should be nonempty) => the intersection of A and B is in the family => by induction that the intersection of all the subsets must be in the family. So this intersection is non empty, because the empty subset can not be in the family.

Tell me if my solution is wrong  :blush:
 :lol:

Let $x_i=|\{j|i \in A_j\}|$ for $i=1,2,...,n$
Then we have

$\sum_{i=1}^{n} \binom{x_i}{3}=\sum_{1 \leq i <j<k \leq 2^{n-1}}|A_i \cap A_j \cap A_k|$

Because $A_i \cap A_j \cap A_k$ is not empty for $i<j<k$,we have :
$\sum_{i=1}^{n} \binom{x_i}{3} \geq \binom{2^{n-1}}{3}$

Let $M=max$  $x_i$

Then $n \binom{M}{3} \geq \binom{2^{n-1}}{3}$
=> $nM(M-1)(M-2) \geq 2^{n-1}(2^{n-1}-1)(2^{n-1}-2)$

Suppose $M<n$,then $n^2(n-1)(n-2)>2^{n-1}(2^{n-1}-1)(2^{n-1}-2)$

Replace $n-1$ by $n$,we get the ineq:

$(n+1)^2n(n-1) > 2^n(2^n-1)(2^n-2)$
=>$ n(n+1)(n^2-1) > (2^n-2)(2^n-1)2^n$ (*)

We have the following ineq for $n \geq 2$

(1) $n \leq 2^n-2$
(2) $n^2-1 \leq 2^n$

(1) and (2) imply that (*) is impossible.
So $M<n$ is wrong,implying that $M \geq n$
=> $M=n$
=> the intersection of all elements in $F$ is nonempty
And we can check the problem for the case $n=1,2,3$,which is trivial.

[quote="Love_Math1994"]Dear KDS,if we have $x_i<3$ for some i then  we don't have the formula $\binom{x_{i}}{3}$
Am I wrong?[/quote]
So then $\binom{x_i}{3}=0$  and that doesn't affect the proof :lol:

Induct on $n$.For $n=2$  if follows right away.Suppose it holds for $n$ let's prove it for $n+1$.Brake all the subsets of $[n+1]$ is two sets;one that contaion $n+1$ say $A_{n+1}$ and the ones that don't say $B$.Now if $\mid B\mid \geq 2^{n-1}$ by induction we're done immediately ,so suppose $|A_{n+1}|>2^{n-1}$.Consider set $C$ obtained from $A_{n+1}$ by throwing out $n+1$ from each set.Now we have a family of more that half subets of $[n]$ and hence in a such family we have a set and its complement say $S,S'$.Now obviously $S\cap S'=\{\}$ and hence by using the triple $(S'\cup n+1,S\cup n+1,X)$ $\forall X\in B$ we have that all elements of $B$ contain $n+1$ a contradiction and hence the desired.

[quote=rafayaashary1]Let $\mathcal{F}_n$ be the family of all subsets of $[n]$. Let $\mathcal{F}_n(k)$ be the subfamily of elements of $\mathcal{F}$ that contain $k\in[n]$. Let the family in the problem be $\mathcal{G}$. Observe the natural poset isomorphism $\mathcal{F}_n(k)\cong \mathcal{F}_{n-1}$. Let $P_n$ be the partition of $\mathcal{F}_n$ into pairs of complements. Suppose that the claim is false; that for every $k\in[n]$, there is a $S\in\mathcal{G}$ so that $k\not\in S$. Clearly $\mathcal{G}$ has at most one element from each pair in $P_n$, and since there are $2^{n-1}$ pairs in $P_n$, $\mathcal{G}$ must have exactly one element from each pair. Consider the partition of $\mathcal{F}_n(k)$ induced by the natural poset isomorphism above and $P_{n-1}$ (call it $P_n(k)\cong P_{n-1}$). Note that each pair in $P_n(k)$ intersects to form the singleton $\{k\}$. But no two elements of $\mathcal{G}$ can intersect in a singleton; otherwise we can find by hypothesis some element of $\mathcal{G}$ not containing said singleton, and the intersection of these three sets is empty, a contradiction. So there are at most $2^{n-2}$ elements of $\mathcal{G}$ in any $\mathcal{F}_n(k)$. It follows that $\mathbb P_{S\in\mathcal{G}}(k\in S)\leqslant 0.5$, and by LoE we see that $\mathbb E_{S\in\mathcal{G}}(|S|)\leqslant 0.5 n$. Now partition $\mathcal{F}_n$ into families $K_0,K_1,\dots,K_n$ where $S\in K_i\iff |S|=i$. Note that if $S\in K_i$ then the element of $\mathcal{F}_n$ paired $S$ to by $P_n$ is in $K_{n-i}$. Finally, $\mathcal{G}\cap K_i$ must respect the Erdős-Ko-Rado Theorem when $i\leqslant 0.5n$, since there are no two sets in $\mathcal{G}$ with empty intersection. But $i<0.5n\implies \tfrac{\tbinom{n-1}{k-1}}{\tbinom{n}{k}}=\tfrac{k}{n}<0.5$, so $\mathbb E_{S\in\mathbb{G}}(|S|)>0.5n$, a contradiction $\blacksquare$

[b]Remark:[/b] A bit overpowered, but oh well ¯\_(ツ)_/¯[/quote]

I am sure your solution is beautiful, but I kind of don't understand the notations. $\mathbb{P}(k\in S)$ means the probability of choosing a set $S$ that contains $k$. "LoE" is " lnearity of expectation I guess, $\mathbb{E}(|S|)$ is the expectation of the cardinality of $S$ ? and why $\mathbb{P}(k\in S)\leq 0.5\Rightarrow \mathbb{E}(|S|)\leq 0.5n$.

Because by LoE we have $\mathbb E(|S|)=\sum_{k\in [n]}\mathbb P(k\in S)\cdot 1$ :)

[b]nikolapavlovic[/b]'s solution motivates another approach: Consider the vertices of the Boolean Lattice $B_n$ where the elements are the subsets of $[n]$. Connect vertices $v_1,v_2$ if they are complementary sets or if there exists an element $k\in v_1,v_2$ and $v_i\setminus \{k\}$ and $v_2\setminus\{k\}$ are complementary with respect to $[n]\setminus \{k\}$. Effectively we have to choose $2^{n-1}$ vertices so that there is exactly one in every edge (we can show that each $k$ is contained in exactly one-half of the sets, and then it follows by pigeonholes). So it suffices to find an odd cycle in our graph. Actually we can do it and prove it by accounting for each digit in the representative binary string as in [url=https://drive.google.com/open?id=0B_QyOg5Kp1eHaUIzQmxPUG1OODg]this image[/url]. In the diagram $l_k$ is the natural complement (if it exists) wrt to the singleton $\{k\}$, and $u$ is the universal complement map.

$\textbf{Proof :}$

If sets $X$ and $[n]\setminus X$ lies in $\mathcal{F}$ then we get obvious contradiction. So from $|\mathcal{F}|=2^n/2$ we get that for any $X\in\mathcal{F}$, $[n]\setminus X\notin \mathcal{F}$. Also true reverse : for any $X\notin\mathcal{F}$, $[n]\setminus X\in \mathcal{F}$. So easy to check that if $X, Y\in\mathcal{F}$, then $\emptyset\not= X\cap Y\in\mathcal{F}$. Let $W$ be minimal set in $\mathcal{F}$, so for every $X\in\mathcal{F}$, $W\cap X\in\mathcal{F}$ and so $W\subseteq X$. $\Box$

The follow up question is: what is the minimum size of $\mathcal{F}$ such that the property given in the original problem still holds.

There is a lower bound: $|\mathcal{F}| \ge 5\times 2^{n-4} + 1$ for $n\ge 4$. For example: $\mathcal{F}'$ is collection of all subsets of the form $A\cup B$ with $A$ is a subset of at least 3 elements of $\{1, 2, 3, 4\}$ and $B$ is subset of $\{5, ..., n\}$. Then $|\mathcal{F}'| = 5\times 2^{n-4}$ and any three elements of $\mathcal{F}'$ has a common element but all elements of $\mathcal{F}'$ don't have a common element.

For $n = 4$, then the lower bound is tight. That is any collection of at least $6$ subsets of $\{1, 2, 3, 4\}$ with any three of them having non-empty intersection. then all of them have non-empty intersection.

Sorry for very poorly written solution. I was writing it up as I was solving it.
----------------------------------------------
The idea is to use the following lemma:
[color=#00f][b]Lemma:[/b][/color] Let $F$ be a family of subsets of $S$ such that for any $X,Y \in F$ satisfy that $X\cap Y$ is not empty. Then $ |F| \leq 2^{n - 1}$.
[color=#00f]Proof:[/color] We can match the subsets on pairs $(X, S-X)$ so $|F\cap (X, S-X)| \leq 1$ this implies the lemma. $\square$

The family $F$ satisfy the Lemma so the equality occurs so always $|F\cap (X, S-X)| = 1$ for any $X \in S$. If exists $A,B \in F$ such that $|A\cap B|=1$ then for any $C \in F$ we have that $|A\cap B\cap C|=1$ and $(A\cap B) \subset C$ this implies the problem.
Then if $A \in F \implies S-a \not \in F$, but if $v \in  A$ then $|A\cap \{(S-A)\cup \{v\}\}|=1$ so by FTSOC $(S-A)\cup \{v\} \not \in F$
By the equality of the lemma we have that $A-\{v\} \in F$, if we suppose that $ |A|$ is minimum this give us a contradiction. $\blacksquare$


function
algebra
polynomial
number theory
relatively prime
number theory solved

Recall that Euler's function phi(n) counts the number of positive integers m which are less than or equal to the positive integer n and are relatively prime to n, e.g. phi(10)=4. Prove that the phi-function satisfy the following property:

phi(1)/1 + phi(1+1)/11 + phi(1+1+1)/111 + .... = 1.111111...,

prove that this is true no matter in what scale (base) the integers 1, 11, 111,... and the "decimal" 1.1111... might be expressed.

To make the text more explicit what must be proven is that
 \sum phi(k)/(1+x+...x k-1)=1+1/x+1/x 2 +..., where x is the base in the previous text and the sum is taken for all k \geq 1.
The sum from the right side is x/x-1 for integers greater that 1.
From the looks of it cyclotomical polynomials could prove useful.

phi(k)/(1+x+...+x k-1)= phi(k)(x-1)/(x k-1)=phi(k)((x-1)/x k)(1+1/x k+1/x 2k+...

 \sum  phi(k)/...=\sum phi(k)(1/x k-1-1/x k +1/x 2k-1 -1/x 2k).

The conclusion follows from the well known identity:
n= \sum {for all d|n} phi(d).


floor function
calculus
integration
AMC
USA(J)MO
USAMO
modular arithmetic

Let $p_1, p_2, p_3, \ldots$ be the prime numbers listed in increasing order, and let $x_0$ be a real number between 0 and 1.  For positive integer $k$, define
\[ x_k = \begin{cases} 0 & \mbox{if} \; x_{k-1} = 0, \\[.1in] {\displaystyle \left\{ \frac{p_k}{x_{k-1}} \right\}} & \mbox{if} \; x_{k-1} \neq 0, \end{cases}  \]
where $\{x\}$ denotes the fractional part of $x$.  (The fractional part of $x$ is given by $x - \lfloor x \rfloor$ where $\lfloor x \rfloor$ is the greatest integer less than or equal to $x$.) Find, with proof, all $x_0$ satisfying $0 < x_0 < 1$ for which the sequence $x_0, x_1, x_2, \ldots$ eventually becomes 0.

I don't think we need any property of that  sequence $p_i$ except that it's integral...  :?

Claim: exactly the rational $x_0$ work.
Let $x_0=\frac{a_1}{a_0}$ with $a_1<a_0$. When $x_1=\left\{ \frac{p_1a_0}{a_1} \right\} = \frac{a_2}{a_1}$, we have $a_2<a_1$ again and so on, thus the sequence $a_i$ defined by this is (strictly) decreasing as long as $a_i \neq 0$. But since this is a sequence of non-negative integers, it will become $0$, thus the sequences starting with rational numbers will eventually become $0$.
Iff $x_i$ is irrational, also $x_{i+1}$ will be, so for all other starting values it doesn't become $0 \in \mathbb{Q}$.

Claim: the sequence goes to $0$ if and only if $x \in \mathbb{Q}$.

$\Rightarrow$ direction: suppose that $x = a/b$. Induct on $a+b$. Clearly, the statement is true for $a+b=3 \Rightarrow x=1/2$. Suppose that the claim holds true for all $a+b=k$. Consider $a_1,b_1$ such that $a_1+b_1=k+1$. Notice that in the sequence, $\frac{a_1}{b_1} \rightarrow \frac{b_1 p \bmod a_1}{a_1}$. Since $b_1 p \bmod a_1 < a_1$ and $a_1 < b_1$, we have that $b_1 p \bmod a_1 + a_1 < a_1 + b_1$, so the sequence converges by the inductive hypothesis.

$\Leftarrow$ direction: pretty clear that this is true, but to be totally rigorous, suppose that $x \not\in \mathbb{Q}$. If the sequence did eventually converge to $0$, then $x$ could be expressed as $a/b$ for integral $a,b$, implying that $x\in\mathbb{Q}$, a contradiction.

This seems too easy for a USAMO problem, even for a #1...  :maybe:

We claim that only $x_0 \in \mathbb{Q}$ satisfy the condition.

Let $x_k = \frac{p}{q} \neq 0$ for some positive integers $p$ and $q$. Since $0 < x_k < 1$, it follows that $p < q$. Then $x_{k+1} = \left \{ \frac{p_{k+1}}{\frac{p}{q}}\right\}$. Suppose that $p_{k+1} \nmid p$. Then $x_{k+1} = \left\{ \frac{qp_{k+1}}{p} \right \} = \frac{a}{p}$, where $a \equiv qp_{k+1} \pmod{p}$.

Now suppose that $p_{k+1} \mid p$. Then $x_{k+1} = \left \{ \frac{q}{b} \right \} = \frac{c}{b}$ where $b = \frac{p}{p_{k+1}}$ and $c \equiv q \pmod{b}$.

In both cases, the numerator of $x_k$ is strictly greater than that of $x_{k+1}$; the numerator of nonzero $\{ x_i \}_{i=0}^\infty$ is strictly monovariant. Therefore, the numerator of the numbers of the sequence will become $0$ at some point, implying that the sequence converges to $0$.

Now let $x_k \not \in \mathbb{Q}$. Suppose that $x_{k+1}$ is rational. This implies that $\frac{p_{k+1}}{x_k}$ is rational, but this implies that $x_k$ is rational, contradiction. Thus all terms of the sequence are irrational, and will not eventually reach $0$.

Looks like I need to start doing nongeo.

[hide="Solution"]Funny.

We claim that $x_0\in\mathbb{Q}$ is necessary and sufficient. Indeed, for necessity, suppose $x_k=0$. Then certainly $\{\frac{p_k}{x_{k-1}}\}=0$, implying that $x_{k-1}$ is rational; finish with induction.

Now for sufficiency. Suppose $x_k=\frac{a_k}{b_k}$ for positive coprime $a_k$, $b_k$ and all nonnegative integers $k$. Then $x_{k+1}=\{\frac{p_kb_k}{a_k}\}=\frac{a_{k+1}}{b_{k+1}}$, whence $a_{k+1}<b_{k+1}\le a_k$ and consequently $a_k$ is monotonically decreasing. It follows that the sequence converges to $0$.[/hide]

Lol this is a funny problem.

[hide="Sketch"]
I claim that all rationals work and all irrationals do not.

First, we shall show that no irrational numbers work.  Suppose $x_0$ is irrational.  Then by properties of irrationals, $c=\tfrac{p_1}{x_0}$ must also be irrational (otherwise $p_1=cx_0$ is a rational number equal to the product of a rational number and an irrational one, contradiction) and taking the fractional part only subtracts this result by an integer, so $x_1$ is also irrational.  Rinse and repeat.

Now we shall show that all rational numbers work.  Suppose $x_0$ is rational.  Then $x_1$ will also be rational; due to the division the denominator of $x_1$ is the numerator of $x_0$, and since $0<x_1<1$ we have that the numerator of $x_1$ is less than the numerator of $x_0$.  Therefore the numerators of the $x_i$ form a monotonically decreasing sequence, implying that for some $n\geq 1$ we can write $x_n=\tfrac 1k$ for some integer $k$.  Then $x_{n+1}$ is an integer, so the sequence evaluates to $0$.  We are done.

[hide="Sidenote"]
I believe the sequence of primes is only there to prevent people from exploiting any sort of symmetry, but other than that I have no idea why it's there.[/hide][/hide]

[hide=Solution]Only $x_0 \in \mathbb{Q}$ satisfy the condition.

Clearly if $x_0$ is irrational, then $\frac{p_1}{x_0}$ will also be irrational etc. Thus, the sequence can never terminate to $0$.

To show that all rationals work, let $x_0=\frac{p}{q}$ such that $q>p$. Notice that $x_1= {\displaystyle \left\{ \frac{p_1}{x_{0}} \right\}}= {\displaystyle \left\{ \frac{p_1 \cdot q}{p} \right\}}$, meaning that $x_1$ has denominator $p$ now. Each number in the sequence after will have a denominator smaller than the previous element so we can conclude that this sequence will eventually become 0.[/hide]

First we check that all rational $x_0$ will produce a series that eventually reaches zero. Let the the denominator of $x_0$ be equal to $k$. Clearly, the numerator is less than $k$. When we calculate $x_1$, the new denominator will be less than or equal to$x_0$'s numerator, hence the denominator decreases. It follows that for any choice of $x_0$, there will be some $i$ such that the numerator of $x_i$ is one. It follows that $x_{i+1}=0$. Hence, any rational $x_0$ will eventually terminate.
For any irrational $x_k$, note that $x_{k+1}$ will also be irrational. Since an irrational $x_k$ will never fully divide $p_{k+1}$, the series will never terminate, so we are done. $\square$

The answer is $x_0$ rational.
If $x_0$ is irrational, then all $x_i$ are irrational by induction. So the sequence cannot become zero.
If $x_0$ is rational, then all are. Now one simply observes that the denominators of $x_n$ are strictly decreasing, until we reach $0 = \frac 01$. This concludes the proof.

[b][color=red]Remark:[/color][/b]  	The sequence $p_k$ could have been any sequence of integers.

All rationals work. Obviously irrationals fail; otherwise let $x_i = \frac{p_i}{q_i}$ in simplest terms. Observe that $p_i < q_i$ for all $i$, so $$x_{i+1} = \frac k{p_i}$$ for some $k < p_i$ by definition. Hence $q_{i+1} < q_i$, and the sequence $q_i$ is decreasing. Therefore, in finitely many terms $q_i$ will become 1, and the next term in the sequence will be 0, as desired.

The answer is all rationals.
Notice that irrationals fail; therefore we may let $$x_k=\frac{n_k}{d_k},$$ where $\gcd{(n_k, d_k)}=1$.
[b]Claim:[/b] $n_k > n_{k+1}$ when $n_k > 0$. This proves the problem.
[b]Proof:[/b] Notice that $$x_{k+1}=\left\{\frac{p_{k+1}d_k}{n_k}\right\},$$ thus $n_{k+1} < d_{k+1} \leq n_k$. $\blacksquare$

I have made a video explanation on this problem: [url]https://youtu.be/OhFyJKqzxlA[/url]

[hide = Solution] I claim all $x_0 \in (0, 1)$ that are rational tend to $0$.

Let $d(x_i)$ denote the denominator of $x_i$. Let $x_0 = \frac{m}{n}$ for coprime integers $m, n$. Then notice $d(x_1) = m < d(x_0) = n$. We then have iterating this sequence $$d(x_k) < d(x_{k - 1}) < \cdots < d(x_ 1) < d(x_0). $$ Now as the numerators of all of these fractions are strictly less than the denominator, we obtain a sequence of decreasing numerators. Therefore the numerator tends to $0$.

If $x_0$ is irrational, then with inductive reasoning $x_k$ is also irrational, hence $\left \{\frac{p_k}{x_k} \right \} \neq 0$. $\blacksquare$ [/hide]

We claim the answer is all rationals. Notice if $x_0$ is irrational, then $x_1,x_2,\dots$ are irrational, and therefore cannot be $0.$ If $x_0$ is rational, all $x_i$ are rational so let $x_{k-1}=m/n.$ Then, $$x_k=\left\{\frac{p_kn}{m}\right\}=\frac{p_kn-\ell m}{m},$$ where we choose $\ell$ such that $p_kn-\ell m<m.$ Hence, the numerators of $x_k$ are strictly decreasing, so eventually $x_k=0.$ $\square$

[hide=Solution]
The answer is $x_0\in \mathbb{Q}$. Let $\mathbb{I}$ denote the set of irrational numbers

[color=#00f]CLAIM: If $x_0\in \mathbb{I}$, then there is no $x_i$ such that $x_i=0$[/color]

[i]Proof:[/i] We can see that,
\begin{align*}
    x_1=\left\{\frac{p_1}{x_0}\right\}\in \mathbb{I}
\end{align*}
So it cannot be zero. Assume that $x_{k-1}\in \mathbb{I}$. Then,
\begin{align*}
      x_k=\left\{\frac{p_k}{x_{k-1}}\right\}\in \mathbb{I}
\end{align*}
So $x_k\neq 0$. Thus by induction, for $x_0\in \mathbb{I}$, we have $x_i\neq 0$ for $i\in \mathbb{Z}^+$. $\blacksquare$
Let $x_0=\frac{l_0}{l_1}$ be a rational number. Then, we have
\begin{align*}
      x_1= \left\{\frac{p_1}{x_0}\right\}=  \left\{\frac{p_1\cdot l_1}{l_0}\right\}=\frac{l_2}{l_0}
\end{align*}
where $l_2\equiv p_1l_1\pmod {l_0}$ and $l_2<l_0$. Again, we will have
\begin{align*}
    x_2=  \left\{\frac{p_2\cdot l_0}{l_2}\right\}=\frac{l_3}{l_2}
\end{align*}
where $l_3\equiv p_2\cdot l_0\pmod l_2$ and $l_3<l_2<l_0$. Now for a relatively large $k$ we will have
\begin{align*}
    x_k=\frac{l_{k+1}}{l_k}<1
\end{align*}
and $l_{k+1}$ will be so small such that $l_{k+1}=1$. So, we can say that \begin{align*}
    x_{k+1}=\{p_{k+1}\cdot l_k\}=0
\end{align*}
Now since for all $i>k+1$ we have $x_i=0$, the sequence has eventually become zero for $x_0\in \mathbb{Q}$
[/hide]

The answer is $X_0$ can be any rational number between $[0,1)$

Observe that $\frac{P_k}{X_{k-1}}$ needs to be an integer so $X_{k-1}$ must be rational. For $X_{k-1}$ to be rational, then $X_{k-2}$ must also be rational, then so on until $X_0$.

Set $X_k=\frac{a}{b}$. $X_{k+1}=\frac{b*P_{k+1}}{a}$ which must have a denominator of $a$, which is also less than $b$. Note that we want $X_k=\frac{1}{b}$, for any positive integer $b$, so that $X_{k+1}$ is an integer.

Note that since the denominator of $X_k$ is strictly decreasing and that $0 \le X_n < 1$ for all whole numbers $n$, the sequence must eventually contain an element having a numerator of 1, hence implying our claim.

$\blacksquare$

[hide=storage]Consider the fraction $\frac{a}{b}$. Then, \[ \left\{ \frac{p_k}{\frac{a}{b}} \right\} = \frac{p_kb \pmod{a}}{a} \]
Thus, for rationals $x_0 =  \frac{a}{b}$, the denominator keeps decreasing and thus eventually the sequence becomes $0$.
If $x_0$ is irrational then the sequence never becomes $0$, since then all values in the sequence are irrational.
[/hide]


Με αφορμή την άσκηση της Βαλκανιάδας πιστεύω ότι το ΑΡΜΟΝΙΚΟ ΤΕΤΡΑΠΛΕΥΡΟ είναι ένα topic που θα είναι πολύ χρήσιμο για όλους τους διαγωνιζόμενους. Ας γεμίσουμε λοιπόν αυτό το topic με θεωρία και ασκήσεις πάνω σε αυτό.
Ελπίζω να δείξετε ενδιαφέρον.:)

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

[quote="bilot4"]Νίκο θα ήθελα να πω ότι συμφωνώ απόλυτα στο να φτιάξουμε ένα τέτοιο topic που αφορά το πλήρες τετράπλευρο (btw, φαντάζομαι ότι εννοείς κυρίως πλήρες κι όχι αρμονικό, έτσι?),

Ομως ήθελα να κάνω μια ένσταση σε σχέση με το χρόνο που έκανες αυτήν την πρόταση. Νομίζω κάθε χρόνο αυτή την περίοδο υπάρχει μια "εξασθένιση" της λειτουργίας του forum (εξετάσεις και λοιπές υποχρεώσεις)... οπότε θα έλεγα να κρατήσουμε αυτήν την πρόταση για αργότερα (εννοείται βέβαια ότι όποιος θέλει να βάλει ασκήσεις είναι κάτι παραπάνω από ευχάριστο, απλά μιλάω λίγο κι απ' την δική μου πλευρά).

Anyway πιστεύω ότι θα προχωρήσει το όλο θέμα (είτε τώρα είτε σε λίγο καιρό) και θα προσπαθήσω κι εγώ να βοηθήσω όσο μπορώ σε αυτό :wink:[/quote]

mim,
egrapsa ennoousa to armoniko tetrapleuro (den einai typo) kai epeleksa auto dioti oloi ligo polu gnorizoun gia to plires tetrapleuo to opoio einai spoudaio, alla polu ligoteroi gnorizoun gia to armoniko tetrapleuo. ithela na do pos tha paei auto kai meta na proteino na kanoume ena paromoio sticky gia to plires tetrapleuo. an thelete boroume na ta kanoume i parallhla sto idio sticky i na anoiksoume duo diaforetika stickies.

tora oso gia to xrono pou les..nai mallon exeis dikio. i alitheia einai oti den to skeftika katholou. ksereis oti molis apofasiso kati apla proxorao sto epomeno vhma xoris deuteri skepsi- kai apo oti fainetai edo xreiazotan...

opote...vlepontas kai kanontas!h protasi uparxei edo-to pote tha ulopoiithei einai stin euxereia tou kathe melous.

oso gia tin askisi pou proteinei o etaratoris : h sugekrimeni lunetai kai xoris xrhsh miquel mono me menelao kai theorima eksoterikis dixotomou. auti pou exei endiaferon einai i genikeusi pou vgainei me armonika suzugh apo plires tetrapleuro. (etaratoris boreis na kaneis edit an theleis na valeis ti genikeusi.)

Αν χρειαστεί, μπορούμε να φτιάξουμε ένα sticky με θέμα [b][color=red]''Αρμονικότητα -  πλήρες τετράπλευρο - αρμονικό τετράπλευρο'' [/color][/b]

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

  Αυτό το αρμονικό τετράπλευρο είναι βέβαια κατααπληκτικό σε εφαρμογές. Αν θυμάμαι καλά , έχω στην γεωμετρία 3 μια άσκηση και ως άλλο τρόπο έχω βάλει μια εφαρμογή του πλήρους τετραπλεύρου. Δεν είμαι σπίτι για να το ελέγξω. μπορεί όμως και την άφησα για τον 4ο τόμο.

  Αρκετό υλικό θα βρείτε και στο αγγλικό τμήμα. Αξίζει όμως να το βάλουμε και εδώ και να ξεμπλέξουμε για πάντα με αυτό το θέμα !

 Μπάμπης

[quote="Protonios"]Μία διευκρινιστική ερώτηση:

Είναι ιδιότητα ή ορισμός του αρμονικού τετραπλεύρου ότι:

Αν $ A,B,C,D,M$ σημεία ενός κύκλου τότε το $ ABCD$ είναι αρμονικό τότε και μόνον όταν η δέσμη $ (MA, MC, MB, MD)$ είναι αρμονική???[/quote]

eksartatai....genika sto armoniko tetrapleuro exeis mia seira apo isodunames protaseis. alla gia na dieukrinistei auto pou rotas tha prepei na kanoume ligi ereuna, na psaksoume to thema kala, na doume pos akrivos orizetai to armoniko tetrapleuro kai na ta mazepsoume edo oste opos polu sosta eipe o k babis prepei na teleionoume mia gia panta me auto to thema. gi auto eksallou ekana auti tin protasi gia to armoniko tetrapleuro. guys up to u tora...ego exo kvantomixaniki!!!:(

[quote="stergiu"]Αν θυμάμαι καλά αρμονικό λέγεται αυτό (το εγγεγραμμένο τετράπλευρο)που οι εφαπτόμενες σε δύο απέναντι κορυφές τέμνονται πάνω στην ευθεία της άλλης διαγωνίου . Από κει και πέρα αρχίζουν οι ιδιότητες - κριτήρια : οι εφαπτόμενες στις δύο άλλες κορυφές τέμνονται πάνω σε διαγώνιο , τα γινόμενα των απέναντι πλευρών είναι ίσα , οι διχοτόμοι των απέναντι γωνιών τέμνονται πάνω στις διαγώνιες, αυτό έγραψε πριν ο ..protonios ,και άλλες ιδιότητες. Θα τις μαζέψουμε λίγο λίγο και θα τις φτιάξουμε. Έτσι κι αλλιώς δηλαδή εγώ θα το κάνω, οπότε αν με βοηθήσετε και σεις θα χαρώ περισσότερο !

 Μπάμπης[/quote]

nomizo oti einai gia to kalo olwn!

an paroume loipon ton orismo tou k.babi tote einai amesi sunepeia oti i diagonios einai kai summetrodiamesos. meta exoume ena karo idiotites, alla opos eipa tha prepei na to psaksoume to thema giati exei polu psomi!

Βαζω αναλυτικα την θεωρια που αφορα το αρμονικο συνολο και τις αρμονικες δεσμες και τις προτασεις που ειναι χρησιμες στην λυση ασκησεων.

                 [b]ΑΡΜΟΝΙΚΗ ΤΕΤΡΑΔΑ ή ΑΡΜΟΝΙΚΟ ΣΥΝΟΛΟ[/b]

$ 1$ Οταν δινονται δυο σημεια $ A,B$ του επιπεδου τοτε υπαρχει μοναδικο σημειο $ M$ του ευθυγραμμου τμηματος $ AB$, ωστε $ \frac{MA}{MB}\equal{}\frac{m}{n}$.
Επισης υπαρχει μοναδικο σημειο $ N$ στην προεκταση του $ AB$, ωστε $ \frac{NA}{NB}\equal{}\frac{m}{n}$. Τοτε τα σημεια $ M,N$ ονομαζονται αρμονικα συζυγη των$ A,B$ και αποτελουν μια αρμονικη τετραδα ή ενα αρμονικο συνολο.

$ 2$ Τοτε και τα $ A,B$ ειναι αρμονικα συζυγη των $ M,N$ και ισχυει $ \frac{AM}{AN}\equal{}\frac{BM}{BN}$.

$ 3$ Αν $ O$ μεσο του $ AB$ τοτε το αρμονικο συζυγες του θεωρειται ενα σημειο στο απειρο της ευθειας $ AB$.

$ 4$ Αν $ O$ μεσο του $ AB$ τοτε τα $ M,N$ βρισκονται παντοτε προς το ιδιο μερος του $ O$.

$ 5$ Αν σε ενα τριγωνο $ ABC$ η εσωτερικη και η εξωτερικη διχοτομος της $ A$ τεμνουν την $ BC$ στα $ D,E$ τοτε τα $ E,B,D,C$ αποτελουν την πιο γνωστη αρμονικη τετραδα.

$ 6$ Αν σε τριγωνο $ ABC$ η $ AD$ ειναι εσωτερικη διχοτομος και $ I,I'$ εγκεντρο , παρακεντρο, τοτε τα $ A,I,D,I'$ ειναι αρμονικη τετραδα.

$ 7$ Αν $ O$ μεσο του ευθ. τμηματος $ AB$ τοτε τα $ N,A,M,B$ αποτελουν αρμονικο συνολο οταν και μονον οταν $ OA^2\equal{}OB^2\equal{}OM.ON$.

$ 8$ Αν $ N,A,M,B$ αποτελουν αρμονικη τετραδα τοτε $ \frac{2}{AB}\equal{}\frac{1}{AM}\plus{}\frac{1}{AN}$.

[b]ΑΡΜΟΝΙΚΗ ΔΕΣΜΗ[/b]

$ 1$ Εστω 4 ευθειες, οι $ a,b,c,d$ που συντρεχουν στο $ O$. Λεμε οτι αποτελουν αρμονικη δεσμη οταν τα σημεια τομης τους απο τυχαια ευθεια $ e$ αποτελουν αρμονικη τετραδα. Το $ O$ ειναι τοτε το κεντρο της δεσμης και οι $ a,b,c,d$ οι ακτινες της.

$ 2$ Αν $ O(a,b,c,d)$ αρμονικη δεσμη και φερω μια ευθεια //λη προς την $ a$ τοτε αυτη τεμνει τις αλλες 3 σε τρεια σημεια ωστε το ενα να ειναι μεσο του ευθ. τμηματος που οριζουν τα δυο αλλα. Η προταση ισχυει και αντιστροφα.

$ 3$ Αν τμησω μια δεσμη $ O(a,b,c,d)$ με μια ευθεια και προκυψει αρμονικη τετραδα τοτε οποιαδηποτε ευθεια τεμνει την δεσμη σε 4 αρμονικα σημεια.

$ 4$ Εστω $ ABC$ τριγωνο και$ M$ μεσο της $ BC$. Τοτε οι ευθειες $ AB,AM,AC$ καιη //λη απο το $ A$ στην $ BC$ αποτελουν αρμονικη δεσμη.

$ 5$ Αν εχουμε μια αρμονικη δεσμη $ O(a,b,c,d)$ και μια τυχαια δεσμη $ O'(a',b',c',d')$ οπου οι ακτινες της ειανι καθετες σε αυτες της πρωτης τοτε και η δευτερη δεσμη ειναι αρμονικη.

$ 6$ ΒΑΣΙΚΗ ΠΡΟΤΑΣΗ: Σε καθε πληρες τετραπλευρο καθε διαγωνιος του διαιρειται αρμονικα απο τις αλλες δυο.

[quote="Nick Rapanos"][quote="Protonios"]Χωρίς φυσικά να είμαι ο κατάλληλος να διδάξω γεωμετρία σε ένα φόρουμ στο οποίο πολλά μέλη είναι just 2 good 4 me έχω συλλέξει μερικές ιδιότητες του αρμονικού τετραπλεύρου (όλες σχεδόν γνωστές), τις έχω αποδείξει και όταν βρω λίγο χρόνο θα κάνω ένα presentation με αυτές (γιατί βλέπετε το σύστημα προβλέπει να πρέπει να γράψω και ένα μάθημα που λέγεται ιστορία...) :([/quote]

auto einai polu thetiko. perimenoume to presentation kosta. tora gia tin istoria....re paidia ego 20 egrafa panta istoria alla de mou exei meinei tpt. telika exei kanena nohma etsi opos ginetai? kalutera tha tane na mathainame 5 pragmata pou ta mas menane kai oxi pou egine i kathe maxi, pios lavothike kai poia kouvalose farmaka kai fagito...[/quote]
Ναι περιμένουμε Κώστα....
Τώρα για την ιστορία τί να πω???
Αυτό το πράγμα με τρελένει....Ώρες ατέλειωτες διαβάσματος βιολογίας,ιστορίας κλπ που τα ξέχασα σε δύο μέρες....


A bin has 5 green balls and $ k$ purple balls in it, where $ k$ is an unknown positive integer.  A ball is drawn at random from the bin.  If a green ball is drawn, the player wins 2 dollars, but if a purple ball is drawn, the player loses 2 dollars.  If the expected amount won for playing the game is 50 cents, then what is $ k$?

By the definition of expected value, we have $ E\equal{}50\equal{}200\cdot\frac5{k\plus{}5}\minus{}200\cdot\frac k{k\plus{}5}\equal{}200\cdot\frac{5\minus{}k}{k\plus{}5}$
$ \implies1\equal{}4\cdot\frac{5\minus{}k}{k\plus{}5}\implies k\plus{}5\equal{}20\minus{}4k\implies5k\equal{}15\implies k\equal{}\boxed3$.

[quote=Lucky_ducky][quote=jeffreyhuang][hide=Offical Alcumus Solution]There are 5 green balls and $5+k$ total balls, so the probability that a green ball is drawn is $\dfrac{5}{5+k}$. Similarly, the probability that a purple ball is drawn is $\dfrac{k}{5+k}$. So the expected value is $$\frac{5}{5+k}(2)+\frac{k}{5+k}(-2)=\frac{1}{2}$$.

Multiplying both sides of the equation by $2(5+k)$ gives $20-4k=5+k$, or $15=5k$. Therefore, $\boxed{k=3}$.[/hide][/quote]

Should we be posting solutions?[/quote]

yes. But not the official alcumus ones. That's cheap

This is the problem that made me master all of Counting & Probability!
[hide=Solution]
$P(\text{Drawing a green ball})=\frac{5}{5+k}$
$P(\text{Drawing a purple ball})=\frac{k}{5+k}$
$0.50=E=2\cdot\frac{5}{5+k}+(-2)\cdot\frac{k}{5+k}=2\left(\frac{5-k}{5+k}\right)$
$\implies\frac{5-k}{5+k}=\frac14\implies 5+k=20-4k$
$\implies 5k=15\implies \boxed{k=3}$
[/hide]


[img]http://www2.hkedcity.net/sch_files/a/lpl/lpl-lsk/public_html/new_cake.JPG[/img]
As shown in the figure, $\triangle ABC$ is a piece of cake divided by three cuts at AD, BE and CF , $AF:FB = \alpha : 1$, $BD:DC = \beta:1$ and $CE:EA = \gamma:1$.
If the area of $\triangle ABC$  is 1 square unit, what is the area of $\triangle PQR$?

Check the posts in the Getting Started forum.
Use some area ratios...... This kind of problem always have the same solution.

I was going to say, to apply a lot of Menelaus, but after reading shobber's post and pondering for a while, there is no need to. Ratios will do. However, it looks to be very ugly regardless.

Beauty is the first test.
Indeed, the solution of this problem is a neat formula which is not messy at all.  :)

[quote="sirorange"]1/7?[/quote]

I would suspect it to be some relation with $\alpha, \beta, \gamma$ but I'm really tired right now so I'm not sure.

[quote="sirorange"]1/7?[/quote]
that is when $\alpha=\beta=\gamma=2$

Standard way gives the answer, $1-\frac{\alpha}{1+\alpha+\alpha \beta}-\frac{\beta}{1+\beta+\beta \gamma}-\frac{\gamma}{1+\gamma+\gamma \alpha}$
But the process of obtaining is ugly. Even for the formula I don't think it's nice..

I don't consider it is ugly...
$\frac{\triangle{ABC}}{\triangle{ABQ}}=\frac{\triangle{ABQ}+\triangle{ACQ}+\triangle{BCQ}}{\triangle{ABQ}}=1+\frac{CD}{DB}+\frac{CE}{EA}=1+\frac{1}{\beta}+\gamma $

So $\frac{\triangle{ABQ}}{\triangle{ABC}}=\frac{\beta}{\beta \gamma + \beta +1}$

Then do the same for the other two triangles.

[quote="siuhochung"]i used the same way, but don't you think that it is tedious?[/quote]
Well, this is a nice and neat solution, but if you keep solving it over and over again, it bcomes really boring...
I have met this problem in ML for at least 3 times!

Believe it or not, the expression can be further simplified to
$\frac{(\alpha\beta\gamma-1)^2}
{(1+\alpha+\alpha\beta)(1+\beta+\beta\gamma)(1+\gamma+\gamma\alpha)}$.
I have seen other problems similar to this topic in questions of many  math tournaments before.
They are just special cases of this solution.
I still consider the expression as pretty for its symmetry and simplicity.
Besides, if you play around with the ratios you can set questions of different levels of difficulty.
Note that the three cevians are current if and only if the area of triangle PQR is equal to zero, and it is equivalent to the condition that $\alpha\beta\gamma =1$, the result is same as Ceva's theorem.

[quote="luimichael"]Believe it or not, the expression can be further simplified to
$\frac{(\alpha\beta\gamma-1)^2}
{(1+\alpha+\alpha\beta)(1+\beta+\beta\gamma)(1+\gamma+\gamma\alpha)}$.
I have seen other problems similar to this topic in questions of many  math tournaments before.
They are just special cases of this solution.
I still consider the expression as pretty for its symmetry and simplicity.
Besides, if you play around with the ratios you can set questions of different levels of difficulty.
Note that the three cevians are [b]current[/b] if and only if the area of triangle PQR is equal to zero, and it is equivalent to the condition that $\alpha\beta\gamma =1$, the result is same as Ceva's theorem.[/quote]
:wow: that's amazing. so complicated this problem but the expression is so beautiful!

also, what is Ceva's theorem? what are cevians?

and also, the bold letters, shouldn't it be [b]concurrent[/b]?

All in all, i still don't consider it as beautiful... (maybe that's because I dont have a sense of beauty in geometry -- I like inequalities much more than that)
Cevian means a segment connecting a vertex and a point on the opposite side.
Ceva's theorem is
http://www.cut-the-knot.org/Generalization/ceva.shtml

[quote="siuhochung"][quote="shobber"][quote="shobber"]Ceva and this problem can be solved in the same way: Area Ratio. I think that's why Ceva is a special case of this problem.[/quote]
I think we cannot use the way i did to prove Ceva as [b]luimichael[/b] said. Since we cannot divide by $0$.[/quote]
 :huh:[/quote]
Forget what i said... :blush:  :blush:

[quote="shobber"]I don't consider it is ugly...
$ \frac {\triangle{ABC}}{\triangle{ABQ}} \equal{} \frac {\triangle{ABQ} \plus{} \triangle{ACQ} \plus{} \triangle{BCQ}}{\triangle{ABQ}} \equal{} 1 \plus{} \frac {CD}{DB} \plus{} \frac {CE}{EA} \equal{} 1 \plus{} \frac {1}{\beta} \plus{} \gamma$

So $ \frac {\triangle{ABQ}}{\triangle{ABC}} \equal{} \frac {\beta}{\beta \gamma \plus{} \beta \plus{} 1}$

Then do the same for the other two triangles.[/quote]

hey plz tell me howz da ratio of triangle ACQ n  ABQ is CD/BD ...
plzzz


I get this error everytime I try to run a program. I have tried reinstalling both the SDK and JCreator, but neither has helped. It stemmed from a while back when I was playing around with somethng (cant remember what it was) in the SDK. I really dont want to use another program because I find Jcreator to be very good (plus Im not familiar with anyhting else but codewarrior and codewarrior costs money).

So yeh, if anoyne has some quick help for me, that would be very appreciative (considering that I want to do the qualifying thing this weekend).

Without (even) further ado, here is the error:

Error : Invalid path, C:\j2sdk1.4.2_01\bin\javac.exe -classpath "C:" -d C: C:\3^k+1.java"

3^k+1
is actually the name of the program I was tyrying to run.

Thanks very much in advance for any help given.

Have you tried renaming your program?  I seem to remember that the Java compiler doesn't like non-alphanumeric names.  Other than that I'm afraid I have no advice.

On a side note, how is JCreator?  I have used NetBeans IDE in the past, but it took forever and a half to load and the .java files it created didn't format nicely outside of NetBeans (i.e. using notepad).

No, thats not it. Even with programs that have just letters in their name, it gives the same error.

About JCreator:
Its great. It is just what you need if you need a quick, easy to use and manipulate, compiler. Plus, it downloads really quickly (even on 56k).

Never mind this topic...the problem has been solved now.

GO MATHFANATIC!!! He is the coolest most awesomest 1337 ever.


Αποδείξτε ότι για τους πραγματικούς αριθμούς $ a,b,c$ ισχύει $ \frac{3a^{2}\minus{}2ab\minus{}b^{2}}{a^{2}\plus{}b^{2}}\plus{}\frac{3b^{2}\minus{}2bc\minus{}c^{2}}{b^{2}\plus{}c^{2}}\plus{}\frac{3c^{2}\minus{}2ca\minus{}a^{2}}{c^{2}\plus{}a^{2}}\geq 0$

H anisotita mporei na graftei os:

$ \frac{4a^2}{a^2\plus{}b^2}\plus{}\frac{4b^2}{b^2\plus{}c^2}\plus{}\frac{4c^2}{c^2\plus{}a^2} \geq\frac{(a\plus{}b)^2}{a^2\plus{}b^2}\plus{}\frac{(b\plus{}c)^2}{b^2\plus{}c^2}\plus{}\frac{(c\plus{}a)^2}{c^2\plus{}a^2}$

Apo tin gnosti anositita $ 2(x^2\plus{}y^2) \geq(x\plus{}y)^2$ pou isxyei gia olous tous pragmatikous arithmous x,y synepagetai oti
to deytero melos tis parapano anisotitas einai mikrotero i iso tou 6.

Opote to provlima einai tora i Nesbit inequality pou mporei na apodeixthei me Cauchy Schwarz.

vasika exo ponokefalo tora opote tha elekso tin lysi mou meta..an einai lathos sorry...

Δεν ειναι η Nesbit γιατι ο αριθμητης ειναι και στον παρονομαστη.
Νομιζω οτι το αριστερο μελος της σχεσης σου μπορει να ειναι μικροτερο του 6 ($ a \equal{}1,b \equal{}2, c \equal{} 3$).
Anyway,nice try :)

Thanks aleksandre,
exeis apolyto dikio vasika..tha prospathiso pali tis askisi pio meta mias kai pao gia ypno tora  :sleeping:  :sleeping:
thanks pali

~Kostas

[quote="Protonios"]Telika??? Den mporw na ti vgalw oyte me Muirhead logw assymetrias... Ta exw dokimasei ola... :maybe:[/quote]

Ούτε εγώ την είχα καταφέρει. Οπότε ας αναλάβουν οι ειδικοί(ξέρουν αυτοί ποιοι είναι :lol: )

Σε καμιά περίπτωση δεν είμαι ειδικός αλλά εγώ θα πρότεινα την εξής προσέγγιση-λύση.

Εύκολα η ζητούμενη ισοδυναμεί με:

$ \sum_{cyc}\frac{4a^2\minus{}2ab}{a^2\plus{}b^2}\geq 3 \iff
\sum_{cyc}\frac{2a^2\minus{}ab}{a^2\plus{}b^2}\geq \frac{3}{2}$

Κατ' αρχάς εύκολα βλέπουμε ότι αρκεί να δουλέψουμε για $ a,b,c$ θετικούς (αφού τότε μεγιστοποιείται το 1ο μέλος της ανισότητας)
Αν τώρα διαιρέσουμε κατάλληλα τον αρριθμητή και παρονομαστή κάθε κλάσματος, και θέσουμε $ x\equal{}\frac{a}{b}$ κι αντιστοιχα για τα άλλα, έχουμε:

$ \sum_{cyc}\frac{2x^2\minus{}x}{x^2\plus{}1}\geq \frac{3}{2}$ με $ xyz\equal{}1$

Από εδώ προσπάθησα να πάω με Jensen αλλά αν δεν έκανα κανένα λάθος στις πράξεις (παραγώγιση) η
$ f(x)\equal{}\frac{2x^2\minus{}x}{x^2\plus{}1}$ δεν είναι πάντα κυρτή στους θετικούς (κι οπότε δεν μπορώ να εφαρμόσω jensen).

Ετσι το μόνο που σκέφτηκα είναι οι πολλαπλασιαστές Lagrange, βάσει των οποίων (με λίγες πράξεις) η παράσταση παίρνει το μέγιστό της όταν $ x\equal{}y\equal{}z\equal{}1$ κι άρα ισχύει το ζητούμενο!

Αν πας να κάνεις Jensen δεν θα κάνεις γιαυτή τη συνάρτηση αλλά για την $ f(x)\equal{}\frac{2e^{2x}\minus{}e^x}{e^{2x}\plus{}1}$ αλλά και αυτηνής η κυρτότητα αλλάζει . Το πρόβλημα βέβαια φιξάρεται εύκολα με το RCF theorem  αλλά για να μην μπλέξουμε με τέτοια , να μια καθαρά elementary απόδειξη (όσο για τους πολλαπλασιαστές πιστεύω ότι θα εχει δύσκολες πράξεις ) . http://canhang2007.files.wordpress.com/2008/12/silouan.pdf


vector
analytic geometry
linear algebra
combinatorics unsolved
combinatorics

Hi all,

I can't solve this problem,
 :(

I was wondering if you guys could help:

St. Petersburg Math Olympiad

In a country there is a parliament. You are given that for every two people in the parliament, there exists another person that is aquainted with exactly one of the two.

There are two parties in the parliament. Every day, the king (not a member of any party) tells some group of people to change parties, at which time all other people that are aquainted with some member of the group also change parties.

Prove the King can make it so that there will only be one party left at some time

I think this may work.  However, it uses linear algebra, which I'm not sure is expected in these olympiads.

[hide]
First, I guess we have to assume that the person who knows exactly one of $x$ and $y$ can't be $x$ or $y$ themselves.  Otherwise a two person parliament where $x$ knows $y$ and they start off in different parties doesn't work.

Now let us reformulate the problem in linear algebra terms:

We view the parliament's current state as a vector in $(Z_2)^n$.  Each day the king can choose a subset $S$ of the parliament, and add the vector whose $i^{th}$ coordinate is 1 if member $i$ is in $S$ or has an acquaintance in $S$, and 0 otherwise.  We want to show we can change the affiliation of any particular group of people, in other words we want to show the vectors corresponding to all the different subsets span $(Z_2)^n$.

If this is not the case, there must be a nonzero vector in $(Z_2)^n$  which is orthogonal to all the vectors corresponding to our subsets.  This corresponds to a subset $T$ of people such that any other subset $S$ has an even number of acquaintances in $T$ (Here I assume that people are acquainted with themselves).  I claim this is impossible.

To see this, we first note that $T$ (being the set of acquaintances of $T$ in itself) must have even cardinality.  Now let $S_0$ be a set of people which is maximal with respect to the property of not knowing everyone in $T$.  $S_0$ must also have an even number of acquaintances in $T$, so there are two people $x$ and $y$ in $T$ who are unacquainted with anyone in $S_0$.

But by assumption there is someone who knows $x$ and not $y$.  Adding this person to $S_0$ leads to a subset who knows more people than $S_0$, but still not everyone, a contradiction.[/hide]


floor function
inequalities
triangle inequality
geometry
angle bisector
geometry unsolved

[quote="mathangel"]I think that it 's wrong with a square. And true for all the cases where n>4[/quote]

Why wouldn't it be true for a square, you have 1 distinct length for sides, and one length for the diagonal, hence 2 lengths, which is $ 4/2$

My idea would be

[hide]
Consider regular shapes
[/hide]

Terribly sorry. I miss the word "sides".

[quote="cyshine"]Consider $ n$ points in a plane which are vertices of a convex polygon. Prove that the set of the lengths of the sides and the diagonals of the polygon has at least $ \lfloor n/2\rfloor$ elements.[/quote]

Obviously, it is enough to prove for all even $ n$ because then easily follows for $ n \plus{} 1$.

Suppose $ n$ is even. Now put in the set $ S$ the greatest of all [b]sides[/b].

Now see that, by triangle inequality, there is a diagonal that connects two vertices between which is only one vertex, which is greater than the greatest side.

Repeat the same process for all [b]"sorts of diagonals"[/b] that connect two vertices between which is $ k$ vertices, for $ 0 \le k < n/2$.

We have $ n/2$ such sorts of diagonals and each time we get one lenght that is greater than previous greatest. The statement follows.

Sorry if I didn't explained well, my English is not well.

[quote="djuro"]
Now see that, by triangle inequality, there is a diagonal that connects two vertices between which is only one vertex, which is greater than the greatest side.[/quote]
Not true.

I almost get it but find my solution all wrong, I can only show there are at least n/4   different distances :(

it's a tough one

This problem is false, here is a conterexample ($n = 6$)

Consider $3$ vertices of an equilateral triangle of side $1$, $A, B, C$.  Take the angle bisector at $A$ choose $A'$ a point of it at distance $1$ from $A$.  If you do this for $B$ and $C$, you obtain $6$ points in convex position that only define $2$ distances.  Thus the problem is false.

You only looked at distances $AB = BC = CA = AA'= BB'= CC' = 1$, and probably $AB' = B'C = CA' = A'B = BC' = C'A$. How about $A'B' = B'C' = C'A'$? There are three distinct distances.

Carlos Yuzo made a little joke by submitting this as a problem. It is a famous result by Altman to a conjecture of Erdös.
See [url=http://books.google.com/books?id=T8AxPKqnQmkC&pg=PA218&lpg=PA218&dq=distinct+distances+between+n+points+in+convex+position&source=bl&ots=-wtMo7rux9&sig=yQ0YVx6ZJnO0U2mPU6fjR3h4RBg&hl=en&ei=bShwTKL9G4nEOKWykZUG&sa=X&oi=book_result&ct=result&resnum=8&ved=0CDcQ6AEwBw#v=onepage&q=distinct%20distances%20between%20n%20points%20in%20convex%20position&f=false]Google-Book[/url]

The only extremal sets are regular $n$-gons, and for $n$ even, also regular $(n+1)$-gons with one vertex removed.


What percent of odd numbers between 0 and 100 are multiples of 3?

there are 50 odd numbers
The odd multiples of 3 are \[ 3,9,15,...,99\]
adding 3 to each number \[ 6,12,18,...,\]102 dividing by 6 gives us \[ 1,2,3,...,17\]
so $ \frac {17}{50} \equal{} \boxed{34\% }$

Another way you could've found the number of odd multiples of 3 is by:
$3 \cdot 1, 3 \cdot 2, 3 \cdot 3, ... , 3 \cdot 33$
We want to find the number of terms with an odd number multiplied to 3. There are 33 terms in total, but the last term is odd, so our answer is $\lceil \frac{33}{2} \rceil = 17$
We reach the same answer of $\boxed{34\%}$


I, a couple of weeks ago, with the assistance from my fried Caelestor (you may know us two from DMAT), started writing a mock AMC.  We, along with a couple of much appreciated helpers, have completed the 25 question exam and will be offering it next week Friday and Saturday for people to take.

The general rules are as follows:

(1) The exam is timed - 75 minutes are allowed, plus a small time window for turning in your answers.
(2) No electronic aids
(3) This is not the family plan - try and do it yourself

yackity yack, you know the drill.

BUT...

If you at all interested post here and let us know, we could always use more participants.  And, dare I do it?, I am going to leave my email address incase anyone wants to get in contact with me about it for some reason.

Fell free to ask questions here, they will get answered... My email is king-of-cards@cox.net

Until next saturday then... Hope to have everyone there.

P.S. I already created a thread like this weeks before in the AMC subforum.  :P
Treat this as an announcement from my friend. If you would like to join, please post [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=298452]there[/url].

I'm going to make this the official choose a specific time thread.


inequalities
rearrangement inequality
inequalities unsolved

For all positive reals $ x,y,z$ such that $ {xyz} \equal{} 1$ prove that:

$ \frac {xy}{x\plus{}1} \plus{} \frac {yz}{y\plus{}1} \plus{} \frac {zx}{z\plus{}1} >\equal{} \frac {3}{2}$

if we assume $ x \equal{} \frac {a}{b} , y \equal{} \frac {b}{c} , z \equal{} \frac {c}{a}$ , the problem can be restated as:

Prove that for every three postitive reals $ {a, b, c}$ the following inequality holds:

$ \frac {ab}{ c(a\plus{}b) } \plus{} \frac {bc}{ a(b\plus{}c) } \plus{} \frac {ac}{ b(c\plus{}a) } >\equal{} \frac {3}{2}$

[quote="madness"]one could say that by rearrangement inequality, we will get nesbitts inequality which is true.

But for the rearrangement inequality, one must assume WLOG that $ a \geq b \geq c$ which i read in some other thread that this cannot be done as the given expression isnt symmetric in its variables. I didnt understand why. Can anyone explain that? Esp Darij, arquady, rust, pvthuan?
thanks :)[/quote]
For application of rearrangement inequality  we need the same orderliness or the opposite orderliness.
The inequality can be non-symmetric.
For example:
$ a^3 + b^3 + c^3\geq a^2b + b^2c + c^2a$ is true for $ a,$ $ b$ and $ c$ are non-negative
because $ (a^2,b^2,c^2)$ and $ (a,b,c)$  have the same order.
Easier to note it in help by a following reasoning:
let $ a\geq b\geq c$ ( but it's non necessarily touching to our inequality! ).
Then $ a^2\geq b^2\geq c^2.$ It gives the same order. Hence, we obtain that $ a^3 + b^3 + c^3\geq a^2b + b^2c + c^2a$ is true.

Also example ( for original inequality ):
Let $ a\geq b\geq c.$ Then $ \frac {ab}{a + b}\geq\frac {ac}{a + c}\geq\frac {bc}{b + c}$ and $ \frac {1}{a}\leq\frac {1}{b}\leq\frac {1}{c}.$ We obtain the opposite orderliness.
Thus, the expression $ \frac {ab}{ c(a + b) } + \frac {bc}{ a(b + c) } + \frac {ac}{ b(c + a) }$ is minimal and
we need to look for another way:
let $ a\geq b\geq c.$ Then $ ab\geq ac\geq bc$ and $ \frac {1}{ac + bc}\geq\frac {1}{ab + bc}\geq\frac {1}{ab + ac}.$
We obtain the same order.
Thus, $ \frac {ab}{ c(a + b) } + \frac {bc}{ a(b + c) } + \frac {ac}{ b(c + a) }\geq\frac {1}{ac + bc}\cdot ac + \frac {1}{ab + bc}\cdot bc + \frac {1}{ab + ac}\cdot ab$ and
$ \frac {ab}{ c(a + b) } + \frac {bc}{ a(b + c) } + \frac {ac}{ b(c + a) }\geq\frac {1}{ac + bc}\cdot bc + \frac {1}{ab + bc}\cdot ab + \frac {1}{ab + ac}\cdot ac.$
Id est, $ 2\left(\frac {ab}{ c(a + b) } + \frac {bc}{ a(b + c) } + \frac {ac}{ b(c + a) }\right)\geq$
$ \geq\frac {1}{ac + bc}\cdot ac + \frac {1}{ab + bc}\cdot bc + \frac {1}{ab + ac}\cdot ab + \frac {1}{ac + bc}\cdot bc + \frac {1}{ab + bc}\cdot ab + \frac {1}{ab + ac}\cdot ac = 3.$
It gives the proof of original inequality.

then is [url=http://www.mathlinks.ro/viewtopic.php?t=47342]this[/url] method right?  :maybe:

[quote="farbod_mp2002"]

Prove that for every three postitive reals $ {a, b, c}$ the following inequality holds:

$ \frac {ab}{ c(a \plus{} b) } \plus{} \frac {bc}{ a(b \plus{} c) } \plus{} \frac {ac}{ b(c \plus{} a) } > \equal{} \frac {3}{2}$[/quote]

let $ x\equal{}ab,y\equal{}ac,z\equal{}bc$ then the inequality becomes:

$ \sum {\frac{x}
{{y \plus{} z}} \geqslant \frac{3}
{2}}$
  wich is true  :ninja:

[quote="madness"]then is [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=196278]this[/url] method right?  :maybe:[/quote]
No! Because we don't have there the same orderliness or ( and  :D  ) the opposite orderliness. :wink:

[quote="farbod_mp2002"]For all positive reals $ x,y,z$ such that $ {xyz} \equal{} 1$ prove that:

$ \frac {xy}{x \plus{} 1} \plus{} \frac {yz}{y \plus{} 1} \plus{} \frac {zx}{z \plus{} 1} > \equal{} \frac {3}{2}$

if we assume $ x \equal{} \frac {a}{b} , y \equal{} \frac {b}{c} , z \equal{} \frac {c}{a}$ , the problem can be restated as:

Prove that for every three postitive reals $ {a, b, c}$ the following inequality holds:

$ \frac {ab}{ c(a \plus{} b) } \plus{} \frac {bc}{ a(b \plus{} c) } \plus{} \frac {ac}{ b(c \plus{} a) }\,\geq\frac {3}{2}$[/quote]
we have $ xyz \equal{} 1$
so inequality $ \iff$

$ \frac {1}{z(x \plus{} 1)} \plus{} \frac {1}{x(y \plus{} 1)} \plus{} \frac {1}{y(z \plus{} 1)}\,\geq\,\frac {3}{2}$

by convexity of $ \frac {1}{x}$ and by jensen inequality :

$ \frac {1}{z(x \plus{} 1)} \plus{} \frac {1}{x(y \plus{} 1)} \plus{} \frac {1}{y(z \plus{} 1)}\,\geq\frac {9}{xz \plus{} xy \plus{} yz \plus{} x \plus{} y \plus{} z}$

now by AM-GM :  $ xz \plus{} xy \plus{} yz \plus{} x \plus{} y \plus{} z\,\geq\,6$
so :

$ \frac {1}{z(x \plus{} 1)} \plus{} \frac {1}{x(y \plus{} 1)} \plus{} \frac {1}{y(z \plus{} 1)}\,\geq \frac {9}{6} \equal{} \frac {3}{2}$

 :D

it's false $ \frac{9}{\sum xy\plus{}\sum x}\geq \frac{9}{6}$.

[quote="mehdi cherif"]no it's true $ \frac {9}{\sum xy \plus{} \sum x}\geq\frac {9}{6}$[/quote]
OK. $ \frac {9}{\sum xy \plus{} \sum x}\geq\frac {9}{6}\Leftrightarrow$
$ \Leftrightarrow6\geq x\plus{}y\plus{}z\plus{}xy\plus{}xz\plus{}yz,$ which wrong. Are you agree with me?


geometry
function
symmetry
analytic geometry
parameterization

A square has its base on the x-axis, and one vertex on each branch of the curve y= 1/x^2. What is its area?

Not sure if I handled this correctly but here goes:

We are looking for the points $ (x,y)$ and $ (\minus{}x,y)$ such that the distance between these two points is the same as the distance between one of the points and the $ x$-axis.  Then the distance between the two points is
$ \sqrt{(x\minus{}\minus{}x)^{2}\plus{}(y\minus{}y)^{2}}\equal{}\sqrt{2x^{2}}\equal{}\sqrt{2}x$
The distance between $ (x,y)$ and $ (x,0)$ (or $ (\minus{}x,y)$ and $ (\minus{}x,0)$, doesn't really matter), is
$ \sqrt{(x\minus{}x)^{2}\plus{}(y\minus{}0)^{2}}\equal{}\sqrt{y^{2}}\equal{}y$
Then
$ y\equal{}\sqrt{2}x\Rightarrow\sqrt{2}x\equal{}\frac{1}{x^{2}}\Rightarrow x^{3}\equal{}\frac{\sqrt{2}}{2}\Rightarrow x\equal{}\sqrt[3]{\frac{\sqrt{2}}{2}}$
Then the length of one side is $ 2x$ and the area is
$ (2x)^{2}\equal{}4x^{2}\equal{}\frac{4}{\sqrt[3]{2}}\equal{}2\sqrt[3]{4}$

In the attached figure, let $ P\left(x,\ \frac {1}{x^2}\right)\ (x > 0)$, we have  the conditon of the square gives $ 2x \equal{} \frac {1}{x^2} \equal{} the\ side\ length\ of\ the\ square$.

$ \Longleftrightarrow x^3 \equal{} \frac {1}{2}$. Thus the area of the square is $ 2x\cdot \frac {1}{x^2} \equal{} \frac {2}{x} \equal{} \boxed{2\sqrt [3]{2}}$.

Yes, kunny is right.  I typed in a 4 beneath the radical instead of a 2.

Very easy, but this problem makes me ask a couple interesting questions. [hide]$ s\equal{}\frac{4}{s^2}\Rightarrow s^3\equal{}4$ and so $ s^2\equal{}2\sqrt[3]{2}$[/hide]
I found the solution simple only because I assumed the square existed. In this case I believe the square's existence can be confirmed with the intermediate value theorem. Here's a related problem I just made I'd like to see how you guys solve it.

Prove or disprove that there exists a square whose vertices lie on the graph of $ y\equal{}\frac{1}{x}$ such that two vertices are in the first quadrant and two are in the third. If such a square exists, compute its area.

[hide="My approach"]Letting $ y\equal{}f(x)$ we see that $ f(f(x))\equal{}x$, so $ f$ is the inverse of $ f$. Thus, the two points in the first quadrant are $ \bigg(\frac{1}{x},x\bigg), \bigg(x,\frac{1}{x}\bigg)\equal{}p_1,p_2$ respectively. Equating the distance between these two points and the distance between the point $ \bigg(\minus{}\frac{1}{x},\minus{}x\bigg)$ and $ p_2$ I derived the identity $ \minus{}4\equal{}4$ which is false. Thus no such square exists.[/hide]

Your approach seems good.  It sort of follows from common sense since the function has no components in the second or fourth quadrants.

[b]@Iguil:[/b] Note, by symmetry, that we must have an origin-centered square that is symmetric about the lines x=y an x=-y, as is implied by your setup of the coordinates in terms of the parameter $ x$. Thus, the diagonals of the square are either on the lines y=x and y=-x, or on the x and y axes. However, in the first case, the line y=-x never intersects the graph of xy=1, and in the second case, neither the x nor y axis intersects the graph (they are asymptotes). Thus, such a square cannot exist.

Ah. And analytically we can extend my approach show letting x tend to infinity which is clearly the only case for equality.


A large square region is divided into four congruent, non-overlapping square regions.  If the perimeter of one of these small square regions is 60 cm, what is the area of the large square?
[metapost=5c6f9045af0d3f9019200c3f3a0e38bb] save u;

 % Set the value of u to scale the entire image
 u:=2.5cm;

 draw (0,0)--(u,0)--(u,u)--(0,u)--cycle;
 [/metapost]

One of the square's side length is 15 because 60/4=15. There are two of these side lengths in the huge square. 15+15=30. 30x30=900

Unfortunately, I can not fix the code, however I don't think a diagram is needed.

If the perimeter is 60, then the side length is $ 60 \div 4 \equal{} 15$. That means the area of one small square is $ 15^2$ or $ 225$. Since the large square is made up of four congruent squares like these, then the total area is $ 225 \times 4 \equal{} \boxed{900}$.

EDIT: Beaten to it.


The sides of a triangle have lengths $ 6$, $ 8$, and $ 10$. Prove that there is exactly one line which simultaneously bisects the area and the perimeter of the triangle.

if i didnot misunderstand,

For the right angle, $ xy \equal{} 24$ and $ x \plus{} y \equal{} 12$ $ (i)$.
For the smallest angle, $ xy \equal{} 40$ and $ x \plus{} y \equal{} 12$. $ (ii)$
For the other angle,  $ xy \equal{} 30$ and $ x \plus{} y \equal{} 12$ . $ (iii)$
$ xy \leq 36$ then it is $ (i)$ or $ (iii)$.
For $ (i)$, $ \max(x,y) \equal{} 6 \plus{} 2\sqrt {3} \geq 8$. It does not hold.
For $ (iii)$, $ 6 \leq \max(x,y) \equal{} 6 \plus{} \sqrt {6} \leq 10$. So only there is one line.


logarithms
function
real analysis
probability and stats

Using the fact that the function $ u(t,x) : \equal{} (1\plus{}t)^{\minus{}1/2}\exp(B^2_t/(2(1\plus{}t)))$ has the property that $ t\to u(t,B_t)$ is a martingale (which is easy to verify), I want to show that we have the bound

\[ \limsup_{t\to\infty} \frac{B_t}{(2t\log t)^{1/2}} \leq 1
\]

(i suspect that $ 1$ is not the best such constant we can get by these methods).  I have tried assuming the contrary (that the limsup is at least $ 1\plus{}\varepsilon$ for some $ \varepsilon>0$) and stopping $ u(t,B_t)$ at the first time $ T\geq 1$ that the fraction above is at least $ 1\plus{}\varepsilon$.  $ T<\infty$ almost surely, so it seems like by considering $ T\wedge t$ and letting $ t\to\infty$ we should be able to get a contradiction from optimal stopping, but i don't think this works because if we apply it to similar martingales we should be able to draw absurd conclusions.

I do not see anything principally wrong with your method. All you need is to take the expectation and stop not the first time where you are above $ 1\plus{}\varepsilon$ but the first such time after some big time $ t_0$ that will go to infinity in the end. :) Basically everything boils down to the fact that if $ M_t$ is a non-negative martingale, then $ \sup_{t\ge 0}M_t<\plus{}\infty$ almost surely. I'm inclined to believe that you had such a statement somewhere (the proof is exactly the same as your stopping time argument).

[quote="fedja"]Basically everything boils down to the fact that if $ M_t$ is a non-negative martingale, then $ \sup_{t\ge 0}M_t < \plus{} \infty$ almost surely.[/quote]

yes, [i]this[/i] is the right idea, not what i had :)


calculus
derivative
algebra
polynomial
parameterization
number theory theorems
number theory

It is sometimes said that polynomials behave like integers, but are easier to deal with, because polynomials have derivatives. (Fermat's last theorem is much easier to prove for polynomials than for integers).

  So what would the derivative of an integer $n$ be? Given its prime decomposition $n=p_{1}^{r_{1}}p_{2}^{r_{2}}\dots p_{s}^{r_{s}}$, it seems reasonable to define $n'=r_{1}p_{1}^{r_{1}-1}p_{2}^{r_{2}}\dots p_{s}^{r_{s}}+r_{2}p_{1}^{r_{1}}p_{2}^{r_{2}-1}\dots p_{s}^{r_{s}}+\dots+r_{s}p_{1}^{r_{1}}p_{2}^{r_{2}}\dots p_{s}^{r_{s}-1}$. Is this "derivative" good for anything?

  P.S. The idea that primes are like independent variables was around for quite some time. Strangely, I did not find the sequence $\{n'\colon n=2,3,4,\dots\}$ in Sloane's encyclopedia. It begins with $2,3,4,5,5,7,12,6,7,11,16\dots$

The proof of FLT is based on Mason's theorem and in that theorem the number of distinct roots of the polynomials is essential. I think you need to define some kind of analogue parameter to generalize the theorem. I have never seen any application of the "derivative of an integer" but who knows if this is a new powerfull method to solve some conjectures, like the abc.


ARML LaTeX probability geometry rectangle trapezoid

Post solutions to the individual problems here and I will collect the best one from each problem and put them into a LaTeX file. (I didn't see ARML in the contest directory)

He's right, but I wrote out a more detailed explanation for Team #8 if anyone wants to see it. I'm more proud of the LaTeX than anything. :)

[hide="hidden because its huge"]We can create a recursive sequence that's based on both the floor and the number of people in the elevator. Let's call this sequence $P(n,f)$ for the probability of $n$ people being on the elevator after it opens on the $f$th floor. We are looking for $P(3,f)$ for any $f$.

\[ P(3,f) = \frac{1}{2} P(2,f+1) \]
\[ P(2,f) = \frac{1}{2} P(1,f+1) \]
\[ P(1,f) = \frac{1}{2} P(0,f+1) + \frac{1}{2} P(2,f+1) \]
\[ P(0,f) = \frac{1}{2} P(0,f+1) + \frac{1}{2} P(1,f+1) \]
\[ P(0,6) = \frac{1}{2} \]
\[ P(1,6) = \frac{1}{2} \]
\[ P(2,6) = 0 \]

The elevator can't have 3 people until after opening on floor 4, so we can start there, using the definitions above.

\begin{eqnarray*} P(3,4) &=& \frac{1}{2} * P(2,5) \\ &=& \frac{1}{2} * \frac{1}{2} * P(1,6) \\ &=& \frac{1}{2} * \frac{1}{2} * \frac{1}{2} \\ &=& \frac{1}{8} \end{eqnarray*} \begin{eqnarray*} P(3,3) &=& \frac{1}{2} * P(2,4) \\ &=& \frac{1}{2} * \frac{1}{2} * P(1,5) \\ &=& \frac{1}{2} * \frac{1}{2} * \left(\frac{1}{2} * P(0,6) + \frac{1}{2} * P(2,6) \right) \\ &=& \frac{1}{2} * \frac{1}{2} * \left(\frac{1}{2} * \frac{1}{2} + \frac{1}{2} * 0 \right)\\ &=& \frac{1}{16} \end{eqnarray*} \begin{eqnarray*} P(3,2) &=& \frac{1}{2} * P(2,3) \\ &=& \frac{1}{2} * \frac{1}{2} * P(1,4) \\ &=& \frac{1}{2} * \frac{1}{2} * \left(\frac{1}{2} * P(0,5) + \frac{1}{2} * P(2,5) \right) \\ &=& \frac{1}{2} * \frac{1}{2} * \left[ \frac{1}{2} * \left(\frac{1}{2} * P(0,6) + \frac{1}{2} * P(1,6) \right) + \frac{1}{2} * \frac{1}{2} * P(1,6) \right]\\ &=& \frac{1}{2} * \frac{1}{2} * \left[\frac{1}{2} \left(\frac{1}{2} *\frac{1}{2} + \frac{1}{2} * \frac{1}{2} \right) + \frac{1}{2} * \frac{1}{2} * \frac{1}{2} \right] \\ &=& \frac{3}{32} \end{eqnarray*}
The total probability is $\frac{1}{8} + \frac{1}{16} + \frac{3}{32} = \frac{9}{32}$.
[/hide]

I can't believe I forgot to count  25 and 26 on the "base 10 in base 3 and 5, digits are same in #" question..... GAAAH!!!!!.....  is the only way to say to myself "hey, I bet 25 and 26 work" to actually try them randomly, or do I have to know that by heart?  Does it just come with fluency in random bases?

Ok my solution is to #1 on the Team questions:

Question:

A cylinder of height 10 cm and radius 6 cm is turning at 1 revolution per
minute. A paintbrush 4 cm wide starts at the top as shown and slowly
moves vertically down the cylinder at 1 cm/minute. Compute the time in
minutes it takes for the paintbrush to paint three-fifths of the lateral surface
area of the cylinder.

My solution (warning: contains really bad paint drawings):
[hide]

Consider the cylindrical surface as a rectangle, such as this one.

[img]http://i19.photobucket.com/albums/b158/japanman2012/paintroller.jpg[/img]

Each color down the rainbow is the next stroke of the brush per second, got it?

Ok, total area of the rectangle is $120\pi$.  I want to find the non-painted $\frac{2}{5}$ of it.  $\frac{2}{5}\ast 120\pi = 48\pi$  At the top, the black area is not painted, and the area of that triangle is $6\pi$, so the area of the trapezoidal non-painted area we want at the bottom is $48\pi-6\pi = 42\pi$.

Consider the bases of that trapezoid to be $x$ and $x+1$, then
$\frac{12\pi(2x+1)}{2}= 42\pi$

Simplified, $12x+6 = 42 \Rightarrow 12x = 36 \Rightarrow x = 3$  So then the base on the left is 4, and the rest of that side is 6.  4 + 1 + 1 = 6, and that was 3 minutes (it's in minutes, right?).  Final answer is 3.[/hide]

[quote="futuremontrealian"]I can't believe I forgot to count  25 and 26 on the "base 10 in base 3 and 5, digits are same in #" question..... GAAAH!!!!!.....  is the only way to say to myself "hey, I bet 25 and 26 work" to actually try them randomly, or do I have to know that by heart?  Does it just come with fluency in random bases?[/quote]

[hide]You'd have to realize that any number between $5^{x}$ and $3^{x+1}-1$ inclusive would work, where x is a non-negative integer.

And once you get to $x = 3$, you'll have to find numbers between 125 and 80, which is impossible, since 125 is bigger than 80.[/hide]

They're all on my blog. I haven't seeen the ARML solutions, so there are probably repeats. (The images don't work yet. :()


Let $ (u_{n})$  be a sequence given by $ u_{1}$  anh the formula $ u_{n\plus{}1}\equal{}\frac{k\plus{}u_{n}}{1\minus{}u_{n}}$,where $ k\geq 0;n\equal{}1;2;...$
Gicen that $ u_{13}\equal{}u_{1}$.Find value of $ k$

You've already posted this here:
[url]http://www.artofproblemsolving.com/Forum/viewtopic.php?t=163241[/url]

Do not double post.


geometry
geometric transformation
reflection

Suppose you have 4 points: (0,0), (0,1), (1,0), and (1,1) on the xy-plane.  The allowed move at each step is to choose any two distinct points and reflect one point with respect to the other point (just like in checkers).  For example, if I reflect (0,0) with respect to (0,1), then I get a new set of 4 points: (0, 2), (0,1), (1,0), and (1,1).

Can you apply this move a finite number of times to get (0,0), (1,1), (2,-1), and (3,0)?

This is a problem from a running contest in Germany. Could mods lock the topic/delete i_like_pie's solution?

(It's problem 4 here: http://www.bundeswettbewerb-mathematik.de/aufgaben/pdf/aufgaben/aufgabenblatt_08_1.pdf)

Oh, btw my solution is a little more complicated; I like it anyway :P


When I'm in Alcumus, the My Classes tab doesn't show on the sidebar.


And that's a screenshot from ... (time, place, etc.)

i think he took that screenshot from a classroom.

I was there at WOOT yesterday when that happened. I saw it. It was real.

Yeah I have no idea what that happens. But the good news is that we'll be changing the classroom soon so these problems should appear anymore ...

[quote="AIME15"]Well you know on the classroom page where it says 'click here if it says ur username is in use"?  if you click there, but keep your other window open, it'll make clones like that...but usually it goes by 2's, and won't go to letters....

like it'll be
AIME15
AIME15_2
AIME15_4
AIME15_6
AIME15_8
AIME15_10[/quote]
It goes to letters when it runs out of numbers. (but i don't know how far the numbers go)

Hmmm I believe the numbers should go by powers of 2. However, by changing the url, you might get that result.

Well I once got to james4l_!

Yes, that's right, that's an exclamation point.

It was during a WOOT party last year.


Having a hard time solving for C in the following equation:

R = Ro + Kc * (1/1 + exp[-(a + b*lnC + cC)])

where Ro, Kc, a, b, c are constants

I get as far as isolating the following on the right side of the equation:

b*lnC + cC

Thanks

hello, do you mean
$ R\equal{}R_0\plus{}K_c\left(\frac{1}{1\plus{}e^{\minus{}a\plus{}b\ln(C)\plus{}cC}}\right)$
What is $ cC$?
Sonnhard.

[quote="Dr Sonnhard Graubner"]hello, do you mean
$ R \equal{} R_0 \plus{} K_c\left(\frac {1}{1 \plus{} e^{ \minus{} a \plus{} b\ln(C) \plus{} cC}}\right)$
What is $ cC$?
Sonnhard.[/quote]

There are parentheses in the exponential beween the negative sign and a, then after the C, i.e.
-(a + b*lnC + cC)

hello, is this the right formula
$ R\equal{}R_0\plus{}K_c\left(\frac{1}{1\plus{}e^{\minus{}(a\plus{}b\ln(C)\plus{}cC)}}\right)$?
What is the meaning of $ cC$?
Sonnhard.

[quote="Dr Sonnhard Graubner"]hello, is this the right formula
$ R \equal{} R_0 \plus{} K_c\left(\frac {1}{1 \plus{} e^{ \minus{} (a \plus{} b\ln(C) \plus{} cC)}}\right)$?
What is the meaning of $ cC$?
Sonnhard.[/quote]

That is the correct formula.

cC represents the constant c multiplied by a concentration C, i.e. c*C.

Thank you

hello, i have found the following solution
$ C\equal{}{{\rm e}^{\minus{} \left( {\it LambertW} \left( c{{\rm e}^{\minus{} \left( \ln
 \left( {\frac {\minus{}R\plus{}{\it R0}\plus{}{\it Kc}}{R\minus{}{\it R0}}} \right) \plus{}a \right)
{b}^{\minus{}1}}}{b}^{\minus{}1} \right) b\plus{}\ln  \left( {\frac {\minus{}R\plus{}{\it R0}\plus{}{\it Kc}}
{R\minus{}{\it R0}}} \right) \plus{}a \right) {b}^{\minus{}1}}}$
Sonnhard.


linear algebra
matrix
linear algebra unsolved

If $A \in {\mathbb R}^{n \times n}$ and $detA > 0$ then can we say that $A$ is positive defined? If yes make a proof, if no why ?

The matrix $\begin{bmatrix}-1&0\\0&-1\end{bmatrix}$ is negative definite, with positive determinant.


Consider $\triangle ABC$ with $c \leq b \leq a$. Points $X$, $Y$, and $Z$ are on $BC$, $AC$, and $AB$ respectively and intersect at point $P$ inside $\triangle ABC$.
Prove $AX+BY+CZ<2a+b$

I think I found a "slick" way to prove this but I want to see others' solutions as well. I will post my solution after a few people have shown their methods.

[quote="DPopov"]By the way, can anyone prove or disprove $AX+BY+CZ<a+b+c$ :P[/quote]
It is wrong statement. Indeed, consider isosceles triangle with large $a=b$ and very small $c$. Take $P$ nearly to $C$. Then $AX+BY+CZ\approx 3a \gg a+b+c$

[quote="DPopov"]Consider $\triangle ABC$ with $c \leq b \leq a$. Points $X$, $Y$, and $Z$ are on $BC$, $AC$, and $AB$ respectively and intersect at point $P$ inside $\triangle ABC$.
Prove $AX+BY+CZ<2a+b$[/quote]
Indeed, $a=BC>BY,CZ$ and $b=AC>AX$.

Indeed you are correct. However, how did you go about proving $BC>BY \displaystyle{?}$

[hide="What do you think of this method?"]
This is how I approached it. Note that point $Z$ lies on $AB$. Assume $CZ>AC, BC$. Rotate cevian $CZ$ to coincide with side $BC$. Since $CZ>BC$ point $Z$ will lie past point $B$. Now rotate segment $CZ$ 360 degrees forming a circle. Clearly, $\triangle ABC$ will lie in the interior of the circle while point $Z$ will lie on the circumference since $CZ$ is the radius.

However, this contradicts the fact that point $Z$ lies on $AB$.

Thus, $CZ< \displaystyle{max}(AC, BC) \Rightarrow CZ<BC \Rightarrow CZ<a$.

Using similar reasoning we can conclude \[BY<BC \Rightarrow BY<a\]
\[AX<AC \Rightarrow AX<b\]

Hence, $AX+BY+CZ<2a+b$

[/hide]

For each cevian $AX$ the following inequality holds: $AX\leq \max(AB,AC)$.

:lol: That is exactly what I did, except I just went about proving it. Also [quote]It is wrong statement. Indeed, consider isosceles triangle with large $a=b$ and very small $c$. Take $P$ nearly to $C$. Then $AX+BY+CZ\approx 3a \gg a+b+c$[/quote] Shouldn't it be $AX+BY+CZ\approx 2a+b \gg a+b+c \displaystyle{?}$

Ah, ok. But if it were not isosceles but any triangle then you would get $ AX+BY+CZ\approx 2a+b \gg a+b+c \displaystyle{?}$

No, it's only in the extreme case that he chose that either of those relations (the approximation or the >>) are valid.  He took an extremely long, skinny triangle so that each of the cevians are approximately as long as the two long sides while the third side is very small.  That is what gives us those two relations.

Two of the cevians become as long as side $a$ while the third becomes as long as side $b$. Thus, shouldn't it be $2a+b$ in the general case? Myth used an isosceles triangle where $a=b$ to get $3a$.

What you're saying doesn't add any generality -- since Myth's example requires one of the sides to be very small, the other two sides are approximately equal to each other anyhow.  There is essentially no distinction between 2a + b and 3a.  If this isn't answering your question, then I'm not sure what you're asking.

I understand his method since it's practically the same but using an isosceles triangle. All I was asking is what happens if the triangle is not isosceles, $a \neq b \neq c$, then $AX+BX+CZ \approx 2a+b \displaystyle{?}$ when their intersection gets infinitely close to vertex $C$


geometry
circumcircle
trigonometry
geometry unsolved

The cyclic octagon ABCDEFGH has sides a,a,a,a,b,b,b,b respectively. Find the radius of the circle that circumscribes ABCDEFGH in terms of a and b.

This should be moved to mathcounts. The circumradius R does not depend on the order of the octagon sides. Let AB = a, BC = b. The arc AC is one quarter of the circumcircle, $\angle AOC = 90^\circ,$ $AC = R \sqrt 2,$ $\angle ABC = 180^\circ-\frac{\angle AOB}{2}= 135^\circ.$ Using the cosine theorem for the triangle $\triangle ABC,$

$2R^{2}= a^{2}+b^{2}-2ab \cos 135^\circ = a^{2}+b^{2}+ab \sqrt{2}$

$R = \sqrt{\frac{a^{2}+b^{2}+ab \sqrt{2}}{2}}$


Let [tex] x,y,z [/tex] be three real numbers that satisfies [tex] x+y+z=\frac{\pi}{2} [/tex]
Prove that:
[tex] |\frac{cosx}{sin(y-z)}|+|\frac{cosy}{sin(x-z)}|+|\frac{cosz}{sin(x-y)}| \geq 2 [/tex]  :)

[quote="kunny"][quote="Anh Cuong"]Let [tex] x,y,z [/tex] be three real numbers that satisfies [tex] x+y+z=\frac{\pi}{2} [/tex]
Prove that:
[tex] |\frac{cosx}{sin(y-z)}|+|\frac{cosy}{sin{x-z}}|+|\frac{cosz}{sin(x-y)}| \geq 2 [/tex]  :)[/quote] :?[/quote]
What do you imply, kunny  :|  :?:

Put $\frac{cosx}{sin(y-z)}=a$,..etc We have:
$cosx.sin(y-z)=sin(y+z)sin(y-z)=\frac{cos2z-cos2y}{2}=cosz^2-cosy^2$Hence:$a=\frac{cosx^2}{cosz^2-cosy^2}$.Put $cosx^2=m,cosy^2=n,cosz^2=p$then $ab+bc+ca=\frac{mn}{(p-n)(m-p)}+\frac{np}{(m-p)(n-m)}+\frac{pm}{(n-m)(p-n)}=-1$
So$\sum ab=-1$And by $(|a|+|b|+|c|)^2=a^2+b^2+c^2+2(|a||b|+|b||c|+|c||a|)\geq a^2+b^2+c^2-2(ab+bc+ca)\geq 4$(Because $a^2+b^2+c^2\geq -2(ab+bc+ca)$ which is equivalen to $(a+b+c)\geq 0$)
And we're done


hey u might have come across some news channels spreading news about the large hadron collider project
wat r ur thoughts on it?
specially that the world is going to end  :rotfl:  :rotfl:  :rotfl:

There's another thread on this in The Round Table.

Its just useless thing  :mad:

9.2 billion dollars wasted(as stephen Hawkings thinks,and me too :rotfl: )

but media made it worse
Many ppl were too frightened :rotfl:

specially 'bout the thing that the earth will transformed in a black hole

yeah......really it is waste of money if it is only to attemt the ultimate triumph of human reason....(the unified field theory)

well actually its not a waste of money at all :o

achieving a speed close to light and getting a glimpse of Higg's boson is no joke
well they r trying to find out what is mass ...and u say its a waste of money????wat's the beneficial use of money then?making action thrillers?F1? :rotfl:

correct that point was worth it!

it is not an easy task to acheive those conditions and its also not  a fools job otherwise india would have never contributed 110 crores for this project and send a delegate of 254 scientists.

and also we are talkin 'bout the grand unified theory and attempting to look into higgs concept of mass speculation.
 :rotfl:
i dont think we are talkin 'bout the unified field theory

I agree. It's not a waste of money. If you calculate how many ppl you could feed with that money, then the same applies for a huge percent of the world spending.

However the "End of World" hysteria is totally bogus and is a media trick to increase TRP.

vignesh u should think for both sides
thats the point :rotfl:  :rotfl:  :rotfl:

no,I was just telling that it was a gamble that the scientists played.
[hide="But"]I'ld have loved to be at their place :rotfl:  :rotfl: [/hide]

I think it is always difficult to comment on any topic till one has complete knowledge about it , but in most cases people comment on topics without having any knowledge about it (not related to anything here :P)

Anyways , all i know is that

hawking didn't say that its waste , indeed he said ->
""Whatever the LHC finds, or fails to find, the results will tell us a lot about the structure of the universe,"

btw the latest news is
'God particle' theorist Peter Higgs attacks Stephen Hawking'
:D

[quote="rt_08"]i am challenging steven hawking and higgs of the rt particle and whose independence doesnt depend upon lhc project.(and ofc those crores of rupees should be sent to me) :D  :)  :roll:[/quote]

thats stephen hawking!  :huh:  :huh:

naah thats me the evil mind :mad:  and the creator of the rt particle :P
 :P

congrats :D
You should get nobel for that

I am proud of knowing nobel laurate rt on whose name,a particle is named :rotfl:

whoooooooooooooppppppppppppieeeeeeeeeeeeeeeee. :P  :rotfl:  :P

sorry for those who are woki'n on that project.i made an unreasonable comment with out knowing what it is actually :blush:  :blush:  :blush:

it is ok and take it down!
by the way where had u lost ur way
u werent active for quite a few days i suppose1

Well apparently there was an electrical problem and since they are worried about energy, they are shutting it down for a few months.

i haven't heard that :o  :mad:
its not a too good news :(

it will regain its start session on 21 october according to my contacts present there


Mr. J left his entire estate to his wife, his daughter, his son, and the cook. His daughter and son got half the estate, sharing in the ratio of $ 4$ to $ 3$. His wife got twice as much as the son. If the cook received a bequest of $ \$500$, then the entire estate was:

$ \textbf{(A)}\ \$3500 \qquad\textbf{(B)}\ \$5500 \qquad\textbf{(C)}\ \$6500 \qquad\textbf{(D)}\ \$7000 \qquad\textbf{(E)}\ \$7500$

Let e be the value of the estate, 4x be the amount that the daughter got, and 3x be the amount that the son got. Then we have the equation 4x + 3x = 1/2 e, so x = 1/14 e. Then the daughter got 4/14 e and the son got 3/14 e. The mother got twice the amount that the son got, which is 6/14 e. That leaves 1/14 e for the butcher. Since he got $ 500, we have the equation 1/14 e \equal{} 500, e \equal{}$7000 (D)


LaTeX
real analysis
real analysis unsolved

Could you help me with this problem  Robin
Method of Images
∇$ ^2u$(ξ,η)=h(ξ,η) ,ξ>0 ,η>0
u(0,η)=f(η)
u$ _h$(ξ,0)=g(ξ)

spinos can you write your problem on Latex ?
and also : what are you asking here ?

My friend Extremal
Iam asking how can I use the method of images to solve the above partial Linear Partial
Differential Equation
Do you know where can I find this method


Let ABC be an acute-angled triangle. Let D, E, F be the feet of the altitudes of the triangle ABC from the vertices A, B, C, respectively. Let one of the two tangents from the point D to the circle with diameter AH (which one exactly is taken doesn't matter!) meet the line CA at a point E', and let the other tangent meet the line AB at the point F'. Prove that the lines AD, BE' and CF' concur at one point.

  Darij

Let $T=E'F'\cap BC,S=E'F'\cap AD$. What we must show is that $E'A\cap F'A,\ E'D\cap F'D,\ E'B\cap F'C$ are collinear, which is equivalent to $(E'C,E'B;E'D,E'T)=(F'B,F'C;F'D,F'T)$, which, in turn, is equivalent to $(B,C;D,T)=-1$, i.e. $T$ is $EF\cap BC$.

This follows from $(B,C;D,T)=(AB,AC;AD,AT)=(AF',AE';AS,AT)=(DF',DE';DS,DT)=-1$. So we can see that it can be made a lot more general: all we need are two lines through $D$ symmetric wrt the altitude.


My school just had a MathCounts school round yesterday. When our team members heard that within our city, they had the highest school round scores, they were really psyched up to make states after chapter. Most of them aren't so great, the average score for the tests was about [color=red]XX[/color], but the rest of our chapter has pretty weak teams this year. Any suggestions for getting the whole team to states?

[color=red]Moderator rcv's note:  Please do not discuss questions, scores, or difficulty of the 2006 School Round until after February 26.[/color]

do good at chapters. If there the best team, they will make it

How fast should I be able to do MC sprint problems at chapter level? Could I make state if I get the answer to about every chapter sprint problem in 4 seconds? Is that fast enough?

woah you can do them that fast :what?: :help:

you can make states guaranteed

Getting one wrong in one second isn't worth as much as taking 1.2 minutes to do one correctly.

Just look at your scores, I would say a 40+ gets you into countdown, 35+ if your lucky, 43+ if your at a crazygood chapter, but don't rely on scores alone.  You have to look at the difficulty of the problems, and dont be discouraged if they're hard, because hard problems are hard for everyone  :D .

I wouldn't worry about scores at all.
If you worried about scores in last year's state, you would have killed yourself for doing so bad.
But the problems were so hard that you could make nationals with a substantially lower score.

[quote="mathnerd314"]On average you get 80 seconds per problem on sprint, 180 seconds per problem on target, and 120 seconds per problem on team.[/quote]

Usually it's more like 30 seconds for the first 15 problems and 130 (of however many left) for the last 15.  :D

[quote="xxm0rg07hxx"]The easier problems are usually at the front so I would say about 15 min. on 1-15 and 25 on 16-30, because 30 and 130 is too big a difference.  The first few problems are not that much harder than the last few.[/quote]

Don't you mean the last few are harder than the first few?   ;)

You also have to remember that most of the top people in the countdown round are going to be on the teams that go, so you could probably go with only a placing like 5th-8th, but that depends on how many people they take to state.

Sorry, I meant the last few are not that much harder than the first few.  But yeah, in my chapter,  at least 6-9 of the top 10 are on the top four teams.  And last year, my school and two other schools had a total of 9 students in the countdown.  Sometimes, it two students from the same school facing off, very disappointing if they are best friends.

chapter is never hard as state so prepare state :P


Given $ 101$ segments on a line, prove that there exist $ 11$ segments meeting in $ 1$ point or $ 11$ segments such that every two of them are disjoing.

[quote="pleurestique"]i think this famous result of Erdos helps:

given a sequence of $ mn \plus{} 1$ real numbers, there either exists an increasing subsequence of length $ m$ or a decreasing subsequence of length $ n$.[/quote]

OK, so how to complete it?  :)

well here's a solution. order the segments according to their left endpoints, and call them $ T_1, T_2, ..., T_{101}$, in that order. assume that no 11 segments meet in one point. we're going to find 11 segments, no 2 of which meet.

take the longest sequence of segments, starting with $ T_1$, such that all the segments of the sequence meet in a point. say that this sequence is $ T_1, ..., T_k$. set $ T_{a_1} \equal{} T_1$ and $ S_1 \equal{} T_1,...,T_k$ and for $ i\geq 1$, given $ S_i \equal{} T_x,...,T_y$, define
\[ T_{a_{i \plus{} 1}} \equal{} T_{y \plus{} 1},
\]

\[ S_{i \plus{} 1} \equal{} T_{y \plus{} 1},...,T_{j}
\]
where this is the longest sequence of segments starting at $ T_{y \plus{} 1}$ that meet in one point.

since, by assumption, each $ S_i$ is at most of length $ 10$, we've thus defined at least 11 segments, $ T_{a_1},T_{a_2},...,T_{a_{11}}$. note that for each $ i$, $ T_{a_i}\in S_i$.

now notice that every $ T_{a_i}$, for $ i\geq 2$, is disjoint from the segment in $ S_{i \minus{} 1}$ that has the leftmost right endpoint (or else $ S_{i \minus{} 1}$ could be extended by adjoining $ T_{a_i}$). in particular, there exists segment $ T_{b_1}\in S_1$ that is disjoint from segment $ T_{a_2}\in S_2$. this is our base case.

assume now that we have $ k$ segments $ T_{b_1}\in S_1, T_{b_2}\in S_2, ..., T_{b_k}\in S_k$, where $ 2\leq k\leq 10$, such that these segments are pairwise disjoint. assume also that $ T_{b_k} \equal{} T_{a_k}$. then by the same argument as in the previous paragraph, $ T_{a_{k \plus{} 1}}$ is disjoint from some segment $ T$ in $ S_k$. then $ T_{b_1},...,T_{b_{k \minus{} 1}},T,T_{a_{k \plus{} 1}}$ is a set of $ k \plus{} 1$ pairwise disjoint segments. ($ T$ may or may not equal $ T_{b_k} \equal{} T_{a_k}$, but either way, $ T$ is to the right of all segments $ T_{b_1}, ..., T_{b_{k \minus{} 1}}$, because $ T_{a_k}$ is, and because the left endpoint of $ T$ is the same as, or to the right of that of $ T_{a_k}$.)

so continuing inductively, we find a set of 11 segments with the desired property.

[quote="pleurestique"]

 because the left endpoint of $ T$ is the same as, or to the right of that of $ T_{a_k}$.)

[/quote]

Eh, are you sure? Why?

because, remember, i ordered the segments by their left endpoints.


$ x$ and $ y$ are two distinct positive integers. What is the minimum positive integer value of $ (x \plus{} y^2)(x^2 \minus{} y)/(xy)$ ?

$\textbf{(A)}\ 3  \qquad\textbf{(B)}\ 8  \qquad\textbf{(C)}\ 14  \qquad\textbf{(D)}\ 15  \qquad\textbf{(E)}\ 17$

[hide="Fast answer based on the form of the question"]Since $ 3$ is attained for $ x\equal{}y\equal{}2$, and it's the smallest of the choices, the answer is $ A$.[/hide]

[hide="answer"]
It's easy to see that [b]A[/b] is the answer by using the values $ 2$ in $ x$ and $ y$ to get $ 3$ and since it's the lowest of the choices then it's the most obvious answer.
[/hide]

Edit: Beaten

For non-multiple choice what would be a valid quick way of finding the answer?

answer key says it is $ 14$.
If you click the link at the top of the question, you will be redirected to the answer key.

$ \mbox{DISTINCT integers}$.

Wow.

I can't believe all three of us fell for that.

woah, they should put that in bold letters! lol

Edit: I was kidding, it was a joke.

They did not use bolds. If they were, probably i would not.

[hide="Good solution? Probably not."] Let such a minimum be $ n$. First, note that neither $ x$ nor $ y$ can divide the top part unless

$ y = kx$ or $ x = ky$, $ k \geq 2$. Two cases:

[b]Case 1[/b]: $ x > y$

\begin{align*} \frac{(x+y^{2})(x^{2}-y)}{xy} = \frac{(ky + y^2)(k^{2}y^{2} - y)}{ky^2} & = \frac{(k + y)(k^{2}y - 1)}{k} \\
& = k^{2}y - 1 + \frac{y(k^{2}y - 1)}{k} \end{align*}

Notice that $ k \nmid k^{2}y - 1 \Longrightarrow y = km,\ m \geq 1$, so

$ \begin{align*} k^{2}y - 1 + \frac{y(k^{2}y - 1)}{k} & = (k^{3}m - 1) + m(k^{3}m - 1) \\
& = (m + 1)(k^{3}m - 1)$.

Since we want to minimize, we pick $ k = 2, m = 1$, which gives us $ \boxed{n = 14}\  (x = 4, y = 2)$.

[b]Case 2[/b]: $ y > x$.

Through analogous logic (cancel $ x^{2}$,  separate $ - (k^{2}x + 1)$ from the factorization, realize $ x = km$), we may simplify to

$ n = (m - 1)(k^{3}m + 1)$;

Once again, we want to minimize, but this time we can't use $ m = 1$, so we pick $ k = m = 2$, which gives us $ \boxed{n = 17}$.

$ \therefore \boxed{n = 14}$

[/hide]


Could we have the problems of the second day ?

thank's

I posted 3 problems from second day, but I don't have the paper with subjects in front of me, and don't remember exactly the other 2. Also, I hope there are no mistakes in the ones I posted.
The final results will be given in a few hours.

Thank you frozen for problems.
Could we have the problem 4 and 6 second day IMC 2006 ?


[b]Let[/b] {$ A_{k}$},{$ B_{k}$} are two sequences matrices $ A_{m},B_{m} \in M_{n} \mathbb{(R)}$
[b]such that [/b] $ aI_{n}-A_{m},bI_{n}-B_{m}$ [b]are symmetric matrices and positive semidefinite  and [/b]
          $ \lim_{m \to \infty} {(A_{m}+B_{m})} =(a+b)I_{n}$
[b]Here[/b] $ I_{n}$[b] is nxn identity matrix .[/b]
[b]Prove that :[/b]
  $ \lim_{m \to \infty} {A_{m}}=aI_{n}$,$ \lim_{m \to \infty} {B_{m}}=bI_{n}$,

I am sorry ,I edited :$ A_{k},B_{k}$ is  $ A_{m},B_{m}$

With $ \forall x \in M_{n1}(R)$ we have :
 $ 0 \leq x^{T}(aI_n \minus{} A_m)x \leq x^{T}(aI_n \minus{} A_m)x \plus{} x^{T}(bI_n \minus{} B_m)x \equal{} x^{T}((a \plus{} b)I_n \minus{} (A_m \plus{} B_m))x$
  from $ \lim_{m \to \infty} {(A_m \plus{} B_m)} \equal{} (a \plus{} b).I_n$
we have $ \lim_{m \to \infty}{(x^{T}(aI_n \minus{} A_m)x)} \equal{} 0$ the same
 $ \lim_{m \to \infty}{(x^{T}(bI_n \minus{} B_m)x)} \equal{} 0$
1) the exist $ C_m \in S^{ \plus{} }_n$ such that :$ aI_n \minus{} A_m \equal{} C_m^2$ from $ Lim(x^{T}C_m^2x) \equal{} 0$ or $ Lim\parallel{}C_mx\parallel{}^2 \equal{} 0$ implies $ LimC_mx \equal{} 0$,   $ \forall x \in M_{n1}(R)$ , cho $ x \equal{} e_i$ implies $ C_m \to 0$
and $ aI_n \minus{} A_m \to 0$ and $ A_m \to aI_n$ when $ m \to \infty$ ({$ e_i$} basic of M_{n1}(R))
2)the  same  for $ B_m$


why is a foldline of a piece of paper always straight?

the area would change and thats impossible for pieces of paper (unlike some other things)


If N is the product of two primes whose sum is 999, compute the value of N.

Do you want people to post solutions to all of these?
[hide]If the sum of two primes is odd, one must be even ie 2 so the other is 997, so product is 1994[/hide]

[quote="Glen Mann"]how do you know 997 is a prime?

is there some fast way to check?[/quote]

Because there's no other possibilities so you don't have to check.

[quote="Inquisitor"][quote]Because there's no other possibilities so you don't have to check.[/quote]
It has been known for question setters to make mistakes... In this case, it does not take too long to check![/quote]

But the problem is invalid in that case so it's pointless.

I'm not actually disagreeing with you, I am just saying that since it takes so little time to check, it would certainly be worth doing it to ensure it actually works, ie that you haven't made a small logical slip earlier.

ok. To settle this down, I'll check.

[hide="checker"]Well, as some of you who are reading this might know, the trick of finding if a number x is prime is to divide it by primes less than or equal to the square root of x. The square rot of 997 is approxitmally 32, so we just diivide it by primes less than 32.

31 isn't a factor, 29, 23, 19, 17, 13, 11, 7, 5, 3, and 2 are all not factors. So it's prime.[/hide]

Yes, I used a calculator. It's stil easy to check without, but I'm at a computer, and the problem maker probably used a calculator too.


Who can say me what is the [u]digital sum[/u] mean ?

- Can be the digital sum of a square be (a)3, (b)1977

-Let Q(n) be the digital sum of n. Show that Q(n)=Q(2n) then 9|n.

Davron

We know that $Q(n) \equiv n \mod 9$, wich solves all the problems immediatly.

Harder one: how many $n$ are there with $Q(n^2)=451332$ not ending with $0$¿ (problem 451332 c) of the DeMO)


Let A and I be as follows.

A = [1 d]
[c b]
I=[1 0]
[0 1]

Prove that if b - cd != 0, then A is row equivalent to I

I'm CLUELESS as to WHERE TO START. Please help me

I tried simplifying to the matrix

[1 d]
[0 b - cd]

And have no clue what to do next.

You've made a good start, but there are some more tools available at your command. To show that two matrices are row-equivalent, you may perform any of the three following elementary row operations:

Multiply a row by a nonzero scalar.
Add a scalar multiple of one row to another row.
Swap two rows (that is, exchange the order).

(Actually, the first and third operations are both special cases of the second, except that the first one has a small restriction. After you've done this problem, think about why that's so. What is the restriction? What's the problem that could arise if we didn't have that restriction?)

Hint: Since $b-cd \ne 0$, you know that $\frac{1}{b-cd}$ is a legitimate nonzero scalar.


Four children are playing with marbles. At the end of the day one child has 4 less than half the marbles, the second child has 6 more than one fifth of the marbles, the third child has one third of what the first child had and the fourth child has 1 less than the third child.
How many marbles are there?

You are in luck; I'm a master at solving linear equations in one variable  :D

[hide]\[\frac{N}{2}-4+\frac{N}{5}+6+\frac{\frac{N}{2}-4}{3}+\frac{\frac{N}{2}-4}{3}-1=N\]\[\Longrightarrow31N-50=30N\Longrightarrow{N}=50.\][/hide]

AntonioMainenti, I appreciate that you're helping out in Getting Started Forum but if I'm correct, you're going to be senior and very experienced problem solver. I think it would be better for other people if you let the problem to be solved by other people first.

Giving hints are very welcome but solving the whole problem may discourage younger problem solvers to try the problem.

Thank you!

Alright, in the future I'll write [hide=solution][/hide] so people will know that if they click they will see more than just a hint. I was just joking when I said the thing about being a master at linear equations in one variable, by the way.

[hide]$\displaystyle\left(\frac12x-4\right)+\left(6+\frac15x\right)+\frac13\left(\frac12x-4\right)+\left(\frac13\left(\frac12x-4\right)-1\right)=x$

$\frac x2+\frac x5+\frac{x-8}{3}+1=x$

$\frac{31x-80}{30}+1=x$

$\fbox{x=50}$[/hide]


N is a positive integer whose units digit is 4. If the 4 is moved to the front of the number, a new integer M is formed which is four times N. Determine the smallest positive integer N that has this property.

Let $ N \equal{} \overline{a_ka_{k \minus{} 1}\ldots a_14}$, $ M \equal{} \overline{4a_ka_{k \minus{} 1}\ldots a_1}$, and $ x \equal{} \overline{a_ka_{k \minus{} 1}\ldots a_1}$

so that $ N \equal{} 10x \plus{} 4$ and $ M \equal{} 4\cdot10^k \plus{} x$.

Since we're given that $ M \equal{} 4N$,

$ 4\cdot10^k \plus{} x \equal{} 40x \plus{} 16$

$ \implies x \equal{} \frac {4\cdot10^k \minus{} 16}{39}$.

It quickly follow that the smallest possible value of $ k$ is $ 5$, which gives us

$ x \equal{} 10256\implies N \equal{} \boxed{102564}$.


modular arithmetic
algebra
polynomial
Rational Root Theorem

I was reading the proof of the rational root theorem in Volume 2 and I don't seem to understand one thing in it. I really understand how they got

$ a_o q^n \equiv 0 (mod p)$

(in case you don't know what i'm talking about, check page 58 and 59 of volume 2

Since $ p/q$ is a root, $ f(p/q)\equal{}0$, which means $ f(p/q)$ is divisible by $ p$.  Multiplying the whole expression by $ q^{n}$ doesn't change anything, so $ q^{n}f(p/q)\equal{}0$ is still divisible by $ p$.  That is, $ q^{n}f(p/q)\equiv 0\pmod{p}$.  The book then expands it out.  All of the first $ n$ terms (from the left) have powers of $ p$ in them, so they are obviously divisible by $ p$.  Since the whole expression is divisible, the last term has to be as well.  That is, $ a_{0}q^{n}\equiv 0\pmod{q}$.

I don't really understand how $ f(p/q)$ is divisble by $ p$

$ f\left(\frac{p}{q}\right)\equal{}0,$ and $ 0$ is divisible by $ p.$


vector
linear algebra
matrix
linear algebra unsolved

If $P=\left[ \begin{array}{ccc} A&0\\0&B \end{array}\right]$ is positve semidefined and $detB \neq 0$ then $A$ is positive semidefined and $B$ si positive defined(strictly)? IS THAT TRUE? If yes give a proof, if no why ?

Try test vectors of the form $\begin{pmatrix}v\\0\end{pmatrix}$ or $\begin{pmatrix}0\\w\end{pmatrix}$.