practice problems

Q1. A DNA chain is composed of basic building blocks in the form of four chemicals, known by the symbols A,C,T,G. Consider three-letter chains consisting of these symbols (with or without repetitions). How many such chains are there?
S1.
4*4*4 = 64

Q2. Consider the set {a,b,c,d,e}. How many three-letter words can be made out of them, with or without meaning? How many of these will have at least one vowel in them? Answer these questions both for the case when repetitions of letters are allowed and for the case when repetitions of letters are not allowed.
S2.
2.1
With repetition: 5*5*5 = 125
Without: 5*4*3 = 60

2.2
With repetition:
Total words: 5^3 = 125
Without any vowels = 3^3 = 27
Answer = 125 - 27 = 98

Without:
Total: 5*4*3 = 60
Without vowels = 3*2*1
Answer = 60 - 6 = 54


Q3. A permutation (a1,a2,a3,a4,a5) of (1,2,3,4,5) is called heavy-tailed if a1 + a2 < a4 + a5. What is the number of heavy-tailed permutations?
S3.
Total such: 5! = 120
Let's fix 1,2 to a1,a2 => 2!*3! = 12
1,3 => 12
1,4 => a3,a4 from 2,3,5 = 2,5 3,5 => 2!*4 = 8
1,5 => 2,3,4 => 3,4 => 2*2 = 4
1 is done.

2,3 => 1,5 4,5 => 8
2,4 => 1,3,5 => 3,5 => 4
2,5 => 0
2 is done

3,4 3,5 => 0
That's it.
Total = 48

Method 2:
By symmetry
Permutations where a1 + a2 > a4 + a5 exactly equal those where a1 + a2 < a4 + a5.
So if we count where a1 + a2 = a4 + a5 and then subtract from total and divide by 2 we will get answer.
Equality happens at:
1 + 4 = 2 + 3 => 2!.2!.2! = 8
2 + 4 = 1 + 5
3 + 4 = 2 + 5

So 120 - 24 = 96
96/2 = 48

Q4. How many ways are there to split the integers from 1 to 14 into 7 pairs such that in each pair, the greater number is at least 2 times the lesser number?
S4.
For e.g.
7,14 6,12 ... 1,2 => This is the simplest split.

Also, note that the lesser number will always be from {1,2...7} and greater will be from {8,9...14}.
If not, then for e.g. if you pick 3,6 then {1,2,4,5,7} will pair with {8,9...14} and at least one pair will be incompatible for e.g. 11,12.

Now.
7,14 has to be fixed. No option. 12 numbers remain.
6 can come with 12,13.

Case 1:
6,12 => 10 numbers remain.
5 has 3 options 10,11,13 => 8 numbers remain since 7,14,6,12,5 and one from (10,11,13) are gone.
4 has 4 options 8,9 and 2 from (10,11,13) => 6 numbers remain.
3 has to choose from 3 remaining from (8,9,10,11,13) => 4 numbers remain.
2 has to choose from 2 remaining from (8,9,10,11,13) => 2 remain (1 of which is 1)
1 will pair with whatever is left.
 = 3*4*3*2 = 72

Case 2:
6,13 => 10 numbers remain.
5 has 3 options 10,11,12 => 8 numbers remain since 7,14,6,13,5 and one from (10,11,12) are gone.
4 has 4 options 8,9 and 2 from (10,11,12) => 6 numbers remain.
3 has to choose from 3 remaining from (8,9,10,11,12) => 4 numbers remain.
2 has to choose from 2 remaining from (8,9,10,11,12) => 2 remain (1 of which is 1)
1 will pair with whatever is left.
= 72

Total: 144

Method 2:
7,14 fixed
6 has 2 options: 12,13
5 has 3 options out of 10,11,12,13
Now 1,2,3,4 can go with any of the remaining 4 greater 7 numbers. 4!
Total: 2*3*24 = 144

Q5. Let S be the set of permutations of the sequence 1,2,3,4,5 for which the first term is not 1. A permutation is chosen randomly from S. The probability that the second term is 2 is a/b in lowest terms. What is a+b?
S5.
First term is not 1 => |S| = 4*4*3*2*1 = 96
First term is not 1 and second term is 2 => 3*1*3*2*1 = 18
a/b = 18/96 = 3/16
a+b = 19

Q6. Suppose 28 objects are placed along a circle at equal distances. In how many ways can 3 objects be chosen from among them so that no two of the three chosen objects are adjacent nor diametrically opposite?
S6.
Prereq: Circular adjacency non consecutive combinatorics
Choosing 'k' non consecutive from 'n' circular laid objects:
(n/n-k) (n-k)C(k)

n = 28, k = 3
28/25 * 25C3 = 28*25*24*23/25*6 = 28*4*23 total ways to select 3 objects such that no 2 of them are touching.

This set will also contain the cases where 2 objects are diametrically opposite.
Let's consider 1,15 as one of the diameters which is part of this set.
When we chose 1,15 we can't choose 2,28 and 14,16 so 28- 6 = 22 objects remain from which to choose the remaining one.
So when 1,15 were chosen, they came with 22 variations.
Since we have 14 such diameters, we have 22*14 such bad cases which we need to subtract.

28*4*23 - 22*14 = 28(23.4 - 11) = 28.81 = 2268

Q7.

Let S = {1,2...n}. For a given positive integer (m), an (r)-subset T ={a1...ar} of S with a1 is said to be m-separated if a_i - a_{i-1} >= m for i = 2...r. Prove that the number of (r)-subsets of (S) which are (m)-separated, where 0 <= r <= n- (m-1)(r-1), is

n-(m-1)(r-1)C(r)

S7.
Example, n = 9, m = 3, r = 3
1,4,7
1,4,8
1,4,9
1,5,8
....

Let's extend our derivation for non-consecutive here.
Let's pick 'r' elements, denote them using 'X', put them at front. Followed by (n-r) unpicked 'O's.
XXXOO...
Between each of the 2 Xs we have to put at least (m-1) Xs.
How many Os gone: (m-1)(r-1)
How many Os remaining: (n-r) - (m-1)(r-1).
Now it's stars and bars.
There are r+1 buckets. Why? 'r' Xs => r+1 buckets.
And (n-r) - (m-1)(r-1) identical objects to distribute.
Stars and bars formula:
(N+K-1)C(K-1)
N = (n-r) - (m-1)(r-1)
K = r + 1
K-1 = r
N + K - 1 = (n-r) - (m-1)(r-1) + r = n - (m-1)(r-1)
H.P.


Q8. Prove Fermat's Little Theorem using a combinatorial argument: if p is a prime number and a is any positive integer, then:
a^p = a mod p

S8.
Let's understand with a = 2, p = 3
Let's say we have 3 beads which can be colored in 2 ways(Red/Blue).
If they are laid out in a line, there are 2*2*2 = 2^3 ways to color them.

Out of these 8, there are 2 ways to color all of them the same.
RRR and BBB.
If we remove them, we are left with 8-2 = 6 non monochrome colorings.
Remaining 6:
RRB
RBR
BRR
BBR
BRB
RBB


Now make a necklace from these beads. Let's say RRB.

  B
 /   \
R- -R

Since 3 is a prime, we have to rotate it 3 times to get the original design back.
  B
 /   \
R- -R

  R
 /   \
R- -B

  R
 /   \
B- -R

  B
 /   \
R- -R


Why can't we rotate it fewer than 3 times to get the original design back?
For that to happen, the necklace will be made up of smaller repeating blocks of size 'k'.
For e.g. ABAB, ABCABC ....
And 'k' should divide 'p'.
But 'p' is a prime and hence only 1, p can divide it. Hence.

So each necklace design is part of a rotation group of size 3.
So something.3 will give 8-2
=>
k.p = a^p - a
=> a^p - a = 0 mod p
=> a^p = a mod p.
H.P.

Q9. An archer has n distinct bows and n distinct arrows, where each arrow is specifically matched to exactly one bow. The archer must perform a sequence of 2n actions to string all the bows and shoot all the arrows. An arrow can only be shot if its specific matching bow has already been strung at some point earlier in the sequence. Determine the total number of valid sequences of these 2n actions.
S8.
Method 1:
Unfiltered ways total: (2n)!
Let's consider a1,b1.
Half of these will be where a1 comes before b1, so only half are valid.
Similarly for each pair.
So answer = (2n)!/2^n

Method 2:
First choose 2 spaces: 2nC2
Then: (2n-2)C2
....
Total
2nC2 * (2n-2)C2 ... 2C2
 = 2n.(2n-1)./2 * (2n-2)(2n-3)/2 ... = (2n)!/2^n

Q10. Consider a 2×n grid of empty cells. You must place the integers 1,2,3,…,2n into the grid such that every integer is used exactly once, and the sum of the two numbers in every column is identical. Determine the total number of valid ways to fill the grid.
S10.
2 rows, n columns.
Sum of each column is same.
Total sum = 2n (2n + 1)/2
Each column sum = Total/n = n(2n+1)
So n pairs will be like:
1, 2n 2,2n-1 ... so on
n columns => n!
Each column has 2 ways => 2^n
Answer = n!.2^n

Q11.

A professor writes n distinct letters and prepares n correctly addressed envelopes. By mistake, he randomly places one letter into each envelope in a completely arbitrary arrangement. His assistant then takes these envelopes and drops one into each of the n distinct mailboxes corresponding to the n addresses, also in a completely arbitrary arrangement. A letter is successfully delivered if the mailbox it ends up in matches the letter's true address, regardless of the envelope it was in. Determine the total number of successfully delivered letters across all (n!)^2 possible paired configurations of the professor's and the assistant's actions.

S11.

Let the letters be L1,L2 ... Ln.
Envelopes be: E1,E2....En
Mailboxes be: M1,M2...Mn

1. Let letter L1 go into envelope Ek. Rest of the letters can go to remaining envelopes in (n-1)! ways.
2. For L1 to be delivered to M1, Ek has only 1 choice. Rest of the envelopes can be arranged to rest of the mailboxes in (n-1)! ways.
3. Also in step 1, L1 has 'n' ways to choose an envelope.
So total number of ways for L1 to go to M1 = n(choose an envelope)*(n-1)!(arrange remaining L+E) * (n-1)!(arrange remaining E+M)
4. And this has to be done for each of the 'n' letters: *n

Total = n!.n! = (n!)^2

To clarify it further for n = 3
One possible arrangement would be:
L1E2M2 L2E1M3 L3E3M1
There are (n!)^2 such arrangements.
Each arrangement has 'n'(3) Letter and mailbox pairs.
So total Letter+Mailbox pair count = n.(n!)^2
Out of which (n!)^2 pairs are correct matched.

Q12. Let Sn be the set of all n! permutations of the sequence (1,2...n). For a permutation π = (a1,a2...an), we call the element ai a record if it is strictly greater than all elements before it. The first element a1 is always considered a record. Determine the total number of records counted across all n! permutations in Sn.

S12.
For e.g. 1,2,3,4
Total permutations: 4!
In all of them first element is a record: 4! records.
In half of them second one is a record. Why?
For e.g.
1,2,3,4 and 2,1,3,4  Since they are distinct numbers, second element will be larger than first half the time.
So 4!/2

For the third element to be the record, it has to be more than first and second.
This will happen 1/3 times.
So 4!/3

Similarly 4!/4 times the last element will be the record.

Total records = 4![1 + 1/2 + 1/3 + 1/4]

For n,
n![1/1 + 1/2 ... 1/n] = answer