practice problems pending

Q1. Three distinct vertices are chosen at random from the vertices of a given regular polygon of (2n+1) sides. If all such choices are equally likely, what is the probability that the center of the given polygon lies in the interior of the triangle determined by the three chosen random points?
S1.
Fact: The center of a regular polygon lies strictly OUTSIDE a triangle if and only if all three chosen vertices lie on a single semicircle.
Explanation: Each regular polygon has a semicircle. If there are even vertices we will have diameters joining 2 vertices. In odd, we don't.

For e.g. in a pentagon,
Diameter from '1' lands on side 3-4.
Here 2n+1 = 5 => n = 2
Here 3 vertices are in 1 half and 2 vertices in other half.
If you make a triangle using 3 consecutive vertices it won't contain the center, else it would.
For e.g. 1-2-3 doesn't but 1-3-5 does.

Here total ways to create a triangle 5C3 = 10
Triangles with center outside: 1-2-3, 2-3-4 ... 5-1-2 = 5 such
With center inside = 10 - 5 = 5 = answer

How to generalize for a regular odd-sided polygon?
If we span 'n' edges using 'n+1' consecutive vertices then any triangles made using these vertices won't have the center.
Total triangles: (2n+1)C3___[1]
With center outside = to avoid double counting start with a vertex and go till next 'n' vertices clockwise. And pick 2 from these 'n'.
That would mean we are spanning 'n' edges using 'n+1' consecutive vertices.
Repeat for each vertex.
 = (n)C2*(2n+1)___[2]
[1] - [2] gives (n+1)/(4n-2)


Q4.

 A 10-digit arrangement 

0,1,2,3,4,5,6,7,8,9 is called beautiful if
(i) when read left to right, 0,1,2,3,4 form an increasing sequence, and 5,6,7,8,9 form a decreasing sequence, and
(ii) 0 is not the leftmost digit. For example, 9807123654 is a beautiful arrangement.
Determine the number of beautiful arrangements.

S4.
First lay down 9_8_7_6_5_ in this order. This order is fixed.
Now we have 5 buckets(gaps) and 5 objects(0,1,2,3,4) for stars and bars.
Even though these objects are distinct but here we can treat them as identical since their order is fixed.
For e.g. if we put 2 objects in the first bucket and 3 in the second bucket, since their order is fixed, once their places are fixed, there is no variation.
5+5-1C(5-1) = 9C4 = 9.8.7.6/4.3.2.1 = 126


Q5.

A set of 25 square blocks is arranged into a 5×5 square. How many different combinations of 3 blocks can be selected from that set so that no two are in the same row or column?
S5.
Method 1:
First block can be selected in 25 ways.
Second in 16 and third in 9 ways.
Total: 25*16*9 = 3600
This is the correct answer if the order of selection matters.
Else divide by 3! = 6 to get 600.

Method 2:
5C3*5C3 to select 3 rows and 3 columns.
Now first block can be picked from first row in 3 ways.
Second from second row in 2 ways.
Third in 1 way.
10*10*6 = 600.

Q6.

Call finite sets of integers S and T cousins if S and T have the same number of elements, S and T are disjoint, and the elements of S can be paired with the elements of T so that the elements in each pair differ by exactly 1.

For example, {1,2,5} and {0,3,4} are cousins. Suppose that the set S has exactly 40 cousins. Find the least number of elements the set S can have.

S6.
To see max cousins possible for a set:
{1} -> {0},{2} => 2 sets
{1,4} -> 0/2, 3/5 => 4 sets
.....
{1,4,7,10,13} => 32 sets
{1,4,7,10,13,16} => 64 sets

Se we need at least 6 elements.
Notice that if the gap between all is >= 2 like shown above, we get 2^k cousins.
But if gap is exactly 1, for e.g.
1,3,5 then we get k+1 cousins.
Why?
Each number has 2 options Left(-1) or Right(+1).
Once any number shifts right, all the next numbers are forced to shift right.
So it will be like this:
RRR => 2,4,6
LRR => 0,4,6
LLR => 0,2,6
LLL => 0,2,4
Exactly k+1 choices.

And if the gap is 0, for e.g. 1,2 => we get 1 way. => 0,3 But for more than 2 consecutive elements, there is no cousin.

Now if combine chains, for e.g.
1,3,5,8,11 then first 3 give 4 and last 2 give 4 options => total 16
So we have to factor 40 and get that:
40x1 => we need 39 alternate numbers.
20x2 => 19 alternate and the last with gap >= 2
10x4 => 9 alternate and 2 with wider gaps
5x8 => 4 alternate and 3 with wider gaps => 7 elements minimum

Q12.

Let n be a positive integer. A frog starts at the origin (0,0) on a Cartesian coordinate plane. In each step, the frog can leap exactly one unit to the right or one unit up. Prove that the number of distinct paths the frog can take to reach the destination (n,n) without ever stepping strictly above the line y=x is given by the n-th Catalan number:
1/(n+1) 2nCn

S12.
Let's call the paths which cross y=x the bad paths.
For e.g. for n = 2
(0,0) -> (1,0) -> (1,1) -> (2,1) -> (2,2)
is a good path since y is always <= x.

But
(0,0) -> (0,1) -> (1,1) -> (2,1) -> (2,2)
is a bad path since in the second step y> x.

Whenever this bad path crosses y=x for the first time, it is bound to touch y = x+1 line.
Let's say it happens at x=k for the first time.
So frog is at (k,k+1).
To reach (n,n) it needs to take n-k right steps and n-(k+1) up steps.
Let's say we swap it to make n-k up steps and n-(k+1) right steps.
So the frog will end up at (n-1, n+1).

Why did we do this?
Because it's difficult to count bad paths so we plant to count something easy and something which has a 1-1 mapping with bad paths.

What do we count now?
All the paths from 0,0 to n-1,n+1.

Why is it a bijection with bad paths?
For that we need to show that each bad path leads to a path to n-1,n+1
And each path from 0 to n-1,n+1 maps to a bad path.

Case 1:
We have already shown how to convert a bad path to end up at n-1,n+1.
Take a bad path. Note the first time it touches y = x+1. Let's say k,k+1.
Now swap the remaining steps by which it would have reached n,n.
Up becomes Right. Right becomes up.
Now it will end up at n-1,n+1.

Case 2:
Now we need to show that any path to n-1,n+1 from 0,0 maps to a bad path.
The frog is going from 0,0 to n-1,n+1 which means that it starts with a gap of 0 = y-x and ends up at gap of 2 = (n+1) - (n-1).
So there is bound to be a time when the gap will be 1, i.e. y = x+1.
=> any path to n-1,n+1 will touch y=x+1 line at least once.
Let's say that is k,k+1.
From here it would have taken n-1-k steps right and n+1-(k+1) = n-k steps up to reach n-1,n+1
Let's swap them.
So it will end up at k + n - k, k+1+n-1-k = n,n.

So we have shown that a bijection exists.

Now how many paths from 0,0 to n-1,n+1?
2nC(n-1)
= 2n!/(n-1)!(n+1)!
= 2n!.n/n.(n-1)!(n+1)!
= 2n!.n/n!.n!.(n+1)
= n/(n+1) * 2nCn

Subtract from 2nCn to get good paths
2nCn - 2nCn.n/n+1
= 2nCn * 1/n+1
H.P.

Q9.

Prove that the number of partitions of n into distinct parts is equal to the number of partitions of n into odd parts.
S9.
We have to show one to one mapping between these 2.
From distinct parts to odd parts:
Let's say n = p1 + p2 .... pk where each pi >= 1 and each pi is distinct.

Focus on only even parts. And keep breaking them into 2 equal parts until each part thus obtained is odd.
So we have successfully transformed from distinct parts to all odd parts.

For e.g.
12 = 6 + 6 = 3 + 3 + 3 + 3. Now all parts are odd.

Reverse:
From odd to distinct.
As long as any 2 parts are equal, add them.
For e.g.
3 + 3 + 3 + 3 = 6 + 3 + 3 = 6 + 6 = 12

Also:
8 + 4 = 4 + 4 + 2 + 2 = 12 times 1
2 + 10 = 1 + 1 + 5 + 5

Why does it work?
Each integer n can be written as n = m.2^k where k>= 0 and m is odd.
If 'n' is odd, k = 0.

So when going from distinct part to odd parts, let's consider an even part.

That would be m.2^k with k>=1.
For e.g.
24 = 3.2^3 upon division by 2 it gives 3.2^2 then 3.2^1 then 3
So ultimately we get 3 + 3 ... 8 times.
So this method guarantees that each even number will eventually split into m + m ... 2^k times.

Now reverse:
Since the odd number 'm' appears 2^k times, when we start combining, the sequence will go like this:
m + m = m.2^1
2m + 2m = m.2^2
...
 = m.2^k
So we get our original number back.

What if 2 different parts both end up on the same m.2^k?
Then the parts were not distinct to begin with.


Q10.

Let 1 ≤ r ≤ n and consider all subsets of r elements of the set {1,2,…,n}. Each of these subsets has a smallest member. Let F(n,r) denote the arithmetic mean of these smallest numbers; prove that

F(n,r) = (n+1)/(r+1) 
S10.

Let's consider n = 3 and r = 2
{1,2,3} gives 1,2 1,3 2,3 as subsets.
1 + 1 + 2/3 = 4/3 = n+1/r+1.

Let's see how often will 1 be the minimum:
1 is picked so pick r-1 elements from n-1 = (n-1)C(r-1)
For 2 => (n-2)C(r-1)

It will go upto  (r-1)C(r-1) => the last minimum element will be n - (r-1).

So their A.M. will be = N/D
where D = nCr
N = 1.(n-1)C(r-1) + 2.(n-2)C(r-1) .... (n-r + 1)*(n-r+1)C(r-1)

= Sigma[k * (n-k)C(r-1)] for k = 1 to n-r+1

Counting it is difficult.

So we will show that this is equal to (n+1)C(r+1) through other means.
For the numbers 1,2...n+1
if we pick the subset of length r+1
then how often will 'k+1' be the second smallest element?
Note that 1 can never be the second smallest, so k = 1 => 2 is the second smallest.

Smallest element: k choices.
Rest of the elements: (n-k)C(r-1) choices.
So (k+1) be second smallest k*(n-k)C(r-1) times.
Doing sigma over it gives the same expression as above and this is equal to (n+1)C(r+1).

So AM = (n+1)C(r+1)/nCr = n+1/r+1
H.P.

Q11.

Let (p_n(k)) be the number of permutations of the set ({1,\ldots,n}), (n \ge 1), which have exactly (k) fixed points.

Prove that

[
\sum_{k=0}^{n} k \cdot p_n(k)=n!.
]

(Remark: A permutation (f) of a set (S) is a one-to-one mapping of (S) onto itself. An element (i) in (S) is called a fixed point of the permutation (f) if (f(i)=i).**)

S11.
Example:
For e.g. consider {1,2}
It has 2 permutations 1,2 2,1.
1,2 has 2 fixed points. 2,1 has 0 fixed points.

p2(0) = 1
p2(1) = 0
p2(2) = 1
0.1 + 1.0 + 2.1 = 2 = 2!

Formal proof:

Left hand side = total number of fixed points across all permutations.
Why?
pn(k) permutations have 'k' fixed points.
So multiplying it with 'k' gives us total fixed points across those permutations.
Add for all 'k' to get total count of fixed points across all permutations.

Now, look at it another way.
For 1 to be fixed there are (n-1)! permutations.
Similarly for 2,3...n
So each number will be fixed (n-1)! times.
Total: n*(n-1)! = n!
H.P.