logarithms
number theory
prime factorization
relatively prime

Problem:

Is $\log_8 10$ rational?

[hide="My proof"]

I'm not sure how good this proof is.. So I'll be grateful on the criticism as well.

$\log_8 10 = \frac{\log_2 10}{\log_2 8}\\
= \frac{\log_2 10}{3}\\
= \frac{\log_2 2 + \log_2 5}{3}$

Now, we can separate the fraction into two smaller fraction.

$\frac{\log_2 2 + \log_2 5}{3} = \frac{1}{3} + \frac{\log_2 5}{3}$

Left fraction is clearly rational. For the right fraction, we can rewrite it as:

$\frac{\log_{10} 5}{\log_{10} 2}$

But clearly, $\log_{10} 5$ and $\log_{10} 2$ both irrationals. Thus, $\frac{\log_2 5}{3}$ is irrational and this implies $\frac{\log_2 5}{3} + \frac{1}{3}$ is irrational.

$\therefore \log_8 10$ is irrational. QED. [/hide]

[quote]But clearly, $\log_{10} 5$ ...... irrationals.[/quote]
why?  It is not any easier (or harder)  to prove this than the original question.
Hint
[hide]can  $8^a $ equals  $10^b$ when  $a$ and $b$ are    integers ?  [hide] Can   a power of  8 have a factor of 5 ?[/hide]

 [/hide]

Here's my proof:
[hide]Since log[size=75]8[/size]10 = 1/(log[size=75]10[/size]8)= 1/(3log[size=75]10[/size]2),
we only have to determine whether log[size=75]10[/size]2 is rational or irrational.

The equation 10^x = 2 has no rational solutions because 2 does not have a factor of 5.

Therefore, log[size=75]10[/size]2 is irrational, and so is log[size=75]8[/size]10.[/hide]
Is this clear?

[quote="JBL"]Silverfalcon, $x$ irrational and $y$ irrational does not imply $\frac{x}{y}$ is irrational.[/quote]

Right.. $\frac{2 \sqrt 2}{\sqrt 2} = 2$ which is rational..

[quote="Gyan"][quote]But clearly, $\log_{10} 5$ ...... irrationals.[/quote]
why?  It is not any easier (or harder)  to prove this than the original question.
[/quote]

just a heads up silverfalcon - always be aware of circular reasoning. in other words, don't use what you're trying to prove as an argument in your proof b/c it will make you lose credibility and your proof will be totally invalid.

frt , Silver falcon -

If you want to take a look, go ahead ...but what follows is more than a hint so  don't look if you don't want to.

[hide]Proof by contradiction:

Assume  otherwise, and let $m$  and $n$ be positive  integers ($n$ is not zero )

let         $\log_8  10 =  \frac  m n $
so         $ 8^{(\frac m n )} = 10 $
so  $8^m =  10^n$
Now since $n > 0 $  RHS contains a factor of $5$  so cannot be equal to LHS (which have no factors of 5).
We get a contradiction ..  Hence the original assumption  is wrong.  QED

Hope this helps.[/hide]

im adding something to Gyan's solution

[hide]the reason there is no factor of 5 in LHS is due to the unique prime factorization theorem[/hide]

[hide]
You got to $\log_8 10 = \frac 1 3 + \frac{1}{\log_2 5}$.  Suppose $\log_2 5 = n$.  So $2^n = 5$.  $n$ is obviously not an integer.  Suppose $n = a/b$ with a and b are relatively prime integers.  However, $2^{a/b}$ is only an integer if a/b is an integer (which you can pretty easily show), so $\log_2 5$ is irrational...[/hide]

[quote="pkothari13"][quote="Palytoxin"]the reason there is no factor of 5 in LHS is due to the unique prime factorization theorem[/quote]

is that the seme thing as the fundamental theorem of arithmetic?[/quote]

Yes

[quote="Silverfalcon"]Problem:

Is $\log_8 10$ rational?
[/quote]
8^a =10. Since the variable a has no factors of 5, taking any power, even fractional, wont give you anything divisible by 5, since 2 is relatively prime to 5.


[quote="Sahand.71"]hello!
please help me in this problem .  :)

is it possible?
number A is 30 digits.
a(i)=ith digit of number A.
a(i) + 10a(i+1) + ...+ 10^4a(i+4) is divisable by 13. (for i=1 ... 26)

sorry for my poor english  :blush:[/quote]
Yes it is. A hint: Use the chinese reminder theorem.

in fact u have to choose $ 5$ sets namely $ S_1,...,S_5$ such that all of the elements of $ S_i$ are congruent $ mod13$:
$ S_i\equal{}\{a_i,4a_{i\plus{}5},3a_{i\plus{}10},12a_{i\plus{}15},9a_{i\plus{}20},10a_{i\plus{}25}\},1 \leq i \leq 5$.but we know that $ 0 \leq a_k \leq 9,1 \leq k \leq 30,and,1 \leq a_{5},a_{10},...,a_{30} \leq 9$.
now u need to find all sets satisfying the conditions mentioned and also this condition:$ a_1\plus{}10a_2\plus{}...10^4a_5 \equiv 0 \mod {13}$.let's check the different cases:(it's obvious that if $ a_i$ is known then all the elements of the set will be defined uniquely since they are between $ 0$ and $ 9$)
1-$ a_i\equal{}0 \implies  a_{i\plus{}5},a_{i\plus{}10},a_{i\plus{}15},a_{i\plus{}20},a_{i\plus{}25}\equal{}0$.
2-$ a_i\equal{}1 \implies  a_{i\plus{}5}\equal{}10,...$.it doesn't satisfy.
3-$ a_i\equal{}2 \implies a_{i\plus{}5}\equal{}7,a_{i\plus{}10}\equal{}5,a_{i\plus{}15}\equal{}11,...$.it doesn't satisfy.
4-....
if u check all the cases u'll get that this kind of set exist if $ a_i\equal{}0$  which implies that $ a_{30}\equal{}0$ contradiction.so there doesn't exist such number $ A$.hope i didn't miss sth!
i hope u understood?!sorry for my poor english! :oops:

Oh. I wasn't thinking right. Don't mind my post.


superior algebra
superior algebra solved

Is there a commutative ring with 1 with exactly 5 units?


inequalities
trigonometry
trig identities
Law of Cosines

Prove that :[tex] \frac{8}{5} \geq \frac{abc}{m_{a}m_{b}m_{c}}[\tex] takes place in any triangle.

[quote="Bottema"]Prove that : [tex]\frac{8}{5} \geq \frac{abc}{m_{a}m_{b}m_{c}}[/tex] takes place in any triangle.[/quote]

Are you sure the triangle doesn't have to be acute  or something?  (think of a very obtuse isosceles triangle)

I agree with last post, it's not true for triangle (2,2,3)  for instance (with 4mA=2b+2c-a)

I think I can prove a little better (with the use of brute force Algebra) :

8/5 > 8/3*sqrt(3) >= prod a / prod ma

[hide]

Using law of cosines twice, we get 4ma=2b+2c-a

Ineq to prove is :  (*) 64/27 >= prod a / prod ma

Since the triangle is acute we have : (**)  6*prod (a+b-c) >= 0.

Surprise ! (*) reduces to (**)    [/hide]

[quote="belenos"]  6*prod (a+b-c) >= 0.[/quote]

Can you please explain this inequality.

Sorry I should have make it more explicit :

a+b-c = 2abcos(C) by law of cosines and cos(C) >= 0 since the triangle is acute.

m_c=what? what is just c?  Is one the side and oen the angle?


geometry
3D geometry
quadratics
algebra
polynomial
Rational Root Theorem

Can someone tell me what the cubic formula is and also solve $x^3+4x^2-27x+40=0$ using the cubic formula.

The cubic formula is ridicously [url=http://www.math.vanderbilt.edu/~schectex/courses/cubic/]LONG[/url].

It is better to use synthetic division, the rational root theorem, and Descartes' rule of sign to solve cubic equations [or factoring (by grouping)].

[quote="lkryptonicl"][quote="DanK"]We were just talking about this today in my pre-calc class...

You can easily find that it has a root of $-8$ (I did it using graphing)...

If I'm remembering this right, we just multiply that by the cube roots of unity.
Therefore:

$(-8)(-\frac{1}{2}+\frac{\sqrt3}{2}i)=-4+4i\sqrt3$
$(-8)(-\frac{1}{2}-\frac{\sqrt3}{2}i)=-4-4i\sqrt3$

So, assuming I remember the lecture correctly, your roots are: $\boxed{-8,-4+4i\sqrt3,-4-4i\sqrt3}$[/quote][/quote] Ummmm............you got one of the roots right  :), and say that you couldnt graph it. Then how would you "easily" tell that one of the roots is -8? Rationaly root theorem or Descartes rule of signs?

[quote="surge"]Hmm... I came to a different conclusion.

using synthetic division, dividing the original equation by $(x+8)$, you end up with the equation $x^2-4x+5=0$

Which gives you the complex roots of: $\boxed {2+i, 2-i}$[/quote]

Rational root theorem [with Descartes'] tells you that the only possible solutions are factors of 40 (1  2  4  5  8  10  20  40).

So there's really no point of knowing the cubic formula right?

[quote="lkryptonicl"][quote="DanK"]We were just talking about this today in my pre-calc class...

You can easily find that it has a root of $-8$ (I did it using graphing)...

If I'm remembering this right, we just multiply that by the cube roots of unity.
Therefore:

$(-8)(-\frac{1}{2}+\frac{\sqrt3}{2}i)=-4+4i\sqrt3$
$(-8)(-\frac{1}{2}-\frac{\sqrt3}{2}i)=-4-4i\sqrt3$

So, assuming I remember the lecture correctly, your roots are: $\boxed{-8,-4+4i\sqrt3,-4-4i\sqrt3}$[/quote] Ummmm............you got one of the roots right  :)[/quote]

Ok, so I didn't remember the second part quite right, but it's still easy enough to do it with quadratics after you find the one root...

There was another way too that we learned today, where you multiply by a certain factor...  Gaaah, stupid memory! :wallbash:

You should use the rational root theorem (which works for a polynomial of any degree). Basically, you list all of the +/- factors of the term without an x in front of it. Then you take the coefficient of the highest degree term and list all of its +/- factors. If the polynomial has a rational root, then it will (a factor of the term without the x in front of it)/(a factor from the coefficient of the highest degree term). Hope I didn't make that too confusing.

For example, take your polynomial: $x^3+4x^2-27x+40$
The term without an x in front of it is 40, and its factors are $\{\pm 1,\pm 2,\pm 4,\pm 5,\pm 8,\pm 10,\pm 20,\pm 40\}$
The coefficient of the highest degree term is 1, and its factors are $\{\pm 1\}$
You then check every possibility of: an element from the first set divided by an element in the second set.

For a cubic, you can use synthetic division to to reduce it to a quadratic and then use the quadratic forumula to find the other two roots.

Yeah, I know, I'll just stick with that.  That way I won't need to take the time to figure that factor out again...


algebra
polynomial
number theory unsolved
number theory

Given integer $ a$ with $ a>1$ , an  integer $ m$ is $ good$ if $ m\equal{}200 a^k\plus{}4$ for some integer $ k$. Prove that , for any integer $ n$ , there is a degree $ n$ polynomial with integer coefficients such that $ p(0), p(1), p(2),...,P(n)$ are dinstinct $ good$ integers

Let $ a_0\equal{}200a^{k_0}\plus{}4,a_1\equal{}200a^{k_1}\plus{}4,...,a_n\equal{}200a^{k_n}\plus{}4$ are good, then we can construct Lagrange approximation
\[ P(x)\equal{}\sum_{i\equal{}0}^n a_i\prod_{j\not \equal{}i}\frac{x\minus{}j}{i\minus{}j}\equal{}a_0\plus{}\sum_{i\equal{}1}^n(a_i\minus{}a_0)\prod_{j\not \equal{}i}\frac{x\minus{}j}{i\minus{}j}.\]
If $ n!|(a_i\minus{}a_0)$, then $ P(x)$ had integer coefficients. Let $ S$ is the set of primes $ S\equal{}\{p\le n,p|a\}$ and $ T\equal{}\{p\le n, p\not |a\}$.
We can choose $ k_0\ge n$, then $ p^{ord_p(n!)}|a^{k_i}\minus{}a^{k_0} \ \forall p\in S$. We can chose $ m$, suth that $ p^{ord_p(n!)}|a^m\minus{}1 \ \forall p\in T$. Then for any $ k_i$, suth that $ m|k_i\minus{}k_0$ polinom $ P(x)$ had integer coefficints.


When I open an "On site" blog and try to quote a comment, a bunch of strange posts come up from an unknown thread. And if I make a comment and press "submit", my comment goes to this thread. The thread looks like this:

[quote]
MaThWhIz2004

solafidefarms wrote:
I don't believe that many messages could be recieved in your life. On the other hand, maybe so, but forward them all to me at solafidefarms @ `'`gmail.com, and I will believe.

Aren't those called Doubting Thomases?

Haha, no, I really don't have *that* many... I was exaggerating, so that's why there's a "like" there xD But spam just annoys me xD

Lol xP
LynnelleYe

avolfson wrote:
Thats twenty point to Griffindor!

(Your in the Griffindor house, right?)

It's spelled Gryffindor.[/quote]

I believe all of these posts are the result of people who tried to quote a comment in an AoPs blog.

What's happening?

I don't really understand what you're describing.  Can you give me a step-by-step method to recreate what you are seeing?

If I enter your blog for example, and then click "1 Comments" right below the post on women in math, and then click "Quote"  right above Lynelleye's post, I see a rather strange screen full of posts.


logarithms
function
calculus
calculus computations

1)Prove that: $ m \le n$ then
$ \sum\limits_{k \equal{} 0}^m {( \minus{} 1)^{m \plus{} k} C_m^k \left( {\frac {k}{m}} \right)^n \le C_n^m \frac {{m!}}{{m^m }}}$
2) Caculate:
$ \sum\limits_{n \equal{} 0}^\infty {\frac {{x^{3^n } \plus{} \left( {x^{3^n } } \right)^2 }}{{1 \minus{} x^{3^{n \plus{} 1} } }}}$
3) prove that:
$ \sqrt {2\sqrt [3]{{3\sqrt [4]{{4...\sqrt [n]{n}}}}}} < 2,n \ge 2$
4 Caculate:
$ \sum\limits_{n \equal{} 1}^\infty  {\frac{{9n \plus{} 4}}{{n(3n \plus{} 1)(3n \plus{} 2)}}}$

hello, to 4. $ \sum\limits_{n \equal{} 1}^\infty {\frac{{9n \plus{} 4}}{{n(3n \plus{} 1)(3n \plus{} 2)}}}\equal{}\frac{1}{6}\left(21\minus{}\sqrt{3}\pi\minus{}9\log(3)\right)$.
Sonnhard.

The correct answer to number 4 is $ S \equal{} \frac92 \minus{} 3 \ln 3$.

Let :$ a_n$
We have:
$ \ln a_n\equal{}\sum\limits_{i\equal{}2}^n\frac{\ln i}{i!}$
 Withall $ i\geqslant 2$then
$ \ln i\leqslant \frac12i\plus{}\ln 2\minus{}1$
i  read hint, but i can't solve more.
We need to prove  that: $ lna_n <ln2$

hello, yes, you have right, the sum is
$ \sum\limits_{n \equal{} 1}^\infty {\frac{{9n \plus{} 4}}{{n(3n \plus{} 1)(3n \plus{} 2)}}}\equal{}\frac{9}{2}\minus{}3\ln(3)$.
Sonnhard.

hello, let $ P\equal{}\sqrt {2\sqrt [3]{{3\sqrt [4]{{4...\sqrt [n]{n}}}}}}$ for $ n \ge 2$ then we get:
$ \ln(P)\equal{}\frac{\ln(2)}{2!}\plus{}\frac{\ln(3)}{3!}\plus{}\cdots\plus{}\frac{\ln(n)}{n!}$.
Since $ \frac{\ln(x)}{x}$ is a decreasing function for $ x \ge e$, we have
$ \ln(P)<\frac{\ln(2)}{2!}\plus{}\frac{\ln(3)}{3!}\left(\frac{1}{2!}\plus{}\frac{1}{3!}\plus{}\cdots\right)\equal{}\frac{\ln(2)}{2!}\plus{}\frac{\ln(3)}{3!}\left(e\minus{}2\right)$.
Sonnhard.


graph theory
combinatorics open
combinatorics

I understand that the only known proof of the 4 color theorem is proved by computer, but I would like some explanation on why. Why cannot you just say that the highest planar complete graph you can have is a (4.4) and a (5,5) graph and higher cannot be planar. So can't you say that of course the minimum # of colors to color any map is 4 because you can't have 5 bodies all touching each other at once? I'm just a little confused on this and I would like some clarification.

There are too many special cases to be checked. See http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=5807CEDADAD376AEFDB77A8D37011CB6?doi=10.1.1.31.5920&rep=rep1&type=pdf

You also appear to have at least two important misunderstandings:
1) Every non-planar graph has a [i]minor[/i] (or equivalently a topological minor) isomorphic to $ K_5$ or $ K_{3, 3}$; this is not the same thing as having a [i]subgraph[/i] isomorphic to one of these graphs.
2) Chromatic number and clique number are not the same thing: the clique number gives a [i]lower bound[/i] on the chromatic number, but they need not be equal.  For example, the pentagon has no triangle (i.e., no three vertices mutually adjacent) but nevertheless requires three colors.  Similarly, there are many graphs that have no five-clique but nevertheless require five or more colors to properly color.


Given a triangle $ABC$ and $P$ is apoint which in its interor.$AP,BP,CP$ intersection triangle's sides at $A_{1},B_{1},C_{1}$,res. The line perpendicular $PA$ at $P$ intersects $BC$ at $A'$.$B',C'$ are defined similarly.Let $P'$ is isogonal conjugate of $P$ wrt triangle $A_{1}B_{1}C_{1}$(its always called Lamoin's point  of P).Show that:$A',B',C'$ lie in a line which perpendicular to $PP'$.

Please see the solution of the problem on pg. 20 at http://www.awesomemath.org/reflections/2006_4/2006_4_solutions.pdf

A short notice about my solution: in fact, one doesn't need the intersections $M$ and $N$. As long as one can prove that the power of the midpoint $U$ of $A_{1}P$ wrt to $(O)$ is equal to $UA_{1}^{2}= UP^{2}$, the problem is completely solved.


function
calculus
derivative
trigonometry
complex numbers
complex analysis
complex analysis unsolved

Hi,

I have two True/False Questions (in the attached file) that i did not manage to Solve

Help would be appreciated.

Thanks.

#1: If an analytic function agrees at two points on the disk, what can you say about its derivative? Look particularly at the line between them, and what you can get out of Rolle's theorem.
#2: Just parametrize the circle the usual way and evaluate the integral. This will require some knowledge of trigonometric identities to handle the square root; it's equivalent to the arclength of a cycloid.

1. Does Rolle's theorem applied also for Complex Functions? I have learned it for Real Functions, not yet for Complex so I,m afraid I can't use it to answer this 1.

2. I Guess my  trigonometry sucks since I've already try your proposal so... I could use more details please

Thanks

Rolle's theorem doesn't apply when there are two degrees of freedom- so project onto one. Does the real part of the derivative have a zero?

For the other question, the quantity inside the square root is a disguised perfect square. It's an identity in the double-angle/half-angle family.


linear algebra
matrix
induction
pigeonhole principle
modular arithmetic
vector
inequalities

assume n>=2 is natural numberand also suppose that $a_1,a_2,...,a_n$ aren't divisible by n and $a_1+a_2+a_3+...+a_n$ isnt either.prove that at least n sequence exist $(b_1,b_2,...,b_n)$ s,t$ b_i=0 $or$ 1$ such that $b_1.a_1+b_2.a_2+...+b_n.a_n$ is divisible by n

any one don't want to try this one(or struggle :D )?I want some other idea :(

oh! of course I don't want to write its official solution because I want to see the new one ,btw  it's lemma that is used in its official sol:
Lemma:assume that $A=(a_{ij})$ $k*n$ matric s.t:
1)$a_{ij}=0 or 1$
2)$k \leq n-2$
3)in each row exists at least one $0$
4)in each row exist at least two $1$
then if u use induction u can prove that we can rearrange the column of$A$ s.t $1$s don't  construct any block( i mean that one $0$ exists between them.)
but I waiting for new solutions :maybe:

This is actually, from my point of view (I am an expert in Zero-sum Theory), quite a trivial problem. Here is a solution (possibly the easiest).

For each permutation $\pi$ of $\{1,2,\ldots,n\}$, consider the following $n+1$ partial sums:
\[
S_0 = 0, S_1 = a_{\pi (1)}, S_2 = a_{\pi (1)} + a_{\pi (2)}, \ldots, S_n = a_{\pi (1)} + \cdots + a_{\pi (n)}.
\]
These $n+1$ sums take on at most $n$ distinct residues modulo $n$ and, by the pigeonhole principle, some two of them are congruent $\pmod{n}$. Subtracting them, we conclude the existence of $k,l$ (depending on the permutation $\pi$) such that
\[
a_{\pi (k)} + a_{\pi (k+1)} +  \cdots + a_{\pi (k+l-1)} \equiv 0 \pmod{n}.
\]
Now, for any choice of $\pi$, we must have $2 \leq l \leq n-1$. Indeed, $l=1$ would contradict the assumption that the $a_i$ are non-zero $\pmod{n}$, and $l=n$ would contradict the assumption that $a_1 + \cdots + a_n$ is non-zero.

In this way, we may assign to each $n$-permutation $\pi$ a block $B(\pi)$ (that is, a vector of the form $B (\pi) = (\pi (k), \ldots, \pi (k+l-1))$ ) of length in the set  $\{2,3,\ldots,n-1\}$, such that the sum of the $a_i$ with indices in this block
is $0 \pmod{n}$.

Let us say that a set $I \subseteq \{1,2,\ldots,n\}$ covers the $n$-permutation $\pi$ if the block $B (\pi)$ is obtained by arranging the elements of $S$ in some order (in other words, if the set of entries of $B (\pi)$ is precisely $S$.) We know that no one-element set covers a permutation, and the set $\{1,2,\ldots,n\}$ does not cover any permutation either. Under these two assumptions, the problem reduces to the following

Claim. If a collection $\mathcal{F} = \{S_1,\ldots,S_k\}$ of subsets of $\{1,\ldots,n\}$ covers all $n$-permutations (that is, each $\pi$ is covered by some element of $\mathcal{F}$), and if $|S_i| \notin \{1,n\}$ for each $i$, then $k \geq n-1$.

To prove the claim, it suffices to remark that each set $S \subset \{1,\ldots,n\}$ with $2 \leq |S| \leq n-1$ covers less than $\frac{n!}{n-2}$ permutations, so
\[
k \frac{n!}{n-2} > n!  \quad \Rightarrow \quad k \geq n-1,
\]
as desired.

I suppose that the official solution you mentioned is conceptually similar, for there hardly exists any solution to this problem which does not employ this pigeonhole-principle quantitive idea.

--Vesselin

Maybe for an expert it is a trivial problem. But I don't know why, I consider this extremeley difficult. Should the reason be the fact that I'm quite mindless in combinatorics? Also, I don't think there are many members of this forum who consider this a trivial problem.

[quote="Valiowk"][quote="vess"]To prove the claim, it suffices to remark that each set $S \subset \{1,\ldots,n\}$ with $2 \leq |S| \leq n-1$ covers less than $\frac{n!}{n-2}$ permutations[/quote]

I am very sorry but I don't see how you come to this conclusion (maybe it's obvious and I'm just missing the point) :(.[/quote]
I examined this inequality and it seems to be true, i.e. I proved it.

Would you please tell me the proof? Thanks!

Hello, Valiowk!
I have some trouble with proof. Actually, I disprove vess's statement.
Let S contains s elements. Desired permutations contains block of rearranged elements of S. There are (n-s+1) positions for this block. Thus we have (s! different rearrangements) * (n-s+1 positions for block) * ((n-s)! rearrangements of remaining elements) = s!*(n-s+1)! desired permutations. Finally, 2!*(n-2+1)! > n!/(n-2).
Maybe I am wrong again?

You're quite right: the number of permutations that are covered by an $s$-element set is precisely $(n-s+1)!s!$. My apologies for making the misteriously incorrect assumption that this quantity is $<\frac{n!}{n-2}$ for $2 \leq s \leq n-1$. All the same, we don't really need this latter inequality. In order to complete the proof of our assertion, all we need to show is that the following claim holds true.

Claim. If $\mathcal{F} = \{S_1,\ldots,S_k\}$ is a family of $k$ subsets of $\{1,\ldots,n\}$ with cardinalities in the set $\{2,\ldots,n-1\}$ is such that each $n$-permutation is covered by some set of $S \in \mathcal{F}$, then $k \geq n-1$.

Here is a proof by a simple induction on $n$, the base cases ($n=2$ and $n=3$) being trivial. Proceed to the inductive step. Fix $n \geq 4$ and assume the assertion for smaller values of $n$.

Assume to the contrary that $k \leq n-2$. Then, observe that there exists some $i \in \{1,\ldots,n\}$ for such that:

(i)  $\{1,\ldots,n\} \setminus \{i\} \notin \mathcal{F}$; and
(ii) $i$ belongs to at most one two-element set in $\mathcal{F}$.

Indeed, let $T$ be the set of all indices $i$ for which $\{1,\ldots,n\} \setminus \{i\} \in \mathcal{F}$. Let $t = |T|$. Because $n \geq 4$, each set of the form $\{1,\ldots,n\} \setminus \{i\}$ has at least $3$ elements. Thus, the number of two-elements sets in $\mathcal{F}$ is at most $n-t-2$. Now, construct a graph $G$ on $n-t$ vertices corresponding to the elements of $\{1,\ldots,n\} \setminus T$; join two vertices $i,j \in \{1,\ldots,n\} \setminus T$ by an edge iff $\{i,j\} \in \mathcal{F}$. Our graph $G$ has $n-t$ vertices and at most $n-t-2$ edges. Thus, some vertex $i$ has at most one neighbor, and this vertex satisfies (i) and (ii).

From now on, we assume that the index $i$ fulfils (i) and (ii). Define a subcollection $\mathcal{F}'$ of $\mathcal{F}$ consisting of $k-1$ elements as follows. If $i$ belongs to some two-element set $X \in \mathcal{F}$, set $\mathcal{F}' = \mathcal{F} \setminus \{S\}$; otherwise, remove an arbitrary set $X \in \mathcal{F}$ (Note: bear in mind this notation --- we will need $X$ a little later.) Now, define a collection $\mathcal{H}$ of subsets of $\{1,\ldots,n\} \setminus \{i\}$ as follows. Pick an arbitrary set $S \in \mathcal{F}'$. If $i \notin S$, we leave $S$ unchanged, i.e. we adjoin $S$ to $\mathcal{H}$. If $i \in S$, adjoin the set $S \setminus \{i\}$ to $\mathcal{H}$. By the definition of $\mathcal{F}'$ and the properties (i) and (ii) of the index $i$, the elements of $\mathcal{H}$ have cardinalities in the set $\{2,\ldots,n-2\}$.

We claim that, because the elements of $\mathcal{F}$ cover all $n$-permutations, the elements of $\mathcal{H}$ cover all $(n-1)$-permutations (of $\{1,\ldots,n\} \setminus \{i\}$.) Indeed, let $\pi'$ be any permutation of $\{1,\ldots,n\} \setminus \{i\}$. We may insert $i$ to any of the available $n$ positions to arrive at an $n$-permutation $\pi$. Because $|X| \notin \{1,n\}$, we may insert $i$ in such a way that the resulting $n$-permutation $\pi$ is *not covered* by $X$. Then, $\pi$ must be covered by an element $S \in \mathbb{F}'$, and the corresponding element $S' \in \mathbb{H}$ clearly covers the initial $(n-1)$-permutation $\pi$. Thus, the elements of $\mathcal{H}$ cover all $(n-1)$-permutations, which allows us to apply the induction hypothesis.

By the definition of $\mathcal{H}$, we have
\[
|\mathcal{H}| = k-1 \leq n-3,
\]
cotradictory to the inductive hypothesis. Thus, $k \geq n-1$. This completes the induction step and concludes the proof of the claim.

The proof is now complete (I hope $\ldots$ .)  :)

And this proves that this problem really is terribly difficult!

oh! I realize two things one :even experts make a mistake and two :official sol is easier :)

:D  :D  :D

And what is the official solution? Why does the lemma you mentioned suffice?

the main part of the sol is the lemma mentioned above ' now assume that $(e_1^i,e_2^i,...,e_n^i) (1\leq i \leq k)$ is sequence st:$\sum e_j^ia_n\equiv 0 (mod n)$ for $e_j^i \in \{0,1\}$ if $k\leq n-2$ according to the lemma above we have $A=(e_j^i)$and assume that $\sigma$ is permutation of column which satisfy the lemma these n+1 number :$0,a_{\sigma(1)},a_{\sigma(1)}+a_{\sigma(2)},...,a_{\sigma(1)}+...+a_{\sigma(n)}$ like vess's state we have :$a_{\sigma(i)}+...+a_{\sigma(j)}\equiv 0(mod n)$ we define $e_m^{k+1}=1 $iff $i\leq M\leq j$ otherwise equals 0,so we can extend the system because 1s (in k+1 th row) construct block but in the other rows don't.so we have at least n-1 nontrivial sol and if u add $e_i=0$ we are done


group theory
abstract algebra
LaTeX
superior algebra
superior algebra solved

if G is a finite group of order n then show that x^n=e for all x is an element of G.deduce that a^p-1=1(mod p)where p is prime and a is co-prime to p an element of Z and a an element of Z.

It is a wrong section for this problem. The moderators should move it to an apprpriate section.

Anyway, it is a base fact that order of group is divisible by order of any element, so $n$ is divisible by $k$, where $k$ is the order of $x$, thus $x^n=(x^k)^{n/k}=e^{n/k}=e$.
Your second question is to show that $a^{p-1}=1$ for $a\in \mathbb Z_p$.

Hi Madhuri -

For second,  consider the numbers:  {a, 2a, 3a, .... (p-1)a}

No two of them can be same modulo p ,    ( Because  that would imply  that a is divisble by p)
 (IOW, eg if  $ma \equiv na \bmod p $ will imply  $(n-m)(a)$ is divisible by p)

So these are the rearrangement of the same numbers as {1,2,3,....(p-1)}

Thus   $a \cdot 2a \cdot  3a \dots  (p-1) a =  1\cdot 2 \cdot 3 \dots (p-1) $
or  $a^{p-1} (1 \cdot 2 \cdot  3 \dots ) =  (1 \cdot 2 \cdot  3 \dots ) $
or  $a^{p-1} = 1$

For first part,  you can't do the same as the elements may not commute but as Myth said, {$1,a,a^2$  ...} will form a  subgroup  and it is easy to prove that order of a subgroup divides order of a group.
 (The proof  given by Myth may be a little terse, but clear  too)
Edited later:minor  tryout of latex editing (thx Blahblahblah)

May be you didn't understand: madhuri wanted proof, which uses the first fact, and I gave it.

Gyan, try using the commands $\cdot$(\cdot) instead of $\times$(\times) and $\ldots$(\ldots) instead of $...$(...) - it makes things look a bit cleaner.

Myth's fact is also known as the Theorem of Lagrange, if that clears anything up.


How would you go by thinking to attack this problem?

Find the number of ordered 4-tuples (a, b, c, d) of odd positive integers with sum 98.

Many ways to approach this.  One way is to find equivalent, but easier problems to grasp.

Let's get rid of the "odd" constraint.  Add 1 to each element of the tuple.  This will add 4 to the total, and make each element of the tuple even.

Let's divide each element of the tuple by 2.  This will make each element of the tuple a positive integer, and make the sum equal to 51.

The new (equivalent) problem is now:  "Find the number of ordered 4-tuples ([i]a[/i], [i]b[/i], [i]c[/i], [i]d[/i]) of positive integers with sum 51."

I can find an even simpler, but equivalent problem.  Let's find [i]p[/i], [i]q[/i], [i]r[/i], and [i]s[/i], such that these new values are the "running totals" of [i]a[/i], [i]b[/i], [i]c[/i], and [i]d[/i].  I.e., [i]p[/i]=[i]a[/i], [i]q[/i]=[i]a[/i]+[i]b[/i], [i]r[/i]=[i]a[/i]+[i]b[/i]+[i]c[/i], and [i]s[/i]=[i]a[/i]+[i]b[/i]+[i]c[/i]+[i]d[/i].  The conditions of the problem require 0 < [i]p[/i] < [i]q[/i] < [i]r[/i] < [i]s[/i].  And [i]s[/i] = 51.

I think we now have a much simpler combinatorics problem.

Imagine a deck of 51 cards, numbered 1 to 51.  Card #51 ([i]s[/i]) must be selected.  We also select any 3 of the remaining 50 cards.  Let the 3 chosen cards be [i]p[/i], [i]q[/i], [i]r[/i], such that 0 < [i]p[/i] < [i]q[/i] < [i]r[/i] < 51.

Now we work backwards.  From the chosen cards, we let [i]a[/i]=[i]p[/i], [i]b[/i]=[i]q[/i]-[i]p[/i], [i]c[/i]=[i]r[/i]-[i]q[/i], [i]d[/i]=51-[i]r[/i].

Clearly, [i]a[/i]+[i]b[/i]+[i]c[/i]+[i]d[/i]=51.  And each of [i]a[/i], [i]b[/i], [i]c[/i], and [i]d[/i] are a positive integer.  There were 50C3 = 19600 ways of choosing [i]p[/i], [i]q[/i], and [i]r[/i].  So there are 19600 ways of choosing [i]a[/i], [i]b[/i], [i]c[/i], and [i]d[/i].

should the answer be from 0 to 999?

-interesting_move

he's right, maybe the original question asked to have the answer divided by 100?

yes, the original problem does ask you to do that.

Different approach. a+b is an even number, and c+d is an even number. (2, 96), (4, 94), (6, 92)......(96,2). There is one possibilily for 2, and 48 possibilities for 96. There is 2 possibilities for 4, 47 posibilities for 94..... So the total equals  :Sigma:n(49-n) where 0<n<49.   :Sigma:n(49-n)=:Sigma:  49n-n:^2:  =  :Sigma:49n-:Sigma:  n:^2:  =49(49)(48)/2-(48)(49)(97)/6=48*49*50/6=19600


logarithms
calculus
integration
calculus computations

for what values of $ p$ does $ \sum \frac{\ln k}{k^p}$ converge?

I know that $ \frac{\ln k}{k^p}<\frac{1}{k^{p\minus{}1}}$, so if $ p>2$ then it will converge, it converges for $ p\equal{}2$ with the integral test, and it diverges for $ p\leq 0$. Is there some way to find all the $ p$ in one step?

fix $ \epsilon >0$ then we know $ \exists K$ s.t. $ k>K \to \ln k<k^\epsilon$

thus
$ \sum_{k\equal{}K^\infty} k^{\minus{}p}\ln k \le \sum_{k\equal{}K}^\infty k^{\epsilon\minus{}p}$

this is finite when $ \epsilon\minus{}p < \minus{}1$ or $ \epsilon\plus{}1<p$

thus, for any $ p>1$ your series converges..

$ \ln k < k^{\delta}$ for any $ \delta > 0$ and sufficiently large $ k.$

So now suppose that $ p > 1.$ Find $ s$ so that $ 1 < s < p.$ Write

$ \frac {\ln k}{k^p} \equal{} \frac {\ln k}{k^{p \minus{} s}}\cdot\frac1{k^s}.$

Note that $ \frac {\ln k}{k^{p \minus{} s}}$ is a bounded sequence. (In fact, it tends to zero.)

That means that we can make a one-sided comparison that say that

$ \sum\frac {\ln k}{k^p}\le C\sum\frac 1{k^s}$ for some $ C,$ and hence the series converges by comparison.

On the other hand, if $ p\le 1,$ then

$ \frac {\ln k}{k^p}\ge\frac {\ln k}{k}\ge \frac1k$ and the series diverges by one-sided comparison to the harmonic series.

So it converges for $ p > 1$ and diverges for $ p\le 1.$

The essential insight is that while $ \ln k$ goes to infinity, it does so slower than [i]any[/i] power of $ k$ and we can hence trade it off against a tiny sliver of a power - not just a first power, as you did.

The integral test works, as does the condensation test, but in my class I wouldn't push that - understanding size is the most important thing here.

Edit: simultaneous post with kenn4000. We both went for the same idea and the same argument.


ratio
Asymptote
trigonometry
integration
geometry
LaTeX
Pythagorean Theorem

This is a document I've been working on recently. So far, it's just derivations for pretty basic formulas. However, I'm not sure how "professional" my formatting is so any constructive criticism would be nice.

\section{Shortest Distance Between Two Points}
[asy]unitsize(150); path A; A = (0,0)--(0,1)--(1,1)--(1,0)--cycle; draw(A); draw((0.1,0.1)--(0.8,0.1),dotted); draw((0.8,0.1)--(0.8,0.9),dotted); draw((0.8,0.9)--(0.1,0.1)); draw((0.75,0.1)--(0.75,0.15)--(0.8,0.15)); label("\scriptsize { $(x_ { 1} ,y_ { 1} )$} ",(0.1,0.1),S); label("\scriptsize { $(x_ { 2} ,y_ { 1} )$} ",(0.8,0.1),S); label("\scriptsize { $(x_ { 2} ,y_ { 2} )$} ",(0.8,0.9),N); label("\scriptsize { $x_ { 2} -x_ { 1} $} ",(0.45,0.1),S); label("\scriptsize { $y_ { 2} -y_ { 1} $} ",(0.8,0.45),E);[/asy]

By applying the pythagorean theorem, we derive the shortest distance between two points formula:
$ \underline{D = \sqrt{(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}}}$

\section{Shortest Distance Between a Point and a Line}
[asy]unitsize(18); path A; A = (0,0)--(0,10)--(10,10)--(10,0)--cycle; draw(A); draw((0,2)--(9.142857143,10)); draw((5,6.375)--(8,2.937),dashed); draw((5,6.375)--(5,2.937)--(8,2.937),dotted); label("\scriptsize { $(x_ { 1} ,y_ { 1} )$} ",(8,2.937),S); label("\scriptsize { $y = ax+b$} ",(1.5,2),S); label("\scriptsize { $y = \frac { -x} { a} +c$} ",(7,7),S); label("\scriptsize { $S$} ",(5,6.375),N); label("\scriptsize { $D$} ",(6.625,4.50857),NE); label("\scriptsize { $K$} ",(5,4.5),W); label("\scriptsize { $J$} ",(6.5,2.937),S); draw((5.5,2.937)--(5.5,3.437)--(5,3.437)); draw((5.33,5.98857)--(5,5.69982)--(4.705,6.116875)); dot((5,6.375)); dot((8,2.937));[/asy]

The derivation of the ``shortest distance between a point and and a line formula'' is shown below:
\textbf{Step 1:} Solve the value of $ c$ by plugging in the point $ (x_{1},y_{1})$ into the equation
$ y = \frac{-x}{a}+c$.

$ y_{1}= \frac{-x_{1}}{a}+c$

$ c = y_{1}+\frac{x_{1}}{a}$

Therefore, the alternate formula for the line is:

$ y = \frac{-x}{a}+\frac{x_{1}}{a}+y_{1}$

$ y = y_{1}+\frac{x_{1}-x}{a}$

\textbf{Step 2:} Find the intersection between both straight lines.

We have $ y = ax+b$ and $ y = y_{1}+\frac{x_{1}-x}{a}$. Using the comparison method, we get:

$ ax+b = y_{1}+\frac{x_{1}-x}{a}$

$ ax+\frac{x}{a}= y_{1}-b+\frac{x_{1}}{a}$

$ \frac{a^{2}x+x}{a}= y_{1}-b+\frac{x_{1}}{a}$

$ \frac{x(a^{2}+1)}{a}= y_{1}-b+\frac{x_{1}}{a}$

$ x(a^{2}+1) = ay_{1}-ab+x_{1}$

$ x = \frac{ay_{1}-ab+x_{1}}{a^{2}+1}$

Now we find the y co-ordinate of the intersection by plugging in the value of $ x$ just attained into either straight line formula. For the sake of simplicity, we'll use
$ y = ax+b$.

$ y = a\left(\frac{ay_{1}-ab+x_{1}}{a^{2}+1}\right)+b$

$ y = \frac{a^{2}y_{1}-a^{2}b+ax_{1}}{a^{2}+1}+b$

Thus, our point of intersection $ S$ is:

$ \left(\frac{ay_{1}-ab+x_{1}}{a^{2}+1}, \; \frac{a^{2}y_{1}-a^{2}b+ax_{1}}{a^{2}+1}+b\right)$

\textbf{Step 3} Solve the value of J.

$ x_{1}-\left(\frac{ay_{1}-ab+x_{1}}{a^{2}+1}\right)$.

$ \frac{(a^{2}+1)(x_{1})}{a^{2}+1}-\left(\frac{ay_{1}-ab+x_{1}}{a^{2}+1}\right)$.

$ \frac{a^{2}x_{1}+x_{1}}{a^{2}+1}+\frac{-ay_{1}+ab-x_{1}}{a^{2}+1}$.

$ \frac{a^{2}x_{1}+x_{1}-ay_{1}+ab-x_{1}}{a^{2}+1}$.

Thus, the value of J is $ \frac{a^{2}x_{1}-ay_{1}+ab}{a^{2}+1}$.

\textbf{Step 4} Solve the value of K.

$ \frac{a^{2}y_{1}-a^{2}b+ax_{1}}{a^{2}+1}+b-(y_{1})$

$ \frac{a^{2}y_{1}-a^{2}b+ax_{1}}{a^{2}+1}+\frac{(a^{2}+1)(b)}{a^{2}+1}-\left(\frac{(a^{2}+1)(y_{1})}{a^{2}+1}\right)$

$ \frac{a^{2}y_{1}-a^{2}b+ax_{1}}{a^{2}+1}+\frac{a^{2}b+b}{a^{2}+1}+\frac{-a^{2}y_{1}-y_{1}}{a^{2}+1}$

$ \frac{a^{2}y_{1}-a^{2}b+ax_{1}+a^{2}b+b-a^{2}y_{1}-y_{1}}{a^{2}+1}$

Thus, the value of K is $ \frac{ax_{1}-y_{1}+b}{a^{2}+1}$.

\textbf{Step 5} Apply the pythagorean theorem such that $ D = \sqrt{J^{2}+K^{2}}$.

$ \sqrt{ \left(\frac{a^{2}x_{1}-ay_{1}+ab}{a^{2}+1}\right)^{2}+\left(\frac{ax_{1}-y_{1}+b}{a^{2}+1}\right)^{2}}$

$ \sqrt{ \left(\frac{(a)(ax_{1}-y_{1}+b)}{a^{2}+1}\right)^{2}+\left(\frac{(1)(ax_{1}-y_{1}+b)}{a^{2}+1}\right)^{2}}$

$ \sqrt{ a^{2}\left(\frac{ax_{1}-y_{1}+b}{a^{2}+1}\right)^{2}+1 \left(\frac{ax_{1}-y_{1}+b}{a^{2}+1}\right)^{2}}$

$ \sqrt{ (a^{2}+1)\left(\frac{ax_{1}-y_{1}+b}{a^{2}+1}\right)^{2}}$

$ \sqrt{ (a^{2}+1)\left(\frac{(ax_{1}-y_{1}+b)^{2}}{(a^{2}+1)^{2}}\right)}$

$ \sqrt{ \frac{(a^{2}+1)(ax_{1}-y_{1}+b)^{2}}{(a^{2}+1)^{2}}}$

$ \sqrt{ \frac{(ax_{1}-y_{1}+b)^{2}}{(a^{2}+1)}}$

Therefore, the shortest distance between a point and a line is:

$ \underline{ D = \frac{|ax_{1}-y_{1}+b|}{\sqrt{a^{2}+1}}}$

\section{Partition of a Line}
[asy]unitsize(18); path A; A = (0,0)--(0,10)--(10,10)--(10,0)--cycle; draw(A); draw((1,1)--(8,1),dotted); draw((8,1)--(8,9),dotted); draw((8,9)--(1,1)); draw((7.5,1)--(7.5,1.5)--(8,1.5)); draw((5,5.7)--(5,1),dashed); draw((5,5.6)--(8,5.6),dashed); label("\scriptsize { $(x_ { 1} ,y_ { 1} )$} ",(1,1),S); label("\scriptsize { $(x_ { 2} ,y_ { 1} )$} ",(8,1),S); label("\scriptsize { $(x_ { 2} ,y_ { 2} )$} ",(8,9),N); label("\scriptsize { $M$} ",(3,3.4),NW); label("\scriptsize { $N$} ",(6,6.8),NW); label("\scriptsize { $(x_ { p} ,y_ { p} )$} ",(5,5.6),NW); label("\scriptsize { $(x_ { p} ,y_ { 1} )$} ",(5,1),S); label("\scriptsize { $(x_ { 2} ,y_ { p} )$} ",(8,5.6),E); label("\scriptsize { $M$} ",(3,1),S); label("\scriptsize { $N$} ",(6.5,1),S); label("\scriptsize { $M$} ",(8,3.3),E); label("\scriptsize { $N$} ",(8,7.3),E); dot((5,5.6)); dot((5,1)); dot((8,5.6));[/asy]

Where $ M$ and $ N$ are the ratio of sides.
First, we solve the co-ordinates of $ x_{p}$. We know that the length of the triangle is $ x_{2}-x_{1}$. We then multiply this value by the ratio of sides $ \frac{M}{M+N}$ to find the length from $ x_{1}$ to $ x_{p}$. Finally, we simply add $ x_{1}$ to find the value of the co-ordinate $ x_{p}$. This gives us:

$ x_{p}= x_{1}+\frac{M(x_{2}-x_{1})}{M+N}$

$ x_{p}= x_{1}+\frac{Mx_{2}}{M+N}-\frac{Mx_{1}}{M+N}$

$ x_{p}= \frac{x_{1}(M+N)}{M+N}+\frac{Mx_{2}}{M+N}-\frac{Mx_{1}}{M+N}$

$ x_{p}= \frac{Mx_{1}}{M+N}+\frac{Nx_{1}}{M+N}+\frac{Mx_{2}}{M+N}-\frac{Mx_{1}}{M+N}$

$ x_{p}= \frac{Nx_{1}+Mx_{2}}{M+N}$

We can find the value of $ y_{p}$ in a similar fashion.

$ y_{p}= y_{1}+\frac{M(y_{2}-y_{1})}{M+N}$

$ y_{p}= y_{1}+\frac{My_{2}}{M+N}-\frac{My_{1}}{M+N}$

$ y_{p}= \frac{y_{1}(M+N)}{M+N}+\frac{My_{2}}{M+N}-\frac{My_{1}}{M+N}$

$ y_{p}= \frac{My_{1}}{M+N}+\frac{Ny_{1}}{M+N}+\frac{My_{2}}{M+N}-\frac{My_{1}}{M+N}$

$ y_{p}= \frac{Ny_{1}+My_{2}}{M+N}$

Thus, the partition of a line formula is:

$ (x_{p},\; y_{p}) = \underline{ \left(\frac{Nx_{1}+Mx_{2}}{M+N}, \; \frac{Ny_{1}+My_{2}}{M+N}\right)}$

It might be better to put everything into an attached pdf so that we can see the layout. Add the tex file as well for the code (you may need to zip the tex file as I don't think that's it's an allowed attachment).

One thing though - it's not usual to underline a formula. If you want to draw attention to it, either centre it (using \ [ ... \ ]) and you can also put it in a box, boxing the [i]whole[/i] formula, as in
\[ \boxed{(x_{p},\; y_{p}) = \left(\frac{Nx_{1}+Mx_{2}}{M+N},\frac{Ny_{1}+My_{2}}{M+N}\right)}\]

The tex files are below. If you want to see them rendered in a pdf format, all you have to do is "build" the document, run asymptote (I do this with an ALT+A shortcut), build the file again then view output. The trigonometry file takes about two minutes for asymptote to render, since there are nine pictures, so sorry about that.

That looks so much better in a document!
One of the things that I think you need to do is display the equations properly. The best way is to use the align environment, or rather align* as you don't want lots of equation numbers. You will need the amsmath package for this but it should be standard in all documents.
So I would replace:
[code]We have $y = ax+b$ and $y = \displaystyle y_{1} + \frac{x_{1}-x}{a}$. Using the comparison method, we get: \\[10pt]
$\displaystyle ax+b = y_{1} + \frac{x_{1}-x}{a}$ \\[5pt]
$\displaystyle ax+\frac{x}{a} = y_{1} -b + \frac{x_{1}}{a}$\\[5pt]
$\displaystyle \frac{a^{2}x+x}{a} = y_{1} -b + \frac{x_{1}}{a}$\\[5pt]
$\displaystyle \frac{x(a^{2}+1)}{a} = y_{1} -b + \frac{x_{1}}{a}$\\[5pt]
$\displaystyle x(a^{2}+1) = ay_{1} -ab + x_{1}$ \\[5pt]
$\displaystyle x = \frac{ay_{1} -ab + x_{1}}{a^{2}+1}$ \\[10pt][/code]by
[code]We have $y = ax+b$ and $y = \displaystyle y_{1} + \frac{x_{1}-x}{a}$. Using the comparison method, we get:
\begin{align*}
 ax+b &= y_{1} + \frac{x_{1}-x}{a}\\
 ax+\frac{x}{a} &= y_{1} -b + \frac{x_{1}}{a}\\
 \frac{a^{2}x+x}{a} &= y_{1} -b + \frac{x_{1}}{a}\\
 \frac{x(a^{2}+1)}{a} &= y_{1} -b + \frac{x_{1}}{a}\\
 x(a^{2}+1) &= ay_{1} -ab + x_{1} \\
 x &= \frac{ay_{1} -ab + x_{1}}{a^{2}+1}
\end{align*}[/code]
Note how \displaystyle is no longer necessary and that the equations are lined up at the = sign by using &. Of course you are going to say that the equations are too close together vertically. It's best to increase the spacing for the whole document rather than line by line.
This is easy to do with [code]\newdimen\jot \jot=10pt [/code]\jot sets the vertical disance between displayed equations and you can make it any size you like.

Some important equations could be boxed and you may even want to number them so that you can refer to them later. Have a look at this complete document for example, which is from page 3 of distanceformulas.tex to see what can be done.
[code]\documentclass[oneside,letterpaper,10pt]{book}
\usepackage{amsmath,amssymb}
% only want the occasional equation numbered. Use \eqnnumber where required
\newcommand{\eqnnumber}{\stepcounter{equation}\tag{\arabic{equation}}}
\newdimen\jot \jot=10pt %sets interline spacing of displayed equations
% clever way to box one equation in align environment. \boxed only works for one side of an equation
\newcommand*{\aboxed}[2]{%
  \rlap{\boxed{#1#2}}%
  \phantom{\hskip\fboxrule\hskip\fboxsep #1}&\phantom{#2}%
}
\begin{document}
We have $y = ax+b$ and $y = \displaystyle y_{1} + \frac{x_{1}-x}{a}$. Using the comparison method, we get:
\begin{align*}
 ax+b &= y_{1} + \frac{x_{1}-x}{a}\\
 ax+\frac{x}{a} &= y_{1} -b + \frac{x_{1}}{a}\\
 \frac{a^{2}x+x}{a} &= y_{1} -b + \frac{x_{1}}{a}\\
 \frac{x(a^{2}+1)}{a} &= y_{1} -b + \frac{x_{1}}{a}\\
 x(a^{2}+1) &= ay_{1} -ab + x_{1} \\
 \aboxed{x}{=\frac{ay_{1} -ab + x_{1}}{a^{2}+1}} \eqnnumber \label{whatever}
\end{align*}

We can refer to formula \eqref{whatever} here.

\end{document}[/code]Documents like this with labels need compiling twice to get the label correctly displayed.

Thanks a bunch for the help!  :D Unfortunately, I still have a couple of formatting issues to deal with.

1) You reccomend using the \align* environment. However, I checked an AMS guide and it seems that I could also have the option of using the equation and split environments together. What exactly is the difference between these two sets of commands?

2) How on earth does the multiline command work and what is it good for?

3) Let's say I have a hypothetical line of equations such as:

$ ax+b$
$ b^{2}-c_{4}+\sqrt{3}$
$ \int_{3}^{5}$

and I wanted to put a note that was flushed right which says something like "factor a" or "substitute this by that". If you're not sure what I mean, check the attachment. In that particular case,  I wanted "$ "if b^{2}-4ac < 0$" then no solution" message to be on the same line as one of the equations, but moved a fair bit to the right as if it were sort of a side note.

So far, the only idea I have on doing this is to either use a bunch of \qquad or \hline{space} commands (which means multiple notes wouldn't be aligned  :( ) or I could use the array environment, but I can't seem to control the space between characters.

4) When making a picture in asymptote dealing with geometry, I have come across the problem of angles. Usually angles in a shape are denoted with a small arc. However, I find it very difficult to manipulate a bezier curve approximation to get the arc I want (proper position, inclination, etc...). Is there an easier way to do this than harsh trial and error?

5) What's the most efficient way of making an asymptote picture? Usually what I do is that I create a separate document, save it as a .asy file then make my asy picture. From there, I just copy paste the code into my tex document and compile it when the document is finished. However, I find that even this seems unecessarily time consuming.

Sorry if I'm asking any silly questions :oops:

1. The split environment is for splitting an equation that's too long to fit on one line, whereas align is for lots of different equqations which need to be lined up, usually with the equals sign vertically under each other.

2. If you look at page 59 of [url=http://texcatalogue.sarovar.org/entries/voss-mathmode.html]Math Mode by Herbert Voß[/url] multline ([i]not[/i] multiline, there is an i missing) is again for long equations where you want the first line to be left justified but subsequent lines to be centred or right justified or on the left - there's a picture of what happens in Math Mode on page 60.

However, 90% of the time you want align; it's only when you have very long equations that you need something else but mostly you want to avoid such things as they are more complicated to read.

3. Use \hfill which fills out the line so forces the text to the right margin.
[code]$\displaystyle \underline{x = -B \pm \frac{\sqrt{B^{2} -4AC}}{2A}}$ \hfill if $\sqrt{B^{2} -4AC} < 0$ then no solution. [/code]

4 & 5. fedja is the asymptote expert on this forum so you may want to repost these two questions in a separate thread (with asymptote in the title) for fedja to answer.
Meanwhile, though for question 5, I see why you would want to work on the asy picture on its own to ensure that you get it perfect, but in your tex doeument you could then include the picture with \includegraphic Or, better still, you could use [code]\begin{figure}[h]
\includegraphics{trigonometry_1.pdf}
\caption{this is a picture}
\end{figure}[/code]which gives a caption, can be scaled, numbers your figures and can give a list of figures for the table of contents with \listoffigures (this requires compiling twice). Then you can change the picture but not have to change the tex document.

The hfill command doesn't seem to be working (see the attachment experiment 3). Maybe I'm using it wrong? Keep in mind that I'm trying to get \hfill to work in an align* environment.

Also, the align command doesn't seem to allow pagebreaks, meaning I get a lot of empty space on certain pages. Should I split each align environment into a maximum of 5 lines or is there another way around this?

Finally, I finished editing the distance formulas document. I didn't caption the pictures because I didn't know what to call them. I used include graphics so if the pictures in the document don't show up, just erase that part of the code.

Never mind about the hfill problem, I found the solution is to simply add another & symbol and the text after the symbol will be justified to the right. The pagebreak issue with the align* environment is still a problem though  :(

[quote="Prime factorization"]The pagebreak issue with the align* environment is still a problem though  :([/quote]Fortunately that's easy to solve. Just add
\allowdisplaybreaks
after \begin{document}.

You may have noticed some warnings from LaTeX that 'h' has been changed to 'ht'. You can stop the warnings by doing that yourself and replacing
\begin{figure}[h]
by
\begin{figure}[ht]
which means that if there's not enough room for the figure then it can appear at the top of the next page (t=top). Yes, I know I missed the t out in my earlier suggestion  :( .


topology
function
invariant
abstract algebra
vector
Functional Analysis
real analysis

assume that $X$ is compact topological space and $T,S: X\rightarrow X$ are continuous such that $TS=ST$ .then thers exists $T and S$-ergodic measure on X.

I’ll (try to :)) prove a generalization, but first, some terminology:

Let $X$ be a compact Hausdorff topological space, and let $\mathcal M(X)$ be the set of regular Borel measures on $X$, regarded as the dual space of $\mathcal C(X)$, the space of real-valued continuous functions on $X$. From now on, all measures under consideration will be members of $\mathcal M(X)$. Finally, let $\mathcal K$ be the subset of $\mathcal M(X)$ consisting of non-negative measures with total mass $1$. Clearly, $\mathcal K$ is convex. The closed unit ball of $\mathcal M(X)$ is weak-$*$ compact (the Banach-Alaoglu Theorem) so $\mathcal K$, being a weak-$*$ closed subset of this unit ball, must also be weak-$*$ compact.

Given a collection $\mathcal T=\{T_\alpha\}$ of continuous maps $T_\alpha: X\to X$, we’ll say that $\mu\in\mathcal M(X)$ is [i]$\mathcal T$-invariant[/i] if $\mu(T_\alpha^{-1}E)=\mu(E)$ for all $T_\alpha$ and all Borel sets $E\subseteq X$. The set consisting of such measures will be denoted by $\mbox{inv}(\mathcal T)$. We’ll say that the $\mathcal T$-invariant measure $\mu$ is [i]$\mathcal T$-ergodic[/i] if $\mu(E)$ is either zero or equal to $\mu(X)$ (i.e. maximal) for all Borel sets $E$ with the property $\mu(T_\alpha^{-1}E\Delta E)=0,\ \forall T_\alpha$ (here, $\Delta$ denotes the symmetric difference). We’ll denote the set of $\mathcal T$-ergodic measures by $\mbox{erg}(\mathcal T)$.

Basically, sam-n’s problem asks for proof that if $\mathcal T$ is a commutative semigroup generated by two maps, then there is a $\mathcal T$-ergodic measure in $\mathcal K$. The generalization is this:

If $\mathcal T$ is an abelian semigroup of maps on $X$, there is a $\mathcal T$-ergodic measure in $\mathcal K$.

For every map $T_\alpha\in\mathcal T$, consider the transformation $\Lambda_\alpha$ on $\mathcal M(X)$ that it induces, defined by $\left(\Lambda_\alpha\mu\right)(E)=\mu(T_\alpha^{-1}E)$ for all $\mu\in\mathcal M(X)$ and all Borel sets $E$. $\Lambda_\alpha$ are continuous linear transformations on $\mathcal M(X)$ (continuous both in the norm and in the weak-$*$ topology on $\mathcal M(x)$). Moreover, they all fix $\mathcal K$. Let $\mathcal K_\alpha$ be the set of points in $\mathcal K_\alpha$ which are fixed by $\Lambda_\alpha$. Consider a finite system $\mathcal K_{1},\ldots,\mathcal K_{n}$ of sets $\mathcal K_\alpha$. Tychonov’s Fixed Point Theorem states that a continuous map from a convex compact subset of a locally convex topological vector space to itself has a fixed point (actually, we only need the weaker evrsion where the map is assumed to be linear). This means that $\mathcal K_{1}$ is non-empty. Moreover, it’s compact (in the weak-$*$ topology) and convex, and because $\mathcal T$ is abelian, it’s fixed by all $\Lambda_\alpha$. Now apply the fixed point theorem cited above to conclude that $\mathcal K_{1}\cap\mathcal K_{2}$ is a non-empty convex compact set fixed by all $\Lambda_\alpha$, and so on. Eventually, we’ll find $\bigcap_{i=1}^{n}\mathcal K_{i}\ne\emptyset$. This means that $\{\mathcal K_\alpha\}$ is a collection of compact sets having the finite intersection property (every finite subcollection has non-empty intersection), so $\bigcap_\alpha\mathcal K_\alpha\ne\emptyset$. Any element in this intersection is a $\mathcal T$-invariant measure in $\mathcal K$. This shows that $\mbox{inv}(\mathcal T)\cap\mathcal K\ne\emptyset$.

We’re interested in $\mathcal T$-ergodic measures in $\mathcal K$. We’ve just seen that $\mbox{inv}(\mathcal T)\cap\mathcal K$ is non-empty. Clearly, it is convex and compact, so by the Krein-Milman theorem, it has extreme points. It suffices to prove that every extreme point is a $\mathcal T$-ergodic measure.

Let $\mu$ be such an extreme point, and assume it is not $\mathcal T$-ergodic. This means that we can find a Borel set $E$ such that $\mu(T_\alpha^{-1}E\Delta E)=0,\ \forall T_\alpha\ (*)$, but both $\lambda=\mu(E)$ and $1-\lambda=\mu(X\setminus E)$ are positive. Consider the measures $\mu_{1}(F)=\frac 1\lambda\mu(F\cap E)$ and $\mu_{2}(F)=\frac 1{1-\lambda}\mu(F\setminus E)$ (for any Borel set $F$). These are both members of $\mathcal K$. Moreover, using $(*)$, it’s easy to check that they are both $\mathcal T$-invariant. However, they are both different from $\mu$, and $\mu=\lambda\mu_{1}+(1-\lambda)\mu_{2}$, contradicting the fact that $\mu$ is an extreme point of $\mbox{inv}(\mathcal T)\cap\mathcal K$. Hence $\mu\in\mbox{erg}(\mathcal T)\cap\mathcal K$, and this finishes the proof.

a stupid question: why the set $E$ (this one used for the ergodicity) does not depend on $\alpha$ ?

Sorry for the delay, alekk. I answered your question, but then I deleted my message because I wanted to post an extension of the problem, and I don't like multiple posts :). First, your question:

I think you misunderstood the definition of $\mathcal T$-ergodicity that I used. It's not the same as saying that the measure is ergodic with respect to every member of $\mathcal T$. Read it again, and you'll see that its negation boils down precisely to what I wrote: there is a set $E$ with the property that $\mu(T^{-1}E\Delta E)=0,\ \forall T\in\mathcal T$, and for which $\mu(E)$ is neither zero nor maximal.

As for the extension I mentioned, I think it suffices to assume that the semigroup $\mathcal T$ is [i]amenable[/i], i.e. there is a functional $\nu$ of the Banach space of real-valued bounded functions on $\mathcal T$ with the supremum norm such that:

(i) $\nu$ is a [i]mean[/i], i.e. $\|\nu\|=\nu({\bf 1})=1$ (where ${\bf 1}$ is the constant function);
(ii) $\nu$ is [i]left invariant[/i]: $\nu(f_{T})=\nu(f)$ for all bounded $f$ and all $T\in\mathcal T$, where $f_{T}(S)=f(TS),\ \forall S\in\mathcal T$.

It can be shown that a commutative semigroup is amenable, so this is indeed a generalization.


induction
pigeonhole principle
combinatorics proposed
combinatorics

I chose to revive this old problem of mine, due to the interesting links between other topics on these fora.

[color=blue][b]Theorem 1.[/b] Let $ X$ be a set. Let $ n$ and $ m\geq 1$ be two nonnegative integers such that $ \left\vert X\right\vert\geq m\left( n \minus{} 1\right) \plus{} 1$. Let $ B_{1}, B_{2}, ..., B_{n}$ be $ n$ subsets of $ X$ such that $ \left\vert B_{i}\right\vert \leq m$ for every $ i\in\left\{1,2,...,n\right\}$. Then, there exists a subset $ Y$ of $ X$ such that $ \left\vert Y\right\vert \equal{} n$ and $ \left\vert Y\cap B_{i}\right\vert \leq1$ for every $ i\in\left\{ 1,2,...,n\right\}$.[/color]

This is the statement of Theorem 1 in [color=green]darij grinberg[/color]'s [url]http://www.cip.ifi.lmu.de/~grinberg/subsetcond.pdf[/url] as an answer to a generalization hinted at by[color=green] tanlsth[/color] at [url]http://www.mathlinks.ro/viewtopic.php?t=118091[/url]

The problem is mine, in all generality, as witnessed by the apparition in the Resources section at
[url]http://www.mathlinks.ro/resources.php?c=142&cid=25&year=2004[/url] with a solution by induction by [color=green]grobber[/color] at [url]http://www.mathlinks.ro/viewtopic.php?p=440858#440858[/url]

(That year $ 2004$, the Romanian Mathematical Olympiad for grade IX was sat, among others, by [color=green]Adi Zahariuc[/color], [color=green]Iurie Boreico[/color] and [color=green]Sasha Zamorzayev[/color]. As far as I remember, no-one gave a full solution during the contest, although nowadays [color=green]Iurie[/color] swears he did solve it! [color=green]Andrei Negut[/color] was orally given the problem, and he came with an induction proof that was somehow needing ...).

As the original problem stated, and [color=green]Darij[/color] noticed, if $ \left\vert X\right\vert\leq m\left( n \minus{} 1\right)$ the result stands no more, since one can take the first $ n \minus{} 1$ blocks $ B_i$ covering $ X$, and an arbitrary $ B_n$; then by pigeonhole principle, any subset $ Y$ of $ X$ with $ \left\vert Y\right\vert \equal{} n$ elements will forcibly have at least $ 2$ of its elements in one of the first $ n \minus{} 1$ blocks.

Let me now present to you my [color=red]original solution[/color] to the hard part, somehow more insightful (I think) than an inductive solution, which relies on building the subset $ Y$ in a way (inductively) that escapes the full grasp of understanding its structure.

A simple observation is that one may assume $ \left\vert B_{i}\right\vert \equal{} m$ for every $ i\in\left\{1,2,...,n\right\}$, since this is only to one's disadvantage (one may arbitrarily enlarge the blocks to full $ m$ cardinality and prove the existence of a set $ Y$; then its intersections with the original blocks can only be of equal or lesser cardinality).
Another simple observation is that, for any fixed $ j$, one has $ \displaystyle \left\vert \bigcup_{i \neq j} B_{i}\right\vert \leq m(n \minus{} 1) < \left\vert X\right\vert$, hence there must exist some suitable $ \displaystyle x_j \in X \setminus \bigcup_{i \neq j} B_{i}$. Now, the set $ Y \equal{} \{ x_j \; ; \; j \in\left\{1,2,...,n\right\} \}$ clearly intersects the blocks in at most one element each, but of course there is no guarantee that $ \left\vert Y\right\vert \equal{} n$, since some of the elements $ x_j$ may coincide!

We will remedy to this with a neat trick. Start with $ j \equal{} 1$ and find a suitable $ x_j$. If $ x_j \in B_j$ proceed with the next value for $ j$; if not, replace (like for a soccer team) an arbitrary element $ y_j \in B_j$ with $ x_j$, i.e. have $ B_j \to (B_j \setminus \{y_j \}) \cup \{ x_j \}$ (in order to keep notations simple, we will call this new block by the same name $ B_j$), and then proceed with the next value for $ j$. This will ensure that any newly selected $ x_j$ does not match any of the ones selected before, hence $ \left\vert Y\right\vert \equal{} n$ and, moreover, $ \left\vert Y\cap B_{j}\right\vert \equal{} 1$ for every $ j\in\left\{ 1,2,...,n\right\}$, with the blocks as they are at the end of the process. Now replace back the elements $ x_j$ with $ y_j$ (where the case), getting the initial blocks. The intersection of $ Y$ with any block $ B_j$ may only keep (if $ y_j \in Y$) or decrease (if $ y_j \not \in Y$) its cardinality, whence the suitability of this set $ Y$.

Thanks for the information!

By the way, I think the following observation:

[quote="mavropnevma"]A simple observation is that one may assume $ \left\vert B_{i}\right\vert \equal{} m$ for every $ i\in\left\{1,2,...,n\right\}$, since this is only to one's disadvantage (one may arbitrarily enlarge the blocks to full $ m$ cardinality and prove the existence of a set $ Y$; then its intersections with the original blocks can only be of equal or lesser cardinality).[/quote]

is not needed in your proof.

Anyway, it seems that all three of us (grobber, you and me, though I had to fix a small mistake in grobber's proof) have found more or less the same solution with different levels of clarity. My solution was a result of some patchwork, what explains the ugly and intricate way it is written (I used to believe I had a short proof, then I noticed some flaws, started fixing them, and in the end I had something that wasn't really transparent to me, so I had to write it down with all details to convince myself of its truth). Grobber and me wrote down the induction explicitely; you encoded it into a recursive process. Somehow it's disappointing that there don't seem to be any alternative approaches to this problem...

I don't remember exactly how long this problem took me, but I fear it would have taken me more time than I'd have left after doing three other problems on the MO. Nice problem anyway!

  Darij

I think you could complete the approach mavropnevma mentioned above also with HALL's Theorem:
Set $ C_i \equal{} X \backslash \bigcup_{j \neq i} B_j$ and let $ I$ be an arbitrary non-empty subset of $ \{1, \ldots, n\}$. Then we have $ \left|\bigcup_{i \in I}C_i\right| \equal{} \left|X \backslash \bigcup_{j \notin I} B_j\right| \geq m(n \minus{} 1) \plus{} 1 \minus{} (n \minus{} |I|)m \equal{} 1 \plus{} m(|I| \minus{} 1) \geq |I|$. The Theorem of HALL implies the existence of pairwise different $ x_i \in C_i$. The set $ Y \equal{} \{x_i \ | \ i \in \{1, \ldots, n\}\}$ is such that $ |Y| \equal{} n$ and $ |Y \cap B_i| \leq 1$ for all $ i \in \{1, \ldots, n\}$ .

All nice and fine, but
\[ \bigcup_{i \in I}C_i \equal{} X \setminus \left ( \left ( \bigcup_{j \notin I} B_j \right ) \bigcup \left ( \bigcap_{i \in I} \left ( \bigcup_{k \in I \setminus \{i\}} B_k \right ) \right ) \right )\]
so the cardinalities are all screwed up.


I'm using the bib style amsalpha, although this should apply to any .sty which uses letters to cite bib items.

One item is a book by S. Mac Lane. This gives rise to [Lan75] when I cite it. However I've been told that I should cite it as [Mac75]. How can I override this?

Try the [url=http://tug.ctan.org/cgi-bin/ctanPackageInformation.py?id=natbib]natbib package[/url] which has a citation aliasing command.


i solved imo 2007 1(a) but cant do the part (b)
can anyone help me :maybe:

Try looking at here: http://www.mathlinks.ro/Forum/viewtopic.php?t=159835

ki khobor ishfaq! shesh porjonto ekhane ashte perecho? :P

ses porjonto aslam.............. :pilot:  :coolspeak:  :rotfl:
feeling .....gooooood


Suppose thousands years have passed. Man had invented a ultimate physical theory capable of explain everything, predict all possible.
They've made a powerful computer capable to simulate everything use this theory with as many digits we need.

They have a theory of how the universe started. suppose it is really the big bang. So they start the program with it and press run. They accelerate it billions of years after.
They search for live in every planet it has simulated. They found a planet similar to Earth.
For those poor people on this simulation, they don't know they are being simulated. The programers who run the program were asked to not interfere.

For the people in this planet the programer would've be God. It create the universe they know.

So. A Powerful physical theory wound contradict our belief in This Kind Of God. We could simulate ourselves without need to tell what We are. or anything at all. we just started with a massive point-mass.

The people in the planet would've never leave the simulation (they are just data).

The point is: With this Non-interference kind of god, would've be possible for them to know the existence of the programer? (they could also make a simulation themselves and ad infinitum). They can also try a means of communication with the programer.

(They've basically constructed a IA machine with just physics)

Well this is not a question and not at all a debate. Just a idea I had (I assume thousand of others since the invention of computer had physics had already thought that)

Man has. It's called 42. There are five books depicting clearly the worthlessness of striving for such theories.

ERr.... Is not actually a theory... I think my english is really bad for you to not understand.

And I think mister Towel, that Adams douglas never said anything about this, for I remember he only talks about restaurants, towels, and fishes.

To cite books without citing books is realy a big thing. And I really like to read about those fancy things. String theory were a fancy thing couple of decades ago, so don't go critizing things. just don't post. This were never intented to be a post were people went sayings things, just read, take a tea and go back to wikipedia

Beyond the surface, Adams' books are very much about the futility of asking questions like these. If you're religious, the best answer to the "purpose in life" question is "God's plan." If you're not, it's "I don't know." Hitchhiker's Guide et al. pretty clearly argue this. Hitchhiker's Guide is a pretty thorough treatment of exactly this quandary.


advanced fields
advanced fields theorems

In a Hilbert space, the norm is defined by $ \|x\|\equal{}\sqrt{(x,x)}$. Is this equivalent to $ \sup_{\|y\|\equal{}1}|(x,y)|$?

Yes. Use Cauchy-Schwarz in one direction and the choice $ y\equal{}x/\|x\|$ in the other.


Hey guys I was wondering if we could discuss here about dimensions in general and more specifically about the existence of dimensions below the point, meaning negative ones......Have you heard anything about them? Can you please share any ideas you might have?

PS. I know that this isn't much of an olympiad issue but I believe it is worth discussing...If the moderators do not like this being here they can transfer it in any other place they would like....

The negative (fractal) dimension is introduced by Benoit Mandelbrot, in which, when it is positive gives the known definition, and when it is negative measures the degree of "emptiness" of empty sets.

I think the diamension of fractal is rational but possitive, there are not negative diamension ?


geometry induction MIT college algorithm

I am very interested in learning Computer Science and Informatics but I have absolutely no idea where to start (plus I am not very good with computers). So can someone advise me on how to begin?

Thanks

I would learn a programming language and play around with it.

You could start with C/C++, Java, or anything that interests you really.

You're going to need a compiler as well.

http://java.sun.com/j2se/1.4.2/docs/tooldocs/windows/javac.html
http://www.bloodshed.net/devcpp.html

If you're only interested in [i]theoretical[/i] computer science (e.g. computability theory, P vs. NP) it doesn't actually matter if you can program or not.  The book I learned out of was Sipser's [url=http://www-math.mit.edu/~sipser/book.html]Introduction to the Theory of Computation[/url].

If you're going to study the theoretical computation, you'll at least to know some of the jargon used in those topics, so learning a language would be helpful.

The book I linked to literally requires no knowledge of programming.  I know this because I had literally no knowledge of programming when I learned theoretical computer science from it.  Any good book in the theory of computation should be readable by those who don't know how to program.

I am interested in both (theoretical and actually programming things). Which should I start off with?

If you find a miracle book like JBL's that requires no prior knowledge of computer workings, then do that first. Otherwise, I doubt you will be able to understand most theoretical books without learning with a nice and simple programming tutorial first.

Okay, let me provide more than just a two-sentence comment this time, in order to elaborate more fully.  I don't know if Temperal has taken any classes in Theory of Computing, but it really resembles mathematics far more closely than it resembles programming.  (In fact, in my experience, math majors in intro theory of computation tend to do better than computer science majors.)  There's really no reason to put off reading about it until after you've learned a language.  If I recall correctly (I unfortunately don't have it here with me), Sipser does include exercizes of the form, "In your favorite programming language, do the following task," but these are essentially peripheral.  In particular, the major ideas of theoretical computer science are models of computation, computability, decidability, reduction theory, and various categories of complexity theory -- the relationship between these (especially the first three) and the actual practice of writing a program to accomplish a task is tenuous at best.  (Even important subjects in time-complexity theory have somewhat questionable applicability -- see, for example, the discussion between Kent Merryfield and myself [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?t=173597]here[/url].)  Understanding why some particular subjects are important (e.g., log-space computing) might be aided by having computing experience, but proving things about it is just like proving things in any other area of mathematics.  Now, while theoretical CS doesn't demand much in the way of programming sophistication, it does demand mathematical sophistication -- you should be fully comfortable with the notion of proofs and with mathematical rigor before you try to jump in.  (Sipser does devote a chunk of his introduction to the basics of mathematics, proofs, induction, etc.)  This may not pose a problem for you -- if you're comfortable reading and solving problems in the Pre-Olympiad forum here, I don't think there should be any issues.

Finally, I keep mentioning Sipser, but that's only because it's the book I happened to use when I took the class.  I don't really know if it's the best book out there.  (They use it at MIT, but that's doubtless due in part to the fact that Sipser is regularly the person [i]teaching[/i] the class.)  You might put an inquiry out either here or in the Mathematical Books & Journals forum to see if others have other suggestions.  It's also quite expensive new, but there are people selling copies for 5 US dollars on Amazon.

I've actually only taken a few classes dubbed as introductory over the summer, and it seemed to me like at least a bit of prior knowledge was needed, with things like binary trees, memory, and stacks referred to offhandedly by the instructors. Some of the exercises the instructors gave us required us to lay out an algorithm for extracting data from the memory of a computer in a certain fashion.

I've never heard of Sipzer, though.

What, in your opinion, is the 'easiest' language to learn. Are there books teaching languages? Because I am not very good at reading stuff on the web.

The 'easiest' is the (now obsolete) BASIC, but I wouldn't recommend it; it's easy to fall into sloppy coding habits with it.

MS Visual Basic is pretty easy to learn, albeit much more complicated than BASIC. It's also very object-oriented, making it easy to learn languages such as Java and C++ later.

There are hundreds, thousands of books teaching languages. Starting off with Sams' line is a good idea, but Deitel and Deitel is a good publisher for more intermediate/advanced topics.

Nah, I would just go with C. Not only will you learn a useful and widely spread programming laguage but you will also get a basic understanding of how computer works because of some similar concepts used in both C and actual computer hardware. There are tons of books written about C and I'm sure that most of them will do just fine. Only make sure that the book you pick is not too much Microsoft Visual C++ or Borland C++ Builder oriented because that way you may end up only knowing some very specific and proprietary parts of the C language. (I'm exaggerating a little bit but that's pretty much what I think.) Oh yes, and I too recommend Dev-Cpp.

By the way, I learned C++ from an online tutorial and I must say that it was pretty easy. I have never read any book about C/C++ so I can't recommend any one. One final note, you may at first be confused about what's the difference between C and C++. Don't worry about it too much, they are mostly the same only C++ add some new features that are not legal in C. You can think of C++ as an extension to C. Most of the materials you'll find will probably deal with C++ beacuse strict C is nowadays not very used at all. On PCs that is.

EDIT: You may have heard about Java, C#, Visual Basic .NET and other modern programming laguages. Learning one of those would be a modern approach to programming. They are great languages but I wouldn't really recommend starting with those. You can always pick one of them after you've learned C and the concepts will seem much less confusing then. (In my opinion.)

Ok, So i first started out programming last year and i started with java. Java is a very quick language to learn but is quite sloppy in some cases you might want that to start out with but i would recommend C++ more than any other lang to start out with. Not only is fast its quite easy to get started with but there are some bad things. Unlike java, in C++ you can't the started with GUI(Graphical User Interface) programming immediately but when you know enough you can do graphics a lot easier in C++. But, if you are doing only really small GUI projects go with java any thing bigger than 40 lines of code you go with C++. And, most games and other software is written in C++ like Quake 4, Doom 3, Gears of War etc is all written in C++ or C. In java, it is really hard to get any sound in your program, but in C++ its about 1/8 as hard. So, its your choice BanishedTraitor and how old are you?!


I found #2 by individually finding the number of possibilities for each number of loops (using combinatorics), then combining them together, resulting in a very messy fraction. Did you find the more elegant way of solving #2?

EDIT: Ah, now I found out how to view previous math jams (thought it's still a reasonable discussion question).

See the Math Jam for a beautiful solution. :)

Yeah, I did it the way that it was done in the Math Jam  :D

My way took a little bit of discovering on scratch paper, but the solution that I wrote down was fairly elegant, although not the best one.

mine was messy... veerrry messy, i found the probability for each loop to form... which made some really messy fractions... stuff over $10395$...  :(  took me forever but i got the right answer...

Well, yeah, that's what I got, too, but there's also a quite nice method for that way, which is what I meant when I said mine was elegant, but not as elegant as the $\displaystyle\sum_{n=1}^{6}\frac{1}{2n-1}$ solution.

[quote="pkerichang"]how do you guys find the probability of each number of loops???

I use recursion for that, but what si the combinatorics way????

(recursion is less hard to find the probabilities, but it is still messy (I have to use a calculator))[/quote]
I've attached my solutions: I took the "probability of each number of loops resulting" approach, and used sums to calculate each one.  Take a look.

[quote="pkerichang"]how do you guys find the probability of each number of loops???

I use recursion for that, but what si the combinatorics way????

(recursion is less hard to find the probabilities, but it is still messy (I have to use a calculator))[/quote]

First I found a formula for the number of possibilities given a particular loop of n ropes, $(n-1)! \times 2^{n-1}$, which easily applied to one loop.
Then for more loops, I found the possibilities given the numbers of ropes in each loop (ie for two loops, five and one, four and two, three and three).
First I found the number of distributions of ropes among the loops. So for two and four, it was just the combination of two out of six (or four out of six).
Then I found the possibilities per given distribution, which can easily be found by applying the above formula to the number of ropes in each loop, and multiplying those results together.
Then I multiplied the number of distributions times the number of possibilities per distribution (this is all given a particular number of ropes in each loop).
Finally, I found the total possibilities for each number of loops, and averaged 1, 2, 3, 4, 5, and 6 together, weighting them based on the number of possibilities for that number of loops, finding the expected value.


In his pocket Sam had \$4 composed solely of quarters and nickels. He had a total of 20 coins. How many nickels did he have?

Let $ q$ be the number of quarters he had and $ n$ be the number of nickels.

$ 0.25q \plus{} 0.05n \equal{} 4$

$ q \plus{} n \equal{} 20$

First, let's rewrite the first equation so it's a little bit easier to deal with.

$ 25q \plus{} 5n \equal{} 400$

What we have is called a system of equations. For a more in-depth explanation, look at the article I wrote in the AoPSWiki, or go to my blog(link's in my signature), in the third entry.

Let's use substitution to solve this.

$ q \equal{} 20 \minus{} n$

$ 25(20 \minus{} n) \plus{} 5n \equal{} 400$

$ 500 \minus{} 25n \plus{} 5n \equal{} 400$

$ 500 \minus{} 20n \equal{} 400$

$ \minus{}20n \equal{} \minus{}100$

$ n \equal{} 5$

Thus, he has $ \boxed{5}$ nickels.


[quote="FoRgE_BlaDe2"][b]There are English, Chinese and Japanese books on a shelf. The number of Japanese books to that of the English books is in the ratio 2:7. The ratio of the number of Chinese books to that of Japanese books is 5:4. Find the ratio of the number of English books to that of Chinese books. If there are 13 chinese books, how many books are here in total.

P.S Respond in detail so I can see how you figured it out[/b][/quote]

[hide]
So the ratio for Chinese:Japanese is 5:4. You have 13 chinese books so, 13:x=5:4.
13*4=x*5
52=x*5
52/5=x
There are 52/5 Japanese books? Is this problem wierd or is it just... wierd?

Now, then we have English books.

The number of Japanese books to that of the English books is in the ratio 2:7.
52/5: x=2:7
52/5*7=x*2
364/5=x*2
364/10=x

364/10 English books? Ok this is a wierd problem.

So total we have 52/5+13+364/10
52/5+13+364/10
=104/10+364/10+13
=468/10+13
=234/5+13
=299/5
I dunno if this is right though...
[/hide]

[quote="FoRgE_BlaDe2"]That is correct very weird at firs the problem is.[/quote]

I don't see how you can have parts of books though.  :P

[quote="FoRgE_BlaDe2"]Cut em up lol?  :lol:[/quote]

Where'd you get this question? In a book or did you make it?

I think he made it up. Either that or the book was made by me :P .

this question is pretty weird and cool at the same time

[hide]5:14
Set the Japanese books to the same number.
36.4[/hide]


[quote="ch1n353ch3s54a1l"]Source: AMC 10B 2005

A subset B of the set of integers from $1$ to $100$, inclusive, has the property that no two elements of B sum to $125.$ What is the maximum possible number of elements in B?

$\text{(A) }50$     $\text{(B) }51$     $\text{(C) }62$     $\text{(D) }65$     $\text{(E) }68$[/quote]

[hide="Click to reveal hidden content"]In the first 62 integers, no two of them add up to greater than 125. So $\boxed {C}$ (This problem really isn't explainable aside from simple logic  :roll: )[/hide]

[hide="solution"]
[url=http://www.mathlinks.ro/Forum/viewtopic.php?p=433227&highlight=#]Look here[/url]  :lol:
[/hide]

[quote="ch1n353ch3s54a1l"]Source: AMC 10B 2005

A subset B of the set of integers from $1$ to $100$, inclusive, has the property that no two elements of B sum to $125.$ What is the maximum possible number of elements in B?

$\text{(A) }50$     $\text{(B) }51$     $\text{(C) }62$     $\text{(D) }65$     $\text{(E) }68$[/quote]

[hide] If we choose the first $62$ numbers, none of those sum $125$. Then, we can`t choose any other numbers, because there is does sum $125$. Then, the answer is $62 \boxed {C}$[/hide]

[hide="some remarks"]
To [b]Zenith Xan[/b] and [b]José[/b]:
although you  got correct answer, you only proved that set $\{1,2,\ldots,62\}$ couldn't be extended, but failed to show that there are no other subsets of more than $62$ elements satisfying given conditions.

Let $B$ denote some $63$-element subset.
There are $38$ subsets $B$ such that $\{1,2,\ldots,62\}\subset B$ and your proof ruled out all of these.
But your proof says nothing about $C_{100}^{63}-38$ subsets $B$ such that $\{1,2,\ldots,62\}\not\subset B$.
[/hide]


Euler
geometry
circumcircle
incenter
rhombus
angle bisector
perpendicular bisector

Triangle ABC is non-isosceles.

Denote the Euler line of this triangle by L, and the internal angle bisector of angle C by D.

Prove that  L  and  D are perpendicular if and only if  $C=\frac{\pi}{3}$.

Prove that  L  and  D are parallel if and only if $C=\frac{2\pi}{3}$.

Let $O, H, I, E_A, E_B, E_C $ be the circumcenter, orthocenter, incenter and excenters against the vertices $A, B, C$ of the triangle $\triangle ABC$, $A', B', C'$ the midpoints of the sides $a = BC, b = CA, c = AB$ and $D, E, F$ the feet of altitudes from the verices $A, B, C$.

Assume that the angle $\gamma = \measuredangle BCA = \frac \pi 3$. Let $K, L$ be the intersections of the internal bisector $CI$ of this angle with the altitudes $AD, BE$. The angles $\measuredangle CAK \equiv \measuredangle CAD = \frac \pi 2 - \gamma = \frac \pi 6$ and $\measuredangle ACK \equiv \measuredangle ACI = \frac \gamma 2 = \frac \pi 6$ are equal. Hence, the triangle $\triangle ACK$ is isosceles and the perpendicular bisector of the side $CA$ passes throught the point $K$. Similarly, the angles $\measuredangle CBL \equiv \measuredangle CBE = \frac \pi 2 - \gamma = \frac \pi 6$ and $\measuredangle ACK \equiv \measuredangle ACI = \frac \gamma 2 = \frac \pi 6$ are equal. Hence, the triangle $\triangle BCL$ is isosceles and the perpendicular bisector of the side $BC$ passes throught the point $L$.

The right angle triangles $\triangle CKD \cong \triangle CKB'$ are congruent, because their common side $CK$ is the bisector of the angle $\measuredangle DCB' \equiv \measuredangle BCA = \gamma$. Similarly, the triangles $\triangle CLE \cong \triangle CLA'$ are congruent, because their common side $CL$ is also the bisector of the angle $\measuredangle ECA' \equiv \measuredangle BCA = \gamma$. Since the circumcenter $O$ and the orthocenter $H$ of the triangle $\triangle ABC$ are isogonal conjugates, the angles $\measuredangle KCO = \measuredangle KCH$. Thus the points $O, H$ are the corresponding points of 2 pairs of congruent triangles $\triangle CKD \cong \triangle CKB'$ and $\triangle CLE \cong \triangle CLA'$. From the 1st pait of triangles, we get $KO = KH$, and from the 2nd pair, $LO = LH$. Thus the quadrilateral $KOLH$ is at least a kite and consequently, its diagonals $AI \equiv KL \perp OH$ are perpendicular. It is even a rhombus, because its opposite sides are parallel: $KO \equiv OB' \parallel BE \equiv LH$ (both perpendicular to $CA$) and $KH \equiv AD \parallel OA' \equiv LO$ (both perpendicular to $BC$).

It is clear that the angle bisector $CI$ is concurrent with the altitude $AD$ and the perpendicular bisector $OB'$ at the point $K$ and also with the altitude $BE$ and the perpendicular bisector $OA'$ at the point $L$ iff $\frac \gamma 2 = \frac \pi 2 - \gamma$. Solving for the angle $\gamma$: $\frac 3 2 \gamma = \frac \pi 2$, $\gamma = \frac \pi 3$. Hence, this condition is not only sufficient, but also necessary for $CI \perp OH$.

Assume that the angle $\gamma = \measuredangle BCA = \frac{2\pi}{3}$. Let $K, L$ be the intersections of the external bisector $CE_A \equiv CE_B$ of this angle with the altitudes $AD, BE$. With this difference, it can be shown in exacly the same way as above, that this external bisector is perpendicular to the Euler line $OH$ of the triangle $\triangle ABC$. Since $CE_A \perp OH$ and $CE_A \perp CI$, we obtain $CI \parallel OH$.


Prove that exist progession arthimetic  a_i such that
a_i= (n^p-1)/ (n-1)
with p be prime  p>2, n possitive number

You ment
$a_{n}= \frac{n^{p}-1}{n-1}$? otherwise $a_{n}$ is constant!
$a_{n}$ is an arithmetical progression then $a_{n+1}-a_{n}$ must be a positive constant wich is not satisfied.

If $a_{i}=\frac{n^{p}-1}{n-1}$ is what was meant, then that is an arithmetic progresion $\forall n \in \mathbb{Z}$ and for all prime $p>2$.