induction
inequalities
combinatorics proposed
combinatorics

Let $ G=(V,E)$ be a simple graph.

a) Let $ A,B$ be a subsets of $ E$, and spanning subgraphs of $ G$ with edges $ A,B,A\cup B$ and $ A\cap B$ have $ a,b,c$ and $ d$ connected components respectively. Prove that $ a+b\leq c+d$.

We say that subsets $ A_1,A_2,\dots,A_m$ of $ E$ have $ (R)$ property if and only if for each $ I\subset\{1,2,\dots,m\}$ the spanning subgraph of $ G$ with edges $ \cup_{i\in I}A_i$ has at most $ n-|I|$ connected components.
b) Prove that when $ A_1,\dots,A_m,B$ have $ (R)$ property, and $ |B|\geq2$, there exists an $ x\in B$ such that $ A_1,A_2,\dots,A_m,B\backslash\{x\}$ also have property $ (R)$.

Suppose that edges of $ G$ are colored arbitrarily. A spanning subtree in $ G$ is called colorful if and only if it does not have any two edges with the same color.
c) Prove that $ G$ has a colorful subtree if and only if for each partition of $ V$ to $ k$ non-empty subsets such as $ V_1,\dots,V_k$, there are at least $ k\minus{}1$ edges with distinct colors that each of these edges has its two ends in two different $ V_i$s.
d) Assume that edges of $ K_n$ has been colored such that each color is repeated $ \left[\frac n2\right]$ times. Prove that there exists a colorful subtree.
e) Prove that in part d) if $ n\geq5$ there is a colorful subtree that is non-isomorphic to $ K_{1,n-1}$.
f) Prove that in part e) there are at least two non-intersecting colorful subtrees.

I can't believe we are filling the Combinatorics forum with chessboard exercises while masterpieces like this remain unsolved.

Let me give some hints to a).

a) For every subset $F$ of $E$, let $c_F$ denote the number of connected components in the spanning subgraph of $G$ with edge set $F$. Then, the problem asks us to prove that $c_A + c_B \leq c_{A\cup B} + c_{A\cap B}$ for any pair $\left(A,B\right)$ of subsets of $E$.

We will prove this by induction over $\left|A\setminus B\right|$. The base case ($\left|A\setminus B\right|=0$) is obvious (in this case, $A\subseteq B$, so that $A\cap B=A$ and $A\cup B=B$). So let us go for the induction step:

Let $k\in\mathbb N$ be positive. Assume that the problem is already solved for all pairs $\left(A,B\right)$ with $\left|A\setminus B\right|<k$. Now let $\left(A,B\right)$ be a pair with $\left|A\setminus B\right|=k$. Let $a\in A\setminus B$ be arbitrary, and let $B'=B\cup\left\{a\right\}$. Then, $\left|A\setminus B'\right|=\underbrace{\left|A\setminus B\right|}_{=k}-1=k-1<k$, so that (by our induction assumption) the problem is already solved for the pair $\left(A,B'\right)$. In other words, $c_A + c_{B'} \leq c_{A\cup B'} + c_{A\cap B'}$. Since $A\cup B' = A\cup B$, this rewrites as $c_A + c_{B'} \leq c_{A\cup B} + c_{A\cap B'}$.

In the following, when $F$ is a subset of $E$ and $x$ is an edge in $F$, we say that [i]$x$ is a bridge in $F$[/i] if $x$ is a bridge in the spanning subgraph of $G$ with edge set $F$.

Now, $c_{B'}$ is either $c_B - 1$ or $c_B$, depending on whether the edge $a$ is a bridge in $B'$ or not. Similarly, $c_{A\cap B'}$ is either $c_{A\cap B} - 1$ or $c_{A\cap B}$, depending on whether the edge $a$ is a bridge in $A\cap B'$ or not. This yields four possible cases:

[i]Case 1:[/i] We have $c_{B'} = c_B - 1$ and $c_{A\cap B'} = c_{A\cap B} - 1$.
[i]Case 2:[/i] We have $c_{B'} = c_B$ and $c_{A\cap B'} = c_{A\cap B} - 1$.
[i]Case 3:[/i] We have $c_{B'} = c_B - 1$ and $c_{A\cap B'} = c_{A\cap B}$.
[i]Case 4:[/i] We have $c_{B'} = c_B$ and $c_{A\cap B'} = c_{A\cap B}$.

In each of the Cases 1, 2 and 4, we can easily deduce $c_A + c_B \leq c_{A\cup B} + c_{A\cap B}$ from $c_A + c_{B'} \leq c_{A\cup B} + c_{A\cap B'}$, and thus the induction step is completed in these cases. So it remains to handle the Case 3. But in fact, this case cannot occur. In fact, $c_{B'} = c_B - 1$ can only hold when the edge $a$ is a bridge in $B'$. But if the edge $a$ is a bridge in $B'$, then $a$ must also be a bridge in $A\cap B'$, so that $c_{A\cap B'} = c_{A\cap B} - 1$. Hence, if $c_{B'} = c_B - 1$, then $c_{A\cap B'} = c_{A\cap B} - 1$. This rules out Case 3, and we are done.

Who can solve b) and c)? (These seem the most interesting to me.)

[b]a)[/b] Let $n$ denote the number of vertices. Let $G_1=G(V,A\cap B)$, $G_2 = G(V,A)$, $G_3=G(V,B)$ and $G_4= G(V,A\cup B)$. Also let $\kappa_j = \kappa (G_j)$ for $j=1,2,3,4$. WLOG $\kappa_4 = 1$, otherwise pick a connected component of $G_4$

Let $T_1\subseteq G_1$ be a spanning tree. It has $n-\kappa_1$ edges and $\kappa_1$ components. Now choose two spanning trees $T_2\subseteq G_2$ and $T_3 \subseteq G_3$ that contain the tree $T_1$. If we let $|T_j|$ denote the number of edges then $\kappa_2 = n-|T_2|$ and $\kappa_3 = n-|T_3|$.

Further, $|T_2|+|T_3| \ge n-1 + (n-\kappa_1)$ because $G_4$ is connected. Therefore

\[\kappa_2 + \kappa_3 = 2n - (|T_2| + |T_3|) \le 2n - (2n-1 -\kappa_1 ) = \kappa_1 + 1 = \kappa_1 + \kappa_4\]

For $\kappa_4 > 1$, summing over all components of $G_4$ gives the desired inequality $\square$

[b]b)[/b] [b]Equivalent Problem:[/b] Let $G(V,E)$ be a graph such that $|V|=n$ and $E = A_1\cup A_2 \cup ... \cup A_m$, where each $A_j$ is non-empty and $m\le n-1$.  If $G(V,E)$ has property $(R)$ then there exists a subforest (collection of disjoint trees) whose edge set contains exactly one edge from each of the sets $A_j$.

[i]Note: you can observe that his problem is equivalent by repeatedly applying the original statement.[/i]

[i]Proof:[/i] Induction on $m$. If $m=1$ then the statement is clearly true because $A_1$ is not empty. Assume true for the case $m-1$.

If the set $E_m = \{A_1,A_2...,A_m\}$ has property (R) then so does the set $E_{m-1}=\{A_1,A_2...,A_{m-1}\}$. By induction we can find a colourful subforest of $G(V,E_{m-1})$, call it $T_0$. If there exists an edge in $A_m$ such that adding it to $T_0$ will decrease the number of components of $T_0$ then we're done. So assume the contrary.

By property (R) there must be an edge in a set $A_j$ ($j<m$) whose addition to $T_0$ will decrease the number of components. Call all such edges [i]nice edges[/i], and call sets containing a nice edge, [i]nice sets[/i]

Adding an edge from $A_m$ to $T_0$ will create a cycle in $T_0$. We can then remove any edge in this cycle to form a new subforest $T_1$. We call this process a [i]switch[/i]; note that all edges of $T$ have distinct colour after a switch and the set of [i]nice edges/nice sets[/i] has not changed (*). So we wish to find a series of switches that ends in removing an edge from a nice set, because then we can add the nice edge from that set and decrease the number of components- giving us a forest with $m$ edges.

We define the family of sets $\mathcal{E}$. If there is a series of [i]switches[/i] that starts by adding edge $x\in A_m$ to $T_0$ and edges by removing edge $y\in A_i$, then place $A_i \in \mathcal{E}$. Also let $A_m\in\mathcal{E}$.

If $\mathcal{E}$ contains a [i]nice set[/i], $A_i$, then by performing that series of switches we can remove and edge $x\in A_i$ from that set and add the corresponding [i]nice edge[/i], $y\in A_i$. By the invariance property (*), this edge $y$ will decreases the number of components of $T$ - giving us a forest with $m$ edges.

If none of the sets in $\mathcal{E}$ are nice then delete all edges from $T_0$ that do not belong to a set in $\mathcal{E}$, call the new forest $T^*$. $T^*$ has $n-|\mathcal{E}|+1$ components (because $A_m\in\mathcal{E}$, but no edge from $A_m\in E(T_0)$). Adding any edge $x\in \mathcal{E}$ to $T^*$ will not decrease the number of components, otherwise $x$ would lie in a cycle of $T_0$ with an edge $y\not\in\mathcal{E}$, contradicting the definition of $\mathcal{E}$. So in fact the graph with edge set $\mathcal{E}$ also has $n-|\mathcal{E}|+1$ components. But this contradicts property (R).

This completes the inductive step $\square$

[b]c) [/b] Suppose the graph has the given property, call it property (P). Let $A_1, A_2, ..., A_m$ be the edge sets of distinct colour in $G$. By applying property (P) for $k=n$ it is clear that $m\ge n-1$. Further it is clear that the graph $G$ is connected, for if we could partition $G$ into two disconnected sets $V_1$ and $V_2$ with no edge between them, we would contradict property (P) for $n=2$.

Let $F\subseteq G$ be the [i]largest[/i] colourful forest, and let $\mathcal{A}=\{A_1,A_2,...,A_j\}$ be the edge sets who have an edge in the forest. Assume for the sake of contradiction that $j < n-1$.

None of the remaining sets $\{A_{j+1},...,A_m\}$ contains an edge that decreases the number of components of $F$. Therefore, such edge must exist in the set $\mathcal{A}$ because $G$ is connected. Let $\mathcal{A}_1\subseteq \mathcal{A}$ be the sets that contain an edge, $x$, such that adding $x$ to $F$ will decrease the number of components

For $k > j$, adding an edge $x \in A_k$ to $F$ will create a cycle. You can then remove any edge from that cycle and you have a new colourful forest, call this operation a [i]switch[/i] (as we did in part b).  If it was possible to remove an edge from a set $A_i\in \mathcal{A}_1$ by a series of switches, then you could add the edge in $y\in A_i$ to $F$ and decrease the number of components (again like part b). This contradicts the fact that $F$ is maximum.

So it turns out that the graph with edges in the set $\{A_1,....,A_m\} \backslash \mathcal{A}_1$ has at least $n-j+\mathcal{A}_1$ components. By placing each of these components in its own set $V_i$ and applying property (P) there are at least $n-j+\mathcal{A}_1 -1$ other edges of distinct colour. These must come from the only remaining sets $\mathcal{A}_1$. But $n-1-j+\mathcal{A}_1 > \mathcal{A}_1$ by assumption. This is a contradiction.

Therefore $F$ has at least $n-1$ edges, that is, it has exactly $n-1$. So $F\subset G$ is a colourful subtree.

This completes the proof of the [i]if[/i] direction. The [i]only if[/i] direction is more or less trivial, so the proof is complete $\square$

[b]d)[/b] We will show that $G$ has property (P) from part c.

It suffices to show that if $V$ is partition into non-empty sets $V= V_1 \cup ... \cup V_k$, with cardinality $|V_i|=v_i$, then the number of edges between these components is at least $\frac{n}{2}(k-2) + 1$. The result will then follow from the pigeon hole principle.

So if $v_1,...,v_k$ are positive integers with sum $n$ then

\begin{align*}
\sum_{i <j} v_iv_j &= \frac{1}{2} \left ( n^2 - v_1^2-v_2^2-...-v_k^2\right)\\
& \ge \frac{1}{2} \left (n^2 - (n-k+1)^2 - 1^2 - 1^2 -...-1^2\right)\\
& = \frac{1}{2} (k-1)(2n-k)\\
& \ge (k-1)\frac{n}{2}
\end{align*}

So there are at least $k-1$ distinct coloured edges between the components $V_1,...,V_k$.

[b]e)[/b] [i]n is odd:[/i] If there was a colourful subtree isomorphic to $K_{1,n-1}$, then we may remove the vertex of degree $n-1$ and reduce the problem to the case of $n-1$ vertices. If we find a desired subtree in the reduced graph then we add back the vertex we removed and connect it to the tree via the remaining edge of distinct colour.

[i]n is even[/i] Again, if there is a colourful subtree isomorphic to $K_{1,n-1}$ we remove the root vertex. But this time we haven't reduced the problem entirely; there are too many colours. So pick an arbitrary colour, say blue, and re-colour the blue edges with the remaining colours (each remaining colour used on one blue edge). Then the problem has been reduced to the $n-1$ vertices case.

In this manner we are done by induction if we can show the claim is true for $n=5$, but this is easily verified by hand. So the proof is complete $\square$

[b]f) [/b] We know that there exists at least one colourful subtree, so find one and remove those edges from the graph. Now each colour is repeated at most $\frac{n-1}{2}$ times, and there are $n-1$ pairs of vertices with no edges.

Therefore, as in part d, we require that $\textstyle\sum_{i<j} v_iv_j \ge (k-2)\frac{n-1}{2} + 1 + (n-1)$, where the $n-1$ is accounting for the edges we removed. But we already showed in part d that the LHS is at least $(n-1)(2n-k)$ so it's left to show that
\[(n-1)(2n-k) \ge (k-2)\frac{n-1}{2} + n\]
Which after some rearrangement becomes
\[nk \ge (k-1)^2 + 1\]
This is clearly true so the proof is complete $\square$


I gave a mean 10th grader this problem:
$ \frac{1}{1\plus{}{\frac{1}{1\plus{}{\frac{1}{1\plus{}...}}}}}\equal{}$  :?:

Since he didn't know the answer, he gave this to me:
$ x^{x^{x^{...}}}\equal{}2$, and i couldn't solve it...
Those are dots at the top, so the expression goes on forever.

I tried doing this:
$ x^{x^{x^{...}}}\equal{}2$
$ x^{x^{x^{...}}}\equal{}\sqrt[x]{2}$
$ \sqrt[x]{2}\equal{}2$
$ x\equal{}1$

Obviously, if $ x\equal{}1$, then the whole thing equals 1.

Is there a solution to this problem? If so, then how do you get it?

Thanks for the help.

[quote="Kevin K."]I gave a mean 10th grader this problem:
$ \frac{1}{1\plus{}{\frac{1}{1\plus{}{\frac{1}{1\plus{}...}}}}}\equal{}$  :?: [/quote]

The thing with solving those infinite problems is to substitute a variable for an expression. For example, in this problem, you can substitute $ x$ for $ \frac{1}{1\plus{}x}$. This usually makes solving them a lot easier  :wink: .

So I believe in this problem then the set up you are looking for is (and just solve for x):

$ x \equal{}\frac{1}{1\plus{}x}$  :?:

[hide]
$ x^{x^{x^{x^{...}}}}\equal{} 2\implies x^{2}\equal{} 2\implies x \equal{}\pm\sqrt{2}$

$ x\equal{}\frac{1}{x\plus{}1}$
$ x^{2}\plus{}x\minus{}1\equal{}0$
$ x\equal{}\frac{1\pm\sqrt{5}}{2}$
[/hide]

I know how to do $ \frac{1}{1\plus{}{\frac{1}{1\plus{}{\frac{1}{1\plus{}...}}}}}$

But it's the second one that I don't get.
If $ x\equal{}\sqrt{2}$, then how does it make an infinite expression equal 2?
I thought that an answer greater than 1 will give you $ \infty$.

No, it converges in this case. Think about it. Do some of $ \sqrt{2}^{\sqrt{2}^{\sqrt{2}^{\cdots}}}$ with a computer. You'll notice the change starts getting very small. In fact, it's not hard to prove that for $ 1 < a < 2$, $ a <\sqrt{2}^{a}< 2$. Then all you'd have to do to show it converges is that you can eventually get above any number less than 2, but that's the harder part (takes a bit of calculus).

You're right to worry about convergence though. When dealing with "power towers"  as they're usually called, it's a very big issue.

[quote="Kevin K."]I know how to do $ \frac{1}{1\plus{}{\frac{1}{1\plus{}{\frac{1}{1\plus{}...}}}}}$

But it's the second one that I don't get.
If $ x \equal{}\sqrt{2}$, then how does it make an infinite expression equal 2?[/quote]

The first expression is infinite and it still converges, doesn't it?  ;)

When we talk about infinite expressions like that we are really talking about the convergence or divergence of the sequence

$ a_{1}\equal{} x$
$ a_{n}\equal{} x^{a_{n\minus{}1}}$

Finding the interval of convergence of $ x$ is in fact not trivial and requires a bit of calculus.

[quote="Kevin K."]$ x^{x^{x^{...}}}\equal{} 2$
$ x^{x^{x^{...}}}\equal{}\sqrt [x]{2}$[/quote]

This step is not valid because the exponent on the left is not $ x$.  What I mean is that

$ 3^{3^{3}}\equal{} a$

Does [b]not[/b] imply

$ 3^{3}\equal{}\sqrt [3]{a}$

In fact, $ \sqrt [3]{a}\equal{} 3^{9}$.  This is because $ 3^{3^{3}}\equal{} 3^{27}$ and not

$ (3^{3})^{3}\equal{} 3^{9}$

[quote="Icy"][quote="AstroPhys"][hide]
$ x^{x^{x^{x^{...}}}}\equal{} 2\implies x^{2}\equal{} 2\implies x \equal{}\pm\sqrt{2}$
[/hide][/quote]

How exactly does $ x^{x^{x^{x^{...}}}}\equal{} 2$ turn into $ x^{2}\equal{} 2$?

I missed the jump from one step to the other...[/quote]
In the first expression, cover up the bottommost x with your finger and you'll see why. :)

The towers of $ x$'s is equal to $ 2$ so $ x^{\text{tower of x's}}\equal{}2\implies x^{2}\equal{}2$.

Oh! These things are so weird...I get it now though, thanks a lot!


function
floor function
number theory unsolved
number theory

How do you prove that:

$ \sum_{n \le x}\left \lfloor \sqrt \frac{x}{n} \right \rfloor \equal{}\sum_{n\le\sqrt {x}}\left \lfloor \frac{x}{n^2} \right \rfloor$

I have tried looking at lattice points (a,b) under ab=x and also looking at $ \left \lfloor \sqrt \frac{x}{n}\right  \rfloor$ as the number of squares less than or equal to $ \frac{x}{n}$ but so far no luck.

count in two different ways the lattice points on or under the graph of $ y(t) \equal{} \sqrt {\frac {x}{t}}$ between $ t \equal{} 1$  and $ t \equal{} x$. when you solve for $ t$, you have $ t \equal{} \frac {x}{y^2}$. the rest is easy...

We can also use $\sum_{n \leq x}\lambda(n) \left\lfloor {\frac{x}{n}} \right\rfloor=\lfloor \sqrt{x} \rfloor$ where $\lambda(n)$ is the Liouville function
so
$\sum_{n \leq x} \left\lfloor \sqrt{\frac{x}{n}} \right \rfloor =\sum_{n \leq x} \sum_{d \leq \frac{x}{n}} \lambda(d) \left\lfloor \frac{x}{dn} \right\rfloor=\sum_{q \leq x} \left\lfloor \frac{x}{q} \right\rfloor \sum_{d|q}\lambda(d)$ on setting q=nd
and $\sum_{d|q}\lambda(d)=1$ if q a square, =0 if not, gives result.


I found this very hard problem in a book. I have worked on it for over four hours, but I am unable to solve it. If you can solve it, please tell me the logic path you took to solve it. This is similar in form to the famous "Einstein Problem". Here is the exact text from the book:

"In the days before it got sadly bare, old Mother Hubbard's cupboard was actually stocked quite amply. At least, it contained enough to meet her needs and those of her loyal pooch, Alphonse. She had a supply of bones, of course; and she kept anchovies, chutney, dill pickles, egg drop soup, farina, gluten, ham hocks, Irish stew, jellied eels, kidney beans, ladyfingers, marshmallows, nutcakes, and oat bran. Each of these 15 necessities was stored in one of 15 compartments of her cupboard, though if there was any method to their placement, only Mother Hubbard (or Alphonse) fathomed it. By boning up on the clues, however, you should be able to identify the compartment in which each item was placed."

FYI, the 15 compartments are arranged in a 3 x 5 grid. 3 rows by 5 columns. Each row has 5 compartments and each column has 3 compartments.

"The Clues:

1. If you scanned the cupboard shelves from left to right, starting with the top shelf and ending with the bottom shelf, you'd find the five canned items (anchovies, ham hocks, Irish stew, jellied eels, and kidney beans) in alphabetical order, with no two side by side.

2. The boxed items (farina, gluten, and oat bran) were all on the same shelf, but only two of these were side by side.

3. The bottled items (chutney, dill pickles, and egg drop soup) were all on different shelves, though no two were in the same vertical file.

4. None of the bagged items (ladyfingers, marshmallows, and nutcakes) was to be found directly beside a canned item.

5. One item was directly below the ham hocks, directly above the farina, and directly left of the ladyfingers.

6. The chutney was either directly beside the marshamallows or directly above the oat bran, but not both.

7. The dill pickles were either directly below the nutcakes or directly beside the gluten, but not both.

8. No corner compartment contained kidney beans or oat bran."

Thank you.

No idea up to now. I think it's harder than Einstein's test(when I was 11, I slved it in 8 minutes :wink: ).

What does "side by side" mean here?
[code]
1   2   3   4   5
6   7   8   9   10
11  12  13  14  15[/code]

I just want to clarify...would 1 and 6 be side to side? What about like 5 and 6? (sorry if these are stupid questions :blush:)

[quote="Textangle"]I couldn't do it.

Anyways, here's a prod for people that can.

[hide="where to start"]
[code]
Row 1      1   2   3   4   5
Row 2      6   7   8   9   10
Row 3      11  12  13  14  15[/code]

Clue number five tells you that the ham hocks must be in Row 1, the farina in Row 3 directly below the ham hocks, and the ladyfingers in row 2 to the right of the ham hocks and the farina.

By clue 1, The ham hocks must be in 3, 4, or 5, and if its in 5, then there would be no place to put the ladyfingers. Thus, the ham hocks are 3 or 4, and the farina in 13 or 14, and the ladyfingers in 9 or 10. The "mystery item" in between them cannot be a canned item by clue 4.

By clue 2 and clue 8, because the farina is in the bottom row, the oat bran is in 12, 13, or 14, and the gluten is in the bottom row.

By clue 1, the kidney beans must be in the bottom row.
[/hide]

That's as far as I got. I almost solved it a few times, and then reached a few contradictions. Good luck people![/quote]

ok
here's what i got
since the kidney beans and the oat bran can't be on the corners, that means the farina, kidney beans, and oat bran are somewhere in 12, 13, and 14
the gluten is either in 11, or 15
if the farina is in 13, then the oat bran would have to be next to the farina, since the gluten has no way of being next to it
if the farina is in 12 or 14, then the gluten could be in 11 or 15, in which case the oat bran is in 14 or 12, or the gluten is in 11 or 15, in which case the oat bran is in 13 or 13 (i made two numbers for the two cases, each of them is in their respective positions)

and just a question, couldn't the ham hocks be in 2, and the anchovies be in 1?

I am not sure what they mean when they say things like "beside", "side by side", or "next to". Sides could mean horizontal only or both horizontal and vertical. That is a major problem with this problem; things are too ambiguous. They don't give definitions of the terms they use.

My teacher said she was able to solve the problem, but I think it is because she interpreted certain terms to mean horizontal only. The bagged items are a big problem. If "beside" meant horizontal only, the problem might be solvable. If "beside" meant horizontal and vertical, then I'm pretty sure the problem is unsolvable.

on that note...
i would say that beside only means horizontal

anyway, anyone get anywhere closer than me yet?

I got everything except the bagged items, but I reached a contradiction, so I had to start over.

Ham hocks can't be in 2 because

[quote="12markkram34"]1. If you scanned the cupboard shelves from left to right, starting with the top shelf and ending with the bottom shelf, you'd find the five canned items (anchovies, ham hocks, Irish stew, jellied eels, and kidney beans) in alphabetical order, with no two side by side. [/quote]

If the Ham hocks are in 2, anchovies are restricted to 1, which can't be true.

ooohhhh
ok
anyway, i know what has to be on the bottom shelf, but i don't know where they go

farina is either in 13 or 14
oat bran is either in 12, 13, or 14
the kidney beans are either in 12, 13, or 14
the bluten is either in 11, or 15 but cannot be next to the farina if the oat bran is (11) or has to be next to the farina if the oat bran isn't (15)
one of the following three: chutney, dill pickles, and egg drop soup, are on the last place on the bottom shelf

that's what's on the bottom shelf and where they could go
but i haven't gotten futher than that yet

[size=150][color=blue][b]I found the solution!!![/b][/color][/size]

I assumed that 1 and 6 aren't beside!

[hide="Solution"]
1-Anchovies     2-Bones                3-Ham hocks      4-Egg drop soup     5-Irish stew
6-Jellied eels    7-Chutney            8-Marshmallows  9-Ladyfingers        10-Nutcakes
11-Gluten        12-Kidney beans   13-Farina            14-Oat bran           15-Dill pickles
[hide="How I got this..."]
[hide="First"]At first, there are two cases: Ham hocks and farina are in 4th column and the other case is that they are in 3rd column.
Try the 4th column way and it leads to contradiction.
So, they are in the third column.[/hide]
[hide="Second"]
Because of the bag-can condition and 1.clue, kidney beans are in 3. shelf. Kidney beans and oat bran are in positions 12 and 14 because of the 8.clue. Trying cases we see that the correct one is: 12-KB, 14-OB.[/hide]
[hide="Third"]
Oat Bran is below Ladyfingers, so in clue 6 we se that chutney and marshmallows are beside so they are in positions 4-5 or 6-7 or 7-8.
But, Irish stew and Jelied eels can be only in 5,6 or 7 so Irish stew is in 5, Chutney in 7 and marshmallows in 8, and eels in 6.
[/hide]
[hide="Finally..."]
Gluten is in 11 or 15, so in clue 7 we see that pickles are directly below nutcakes, so they are in 10 and 15, and gluten in 11.
The remaining fields are 2 and 4. As Chutney is in 2. column, egg drop soup can't be so it's in 4, and bones in 2[/hide][/hide][/hide]

wow!
nice!
i couldn't find any contradictions, so...
markkram, do you have the answer?

Well,thank you very much!

Most of my contradictions were e.g: bag is next to can, in clues 6 or 7 both or none holds or couldn't find place for all 5 canned items.

Good job. I will check when I find out the answer in the book. I guess that "beside" meant "horizontal only" after all.

Well, it wasn't so hard. It took me a hour to solve it. I assumed that beside is horizontal only.

Also, for those who don't know: Einstein's test:
Einstein said that only 2% of people in the world can solve this test in less than 15 minutes with only paper and pencil.
Here's the test:

5 houses are painted in 5 different colors, in every house lives a person of different nationality, those 5 owners drink specific drink, smoke specific cigarettes, and hold specific pets, none 2 owners have same pet, cigares or drink.
Question: Who has the fishes?
[u][b]Clues[/b][/u]:
British lives in red house
Swedish has dogs
Danish drinks tea
Green house is left from the white house
Owner of green house drinks coffee
Person who smokes Pall-Mall has birds
Owner of yellow house smokes Dunhill
Owner of the middle house drinks milk
Person from Norway lives in first house
Person who smokes Blend lives beside the person who has cats
The man who has horses lives beside the person which smokes Dunhill
Owner which smokes Blue Master drinks beer
German smokes Prince
Person from Norway lives beside blue house
Person which smokes Blend has neighbour who drinks water

[u][b][size=125]There is only one true solution!!![/size][/b][/u]

I think I should put this in my mock MC test. :D

Hmmm, I wish I had some graph paper.  :roll:

[u]Answer to Einstein Question[/u]:

[hide]German owns the fish.[/hide]

[quote="isabella2296"]Can you please show your solution?[/quote]

Just draw a table and fill in things you know.

:D that was a 4th grade homework assignment for the advanced math group at my elementary school lol


Sorry,I can't understand the meaning of the inequality.
Can you explain more,VASC?

[quote="Hawk Tiger"]Did Vasc want to say that the two form of the Inequalities is equivalent?[/quote]
I know now,thank you :)

[quote="Albanian Eagle"]hey I have the proof for $(n-1)\sum a_i ^{n+k}+\prod a_i \sum a_i ^k \geq \sum a_i \sum a_i ^{n+k-1}$ where k  and $a_i$ are positive real[/quote]

is k positive real or positive integer?

k real positive (or maybe for some egative too but i have to check)!

A. Eagle, have you a nice solution for positive real or only positive integer k ?

$k$real
and since the solution is quite similar to the basic suranyi ineq I guess it's nice...

Could I have question that what  the basic suranyi Ineq is,and  where  the proof is.
I just proove the original inquality.

it's the inequality in my post above for $k=0$
(I emember harazi has posted a proof somwhere in the forum...)

[quote="Vasc"]Indeed, as You and Son of Skanderbeg had prove, the inequality is valid for any real k.
Congratulations for this generalization. :lol:[/quote]

Thank you !
 :)

(We are working now on an inequality which is a bit more general than that generalisation. :) )

Congratulations for this generalization from you're friends Fitim Dika! :D
[b]Go for it[/b] and [b]Good for you![/b] :wink:


A space-shuttle revolves around the Earth along an elliptical path, the smallest distance between the Earth and the shuttle is $ 6870$ km (measured from the centre of the Earth), the speed of the shuttle at this position is $ 10 km/s$. What is the least speed of the shuttle? (The radius of the Earth is $ 6370$ km)

Actually, is enough information given? I'm not so sure...


Prove  that
x/(y+z) + y/(z+x) + z/(x+y) >=3/2  for  any  positive  reals  x,y,z
12 th  british  mo , 1976
Thanks

Isn't-it [b]THE[/b] inequality (Nesbitt's) found in every tutorials on inequalities ??

One of the many solutions (the classical one?) is to use rearrangement

x,y,z  and 1/y+z, 1/z+x, 1/x+y are ordered the same way so

x/(y+z) + y/(z+x) + z/(x+y) >= x/(z+x) + y/(x+y) + z/(y+z)
and
x/(y+z) + y/(z+x) + z/(x+y) >= x/(y+x) + y/(z+y) + z/(x+z)

Adding these two inequalites gives the wanted result.

Cauchy is also straightforward:

\sum x/(y + z) \sum x(y + z) \geq (\sum x)2

Since 3/2 \sum x(y + z) \leq (\sum x)2 the result follows.

Or
a=y+z, b=x+z, c=x+y
The inequality comes to
(a+b-c)/2c+(a-b+c)/2b+(-a+b+c)/2c \geq 3/2 <=>
a/b+b/a+a/c+c/a+b/c+c/b \geq 6.
This is true because we know A/B+B/A \geq 2 for all A,B>0

heh.. this one is really easy.. :D

it is equivalent also to:

sum ((x+y)(x-y)^2))>=0. which is obiuos.

cheers!

I think that this problem has a lot of solutions .. here is another one:

Put x=p-a; y=p-b; z=p-c and we have:

sum((p-a)/a)>=3/2 <=> (a+b+c)(1/a+1/b+1/c)>=9 (true) :D :D

Are you trying to gather as many solutions as possible for this WELL-KNOWN ineq? :D

We add 1 to each fraction and it becomes equivalent to (x+y+z)(1/(x+y)+1/(y+z)+1/(z+x)) >= 9/2, which is equivalent to (a+b+c)(1/a+1/b+1/c) >= 9, where a=y+z etc.


Great Aunt Minnie's age plus the square of Great Uncle Paul's age is 7308. Great Uncle Paul's age plus the square of Great Aunt Minnie's age is 6974. What is the sum of Great Aunt Minnie's age and Great Uncle Paul's age?

I formed an equation:
[hide][b]M+P^2=7308
P+M^2=6974
P+M=???
[/b][/hide]

Please help me solve this

[hide="hint"]Solve the system of equations[/hide]

[hide]Well, obviously they have to be pretty old. I just picked numbers. You know that Great Uncle Paul has to be older than 80 and younger than 90. I just picked 85.
85 2 =7225 and to get 7308, you add 83 to it. When you then take and square Great Aunt Minnie's age 83 2 = 6889, and 6889 + 85 = 6974.

The sum of their ages = 85 + 83 = 168.
 :)  :)  :)

BTW- For those of you who didn't know this- a quick way to multiply 2 two digit numbers that both have the same 10's digit and the sum of the 1's digits add up to 10 is that the last two digits of the number are the 1's digits multitplied and the first digit/s are the first two digits multiplied, where you raise one of the numbers to the next number. So if you have 34 x 36, you would get 1224, because 4 x 6 = 24, and     3 x 4 = 12. (If the last two numbers are 1 and 9, the last two digits are 09.)

 :)  :) [/hide]

Yeah, guess and check appears to work better for this one than algebra; when I tried to solve the system I got a fourth degree equation :o

I've got a solution using number theory:

[hide] Suppose x=Great Uncle Paul's age and y=Great Aunt Minnie's age. Thus x^2+y=7308 and y^2+x=6974. Subtracting the second from the first gives x^2-y^2=y-x=334, and factoring and rearranging gives (x+y)(x-y)+(y-x)=334. Multiply by -1 on both sides gives:

(x-y)(-x-y)+(x-y)=-334, which is also (x-y)(1-x-y)=-334.

Multiply by -1 again gives (x-y)(x+y-1)=334. Factoring 334 gives 2x167. Supposing x-y=2 and x+y-1=167, then solve the systems of equations, which gives x=85 and y=83.

[/hide]

[hide]
Easy guess-and-check:
\begin{eqnarray*}
m+p^2=7308\\
p+m^2=6974
\end{eqnarray*}

You know that $p^2 < 7308$, so $p < 85.5...$. Try $p = 85$. Then $7308 - 85^2 = 83$, so $m = 83$. Try this in the other equation. It also works, and is reasonable. $83 + 85 = 168$.
[/hide]

Yea I guess guess and check is better...

This was on the 1997-1998 Mathcounts Sprint Nationals round, so you aren't given a calculator. Doing it algebraically would be more reliable.

If you know the rational roots theorem, it's pretty easy to solve a fourth degree polynomial. I personally hate algebra(no offense) so I would have done guess and check. But algebra is more reliable. :help:


In $ R^{n\plus{}1}$, indentify $ R^{n}$ as $ span(e_{1},...,e_{n})$.
For any fixed $ z\in R^{n}$, define $ f: R\to S_{n}$ by $ f(t)\equal{}cos(\parallel z\parallel t)e_{n\plus{}1}\plus{}sin(\parallel z\parallel t)\frac{z}{\parallel z\parallel }$

How to show $ f(t)$ is a great circle of $ S_{n}$? (maybe this is the defination of great circle).

Here is a [url=http://www.d-e-f-i-n-i-t-e-l-y.com/]very helpful link[/url].

A great circle is the intersection of $ S^{n}$ with a two-dimensional subspace (a plane passing through the center of the sphere). The plane you have here is spanned by $ e_{n\plus{}1}$ and $ z$. It is easy to show that a linear combination $ ae_{n\plus{}1}\plus{}bz$ has norm one if and only if it is equal to $ f(t)$ for some $ t$.


Find $ a$ if:

$ a \equal{} \displaystyle\sum_{i\equal{}1}^\infty {\displaystyle(\frac{2007n}{2007^n})}$


Prove that the statement  "The sum of 2 irrational numbers is irrational." is wrong, using straight forward prove (not a simple counter example). :(
thanks in advance.

If x irratianal, then -x irrational $x+(-x)=0$ rational.  :D

thats an counter example...
straight forward prove? also for all positive irrational numbers please.

if x irrational and a rational then a-x irrational.(a-x)+(x)=a is rational
(if a>x>0 then x,a-x are positive)


geometry
perimeter
rotation
absolute value

[hide]Graph it out. Looks like a square with sides of $\sqrt 2$. The answer is $2$.[/hide]

this was a national sprint question...you cant graph it in less than 40 seconds...but thanx for the answer

[quote="NoSoupForYou"]$|x-a|+|y-b|=c$ is the generic equation for a square with a center at $(a,b)$ and a a side length of $\sqrt{2c}$ (so a diagonal is equal to $2\sqrt{c}$ , perimeter is equal to $4\sqrt{2c}$ and area is equal to $2c$).[/quote]

So if we were to have $|x+2|+|y-3|=2$, then the side length would be $2\sqrt{2}$? I thought it was $2c$.

try solving the problem using $s=2c$; I'm pretty sure the answer you get won't be 2

[quote="mathwizard91"]|x+2| + |y-3| = 1 is an equation for a square. How many units are in the length of its diagonal.

Please show ur solution[/quote]

[hide="Something"]
It looks like each side length is 1. [b] :sqrt: 2[/b].
[/hide]

The vertices are located at $(-2,2)$,$(-1,3)$,$(-2,4)$ and $(-2,3)$

The side length is $\sqrt{2}$, so the area is 2

For abs(x-a)+abs(y-b)=c, it is a square with center (a,b).  Think about it., when x is a, y is b+c or b-c, and when y is b, x is a+c or a-c.  These are the four vertices.  The square is rotated 45 degrees.  That makes the diagonal 2c and the area 2c 2  because dist((a,b-c),(a,b+c)) is 2c.

Oh yeah, I messed up. Here is what I should have put;

$|x-a|+|y-b|=c$ is the generic equation for a square with a center at $(a,b)$ and a a side length of $c\sqrt{2}$ (so a diagonal is equal to $2c$ , perimeter is equal to $4c\sqrt{2}$ and area is equal to $2c^2$).

this is a annoying problem becuz there is no use memorizing the formula but u still need to know how to do it so just learn how to do it w/o the formula

You can solve the problem just by memorizing the formula.

[quote="236factorial"]I'm not very familiar with these equations of a polygon. What does the equation of a square tell me?[/quote]

Umm, well you graph it out and you get a square.

how do you get the formula for a square?

think about it: a regular absolute value graph is a right angle up and two x values can lead to a single y value.  But for a square, you need two x values to lead to two y values, which will make another right angle and a square


How do I make a table of contents like this one:

[img]http://img78.imageshack.us/img78/8190/asdasdkg3.png[/img]

The command for producing a table of contents is: \tableofcontents. To change the way the sections and subsections are numbered  (x1.x2.x3.x4), use \setcounter{tocdepth}{x}.
Sameet.

Okay, but what could be the code to produce the result above?

ssn116 has just told you, \tableofcontents.
You will need to compile your document more than once so LaTeX can go through the document, saving the details in a .toc file, and then printing the result.


Στο βιβλίο του απειροστικού 1 υπάρχει η εξής άσηση:
Αν α,β>0 και α+β=1, τότε (α+1/α)^2+(β+1/β)^2>=25/2
Εγώ τα έφερα όλα στο πρώτο μέλος,έκανα πράξεις,παραγοντοποιήσεις κτλ και κατέληξα στο:
(β^2)(α^2-1)^2+(α^2)(β^2-1)^2>=0 που ισχύει.Ελεγξα ξανά τη λύση και διαπίστωσα οτι δεν χρησιμοποίησα το στοιχείο [u]α+β=1[/u].
Τι γινεται εδω?Δίνει περιτά δεδομένα η άσκηση?

[quote="DIMITRIS T"]Στο βιβλίο του απειροστικού 1 υπάρχει η εξής άσηση:
Αν α,β>0 και α+β=1,

τότε (α+1/α)^2+(β+1/β)^2>=25/2
[/quote]
Το παραπανω ειναι: πχ για την πρωτη παρενθεση (α+1/α) :
(α + (1/α)) εξ ορισμου.

Μηπως ομως εννοεις ((α+1)/α) ?

Ετσι ή αλλιως παντως δεν βλεπω πως με ισοδυναμιες μπορεις να καταληξεις σε αυτο που κατεληξες.

Είναι μια απλή B. C. S. αν πολλαπλασιάσεις και τα δύο μέλη με 2.
Μετά μπορείς να κάνεις αντικατάσταση και να χρησιμοποιήσεις παραγώγους για το ελλάχιστο μετά από αυτό.

:oops_sign:   Sorry παιδιά.Εφαγα ένα όρο όταν έκανα παραγοντοποίηση και κατέληξα σε λάθος συμπέρασμα.


Compute the least positive prime $p$ greater than $2$ such that $p^{3}+7p^{2}$ is a perfect square.

[hide="Solution"]  If $p^{3}+7p^{2}$ is a perfect square, then $p+7$ must also be a perfect square.  Checking, we find that the smallest perfect square for which this is true is $p=29$.[/hide]


integration
floor function
calculus
real analysis
real analysis unsolved

If I remember correctly, $\int_{a}^{b}f(x)dh(x)$ is the limit of sums like $\sum_{i}f(x_{i}^{*})(h(x_{i})-h(x_{i-1}))$, where $x_{i}*\in [x_{i-1},x_{i}]$. Since $h$ is piecewise constant, only subintervals about $1$ and $2$ will contribute nonzero terms to the sum. Consequently, the integral is $e+e^{2}$.

Now how do we put this theory into practice?  :maybe:


linear algebra
matrix
trigonometry
function
complex numbers

There are given 2 numbers $ a$ and $ b$ with $ a^2\plus{}b^2<1$ and two rows $ (u_n)_{n\geq 1}$ and $ (v_n)_{n\geq 1}$ defined by
\[ u_{n\plus{}1}\equal{}au_n\minus{}bv_n\]
\[ v_{n\plus{}1}\equal{}bu_n\plus{}av_n\]
Prove that $ lim u_n\equal{}lim v_n\equal{}0$ and the series $ \sum_{n\equal{}1}^{\infty} u_n$ and $ \sum_{n\equal{}1}^{\infty} v_n$ are convergent and calculate them

[hide="nice problem"]Use matrix representation of complex numbers $ a\plus{}bi \to \rho \begin{pmatrix}\cos \varphi&\minus{}\sin \varphi\\ \sin \varphi&\cos \varphi\end{pmatrix}, 0\le \rho < 1$ [/hide]

[hide]Let $ \alpha \equal{} a \plus{} bi$ and $ \omega_k \equal{} u_k \plus{} v_k i$, then $ \omega_k \alpha \equal{} au_k \plus{} b i u_k \plus{} a i v_k \plus{} b i^2 v_k \equal{} (a u_k \minus{} b v_k ) \plus{} (a v_k \plus{} b u_k) i \equal{} \omega_{k\plus{}1}$. So $ \omega_k \equal{} \omega_1 \alpha^{k\minus{}1}$.[/hide]

[hide]I had actually gotten exactly that far, but failed to make the final connection with the geometric sum formula. Thanks anyway![/hide]

[quote="Darmani"]Digger, I can easily see how that statement proves both sums converge,  but could you explain how that representation allows one to actually calculate the sums?[/quote]
[hide="what i was thinking about"]Write the given recursion in the form $ w_{n+1}=Cw_n$, where $ w_n=\begin{pmatrix}u_n\\ v_n\end{pmatrix}, \ C=\begin{pmatrix}a & - b \\ b & a\end{pmatrix} \Rightarrow w_n=C^nw_0$ - I prefer to start the recursion whith $ n=0$.

It is easy to see that the map $ a+bi \rightarrow \begin{pmatrix}a & - b \\ b & a\end{pmatrix}$ preserves convergence - for this we need distance-function for matrixes of our form. It is evidently to see that $ \parallel{}C\parallel{} = \sqrt{\det C}=|a+bi|$ works.

Because complex serie $ \sum\limits_{n=0}^\infty z^n$ converges for $ |z|<1$ it follows that matrix serie  $ \sum\limits_{n=0}^\infty C^n$ also converges and $ \sum\limits_{n=0}^\infty C^n=(I-C)^{-1}$ and

$ \sum\limits_{n=0}^\infty \begin{pmatrix}u_n\\ v_n\end{pmatrix}=\sum\limits_{n=0}^\infty w_n=\sum\limits_{n=0}^\infty C^nw_0=(I-C)^{-1}w_0=
\frac{1}{(1-a)^2+b^2}\begin{pmatrix}1-a & - b \\ b & 1-a\end{pmatrix}\begin{pmatrix}u_0\\ v_0 \end{pmatrix} \Rightarrow \sum\limits_{n=0}^\infty u_n = \dots, \ \sum\limits_{n=0}^\infty v_n = \dots$[/hide]

[hide="how to eliminate matrixes from the above"]
Just write the given recursion twice:

$ \begin{pmatrix}u_{n+1} & -v_{n+1} \\ v_{n+1} & u_{n+1}\end{pmatrix}=\begin{pmatrix}a & -b \\ b & a\end{pmatrix}\begin{pmatrix}u_n & -v_n \\ v_n & u_n\end{pmatrix}$, use the inverse map $ \begin{pmatrix}a & - b \\ b & a\end{pmatrix} \rightarrow a+bi$ and get $ w_{n+1}=u_{n+1} +i v_{n+1}=(a+bi)(u_n+v_ni)=cw_n$ - what have got [b]MellowMelon[/b]
[/hide]


Find constants $ a, b, c,$ and $ d$ such that:
$ 4x^3 \minus{} 3x \plus{} \frac{\sqrt3}2\equal{}a(x\minus{}b)(x\minus{}c)(x\minus{}d)$

Rules:

#1: Your factors must be exact. No numerical approximations allowed.
#2: Neither the imaginary constant, nor the square root of any negative number may appear in your answer.
#3: Your answer must be simple. Nothing more complicated than a trigonometric function may appear in your answer.
#4: Yes, this problem is solvable.

[hide="Hint"] The first two constants should remind you of a trigonometric identity. [/hide]

hello, you have
${ 4x^3-3x+\frac{\sqrt{3}}{2}}=ax^3+x^2(-ad-ac-ab)+x(acd+abd+abc)-abcd$
and from this equation we get the equation system
$ 4=a$
$ 0=-ad-ac-ab$
$ -3=acd+abd+abc$
$ \frac{\sqrt{3}}{2}=-abcd$
Sonnhard.

[quote="Dr Sonnhard Graubner"]we get the equation system
$ 4 \equal{} a$
$ 0 \equal{} \minus{} ad \minus{} ac \minus{} ab$
$ \minus{} 3 \equal{} acd \plus{} abd \plus{} abc$
$ \frac {\sqrt {3}}{2} \equal{} \minus{} abcd$
Sonnhard.[/quote]

How do you solve a continuation? :D

[hide="My Solution"]We use $ \cos 3 \theta \equal{} 4 \cos^3 \theta \minus{} 3 \cos$.

Let, $ x \equal{} \cos \theta$.
So
$ 4x^3 \minus{} 3x \plus{} \frac{\sqrt{3}}{2} \equal{} 4 \cos^3 \theta \minus{} 3 \cos \plus{} \frac{\sqrt{3}}{2} \equal{} \cos 3 \theta \plus{} \frac{\sqrt{3}}{2}$

Therefore, $ \cos 3 \theta \plus{} \frac{\sqrt{3}}{2} \equal{} 0 \iff 3 \theta \equal{} \frac{5\pi}{6}, \frac{7\pi}{6}, \frac{17\pi}{6} \iff \theta \equal{} \frac{5\pi}{18}, \frac{7\pi}{18}, \frac{17\pi}{18}$

Thus,
$ 4x^3 \minus{} 3x \plus{} \frac{\sqrt{3}}{2} \equal{} 4 \left(x \minus{} \cos \frac{5\pi}{18}\right) \left(x \minus{} \cos \frac{7\pi}{18}\right) \left(x \minus{} \cos \frac{18\pi}{18}\right)$[/hide]

[color=darkblue]Oh. Your problem is nice, but it's easy!

We will find a root of equation: $ 4x^3\minus{}3x\plus{}\frac{\sqrt{3}}{2}\equal{}0$, (1)
Let $ x \equal{} sin\ t$ so equation (1) $ \Longrightarrow 4sin^3t\minus{}3sint\plus{}\frac{\sqrt{3}}{2}\equal{}0$, (2)
$ \Longleftrightarrow sin3t\equal{}\frac{\sqrt{3}}{2}$
$ \Longleftrightarrow sin3t\equal{}sin\frac{\pi}{3}$
$ \Longrightarrow$ equation (2) has a root $ t\equal{}\frac{\pi}{9}$
$ \Longrightarrow$ equation (1) has a root $ x\equal{}sin\frac{\pi}{9}$
Hence $ 4x^3\minus{}3x\plus{}\frac{\sqrt{3}}{2}\equal{}4(x\minus{}sin \frac{\pi}{9})(x^2\plus{}mx\plus{}n)$
Very easy you will get $ m$ and $ n$.
Then OK![/color]


Use the series method, I am having problems constructing the solution to y''+ay=0, a>0

The solution should be y=Asin((a^.5)x)+Bcos((a^.5)x)

In the recursion relation I get -aCn/(n+2)(n+1) = Cn+2

However to construct sin, I need a to have fractional power which I cannot seem to get.

i.e. for odd n, Cn should have 'a' with a fractional power like n+.5 or a^(n+.5) but I can only see a^n in Cn for all n.

Where have I gone wrong?

In my series solution I have a constant C1 so if I can show C1=a^.5 then things will work out. But how do I do that? Is that what is left to do?

I also have to show C0 = 1 for even n series.

As $C1$ is not determined, you may assume $C1 = B\sqrt{a}$. Then you will have the desired result $C_{2n+1}= B \frac{(-1)^{n}(\sqrt{a})^{2n+1}}{(2n+1)!}$.


An integer is square-free if it is not divisible by $a^2$ for any integer $a>1$. Let $S$ be the set of positive square-free integers. Determine, with justification, the value of\[\sum_{k\epsilon S}\left[\sqrt{\frac{10^{10}}{k}}\right]\]where $[x]$ denote the greatest integer less than or equal to $x$

Anyone knows how to do this problem?  :?:   :?

I have a strong suspicion that the answer is $10^{10}$.

I do not, however, have a strong proof...

The main thing is that the result is independent of the number $10^{10}$ - I'm pretty sure $\sum_{k\in S}\left\lfloor\sqrt{\frac{a}{k}}\right\rfloor=\lfloor a\rfloor$ for all positive reals $a$.

Yes, you're right Diarmuid, you put me on the right track. I will prove your stronger statement for all integers $a$.

[b]Lemma[/b]: if $n$, $k$ are positive integers then $\left[\sqrt{\frac{n}{k}}\right] =\left[\sqrt{\frac{n - 1}{k}}\right]$, unless $\sqrt{\frac{n}{k}} \in \mathbb{N}$, in which case we have $\left[\sqrt{\frac{n}{k}}\right] =\left[\sqrt{\frac{n - 1}{k}}\right] + 1.$

[b]Proof[/b] Take $\left[\sqrt{\frac{n}{k}}\right] = m$. Then $m \leq \left[\sqrt{\frac{n}{k}}\right] < m + 1$. Hence $m^2 - \frac{1}{k} \leq \frac{n - 1}{k} < (a + 1)^2 - \frac{1}{k}$. Hence $m - 1 = \left[\sqrt{m^2 - \frac{1}{k}}\right] \leq \sqrt{\frac{n - 1}{k}} \leq \left[\sqrt{(m + 1)^2 - \frac{1}{k}}\right] = m.$  :| Now, if $\sqrt{\frac{n}{k}} = m \in \mathbb{N}$, $n = km^2$, and $\left[\sqrt{\frac{n - 1}{k}}\right] = \left[\sqrt{m^2 - \frac{1}{k}}\right] = m - 1.$ So $\left[\sqrt{\frac{n}{k}}\right] =\left[\sqrt{\frac{n - 1}{k}}\right] + 1.$ Conversely, if $\left[\sqrt{\frac{n}{k}}\right] = m$ and $\left[\sqrt{\frac{n - 1}{k}}\right] = m - 1$, we get $\sqrt{\frac{n - 1}{k}} < m \leq \sqrt{\frac{n}{k}}$ or $km^2 \leq n < km^2 + 1$. Hence $n = km^2$, or $\sqrt{\frac{n}{k}} \in \mathbb{N}$, and the lemma is proven. (That was NOT a fun proof :P)

Now we define $f(n) = \sum_{k \in S}\left[\sqrt{\frac{n}{k}}\right]$. We only need to show that $f(n) = f(n - 1) + 1$ but that is obvious from the lemma (indeed, for all positive integers $n$ there exists a unique $k \in S$ such that $\sqrt{\frac{n}{k}} \in \mathbb{N}$.

And we are done. :D

[quote="Ravi B"]A related approach is to note that $\lfloor \sqrt{a/k} \rfloor$ is the number of integers less than or equal to $a$ whose square-free part is equal to $k$.[/quote]

I see. That's neat :) it's basically the same, but the combinatorial interpretation looks much simpler.

Sry, how do you use the lemma to find the answer/value?

We have $f(n) = \sum_{k \in S}\left[\sqrt{\frac{n}{k}}\right]$. We only need to show that $f(n) = f(n - 1) + 1$... Now \[f(n) - f(n - 1) = \sum_{k \in S}\left(\left[\sqrt{\frac{n}{k}}\right] - \left[\sqrt{\frac{n - 1}{k}}\right]\right).\] By the lemma, this is equal to 1 since there is a unique $k \in S$ such that $\sqrt{\frac{n}{k}} \in \mathbb{N}$ (and for the other $k$, we get $\left[\sqrt{\frac{n}{k}}\right] = \left[\sqrt{\frac{n - 1}{k}}\right]$, giving only zeroes).

Clear?

Very cool.  :maybe:

Rewrite the equation as
\[\sum_{k\in S} \lfloor \sqrt{\frac{10^{10}}{k}}\rfloor=\sum_{k\in S} \sum_{ki^2\leq 10^{10}, i\geq 1} 1 = \sum_{m=1}^{10^{10}} 1= \boxed{10^{10}}\]
where $m=ki^2$, which has a unique representation as a product of a non-square number and a square number.

Note that $\left \lfloor \sqrt{\frac{10^{10}}{k}}\right \rfloor$ counts the number of integers $m \geq 1$ with $km^2 \leq 10^{10}$, so we have
$$\sum_{k \in S} \left \lfloor \sqrt{\frac{10^{10}}{k}}\right \rfloor=\sum_{k \in S} \sum_{km^2 \leq 10^{10}} 1=\sum_{n=1}^{10^{10}} 1=10^{10},$$
where the second equality comes from counting over $n=km^2$, since $k$ is squarefree.


Mr. Green receives a $ 10 \%$ raise every year.  His salary after four such raises has gone up by what percent?

\[ \textbf{(A)}\ \text{less than }40 \% \qquad
\textbf{(B)}\ 40 \% \qquad
\textbf{(C)}\ 44 \% \qquad
\textbf{(D)}\ 45 \% \qquad
\textbf{(E)}\ \text{More than }45 \%
\]

[hide="Alternate Solution"]
Clearly, $ (1.1)^4$ has more than two digits past the decimal point, so we eliminate $ \textbf{(B)}$, $ \textbf{(C)}$, and $ \textbf{(D)}$.  It is also quite clearly greater than $ 40 \%$, so the only answer choice left is $ \textbf{(E)}$.
[/hide]


abstract algebra
group theory
superior algebra
superior algebra unsolved

Problem. Let $G = \{g_1,\ldots,g_n\}$ be a non-abelian finite simple group of finite order $n$. For a subset $S \subseteq G$ and integer $k \in \mathbb{N}$, define $S^{(k)} := \{a^k \, | \, a \in S\}$. Consider the set
\[
P_G := \{g_{\pi(1)} \cdots g_{\pi (n)} \, | \, \pi \in \Pi_n\},
\]
where $\Pi_n$ is the set of all permutations of $\{1,\ldots,n\}$. Show that there exists an integer $m$ such that $P_G^{(m)} = G$.

--Vesselin

Actually, for $G$ simple and non-commutative, we have that $P_G = G$, but I guess that would be very difficult to prove (I don't know if an elementary proof is known). So, I invite you to try to prove the weaker version above to which I am sure that there is a very short and elementary (yet beautiful) solution.

--Vesselin


analytic geometry
geometry
geometric transformation
reflection

[quote=GameBot]AB with endpoints A($ \minus{}4,2$) and B(5,5) is reflected over the $ y$-axis. Then, its image is reflected over the $ x$-axis. What is the product of the coordinates of the midpoint of the final image?[/quote]

um in ftw it says $A=(-1,2)$

[quote=james4l]current midpoint: (0.5,3.5)
reflect over y then x = (a,b) => (-a,-b)

Product: [b]1.75[/b][/quote]

ftw says the ans is 7


Kesha caught 40 fish, marked them, and returned them to the pond.
Later, she randomly netted 60 fish and found 4 marked fish in this
group. What is the expected number of fish in the pond?

If out of 60 you find 4 marked fish, out of n you find all 40 marked fish.

This is a simple proportions problem, for which n=600 (answer)


[quote="davidlizeng"]you have triangle ABC. the three medians are AX, BY, and CZ, where X,Y,Z, are on BC, AC, AB respectively
the medians intersect at point G. if AG= sqrt(5), BG= sqrt(3),
CG= sqrt(2), then find the area of triangle ABC[/quote]
[hide="interesting"]Set the sides to be x, y, and z. We now know can use the formula for the length of a median to get $\sqrt{\frac{2a^{2}+2b^{2}-c^{2}}{2}}=1.5\sqrt{3}$ and some other equations. Squaring our equations gives us the equations:
$2a^{2}+2b^{2}-c^{2}=27$
$2a^{2}+2c^{2}-b^{2}=45$
$2b^{2}+2c^{2}-a^{2}=18$
Adding them, we have
$5a^{2}+5b^{2}+5c^{2}=90$
$2a^{2}+2b^{2}+2c^{2}=36$
Now I'm getting that $b=i\sqrt{3}$ uh oh.[/hide]
Can someone point out my mistake? I think I have the right method...

I am not quite sure if this is correct, but here is an idea.
[hide] Well, I will use the same exact method to do this as bpms used.  Say the side opposite point A has a length of a, the side opposite point B has a length of b, and the side opposite point C has a length of c.  We have that the median to the side with length a is $\sqrt{\frac{2c^{2}+2b^{2}-a^{2}}{2}}=1.5(\sqrt{5})\Rightarrow 2c^{2}+2b^{2}-a^{2}=22.5$ (2 is also under the squareroot, bpms, this is where you made the mistake).  Therefore, we can just take all of bpm's numbers and divide them by 2.  We have:
1. $2a^{2}+2c^{2}-b^{2}=13.5$
2. $2a^{2}+2b^{2}-c^{2}=9$
3. $2c^{2}+2b^{2}-a^{2}=22.5$.
Now, when you add these all up, you have that 3a^2+3b^2+3c^2=45 (You added the variables wrong here, bpms).  We have that $a^{2}+b^{2}+c^{2}=15$.  Adding this to 1,2, and 3 respectively and dividing by 3, we get:
4. $a^{2}+c^{2}=9.5$
5. $a^{2}+b^{2}=8$
6. $c^{2}+b^{2}=12.5$
From here, we can solve for a, b, and c.  Then, we can use Hero's Formula to get the area.[/hide]

Where did you get all the square roots and stuff? I don't quite follow.

Oh, sorry about that; I didn't make it quite clear.  The length of the median of a triangle to the side with length a (the sides if the triange have lengths are a, b, and c) is going to be $\sqrt{\frac{2b^{2}+2c^{2}-a^{2}}{2}}$.


Nine different two-digit numbers can be formed with the
digits 1, 3 and 7. How many of these numbers are prime?

The 9 numbers that can be formed are
11,13,17,31,33,37,71,73,77.
The 2 not prime numbers are 33 and 77.
The rest are prime-the answer is 7.

You don't have to really list them out - you can just see that only numbers that aren't prime are 33 and 77, so our answer is $ 9 \minus{} 2 \equal{} 7$.


Anyone knows the question for #10?
I also find out that E, A, D are colinear, but i got a different answer.


Είναι η πρώτη (και τελευταία---δεν είμαι καθόλου fan του συγκεκριμένου κλάδου) άσκηση που βάζω σε abstract algebra. Μου την είχε δείξει ο Anto πριν αρκετό καιρό, και νομίζω ότι αδικώ την άσκηση κρατώντας την για τον εαυτό μου, καθώς δεν εκτιμώ τη θεωρία ομάδων όσο (κάποιοι λένε ότι) θα έπρεπε. Πιστεύω ότι έχω λύση, αλλά θεωρώ ότι ήταν κάπως τυχαία, οπότε ευελπιστώ κάποιος να βρει μια πολύ πιο απλή/elegant/common-sense λύση:

Αν οι $ G$, $ H$ είναι ομάδες, τέτοιες ώστε:
- Η $ G$ είναι ισόμορφη μιας υποομάδας $ H'$ της $ H$.
- Η $ H$ είναι ισόμορφη μιας υποομάδας $ G'$ της $ G$.
Μπορούμε να καταλήξουμε στο ότι οι $ G$, $ H$ είναι ισόμορφες;

(Για τους αγγλόφωνους αναγνώστες μας, if any: if $ G, H$ are groups such that $ G \cong H' \leq H$ and $ H \cong G' \leq G$, then does it necessarily follow that $ G \cong H$?)

[quote="cmad"]Αν οι $ G$, $ H$ είναι ομάδες, τέτοιες ώστε:
- Η $ G$ είναι ισόμορφη μιας υποομάδας $ H'$ της $ H$.
- Η $ H$ είναι ισόμορφη μιας υποομάδας $ G'$ της $ G$.
Μπορούμε να καταλήξουμε στο ότι οι $ G$, $ H$ είναι ισόμορφες;[/quote]

Let me see if I get this straight (που με τις ασκήσεις του Anto, I never do ;) )... ισοδύναμα θέλουμε να δούμε αν η σχέση $ K\leq H\leq G$ όπου $ G,K$ ισόμορφες συνεπάγεται ότι $ H\cong G$, σωστά?

Cheerio,

Durandal 1707

Ναι μπορείς να δείξεις και εκείνο, ισοδύναμα.

ΥΓ: Oops, τελικά βρήκα μια αρκετά απλούστερη λύση... Όπως καταλαβαίνεις, δεν είναι όσο δύσκολη όσο οι υπόλοιπες ασκήσεις του (αλλιώς, to be honest, ειδικά επειδή είναι άλγεβρα, δε θα μου έβγαινε με τίποτα :oops:)

Νομίζω πως τέτοιες ασκήσεις είναι αρκετά ωραίες. Στα περισσότερα προπτυχιακά μαθήματα μαθαίνουμε θεωρία ομάδων αλλά ασχολούμαστε συνήθως μόνο με πεπερασμένες ομάδες (άντε και με το $ \mathbb{Z}$). Συμβαίνουν όμως αρκετά περίεργα στις μη πεπερασμένες ομάδες που η διαίσθησή μας (με βάση το τι γνωρίζουμε από τις πεπερασμένες ομάδες) μας λέει πως δεν πρέπει να συμβαίνουν.

[hide]
Κοιτάξτε στα free groups.
[/hide]


inequalities
calculus
integration
derivative
real analysis
real analysis unsolved

Let $ f$ differentiable, $ f(0) \equal{} 0$ and $ 0 < f'(x)\leq1$.

Prove that for all $ x\geq 0$

$ \int_0^xf^3 \leq (\int_0^x f)^2$

[hide="Hint"]Show that $ g(x) \equal{} 2\int_0^x f \minus{} f^2(x)$ and $ h(x) \equal{} (\int_0^xf)^2 \minus{} \int_0^x f^3$ have non-negative derivatives with $ g(0) \equal{} h(0) \equal{} 0$.[/hide]


The equation of a circle which passes through the point $ (1,2)$, bisects the circumference of the circle $ x^2\plus{}y^2\equal{}9$ and cuts orthogonally the circle $ x^2\plus{}y^2\minus{}2x\plus{}8y\minus{}7\equal{}0$ is ......

ans:$ x^2\plus{}y^2\plus{}8x\minus{}2y\minus{}9\equal{}0$

Errr...Do you want the method?? Assume general equation of circle. Since it bisects the C1, the chord of contact passes through the centre of circle (diameter).

2. Use the equation for orthogonal cutting.

3. Substitute (1,2)

3 Equations, 3 unknowns, solve!~

[quote="anandghegde"]sorry shreyas i have got the ans now. :huh: ...but i did in a different way :)

I assumed the circle as $ S \plus{} \lambda L \equal{} 0$ :)[/quote]
Atleast someone got my trick at last. :D

yeah chemrock. :)

thanks for that idea :D

[quote="anandghegde"]sorry shreyas i have got the ans now. :huh: ...but i did in a different way :)

I assumed the circle as $ S \plus{} \lambda L \equal{} 0$ :)[/quote]

This method of solving problems is very powerful and gives you answers fast.
Especially say when you want to find the conic $ \Gamma$ that circumscibes the triangle formed by some three lines, say $ L_{i}, i\equal{}1,2,3.$
A simple method would be to assume it to be of the form
$ \Gamma \equal{} \lambda L_{1}L_{2} \plus{} \mu L_{2}L_{3} \plus{} L_{3}L_{1}$.
Then use constraints on the kinda conic you want $ \Gamma$ to be to solve for the parameters,
for a circle, tha cross term must vanish and the square terms coeff must be equal and stuff like that.


Rectangulaer cards, 2 inches by 3 inches are cut froma  rectangular shett 2 feet by 3 feet.  What is the greatest number of cards that can be cutr from the sheet?

[hide]There are 12 inches in a foot, so we have 12 * 12 or 144 rectangles. [/hide]


projective geometry
geometry proposed
geometry

Let ABCD be a convex quadrilateral (AC,BD are two diagonals).Let be given points E,F on AC,BD respectively.AF $\cap BE=K,DE\cap CF=P,AD\cap BC=S$.prove that:S,K,P are colinear

Are you sure about the question?
I think you mean ${P}= DE \cap CF$.

If you do: it's literally Pappus-Pascal and a very transparent question.
$B,F,D$ are collinear, $A,E,C$ are collinear.
Therefore, $S,K,P$ are collinear.

If you don't: Please post the correct problem, I'm curious.


$ \mbox{Given a convex quadrilateral } ABCD. \mbox{ On the segments } AB,BC,CD,DA \mbox{ are chosen points }M,N,P,Q$ $ \mbox{ , respectively, such that } AQ\equal{}DP\equal{}CN\equal{}BM.$
$ \mbox{Show that if } MNPQ \mbox{ is a square, then } ABCD \mbox{ is also a square. }$  :)

easily proved $ AQM\equal{}DQP \Longrightarrow AM\equal{}DQ ,AQ\equal{}BM \Longrightarrow AB\equal{}AD$
<AQM+<AMQ=<AQM+DQP=90 thus <A=90
same  as this ...ABCD is square

How can you prove $ \Delta AQM\equal{}\Delta DQP$ ?

<AQM+<DQP=90 thus sin(AQM)=cos(DQP)
$ \frac{AM}{QM}\equal{}\frac{DQ}{PQ}$ thus AM=DQ

It's not right because if $ \angle QDP<90^o$, we can construct $ D'$ on $ AD$ such that $ PD'\equal{}PD$ ...


This is a fun one.

Source: College of Charleston Math Meet, 2003 Lv. 2

The 2003 inhabitants of an island are divided into two groups: the truth tellers and the liars.  The former group always tells the truth, while the latter one always lies.  Each person is either a soccer player, a singer, or a fisherman (but not both or all 3).  We ask each inhabitant these three questions:
1) are you a soccer player?
2) are you a singer?
3) are you a fisherman?

1000 people answer "yes" to the first question.  700 answer "yes" to the second one, and 500 answer "yes" to the third one.  How many liars are there on the island?

spoiler

[hide]

Every truth-teller says yes to one of the questions and no to two of the questions (he answers 'yes' to whichever of the three is his job and 'no' to the other ones.) Every liar answers yes to two questions and no to one ('yes' to whichever two jobs he doesn't do and no to the job that he actually has.) Straightforward algebra from there. [/hide]

Well, its' not THAT straightforward. THere are still several cases to consider, such as which ones the liars say yes to. BUt, still, it is pretty easy...

Does it matter which jobs the liars choose?
I was just assuming there were 2003 real jobs, 2200 claimed jobs, and each liar answered twice, which would make 197 liars?


function
algebra
polynomial
domain
ratio
complex numbers
complex analysis

let $f(z)=\frac{p(z)}{q(z)}$ where $p(z)$ and $q(z)$ are polynomials, all 3 are $\mathbb{C} \rightarrow \mathbb{C}$ functions, prove either prove or disprove the existence a function $f(z)$ such that $f(z)=\overline{z}$ for all $z$ in the domain of $f(z)$

More simply:

Prove or disprove that the complex conjugate function can be expressed as a ratio of two complex polynomials.

[hide="A first step hint"]Consider the roots of the denominator[/hide]

$f(z)=\overline{z}$

in never analytcic in the complex plane.

You need \overline, not \overbar.  Anyhow, there are PreOlympiad methods (i.e. not using complex analysis) that can solve this question.

Just thought i was a nice way of doing it! Ill have a look for a more accessible proof


linear algebra
matrix
induction
algebra
binomial theorem

The matrix $ M$ is given by $ M\equal{} \begin {bmatrix} 1 & 2 \\ 0 & 1\end {bmatrix}$.

(i) Find $ M^{2}$ and $ M^{3}$.

(ii) Hence suggest a suitable form for the matrix $ M^{n}$.

(iii) Use induction to prove that your answer to part (ii) is correct.

(iv) Descibe fully the single transformation represented by $ M^{10}$.

In general, if we can write $ M\equal{}I\plus{}N,$ where $ N^2\equal{}0,$ we can just use the binomial theorem for $ M^n$, and then have that binomial expansion simplify enormously.

The geometric word I would use to describe $ M^n$ for any $ n$ is "shear." (And the Lay textbook that I use for an elementary course, in one of the author's few moments of levity, has a picture of a "sheared sheep" - you'll have to pick up a copy of the book to see it.)

This will help you.

[url]http://www.mathlinks.ro/Forum/viewtopic.php?t=308360[/url]


function
combinatorics proposed
combinatorics

prove that $\sum_{k=0}^{\infty}\frac {k^n}{2^{k+1}}$ ,(n is natural )is positive integer.

Hi!
I use gf.
Take f[n](x) = your formula. I don't know latex.Sorry.
Now you get Integral(f[n](x)/x) = f[n-1](x) / 2!!!
So you can get a formula for f[n](x). You have a reccurence.
Then you need only f[n](1).
I think, though I didn't check, that the number is a power of 2 ?

First of all, I think we have to show that for $\displaystyle \sum_{k\geq 1}\frac{k^n}{2^k}$, because if the exponent of $2$ is $k+1$ then for $n=0$ we get $\frac 1{2^2}+\frac 2{2^3}+..=\frac 12$, which isn't an integer.

Let $f(n)=\displaystyle \sum_{k\geq 1}\frac {k^n}{2^k}$. $f(0)=1\in Z$. Now let's assume we have shown that $f(k)\in Z,\ \forall k\in \overline{0,n}$ and let's try to show it for $f(n+1)$.

We have (a very well-known trick) $f(n+1)\cdot \frac 12=f(n+1)\cdot (1-\frac 12)=\displaystyle \sum_{k\geq 1}\frac{k^{n+1}-(k-1)^{n+1}}{2^k}$ and by decomposing $k^{n+1}-(k-1)^{n+1}$ we find that $\frac{f(n+1)}2$ can be written as a linear combination with integer coefficients of $f(k),\ k\in \overline{0,n}$. This shows that $f(n+1)$ is an even integer for $n\geq 1$. Let's observe that the problem as you had initially posed it is true for $n>0$. When you say "natural" I also understand $0$, and that's why I've modified it. However, as you can see, your assertion is also true for $n\in N^*=N-\{0\}$.

may I'd better to post the prob to combinatorics because the official idea of the problem is pure combinatorics :(

It is true because we have following representation:
\[k^n=\sum_{i=0}^{n-1}(-1)^{n-1-i}C_n^i(1^i+2^i+\dots+k^i)\]

its nice solution is here:
assume that $A_n$ is the number map $f:${$1,2,3,..,n$}$\rightarrow${$1,...,n$} s.t satifies this condition: if $f^{-1}(i)$ is'nt empty then $f^{-1}(j)$ for $j=1,..,i$ isnt either .so if $a_n=|A_n|$ .and the number of map in $A_n$ s.t exactly$ l $number of $i$ exsits such that $f(i)=1$is ${l\choose n}.a_{n-l}$so we have :
$a_n=\sum_{l=1}^{n}{l\choose n}.a_{n-l}=\sum {l \choose n}a_l$we suppose that $a_0=0$and $b_n=\frac { a_n}{n!}$so we have $b_n=\sum_{l=0}^{n-1}\frac {b_l}{(n-l)!}$ now we use generating function .let $f(z)=\sum_{n=0}^{\infty}b_n.z^n$ so we have $f(z)=1+\sum_{n =1}^{\infty}z^n.(\sum_{l=0}^{n-1}\frac {b_l}{(n-i)!})=1+(e^z-1)f(z)$ therefore $f(z)=\frac {1}{2-e^z}$ so $f(z)=\sum_{k=0}^{\infty}\frac {e^{kz}}{2^{k+1}}=\sum \frac {z^n}{n!}(\sum \frac {k^n}{2^{k+1}}$ so we are done.


ceiling function
pigeonhole principle
modular arithmetic
search
combinatorics proposed
combinatorics

Let $A$ be the largest subset of $\{1,\dots,n\}$ such that for each $x\in A$, $x$ divides at most one other element in $A$. Prove that \[\frac{2n}3\leq |A|\leq \left\lceil \frac{3n}4\right\rceil. \]

Iran TST? I'm happy! I really like iranian problems!

First a few observation: let us divide A in the set $A_{1}$, the set of numbers that divide exactly another element of A, and $A_{2}$, the set of numbers that divide no other element of $A_{2}$. By definition, $A_{2}$ is an antichain. But it's obvious that also $A_{1}$ is an antichain. Therefore, A is the disjoint union of two antichains.
What is the maximum size of an antichain? $\frac{1}{2}n$, because if you take the greatest odd divisor of each element, these must be distinct, but there are only $\frac{1}{2}n$ odd numbers $\le n$. An example of a maximal antichain is the set $\frac{1}{2}n+1 ,\frac{1}{2}n+2 \ldots, n-1,n$.

Now let's start solving the problem. Suppose that $|A| > \frac{3n}4$. Take the greatest odd divisor of each element of A. There are no three elements with the same greatest odd divisor, and there are only $\frac{n}{2}$ odd numbers, then, by the pigeonhole principle, there are more than $\frac{n}{4}$ couples of elements of A with the same greatest odd divisor. Among their greatest odd divisors, take d, the greatest. Since in $[1,\frac{n}{2}]$ there are at most $\frac{1}{4}n$ odd numbers, it must be $d > \frac{n}{2}$. But then, there is a pair of elements of A with d as divisor, and the bigger must be $\ge 2d > n$, contradiction.

To prove that $|A| \ge \frac{3}{2}n$, consider
$A = \{ k : \frac{1}{3}n \le k \le \frac{1}{2}n \land k \equiv 1 \pmod 2\}\cup \{ 2k : \frac{1}{3}n \le k \le \frac{1}{2}n \land k \equiv 1 \pmod 2\}$.
The two sets of which A is union are antichains, the first because if an odd number divides another, the second is at least 3 times the first, the second set because if $2k \mid 2j$ with both k,j odd, we have $k \mid j$.

What about the case $A = \{1\}$, $n = 1$? Then we have $|A| = 1 > \frac{3n}{4}$...

Excuse me, that must be $\left\lceil \frac{3n}4\right\rceil$.
Moderators, Could you please edit this topic?

Do you know what a search engine is?

http://mathworld.wolfram.com/Antichain.html

The poset in question is the set of integers from 1 to $ n$ ordered by division.

[quote name="bodom" url="/community/p882822"]
i think this solution is a bit easier than the one presented above :) :

for the first part it is clear just by taking  $ B={k+1,k+2,......,3k+e}$ where $ n=3k+e$ and $ e = 0,1,2$ because $ |A|\geq |B|$for the second part,let's take $ n=4k$ and for $ n=4k+1,2,3$ it can be done almost exactly the same way.we can write $ {1,2,....,4k}$ as $ 1,3,.....,4k-1; 2*1,2*3,....2*(2k-1); 4*1,4*3,.....; ..........;2^{v}*1;$ where$ 4k\geq 2^{v}$and v is the greatest number with that property.so $ {1,2,3,....,4k}$can be partitioned in $ A_{1}={1,2*2,4*1,......,2^{v}*1}+A_{3}{3,2*3,4*3,.......}+........A_{(}2k-1)={2k-1,2*(2k-1)}+C={2k+1,2k+3,.....,4k-1}$.it is clear that from $ A_{(}2j-1)$ we can choose at most 2 numbers,for every $ j=0,1,2,....,k-1$ so we can get at most $ 2k$ numbers from there and we are left with just $ k$ numbers that we can choose ,the numbers from $ C$.so we kave at most $ 3k$ numbers in $ A$. that's all :lol:
[/quote]

How is this clear for the first part? Still confused with that

[hide=wrong solution]Note that
$$ A = \left\{ \left\lfloor \frac{n}{3} \right\rfloor + 1, \ldots,n \right\}  $$
works. Hence we get
$$|A| \ge \frac{2n}{3}$$
Next assume on the contrary that
$$ |A| \ge \frac{3n}{4} + 1 $$
Let set
$$ B = 2A := \{2a : a \in A\} \qquad , \qquad C = A \cap B $$
Since
$$ |A|,|B| \ge \frac{3n}{4} + 1 \textcolor{red}{\implies |C| \ge \frac{n}{2} + 2} $$
This means one can pick $c_1,c_2 \in C$ such that
$$ c_1 \mid c_2 $$
But as $c_1  \in B$, so we can pick some $a \in A$ such that
$$ \frac{c_1}{a} = 2^l ~~, l \ge 1$$
Pick the least such $a$ (i.e. $l$ is max possible). We get that $a \notin B$ (otherwise minimality gets contradicted). Then $a \in A$ divides both of $c_1,c_2 \in A$, as desired. $\blacksquare$[/hide]


If $ T$ is Toricelli's point and $ O$ the circumcenter of $ \triangle ABC$, prove that $ OT^2\equal{}a^2\plus{}b^2\plus{}c^2\minus{}4S\sqrt{3}$(usual notations)

I remember I have read the formula in an articles of a fourteen boy (it seem that he is the member [b]mr.danh[/b]), but I don't have more details.
Maybe, the proof proceeds from $ \vec{OA}\equal{}\vec{OT}\plus{}\vec{TA}$


[quote="ehehheehee"][quote="pgpatel"][quote="ch1n353ch3s54a1l"]A circular garden is surrounded by a sidewalk with a uniform width of 25 feet. The total area of the sidewalk equals the total area of the garden. How many feet are in the diameter of the garden? Round your answer to the nearest whole number.[/quote]
[hide]$(x+25)^2-x^2=x^2$
$50x+625=x^2$
$x^2-50x-625=0$
$x=25+25(sq(2))$
$60.35...$
$60$[/hide][/quote]

[hide]$25/(sqrt(2)-1)=60.355... 60.355*2=120.71$

[b]121[/b]

I think you want the diameter of the garden, not the radius...I am probably mistaken though...[/hide][/quote] no you are right...
 :wallbash_red:  :wallbash_red: :wallbash_red: :wallbash_red: :wallbash_red: :wallbash_red: :wallbash_red: :wallbash_red: :wallbash_red: :wallbash_red:

[quote="ch1n353ch3s54a1l"][quote="pgpatel"][quote="ch1n353ch3s54a1l"]A circular garden is surrounded by a sidewalk with a uniform width of 25 feet. The total area of the sidewalk equals the total area of the garden. How many feet are in the diameter of the garden? Round your answer to the nearest whole number.[/quote]
[hide]$(x+25)^2-x^2=x^2$
$50x+625=x^2$
$x^2-50x-625=0$
$x=25+25(sq(2))$
$60.35...$
$60$[/hide][/quote]

Sorry...I don't really understand your first expression...[/quote]

I'll explain it for pgpatel. x is the radius of the garden, so the first equation is the area of the sidewalk on the LHS and the area of the garden on the RHS (with the $\pi$s already cancelled out.) :D

[hide]Let $x$ be the radius of the inner circle. You are trying to find $2x$.
$x^2\pi = (x+25)^2\pi - x^2\pi$ as the radius of the inner circle plus the walkway's length would be $x+25$. That would be radius of the larger circle so you'd use that in finding area. But, you don't want total area so you subtract the area of the inner circle to get the area of the walkway.
Expand to get $x^2\pi = x^2\pi + 50x\pi + 625\pi - x^2\pi$.
Simplify to get $50x + 625 = x^2$.
Subtract $x^2$ from both sides to get $-x^2 + 50x + 625 = 0$.
Apply quadratic equation to get $\frac{-50 \pm \sqrt{2500 + 2500}}{-2}$.
Simplify this to $25 \pm -25\sqrt{2}$.
Since it obviously can't be negative and $+-$ would make negative, reject $+$ and change the double negative to $+$ to get $25+25\sqrt{2}$.
Now, just calculate it with a calculator and multiply the result by $2$ and round to the nearest integer to get $\boxed {121}$.[/hide]

[quote="ch1n353ch3s54a1l"]OHH... For some reason I assumed the sidewalk was a square... :read:  :huh:[/quote]

But then a vertice of the square would be a larger distance away than the vertice of the midpoint of a side and the distance wouldn't be uniform. It probably would be solvable if it was a square but you'd need more information to narrow it down to one solution and it'd be harder.

Well the problem said "[u]with[/u] a uniform width of 25" so I thought the 25 was referring to the sidewalk...and I didn't know what it was talking about.

It is.  Basically just picture two concentric circles, and the larger circle has a radius that is 25 feet larger than the radius of the other circle.  Then the area of the larger circle is twice that of the area of the smaller circle.


Let X be a compact space, Y be a Hausdoff space and f a continumous mapping from X to Y. If f is bijective, prove that the inverse of f is continuous.

take a closed set $ F\subset X$ which is compact then $ F$ is compact, $ f(F)$ is compact in $ Y$ which is Hausdorff, so $ f(F)$ must be closed in $ Y$, i.e $ f^{\minus{}1}$ is continuous !


geometry
calculus
integration
calculus computations

d:1  2   3  4   5   5   4   3   2  1(in m)
X:1 10 20 40 50 60 70 80 90 100(in m)

Here X denotes distance in m of a pond from the starting pt.
d denotes depth of the pond coresponding to "X"

Find the area of such pond :(

which methods of numerical integration is your class working on?

simpsons rule, midpoint rule, trapezoidal rule?


Let -positive real numbers,
Show that: $ a\plus{}b\plus{}c\plus{}\frac{3}{\frac{1}{a}\plus{}\frac{1}{b}\plus{}\frac{1}{c}}>\equal{}4\sqrt[3] {abc}.$ thanx :wink:

[color=#FF0000][Mod: Do not double post: [url]http://www.artofproblemsolving.com/Forum/viewtopic.php?t=229033[/url].][/color]

The inequality is equivalent to

$ a\plus{}b\plus{}c \plus{} \frac{3abc}{ab\plus{}bc\plus{}ca} \geq 4 \sqrt[3]{abc}$.

Many approach to solve. ABC might be the nicest.

[quote="ely_en"]Let -positive real numbers,
Show that: $ a \plus{} b \plus{} c \plus{} \frac {3}{\frac {1}{a} \plus{} \frac {1}{b} \plus{} \frac {1}{c}} \ge\ 4\sqrt [3] {abc}.$ thanx :wink:[/quote]
Assum $ abc \equal{} 1$.

$ Ineq \leftrightarrow a \plus{} b \plus{} c \plus{} \frac {3}{ab \plus{} bc \plus{} ca} \ge\ 4$

Follow AM-GM:

$ LHS \ge\ a \plus{} b \plus{} c \plus{} \frac {9}{(a \plus{} b \plus{} c)^2} \ge\ \frac {a \plus{} b \plus{} c}{3} \plus{} 3 \ge\ 4$


inequalities
combinatorics unsolved
combinatorics

Prove by combinatorial reasoning,

\[ \sum_{i\equal{}1}^{n} {n\choose i}\leq {\bigg( \frac{2^n\minus{}2}{n\minus{}1} \bigg)}^{n\minus{}1}\quad \forall n>1,n\in \mathbb{N}\]

Did you mean
\[ \prod_{i \equal{} 1}^{n} {n\choose i}\leq {\bigg( \frac {2^n \minus{} 2}{n \minus{} 1} \bigg)}^{n \minus{} 1}
\]
?  If so, it can be checked directly for small $ n$, and proven for $ n$ greater than $ 5$ or so by asymptotic estimates, as the left hand side is substantially smaller for sufficiently large $ n$.

That is simply AM-GM inequality, which in equivalent form is:
\[ \sqrt [n \minus{} 1]{\prod_{i \equal{} 1}^{n \minus{} 1}{n\choose i}} \leq \frac {\sum_{i \equal{} 1}^{n \minus{} 1} {n\choose i}}{n \minus{} 1}
\]

Sorry, I meant the product.

Yes, I am aware of the proof through AM-GM Inequality. Can we have a counting argument for it ? or do we have a way to combinatorially interpret AM-GM Inequality ?


1.
well im pretty sure you can program even though i dont know why because it would give people unfair advantages, but the rules say you can use any calculator that doesnt have a qwerty keyboard, so if we can use programmable calcs then im assuming we can write programs.

[quote="Lawrence Wu"]1. Are we allowed to program formulas?
2. If I archive a program and then change out my calculators batteries, will my program be deleted?[/quote]

1. Yes, as long as you are using a non-QWERTY calculator. (Concise version of micromath's answer).
2. No. But it helps to use TI Connect and backup the programs anyway.

[quote="Lawrence Wu"]thx. does anyone know how to program a bases program
btw, distracted523, according to your "location", you live in texas. I'll see you at states![/quote]
whoa, dang I'm in your chapter, distracted! Were you in the top 10?

Ontopic:
1. yes you can use programmed calc's, I know someone who always does
2. I think no but I'm not sure..

Programming calculators are not necessary, and they take more time, in my opinion.

Two ways to run a program:

1. Type the name of the program (note the calculator doesn't implement a qwerty keyboard, so that step takes about 20 seconds)

2. Go to the program directory and scroll millions of times until you find the program name you want. That takes about 10-30 seconds, depending how many programs you have :D

I usually program functions that take more than 30 seconds to calculate manually...

But I got third  in my state without using any user-defined programs on my calculator.

[quote="ZhangPeijin"]Programs give you a bit of advantage in MC.
Although it's not really worth the time it takes for you to program it unless you have a lot of free time.
Anyways, for 2, it depends on what calculator you have I guess.[/quote]

I'm a fast calculator programmer, but I'm not concerned about that part. It's actually finding the program under pressure that I'm concerned about.

Hmm...I don't remember seeing many base problems, especially not in calculator rounds.

[quote="ZhangPeijin"]Don't calculators have an archive for all the programs?
Unless you have so many you can't find the one you want.[/quote]

But unfortunately, I have a TI-89 and it stores programs as "files", along with other "files" that were added to my calculator.

[quote="Lawrence Wu"][quote="dingzhou"]base programs? like what?[/quote]
a program that can convert a number from base 10 to say, base 2
and vice versa[/quote]

oh...well...its easy enough to just do it by hands, and its unlikely that you need to convert bases in this years target...i don't even remember a question where it told you to convert bases...why dont u try to make ur own?

1. Yes you're allowed to program formulas.

2. As long as the programs are archived. NEVER pull the batteries from your calculator. Ever. Only do it if your calculator freezes for over 5 minutes. I also find it helpful to make backups (just use the Recall function to copy and paste programs) and archive+hide them in case my memory does randomly clear.

[quote="distracted523"][quote="kthxbai"][quote="Lawrence Wu"]thx. does anyone know how to program a bases program
btw, distracted523, according to your "location", you live in texas. I'll see you at states![/quote]
whoa, dang I'm in your chapter, distracted! Were you in the top 10?
[/quote]

Yep! I was the winner!  :lol:

6th last year at state...so much pressure.[/quote]
OH U!
...expect some messages in ftw and pm's :lol:

[quote="kthxbai"][/quote][quote="distracted523"][quote="kthxbai"][quote="Lawrence Wu"]thx. does anyone know how to program a bases program
btw, distracted523, according to your "location", you live in texas. I'll see you at states![/quote]
whoa, dang I'm in your chapter, distracted! Were you in the top 10?
[/quote]

Yep! I was the winner!  :lol:

6th last year at state...so much pressure.[/quote][quote="kthxbai"]
OH U!
...expect some messages in ftw and pm's :lol:[/quote]

kthxbai, are you in tx too?

[quote="Lawrence Wu"][quote="dingzhou"]base programs? like what?[/quote]
a program that can convert a number from base 10 to say, base 2
and vice versa[/quote]

Is there a remainder function? Or mod?
It's really easy if there is one.
I'll try to make one

-EDIT-
Here we go:
-> means Store (button above on) <= means less than or equal
0->B
0->C
Disp "What number"
Prompt A
Lbl 1
If A<=1
Then
10^B+C->C
Disp C
Stop
End
If (A/2-int(A/2)=.5
Then
10^B+C->C
B+1->B
A-int(A/2)->A
Goto 1
Else
B+1->B
A-int(A/2)->A
Goto 1
End


Hello I am a Chinese student ready to receive my undergraduate education in American universities---I don't have much prominent experiences in my resume---even though I did well at school and I am a quality student---I love math---I would like to know what do you think of Math department of Purdue University West Lafayatte, University of Illinois Urban-Champaign and University of California San Diego?
I would like to listen to your comments and informations---
Thanks a lot---

following is written in Chinese, please choose GBK/GB2312 encoding to read.

和中国大学比，一般美国大学都是很好的。所以，不管你去哪个学校，都不会失望的。只要能被录取，其他的事情没有什么好担心的。

不过要注意身体是否适应长途旅行、以及日夜颠倒(倒时差)的生活。

All three of those schools have respectable math departments.  (Personally, I think UCSD is pretty good, but consult US News for the "conventional wisdom.")  I see little reason to chose one over the others for an undergraduate degree simply because of math.

Thank you for your advice---I think what you said make sense---


Let the polynomial $ p(x)\equal{}x^3\plus{}bx^2\minus{}(4\plus{}3b\plus{}2d)x\plus{}d$ where the numers $ b,c,d$ are nonzero integers . Prove that $ p(x)$ can't have three integer roots .

Counterexample: b=-3, d=3 (has roots 3,1,-1)

Yeah, silouan must have left out a $ c$.

There is no $ c$ . The one I missed is that $ 3\plus{}3d\neq \minus{}4b$


geometry
quadratics
algebra
polynomial
conics
parabola
analytic geometry

These are stolen from the Lehigh Univ. contest (2002 and 2003). (I don't know how to solve 1 and 4, the rest are just nice problems I came across).

1. For each point (m,n) in the plane, with m and n integers, draw a circle of radius 1/(2^((absolute value of m)+1))(3^((absolute value of n) +1)). What is the total area enclosed by all these circles?

2. Write a quadratic polynomial having as its two roots the numbers obtained by increasing each root of x :^2: -2x-5=0 by the reciprocal of the other.

3. What is the largest number of 0s that can occur at the end of 1^n+ 2^n + 3^n + 4^n for any positive integer n?

4. Suppose the parabola y= x^2+px+q is situated so that it has two arcs lying between the rays y=x and y=2x, x  :ge: 0. These two arcs are projected onto the x-axis, yielding segments SL and SR, with SR to the right of SL. What is the difference of the lengths (SR-SL)?

5. In triangle ABC, D is the midpoint of AB, while E lies on BC satisfying BE= 2EC. If angle ADC= angle BAE, then how many degrees are in angle BAC?

6. Find the smallest possible value of (x^2+y^2)/(x-y) for all real numbers x and y satisfying x>y>0 and xy= 3.

These are nice questions.  This will be edited to include my solutions, when I get any.

[quote="314159265358979323846"]
2. Write a quadratic polynomial having as its two roots the numbers obtained by increasing each root of x :^2: -2x-5=0 by the reciprocal of the other.
[/quote]

Let the two roots of x^2 - 2x - 5 = 0 be r and s. Then the roots of the new quadratic are r+1/s and s+1/r. Their sum (with use of Viete's formula) is r+s+1/r+1/s=r+s+(r+s)/rs=2-2/5=8/5, while their product is (r+1/s)(s+1/r)=rs+1/rs+2=-5-1/5+2=-16/5. The new quadratic is thus P(x)=x^2-(8/5)x-16/5.

Jennifer wrote:. For each point (m,n) in the plane, with m and n integers, draw a circle of radius 1/(2^(|m|+1))(3^(|n| +1)). What is the total area enclosed by all these circles?

2. Write a quadratic polynomial having as its two roots the numbers obtained by increasing each root of x :^2: -2x-5=0 by the reciprocal of the other.

3. What is the largest number of 0s that can occur at the end of 1^n+ 2^n + 3^n + 4^n for any positive integer n?

4. Suppose the parabola y= x^2+px+q is situated so that it has two arcs lying between the rays y=x and y=2x, x  :ge: 0. These two arcs are projected onto the x-axis, yielding segments SL and SR, with SR to the right of SL. What is the difference of the lengths (SR-SL)?

5. In triangle ABC, D is the midpoint of AB, while E lies on BC satisfying BE= 2EC. If angle ADC= angle BAE, then how many degrees are in angle BAC?

6. Find the smallest possible value of (x^2+y^2)/(x-y) for all real numbers x and y satisfying x>y>0 and xy= 3.

2. [hide]The roots of our new polynomial will have sum (1+1/ab)(a+b)=(1+1/-5)(2)=8/5 and product (a+1/b)(b+1/a)=ab+2+1/ab=(-5+2+1/-5)=-16/5, where a and b are the roots of the original polynomial. Thus one possible new polynomial is 5x:^2:-8x-16. Correct?[/hide]

4. [hide]The lengths of SL and SR are the distances between the x-coordinates for where this parabola intersects the two lines. y=x:^2:+px+q intersects y=2x at x:^2:+(p-2)x+q=0 while it intersects y=x at x:^2:+(p-1)x+q=0. Let the points of intersection for y=2x be a and b and let the points of intersection with y=x be c and d. Then we are looking for (b-d)-(c-a)=a+b-c-d=(a+b)-(c+d)=(p-2)-(p-1)=-1. Correct?[/hide]

6. [hide](x:^2:+y:^2:)/(x-y)=((x:^2:-2xy+y:^2:)+2xy)/(x-y)=

(x-y)+2xy/(x-y)=a+6/a, where a is the real number x-y. a+6/a:ge:2:sqrt:(a*6/a)=2:sqrt:6 by AM-GM, which is attainable when x=y+:sqrt:6. Correct?[/hide]

Odd problems forthcoming.

But Mystic,

For #4, the question is to find not the difference between the x-coordinates, but the difference in the x-coordinates after the arcs are projected onto x-axis (which i think means transforming the curves into lines).

think about it a little; i think i'm right

Well, I will wait for someone else to chime in, since I don't know much about projecting stuff (is this related to projective geometry?), but I just saw your statement [hide]The lengths of SL and SR are the distances between the x-coordinates for where this parabola intersects the two lines. [/hide] and noticed how it contradicted with the actual problem.

http://www.lehigh.edu/~dmd1/test02.pdf  - solutions

According to the website, the solution for number 4 should be (d-b)-(a-c).. whether this is right or not, I don't know... I didn't actually figure out what an x-projection was until this morning...

The other two are correct. (It is interesting to note that none of the contestants who took this test got number 6 right...)

well the only one i see a solution for off the bat is #6... so..

[hide] (x :^2:+y :^2:)/(x-y) = {(x-y) :^2:+2xy}/(x-y), break it up, you get (x-y) + 6/(x-y)...cuz xy=3... so let z=x-y, then you have to minimize z+6/z. by am-gm, we have (z+6/z)/2 :ge:  :sqrt: (6), multiplying both sides by two and you get z+6/z :ge: 2 :sqrt: (6)....ill update with the eq case in a few min...[/hide]

[color=cyan]"Projection" means dropping perpendiculars at each point.  Thus, the difference in the x-coordinates of the endpoints of an arc is [i]equal[/i] to the difference in the x-coordinates of the projections of the arc.  That is, the process of projection is such that it does not change the value of the x-coordinates at all.[/color]

Oh, so projection is NOT what this problem is refering to, right?

[color=cyan]The problem IS refering to projection -- the two arcs are projected onto the x-axis, meaning that you drop a perpendicular from each point of the arcs to the x-axis.  The set of the feet of the perpendiculars is the segment the problem refers to.

A question, however:  why is the letter S used twice there?  I find that rather confusing.[/color]

[quote="314159265358979323846"]1. For each point (m,n) in the plane, with m and n integers, draw a circle of radius 1/(2^(|m|+1) * 3^(|n| +1)). What is the total area enclosed by all these circles?[/quote]

Well, lets take this question apart a bit -- fix n.  That is, consider it not to be variable but instead constant for a while.  Now, what we are looking for is the summation :Sigma: :pi:*[1/(2^(|m|+1) * 3^(|n| +1))]:^2:  over all integers m.  The n and the pi parts are constant, so lets pull them out front, to give us
:pi:/3^(2|n| + 2) * :Sigma: 1/(2^(2|m| + 2)
Let us just calculate the value of the sum first, and then multiply it by the other stuff afterwards.
:Sigma: 1/(2^(2|m| + 2) = . . . 1/64 + 1/16 + 1/4 + 1/16 + 1/64 + . . .
1/16 + 1/64 + 1/256 + . . . is a geometric series with first term 1/16 and common difference 1/4.  Thus, its sum is (1/16)/(1 - 1/4) = 1/12.  Thus the total sum here is 1/12 + 1/4 + 1/12 = 5/12.

So, going back to the expression we want, we have that it is
:pi:/3^(2|n| + 2) * :Sigma: 1/(2^(2|m| + 2) = :pi:/3^(2|n| + 2) * 5/12
= 5:pi:/12 * 1/3^(2|n| + 2), which we want to sum over all integral values of n.  Ignore the coefficient for a bit again, and just look at
:Sigma: 1/3^(2|n| + 2) = . . . 1/729 + 1/81 + 1/9 + 1/81 + 1/729 + . . .
1/81 + 1/729 + . . . is a geometric sequence with initial term 1/81 and common difference 1/9.  Thus, its sum is
(1/81)/(1 - 1/9) = 1/72.  This makes the total value of our sum
1/72 + 1/9 + 1/72 = 5/36.  Thus the sum of all of the areas is
5:pi:/12 * 5/36 = 25:pi:/432.

If you see any arithmetic errors or have questions on the technique, feel free to point them out/ask, or to otherwise comment.


modular arithmetic
quadratics
number theory proposed
number theory

Find all integer solutios  to  $\frac{13}{x^2}+\frac{1996}{y^2}=\frac{z}{1997}.$

We claim that there are no possible solutions.

Rearranging the equation, we get $13\cdot 1997 y^2z + 1996 \cdot 1997x^2z = {(xyz)}^2$. Note that $1997$ divides the L.H.S., so since $1997$ is prime and ${(xyz)}^2$ is a perfect square, we have ${1997}^2$ divides R.H.S., so $1997$ must divide at least one of $x,y, z$.

Suppose $1997 \nmid z$, then taking $\mod 1997$ to the above equation, we mst have $1997 \mid x$ and $1997 \mid y$. Letting $x=1997x_0, y = 1997y_0$, we have \[ 13{y_0}^2z + 1996{x_0}^2z = 1997{x_0y_0z}^2 \] \[ \Rightarrow 13{y_0}^2 + 1996{x_0}^2 = 1997{x_0}^2{y_0}^2z \] \[ \Rightarrow 13{y_0}^2 - {x_0}^2 \equiv 0 \pmod{1997} \] \[ \Rightarrow 13 \text{ is a quadratic residue} \mod 1997 \] Yet $(\frac{13}{1997})(\frac{1997}{13}) = (\frac{13}{1997})(\frac{8}{13}) = 1$ and $(\frac{8}{13}) = -1$ implies $(\frac{13}{1997}) = -1$. (Contradiction)

Thus $1997\mid z$. Letting $z=1997z_0$, we have \[ 13y^2z_0 + 1996x^2z_0 = x^2y^2{z_0}^2 \] \[ \Leftrightarrow z_0(x^2y^2z_0 - (13y^2 + 1996x^2)) = 0 \] \[ \Rightarrow z_0 = 0 \text{ or } z_0 = \frac{13y^2+1996x^2}{x^2y^2} \] Note that $z_0 = 0$ is not possible as $\frac{13}{x^2} + \frac{1996}{y^2} > 0 \forall x,y \in \mathbb{R}$ , so we have $13y^2 + 1996x^2 \equiv 0 \pmod{x^2y^2}$. Letting $\gcd (x,y) = d, x = dx_0, y = dy_0$, we have $\frac{13{y_0}^2 + 1996{x_0}^2}{d^2{x_0}^2{y_0}^2} \in \mathbb{Z} \Rightarrow 13{y_0}^2 + 1996{x_0}^2 \equiv 0 \pmod{{x_0}^2{y_0}^2}$. Taking $\mod {x_0}^2$, we have $13{y_0}^2 \equiv 0 \pmod{{x_0}^2} \Rightarrow 13 \mid x_0$.
Letting $x_0 = 13x_1$, we have $\frac{{y_0}^2 + 1996\cdot 13{x_1}^2}{13d^2{x_1}^2{y_0}^2} \in \mathbb{Z}$
$\Rightarrow {y_0}^2 + 1996\cdot 13{x_1}^2 \equiv 0 \pmod{13}\Rightarrow y_0 \equiv 0 \pmod{13}$. This contradicts the original assumption that $x_0, y_0$ are coprime.

Therefore there are no solutions.


How many pythagorean triangles are there such that their perimeter equals their area?
[hide="hint"]Diophantine[/hide]

[quote="Elemennop"]5,12,13 is the only solution, I think.[/quote]
did you use trial and error? :P
If not, please post your solution.

[quote="Farenhajt"]Denote the sides by $a,b$. Then we have
\begin{eqnarray*}\frac{ab}{2}=a+b+\sqrt{a^{2}+b^{2}}&\iff& \frac{ab}{2}-a-b=\sqrt{a^{2}+b^{2}}\\ &\implies& \frac{a^{2}b^{2}}{4}+a^{2}+b^{2}-a^{2}b-ab^{2}+2ab=a^{2}+b^{2}\\ &\iff& \frac{a^{2}b^{2}}{4}-a^{2}b-ab^{2}+2ab=0\\ &\iff& \frac{ab}{4}-a-b+2=0\\ &\iff& ab-4a-4b+8=0\\ &\iff& (a-4)(b-4)=8\end{eqnarray*}
Since $8$ can be factorized as $1\cdot 8,2\cdot 4,4\cdot 2,8\cdot 1$, we get $4$ possibilities that reduce to $2$ different triangles: $5,12,13$ and $6,8,10$.[/quote]
thanks Farenhajt. :)

[quote="Elemennop"]Jeez, I didn't even consider the 2*4 factorization... I'm getting lazy.[/quote]
It happens. :)
thank you for your contribution.

[quote="Inspired By Nature"]Continuing along this topic, find all primitive pythagorean triangles whose perimeters are twice their areas. :)[/quote]

[hide="Answer"]The equation would be $(a-2)(b-2)=2$ and the only solution is $3,4,5$.[/hide]

thats what I found, thanks Farenhajt. :D

[quote="Gyan"]This has been asked here  a few times, but remove the condition about "pythagorean" ..how many triangles (whose sides are integers - but  they need not be right angle) are there whose perimeter is equal to the area.

[hide](For example triangle  with the sides like (9,10,17) and others in additon to the two given above.. [/hide][/quote]

well...
[hide]
you get $4s = (s-a)(s-b)(s-c)$,multiply both side by 8 we get:
$16(a+b+c) = (b+c-a)(a+c-b)(a+b-c)$, and what now... :maybe:
[/hide]

[quote="pkerichang"]
$16(a+b+c) = (b+c-a)(a+c-b)(a+b-c)$, and what now... :maybe:
 [/quote]
Some Hints:
1. The problem (though harder than that of pythagorean triangles) is not that hard ( I think, it can still be in "intermediate" or " pre-olympiad level")
2. It may be a little easier to work with:
[hide]Iif you let  $x=b+c-a,y=a+c-b,z=a+b-c$ the equation becomes $16(x+y+z)= xyz$
(and x,y,z all are >0)     [/hide]
3. There are only a few answers.

edit: removed a typo.

Using Gyan's hints so far I can find the following triples:
$(6, 25, 29), (7, 15, 20), (9, 10, 17), \text{ and }(14, 15, 20)$

Think, there is a typo, No $(14,15,20)$, all other three  are okay.
[hide="Also"](And if you include  the two already given before ($(6,8,10)$ and $(5,12,13)$ there are no more solutions.) [/hide]

If there is still interest.. here  are hints which give away the solution.

[hide]1.  (x, y, z ) are all even and thus the equation can be further simplified.
to $4(p+q+r)= pqr$
[hide="because"]
(If $x$ is odd, so is $y$ because $a=(x+y)/2$ is integer. .., and $z$ too  is odd because ($(x+z)/2$ is also a  side of the triangle  .. and if all are odd the product  of xyz can't be even)
[/hide]
2. WLOG, if you assume $p \ge q \ge r$ then $r \le 3$ (In fact one can see that it is not 3, and thus only possible values  of r are 1 and 2)
[hide="because"]
$4(p+p+p) \ge pqr \implies qr \le 12 \implies r^{2}\le 12$ [/hide]

3. Once you know r, finding p and q is trivial.  [/hide]

BTW - One geometric answer makes the above solution trivial is to notice that  in-circle of  all such triangles  have radius =2.
Once you notice that (and realize one of the angle has to be more than, or equal to $60^{o}$ you can find all the answers .. just as the above logic.


Ring Theory
algebra
polynomial
calculus
integration
function
domain

I have two questions about R-Algebras.
First I don't think that if R is a UFD, then every finitely generated R-Algebra is a UFD. Is it true? My reasoning is since the R-Algebra, say A, is an extension of A, there could be elements which are not characteristic to UFDs adjoined to R. I mean given a ring R which is not a UFD, there may be a subring which is a UFD.

Also is every finitely generated R-Algebra isomorphic over R to a quotient of a polynomial ring in many variables by a prime ideal??

Thanks

Um, im not sure what your definition of an algebra is, so I'll state mine and you can tell me if we're on the same page:

A (commutative) $ R$-algebra is a ring $ A$ with a homomorphism $ \phi: R\rightarrow A$. Given this definition of an $ R$-algebra certainly not every algebra over a UFD is a UFD: for example, consider $ \mathbb{Z}[\sqrt { \minus{} 5}]$. Then $ 6 \equal{} (1 \plus{} \sqrt { \minus{} 5})(1 \minus{} \sqrt { \minus{} 5}) \equal{} 2\times 3$ so we don't have unique factorization.

As for the second, I'm pretty sure that its true.

My definition is: A finitely generated R algebra is an integral domain A, extending R, with the property : there exists a finite number of elements in A such that there is no proper subring of A containing R and the finite elements.

How would the second thing be proven?

Alright so I didn't know you wanted integrality (thats ok, my counter example to UFD still holds). I actually messed up in my last post cause if you didn't want integrality the ideal doesnt have to be prime so I implicitly assumed it was. my bad. So, basically your definition is the same as mine except you want the homomorphism $ R\rightarrow A$ to be the inclusion map. The second condition that there is a finite number of elements in $ A$ such that no proper subring of $ A$ containing $ R$ and those elements means that those elements generate $ A$.

Alright, so suppose our finite set of elements is $ \{a_1, a_2, a_3... a_n\}$. Then $ R[a_1, a_2,...a_n] \equal{} A$. Consider the polynomial ring $ R[x_1,...x_n]$. There is an $ R$-algebra homomorphism $ R[x_1,...x_n]\rightarrow A$ by taking $ x_i$ to $ a_i$. This map is surjective because the $ a_i$ generate $ A$. Now, call its kernel $ I$. Then $ A\cong R[x_1,...x_n]/I$ by the first isomorphism theorem. This actually proves a stronger result than what you asked for because we don't need integrality. If indeed $ A$ happens to be integral, then we know $ I$ is a prime ideal because the product of two things cannot land in $ I$ without one of them being in $ I$.

The rationals are an extension of the integers which is not a $ \mathbb{Z}$-algebra, hm? (Since the rationals are not finitely generated)

yeah its not finitely generated, thats why it doesn't work. I'm starting to think we might want to add finite presentation just to be safe but I think it works with just finite generation. Also if you think about it, the rational numbers are obtained by adjoining the roots of all linear polynomials to $ \mathbb{Z}$ in the similar way that roots to polynomials are adjoined to ring extensions, so its really not that different. For example, the subset of rational numbers of the form $ a \plus{} b/2$ with integer values for $ a$ and $ b$ is formed by $ \mathbb{Z}[x]/(2x \plus{} 1)$. So we can think of $ \mathbb{Q}$ as some sort of giant binding together of all these extensions.

I don't know what a finite presentation is at all. So I don't think it will be necessary =)
Do you have any suggested books on which I can read up on this stuff some more? Its difficult for me but I hardly want to give up XD

If you want a very thorough introduction to commutative algebra (which is where your inquiries seem to direct you), then i would recommend Commutative Algebra with a view toward Algebraic Geometry. (You don't have to read the second half of the book, the first half of the book should be more than enough). I would also recommend Hungerford's Algebra.

Your argument that $ I$ is prime is slightly more obscure than it needs to be. $ R[x_1, \ldots, x_n]/I$ is isomorphic to an integral domain, so $ I$ is prime (any ideal such that the ring mod this ideal is an integral domain is prime).

Right, I was trying to prove the above statement (or at least explain it) by saying that the reason why it must be the case is because if the product of two things is congruent to zero mod $ I$, by integrality one of them must be congruent to zero mod $ I$ which means one of the must be in $ I$ which means $ I$ is prime. From your reaction, I guess my explanation was unsuccessful.


inequalities
real analysis
real analysis unsolved

Let $(x_i)$ be a decreasing sequence of positive reals, then show that:

(a) for every positive integer $n$ we have $\sqrt{\sum^n_{i=1}{x_i^2}} \leq \sum^n_{i=1}\frac{x_i}{\sqrt{i}}$.

(b) there is a constant C for which we have $\sum^{\infty}_{k=1}\frac{1}{\sqrt{k}}\sqrt{\sum^{\infty}_{i=k}x_i^2} \le C\sum^{\infty}_{i=1}x_i$.

[quote="Fermat -Euler"]see http://www.mathlinks.ro/Forum/viewtopic.php?t=56175[/quote]No, you only write a trivial start to the problem. the real question is part (b), which is only in this topic. ;)

[quote=Peter]Let $(x_i)$ be a decreasing sequence of positive reals, then show that ... there is a constant [url=https://www.imc-math.org.uk/imc2000/prob_sol1.pdf]${\it{C}}$[/url] for which we have $\sum^{\infty}_{k=1}\frac{1}{\sqrt{k}}\sqrt{\sum^{\infty}_{i=k}x_i^2} \le {\it{C}}\sum^{\infty}_{i=1}x_i$.[/quote]

In fact, we have \[\sum_{m=1}^\infty{\mspace{-4mu}\sqrt{\frac1m\sum_{i=m}^\infty{\mspace{-1mu}x_i^2}}}\leq\frac\pi2\sum_{i=1}^\infty{\mspace{-1mu}x_i}\] for any decreasing sequence \(\left\{x_i>0\right\}_{i\geq1}\), where the constant $\frac\pi2$ on the right-hand side is best possible.
For more details, please see [url=http://nsmath.cn/filedownload/173078]here[/url].

Does anybody take care of convergence of both series? What if x_i=1+1/i ? C can be in that case arbitraty small...


calculus
real analysis
real analysis unsolved

For a partition P $ \equal{} \{ x_0, x_1,\ldots, x_n \equal{} b\}.$

Let $ f: [a,b]$ $ \to$ $ \mathbb{R}$ satisfy the Lipschitz condition i.e. for u,v, in [a,b] where $ \mid f(u) \minus{} f(v)\mid \leq c\mid u\minus{}v\mid$ for a positive constant c. Prove that
$ 0 \leq$ U(f,P) $ \minus{}$ L(f,P) $ \leq c[b\minus{}a]*gap P$

[quote="ayatollah85"]For a partition P $ \equal{} \{ x_0, x_1,\ldots, x_n \equal{} b\}.$

Let $ f: [a,b]$ $ \to$ $ \mathbb{R}$ satisfy the Lipschitz condition i.e. for u,v, in [a,b] where $ \mid f(u) \minus{} f(v)\mid \leq c\mid u \minus{} v\mid$ for a positive constant c. Prove that
$ 0 \leq$ U(f,P) $ \minus{}$ L(f,P) $ \leq c[b \minus{} a]*gap P$[/quote]

This is straighforward. What are you having trouble with?


Let P be the intersection of the diagonals of an inscribed quadrilateral ABCD. Prove that all four Euler lines of the triangles PAB, PBC, PCD, and PDA intersect in a single point.( the Euler line of a triangle is the line connecting its centroid and its orthocenter).