In a line up of 10 soldiers, what is the maximum number of soldiers that can be picked in order of either ascending or descending heights? Assume that no two soldiers have the same height. Soldiers can be picked from anywhere in the line, but their order of standing cannot be changed.  In other words, we want to find the maximum number k such that, for any permutation of 10 elements, we can always either find an increasing subsequence of length k, or a decreasing subsequence of length k.
88833
Today my friend asked me following question:  Consider the set $ A= \{1,2,3,4,5\}$ By using the elements of this set, can you find a permutation that neither has an increasing sequence of length 3, nor has a decreasing sequence of length 3?  for example:   $3,4,2,1,5$ has an increasing sequence of length $3$, namely $3,4,5$   $5,3,1,2,4$ has a decreasing sequence of length $3$, namely $5,3,2$  I feel like I cannot find such a sequence. I guess problem is that this set has 5 elements and therefore I cannot create such a sequence. If it had 4 elements, I would find lots of sequences with that property. (With the same number of elements, length 4 would be OK too.) But how can I prove it to him? Could you please explain to me?  Best Regards
34857
I'm reading an algorithm book. In which it mentioned:     Imagine (once again) you have n people lined up to see a movie, but   there are only k places left in  the theater. How many possible   subsets of size k could possibly get in? That’s exactly $C(n,k)$, of   course,  and the metaphor may do some work for us here. We already   know that we have $n!$ possible orderings of  the entire line. What if   we just count all these possibilities and let in the first $k$? The only   problem then is  that we’ve counted the subsets too many times. A   certain group of k friends could stand at the head of  the line in a   lot of the permutations; in fact, we could allow these friends to   stand in any of their $k!$  possible permutations, and the remainder of   the line could stand in any of their $(n–k)!$ possible  permutations   without affecting who’s getting in. Aaaand this gives us the answer!       $$C(n,k)= \frac{n!}{k!(n −k)!}$$      This formula just counts all possible permutations of the line (n!),   and divides by the number of  times we count each “winning subset,” as   explained.   I'm not quite understand why the reminder can in any $(n-k)!$ permutation, if he stands at the end of the queue, won't he let all these people in?  And why I should use $n!$ to divide by $k!(n-k)!$ ? Didn't see that consequence from the metaphor.  If you have better ideas to explain this formula, you can use them of course.
82736
This question is generalization of different cases of  combinatorics problems that are generally asked.  We will find general way of arranging $n$ balls in $r$ boxes. Cases :    Identical Balls. Distinct Balls. Order considered. Distinct Balls. Order not considered.   Two cases arise in each case :    Empty boxes allowed. Empty boxes not allowed.   Please feel free to add any other cases or minor variations you might think can be generalized.
6646
Background: I'm working on  for , and I've run into a problem with how I'm creating the individual matchups (groups of 4 entries).  Currently, I'm simply generating all combinations of 4 elements (in the combinatoric sense) of entries, but that gets really big really quickly:  $$x \choose 4$$    (from )  Therefore, my question is: How can I choose subsets (of length $n$) of a set such that each element of that set appears in the same subset as every other element at least once, while maintaining a minimal amount of subsets?  I can figure this out for $n = 2$, since the solution is quite intuitive: simply combine the first element with every other element, combine the second element with every other element that comes after it, etc. For a set of length $L$, this yields:  $$\sum_{x=1}^{L-1}(L - x)$$    (from )  which is much smaller and more manageable.  However, I still have not been able to figure out: How can I generalize this to any $n$?
108163
It seems to be known that the minimum size of a generating set for a finite group of order $n$ is at most $\log_2 n$. Can someone explain why this is true?  Edit: noted that the logarithm is base 2, and $n$ represents the order of the group.
116273
In the UK there are 90 bingo balls. A bingo card consists of 9 columns and 3 rows. A row contains exactly five numbers and four blanks. A column consists of one, two or three numbers and never three blanks. The columns are occupied by the number chosen from 1-9 (only nine), 10-19 (ten), 20-29 ... 70-79 and importantly 80-90 (eleven). Numbers in columns are ordered from top to bottom.  How many possible unnumbered card layouts are there?  How many possible numbered cards are there?  I have started to approach this problem by first choosing the blanks for the first two rows and then attempting to work out a compensating row. This was hard.  Next I begun to understand that there were a number of equivalence classes as columns could be reordered for the purposes producing different layouts.  Next I looked into the most convoluted card which had five numbers followed by four blanks in the first row and four blanks followed five number in the second. This satisfied the "no blank column" requirement. Now the final row could be arranged however it wanted, though there was one confusing overlap to deal with.   I considered another convoluted card which had as many columns of three as possible. It turns out it's possible have a maximum of three columns of three which also gives rise to the maximum of six columns of one. It also turns out you can have a maximum of six columns of two. I think the starting point might be to determine the classes of card initially by column combinations and then permute them.  Having gotten all muddled by the layouts, I turned to the numbers. With a single number, it was one of 9, 10 or 11 depending on the column and that was easy. For the two number case, let's say with a column of ten, the first ($i$) was chosen from 9 and the next from $10-i$. It suddenly occurred to me that it was just combinations, phew. How to fit that with the whole business of column choice lost me.  It seems possible that for each possible "set" of columns, there will be a way of determining the distribution of possible first columns and adding in an appropriate factor for the number combinations.  Frankly, it's all getting bigger than my coffee table.   Any simplifications from higher maths I'm missing?
84068
A security company consists of $7$ men and $6$ women. Determine the number of ways to form the night shift team of $3$ men and $3$ women if it can include at most one of the oldest man or oldest woman.  I know the first step is to pick $3$ from each group which is   $_6C_3 \cdot _7C_3 $  but I am not sure how to account for the "include at most one of the oldest man or oldest woman"   The answer is $_6C_3 \cdot _7C_3 + _6C_3 \cdot _5C_3 + _6C_2 \cdot _5C_3 $  Also, how do I account for it in my calculations if I want to include the oldest man and oldest woman from the group?
35990
What are common lower bounds for ${{2n} \choose {n}}$?    Edit:  I made a mistake in my original question.  It doesn't change my question but there is no reason for me to include the mistake.
106666
A 5x5 board has $25$ cells. The numbers $\{1,2,3,4,5\}$ are written on every row,every column and the two main diagonals without any repetition. If the sum of the numbers of the diagonal below the leading diagonal be represented as $A$. Show that $A\ne 20$. Also find the maximum possible value of $A$.    I could prove that $A\ne 20$ by showing that each of the cells of the diagonal below the leading diagonal cannot be $20$ as if such arrangement exists, then the board cannot have $5$ five times, which actually should be by the given condition of the question.    For the second part, I can imagine the maxiumum value to be $17$. For which I proved that $5$ can occur only $2$ times in the four cells and probably $4$ cannot occur twice. But I got no formal proof. Please help!
71345
Let $n&gt;0$ be an integer. Consider all partitions of $n$, i.e. all possible ways of writing $n$ as a finite sum of positive integers,   $$n=n_1+n_2+\cdots+n_k.$$   What partition maximizes the product $n_1n_2\cdots n_k$?   Examples:   $2=2$ $3=3$ $4=2+2$ $5=3+2$ $6=3+3$ $7=3+2+2$ $8=3+3+2$ $9=3+3+3$ $10=3+2+2$ $20=3+3+3+3+3+3+2$ $30=3+3+3+3+3+3+3+3+3+3$ $40=3+3+3+3+3+3+3+3+3+3+3+3+2+2$ $50=3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+2$      Conjecture: It is the partition that has the maximum number of $3$'s among those consisting only of $3$'s and $2$'s.
56753
Assume that there are $n$ people line up to get into $m$ different clubs. How many ways to do it if each people is different and order of people in the line matters.  Sol. Clearly, each people has $m$ different choices for clubs. So there are $m^n$ ways of choosing clubs. Now we count number of different lines. Let $x_i$ be the number of people lining to get to the club $i$, $1 \leq i \leq m$, $x_i \geq 0$.  Then $$x_1 + x_2 + ... + x_m = n$$ with $x_i$ non-negative integers. So there are ${m+n-1}\choose{n-1}$ ways, ignore order in each line. So there are ${m+n-1}\choose{n-1}$$ x_1!x_2!...x_n!$ possible lines.  The answer is weird since it is in $x_1, ...,x_n$ terms, and I think it is wrong. However, I am not sure how to fix it.  Any help please ?
32269
I am not sure how to approach this problem:  $n$ people are seated in numbered chairs $1$ to $n$. Let $N$ be the number of ways the people can be reseated so that no one is in the same chair as before. Show that $N=n! \sum_{k=0}^n \frac {(-1)^k}{k!}$.  I feel like the way to do this is to come up with a way to count all the seating arrangements, yet I am not sure how to take into account the seat where the person already sat into account when counting them. Because it would seem that there is $n-1$ possible places to sit at, yet placing the first person does not eliminate one possibility for everyone...  Any help is appreciated. Thank you in advance.
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.
83255
This problem comes from a seemingly innocuous question from a professor during a lesson for a Math Olympiad course. [A part of this question is really a classic of number theory/combinatorics]  Problem: Let $S$ be a a non-empty subset of $\{1,2,\ldots,2n\}$. It is clear that if $|S|$ is "enough large" then, independently from the choice of $S$, there are for sure some distinct $a,b \in S$ such that $a$ divides $b$.  Then, what is the maximal $k$ such that, for some $S$ with cardinality $k$, if $a,b$ are distinct members of $S$ then $a$ does not divide $b$?  [Ps. I know the solution]
75749
0 choices for the 1st person.  17 choices for the 2nd person (must exclude 1st and his/her two neighbours)   For 2 of these choices of 2nd person, there is one shared neighbour, so 15 remaining choices. (e.g. if they are numbered 1 to 20 in a circle, 1st person is #1, 2nd is #3, then people 20,1,2,3,4 are excluded).  For the other 15 choices of 2nd person, there are no shared neighbors, so 14 remaining choices.   So if order matters, total is $20 \cdot (2 \cdot 15 + 15 \cdot 14) $ but since order does not matter, divide by $3! = 6$ to account for the permutations in order of the 3 people.  So total = $20 \cdot \frac{2 \cdot 15 + 15 \cdot 14}{6}$  just redid it; does this make any sense?
30709
If $n$ distinct objects are arranged in a circle, I need to prove that the number of ways of selecting three of these $n$ things so that no two of them are next to each other is $\frac{1}{6}n(n-4)(n-5)$.  Initially I can select $1$ object in $n$ ways. Then its neighbours cannot be selected. So I will have $n-3$ objects to choose $2$ objects from. Again, I can select the second object in $n-3$ ways. The neighbours of this object cannot be selected. However from here onwards, I am unable to extend this argument as the selection of the third object is dependent on the position of the first and the second object. Is there any simpler method to prove the result?
70625
This was a question from my textbook. This is how I approached it.   For the first part, you can do c(10,5) so you choose 5 of the 10 to be on a team.   For the second part, you have 10 ways to choose the "best player" and you multiply it by c(10,4) to pick the other 4 players. However, I am not sure how you can exclude the "worst player". Although this sounds subjective, I believe the question is saying that the "best" and "worst" players are distinct, whereas the other players aren't.