Suppose that $mn$ people of a marching band are standing in a rectangular formation of $m$ rows and $n$ columns in such a way that in each row each person is taller than the one to his or her left. Suppose that the leader rearranges the people in each column in increasing order of height from front to back. Show that the rows are still arranged in increasing order of height from left to right.   EDIT: Thanks. I didn't know that this question was already here, only differently phrased.
123930
$m \times n$ persons stand as a rectangle of $m$ rows and $n$ columns. Each one is taller than the one next to his left.  Now, if commander orders each column to sort by height, prove that after such sorting, each one is still taller than the one next to his left.   I'm reading a Combinatorics book on my own, but some exercises I can't solve... many thanks!
38649
Let $G$ be a group and $g,h \in G$. I need to prove that if $g$ and $h$ commute and their orders are coprime, then $|gh| = |g||h|$, that is, the order of their product is the multiple of their orders.  Since $gh = hg$, then $(gh)^{ lcm(|g|, |h|)} = e$, so, $|gh|$ divides $lcm(|g|, |h|)$. Since $\gcd(|g|, |h|) = 1$, then $lcm(|g|, |h|) = |g||h|$.  So, $|gh|$ divides $|g||h|$.
31446
Show that in a party of $n$ people, there are two people having identical number of friends.  I am a beginner at Pigeonhole Principle problems and have produced a solution to this intermediate level question. I am excited about it and I want my solution to be cross-checked and if anything is going wrong, please point it out.  So here it goes:  Let us consider an $n$ by $n$ symmetric matrix $A$ such that $a_{ij}=1$ if $i$-th and $j$-th persons are friends, otherwise $0$.  Please understand that I have assumed that friendship is mutual in the ordinary sense and also, $a_{ii}=1$ for all $i$. The matrix visualization is not necessary, but it just helped me in my thinking process.  So all we need to do is count the number of $1$'s in a particular row as this will give the number of friends of that particular person to whom that row corresponds. For example, the total number of $1$'s in row $3$ will give the total number of friends the third person has, after we have arbitrarily chosen a first person and begun counting.  So it boils down to showing that there will be two rows with same number of $1$'s. First consider that no person is friend only with himself, and no person has everyone a friend i.e. no row in the matrix has only one $1$ and no row has all $n$ entries $1$. Then the sum of $1$'s in a row can be maximum $n-1$ and minimum $2$, giving a total of $n-2$ possible sums, but there are $n$ rows. So, two rows must have the same sum of $1$'s, and those two persons have the same number of friends.  Now consider the case where one person, say person $1$ is friend with no one except himself. That means $a_{11}=1$ and $a_{1j}=0$ for $j=2,3,...,n$. We claim that in this case, the sum of $1$'s in any row other than the first row, has a minimum value of $2$ and a maximum of $n-1$, which is easy to check. The minimum is not a problem, but in case questions arise regarding the maximum, it is clear that the maximum is not $n$ because that would imply there exists a person with $n$ friends, contradicting the fact that the first person is friend only with himself. So there are $n-1$ rows and $n-2$ possible sums, for which two rows have the same sum.  The case where one person is friends with all others is similar.  We have exhausted all the three cases and thus we are done.
81042
let $n \gt 1$ be an integer, and consider $n$ people; $P_1, P_2,..., P_n$ let $A_n$ be the number of ways these $n$ people can be divided into groups, such that each group have either one or two people  determine $A_1, A_2, A_3$  So I have  $A_1 = 1$ way $A_2 = 4$ way $A_3 = 12$ way  But I am not sure if this is right... Can anyone confirm?  edit:  My way of getting this is  $A_1 = 1 $ because {P1} only has 1 way to sort  $A_2 = 4$ because {P1,P2} = {P1,P2},{P2,P1},{P1P2},{P2P1}  etc.
58605
Question is:     Let $G$ be a group of  order 2n. Suppose half of the element of G are of order 2 and the other half form  a subgroup $H$ of order n . Prove that $H$ is of odd order  and is an abelian subgroup of $G$   What could i see is..  if we prove that order of every element of $H$ is odd , then order of $H$ is odd . Also i am unable to use the fact that half of the element of $G$ are of order 2.  Please help me to clear this.  Thank You.
14842
Well if one looks at the formula of circular permutations $Pc = (n-1)!$  But as we come to that formula, I need a concrete example and an explanation.  Another thing, I have seen that when working with a bracelet, the formula changes. A concrete example please along with an explanation  Finally how the formula is worked when there are repeated elements that are permuted.  Thank you
58111
There are $2014^{2014}$ children at a mathematics camp. Each has at most three friends at the camp, and if A is friends with B, then B is friends with A. The camp leader would like to line the children up so that there are at most $2014$ children between any pair of friends. Is it always possible to do this?  I thought maybe the pigeon hole principle. Obviously the 2014 is arbitrary. I googled it looking for a solution and it turns out it is from the BMO round 2. there it is 2010. Any help would be much appreciated.
17412
I searched in the existing post and didn't find this problem. I am sorry if someone else have already posted.     Let $G$ be a group of order $2m$ where $m$ is odd. Prove that $G$ contains a normal subgroup of order $m$.   There is a hint:     Denote by $\rho$ the regular represetation of $G$: find an odd permutation in ${\rho}(G)$.   I don't know how to find an odd permutation in the regular representation. I am wondering whether all the elements of $G$ of odd order form this subgroup in this case.  Thanks.
101026
Let $G$ be a cyclic group of order $m$. What is the order of $\text{Aut}(G)$?  I want to know the proof as well (elementary if possible). I would still accept the proof if one answers with $m = p$, a prime. Or on top of that, I would accept the answer with extra assumption: $q \equiv 1$ mod $p$ with another prime $p$.
36047
Given $G$, $H$, $G&#39;$, and $H&#39;$ are cyclic groups of orders $m$, $n$, $m&#39;$, and $n&#39;$ respectively.   If $G*H$ is isomorphic to $G&#39;* H&#39;$, I would like to show that either $m = m&#39;$ and $n = n&#39;$ or else $m = n&#39;$ and $n = m&#39;$ holds. Where * denotes the free product.  My approach:  $G*H$ has an element of order $n$, thus $G&#39; * H&#39;$ has one too.  But already the next step is not clear to me, should I show that there is an element of length $&gt; 1$ which has infinite order or what would be the right approach here?  Thank you.
24805
Hello guys I have this problem which has been really bugging me. And it goes as follows:  Using induction, we want to prove that all human beings have the same hair colour. Let       S(n) be the statement that “any group of n human beings has the same hair colour”.  Clearly S(1) is true: in any group of just one, everybody has the same hair colour.  Now assume S(k), that in any group of k everybody has the same hair colour. If we replace any one in the group with someone else, they still make a total of k and hence have the same hair colour. This works for any initial group of people, meaning that any group of k + 1 also has the same hair colour. Therefore S(k + 1) is true.  I cant seem to figure out where the problem lies in this proof. I have tried a few things and I have concluded the base case is correct. But other than that I can't seem to disprove this proof.
73885
Can anyone give me a vectorial solution to the following problem:     Prove that if each pair of opposite edges of the tetrahedron $ABCD$ is perpendicular (that is, $AB \perp CD$ and $AC \perp BD$ and $AD \perp BC$), then the heights of the tetrahedron are concurrent.   Here, the heights (also known as the altitudes) of tetrahedron $ABCD$ are the perpendicular from $A$ to the plane $BCD$, and three other similarly defined perpendiculars.  Tetrahedra satisfying the condition of this problem are called , and this appears to be a known result.
11601
I am looking for an intuitive explanation as to why/how row rank of a matrix = column rank. I've read the proof at  and I understand the proof, but I don't "get it". Can someone help me out with this ?   I find it hard to wrap my head around the idea of how the column space and the row space is related at a fundamental level.
64228
Let $G$ be a group and $a,b \in G$ with $a \ne 1$ and $b \ne 1$. Assuming $ab^2 = b^3a$ and $a^2=1$ I need to prove that the order of $b$ is $5$.   I have proved by contradiction that it can't be 2 or 3 but I don't know how to prove that it must be 5 and it can't be 4.
109592
Suppose that there is a man standing on the origin of the real line and plays heads or tails. Everytime he gets a head, he moves $1$ unit right and everytime he gets a tail, he moves $1$ unit left. What is the expected value of the number of his steps when he reached to $-7$ or $10$ for the first time? A friend of mine asked me this question today and my approach to solve it was quite complex. So any help is appreciated.
66754
I have been working on this exercise for a while now. It's in B.L. van der Waerden's Algebra (Volume I), page $19$. The exercise is as follows:     The order of the symmetric group $S_n$ is $n!=\prod_{1}^{n}\nu$. (Mathematical induction on $n$.)   I don't comprehend how we can logically use induction here. It seems that the first step would be proving $S_1$ has $1!=1$ elements. This is simply justified: There is only one permutation of $1$, the permutation of $1$ to itself.  The next step would be assuming that $S_n$ has order $n!$. Now here is where I get stuck. How do I use this to show that $S_{n+1}$ has order $(n+1)!$?  Here is my attempt: I am thinking this is because all $n!$ permutations of $S_n$ now have a new element to permutate. For example, if we take one single permutation $$ p(1,\dots,n) = \begin{pmatrix} 1 &amp; 2 &amp; 3 &amp; \dots &amp; n\\ 1 &amp; 2 &amp; 3 &amp; \dots &amp; n \end{pmatrix} $$ We now have $n$ modifications of this single permutation by adding the symbol $(n+1)$:  \begin{align} p(1,2,\dots,n,(n+1))&amp;= \begin{pmatrix} 1 &amp; 2 &amp; \dots &amp; n &amp; (n+1)\\ 1 &amp; 2 &amp; \dots &amp; n &amp; (n+1) \end{pmatrix}\\ p(2,1,\dots,n,(n+1))&amp;= \begin{pmatrix} 1 &amp; 2 &amp; \dots &amp; n &amp; (n+1)\\ 2 &amp; 1 &amp; \dots &amp; n &amp; (n+1) \end{pmatrix}\\ \vdots\\ p(n,2,\dots,1,(n+1))&amp;= \begin{pmatrix} 1 &amp; 2 &amp; \dots &amp; n &amp; (n+1)\\ n &amp; 2 &amp; \dots &amp; 1 &amp; (n+1) \end{pmatrix}\\ p((n+1),2,\dots,n,1)&amp;= \begin{pmatrix} 1 &amp; 2 &amp; \dots &amp; n &amp; (n+1)\\ (n+1) &amp; 2 &amp; \dots &amp; n &amp; 1 \end{pmatrix} \end{align}  There are actually $(n+1)$ permutations of that specific form, but we take $p(1,\dots,n)=p(1,\dots,n,(n+1))$ in order to illustrate and prove our original statement. We can make this general equality for all $n!$ permutations: $p(x_1,x_2,\dots,x_n)=p(x_1,x_2,\dots,x_n,x_{n+1})$ where $x_i$ is any symbol of our finite set of $n$ symbols and $x_{n+1}$ is strictly defined as the symbol $(n+1)$.  We can repeat this process for all $n!$ permutations in $S_n$. This gives us $n!n$ permutations. Then, adding in the original $n!$ permutations, we have $n!n+n!=(n+1)n!=(n+1)!$. Consequently, $S_n$ has order $n!$.  How is my reasoning here? Furthermore, is there a more elegant argument? I do not really see my argument here as incorrect, it just seems to lack elegance. My reasoning may well be very incorrect, however. If so, please point it out to me.
48825
I want to show that if $g,h\in G$ are group elements with finite coprime orders $m$ and $n$ and $gh=hg$ then the order of $gh$ is $mn$.    We have that  $$ (gh)^{mn}=g^{mn}h^{mn}=1 $$  using $gh=hg$, so $|gh|\leq mn$. On the other hand, $mn=\operatorname{gcd}(m,n)\operatorname{lcm}(m,n)=\operatorname{lcm}(m,n)$, since $m$ and $n$ are coprime. I am not sure how to proceed, I tried assuming that $|gh|&lt;mn$ and arriving at a contradiction, but it did not take me anywhere.