Combinatorics shortlist

[•Cosmin]

http://infoarena.ro/blog/combinatorics-shortlist

[•danalex97]

Thanks for the pices of advice about math books - I find the last one very useful.    I will also try to solve the problems.

[•Cosmin]

Any ideas?

[•mugurelionut]

O sa incep eu cu cele simple

1) 9! / (3! * 3! * 3!) = 1680
sau
Comb(6,3) * Comb(9,3) = (tot) 1680
Comb(6,3) = in cate moduri poti interclasa 3 a-uri cu 3 b-uri
Comb(9,3) = in cate moduri poti interclasa un sir fixat de 3 a-uri + 3 b-uri cu un sir format din 3 c-uri

2) Fibonacci(n)  (considerand Fibonacci(0) = Fibonacci(1) = 1)

[•mugurelionut]

Hm... Since I forgot that the post was in English, I will restate my comment in English

1) 9! / (3! * 3! * 3!) = 1680
or
Comb(6,3) * Comb(9,3) = (also) 1680
[ Comb(n,k) = n choose k ]

2) Fibonacci(n)  (considering Fibonacci(0) = Fibonacci(1) = 1)

[•a_h1926]

4. Let’s assume that with n lines, the plane can be split in maximum Sn regions. Now when we add the (n+1)th line, we must draw it such that no 3 lines intersect at the same point, and such that there are no parallel lines (otherwise we lose regions which we could have generated). If we draw the (n+1)th line according to the previous restrictions, it will intersect all the previous n lines in exactly one point, so n regions determined by the previous lines will be split in two, thus adding n new regions. From here we deduce the relation Sn = n + Sn-1. S0 = 1, since the plane cannot be split without any lines, from where we can write Sn = 1 + (1 + 2 + ... + n) = 1 + n(n+1)/2. If we consider the same problem for circles, we can similarly deduce a recurrence S1 = 2 and Sn = 2*(n-1) + Sn-1. We proceed similarly for planes and spheres.

5. We will use the fact that x * (n - x) is maximal when x is n/2. Thus, if we want to write n as a sum of 2 numbers, their product would be maximal if we write n = [n/2] + [(n+1)/2]. We can extend this for arbitrarly many numbers. So we will write n = [n/k] + [n/k] + ... + [n/k] + (n - (k-1)*[n/k]). Now we can notice that [n/k] can’t be greater than 4, because if it were, it could be decomposed as a sum of 2 other numbers (if it is 5, we could decompose it in 2 + 3), which would give a greater value (from the relation we stated above). At is also obvious that [n/k] is greater than 1 (it doesn’t make sense to write n as 1+1+1+...+1), so the only 3 candidates are 2, 3 and 4. Writing 4 as a term is the same as writing 2+2 (because 2*2 is also equal to 4), si we only have 2 candidates left: 2 and 3. We notice that 3*3 is greater than 2*2*2, so we will use as many 3’s as possible, and fill in the remaining with 2’s. So, if n mod 3 = 0, we write n = 3 + 3 + ... + 3 = n/3 * 3. If n mod 3 = 2, we write n = 3 + 3 + ... + 3 + 2 = [n/3] * 3 + 2, and if n mod 3 = 1 we write n = 3 + 3 + ... + 3 + 2 + 2 = ([n/3] - 1) * 3 + 2 + 2.

6. We can use dynamic programming. Let’s note F(n) = number of ways we can entirely cover a 3xn rectangle with dominoes and G(n) = number of ways we can cover a 3xn rectangle but with one missing corner (let’s say the upper-right one). We can observe the recurrence F(n) = F(n-2) + 2 * G(n-1) (we can cover a 3x2 rectangle, so we continue all the previous 3x(n-2) possibilities, and we can cover with an “L” shape the previous states with 1 missing corner – there is a 2 factor because we can also mirror the state so the missing corner is the lower-right one), and G(n) = F(n-1) + G(n-2) (we add a single domino to a previous entirely covered rectangle, or we add a square and another domino below to continue a previous missing-corner state). So, we have F(0) = 1, F(1) = 0, G(0) = 0, G(1) = 1 and F(N) = F(N-2) + 2*G(N-1) and G(N) = F(N-1) + G(N-2).

8. It is obvious that we can only place one rook on a line or on a column. So let’s consider we have k fixed rows and k fixed columns on which we place the rooks. Now we reduced the problem to determining in how many ways we place k rooks on a kxk board. We can observe that the answer is k!, because we can index each rook with the line on which it is placed, and now we need to place the numbers 1, 2, ..., k on k columns, which is exactly a permutation of those numbers. The final answer is Comb(n, k) * Comb(n, k) * k!.

9. Using the inclusion-exclusion principle, we will count how many permutations have any number of fixed points minus the number of permutations which have at least 1 fixed point and so on. The formula is Sum (k from 0 to n) (-1)^k * Comb(n, k) * (n-k)!  (Comb(n, k) is the number of ways we can pick the k fixed points and (n-k)! is the number of ways we can permute the remaining elements).

10. I remember this as beeing the combinatorial explanation for the nth Catalan number ( which is equal with Comb(2n, n)/(n+1) ), but I don’t remember a mathematical proof.

11. We have to make n-1 steps on the OX axis and m-1 steps on the OY axis, so a total of n+m–2 steps. We just need to see in how many ways we can make n-1 OX steps out of the total of n+m-2  (the remaining ones are OY steps). The solution is Comb(n+m-2, n-1) ( which is also equal with Comb(n+m-2, m-1) ).

12. I think the result is n - c, where c is the number of cycles in the permutation, because each cycle of length l can be solved with l-1 swaps, and since the sum of the lengths of all cycles is n, the result is n - c.

14. We can decompose the permutation p in cycles. Let’s assume that it’s formed out of m cycles of lengths l1, l2, ..., lm. If we compute p^l1, the first cycle will be in the correct order (the same as in the idendity permutation), because we circularly shift every element l1 position to the right, after which it gets to its original positon. So, the minimal k we seek is a multiple of l1. Same applies for l2, ..., lm, from where we deduce that k is the lowet common multiple of l1, l2, ..., lm.

[•S7012MY]

At problem 4) i think that for n=3 there are 7 regions

[•mugurelionut]

At problem 6) (counting the number of ways of covering a 3xn rectangle with dominoes - let's assume 3 = number of rows and n = number of columns) I personally prefer using dynamic programming with 2^3 states (i.e. compute nways[i, conf] = the number of ways of covering the first i columns such that: the first i-1 columns are fully covered and column i is in state conf -- where a 1-bit denotes that the cell on that row is covered and a 0-bit denotes that the cell on that row is empty ; 0 <= conf <= 2^3 - 1). The answer would either be in nways[n, 7] or in nways[n+1, 0].

A nice thing is that this problem can be solved even for large values of n (e.g. n <= 10^18) by raising an appropriate matrix to an appropriate power.

[•Cosmin]

Thanks Petru, I've modified the example.

[•Cosmin]

Andrei and Mugurel your solutions look correct.

3, 7, 13, 15, 16, 17 left to solve.
Anyone?

[•mugurelionut]

15) Since the exponent k for which a permutation becomes the identitiy permutation is the lowest common multiple of its cycle lengths, we could use dynamic programming to solve this:
kmax[i,j] = the maximum k for a permutation with j elements and using only the first i prime numbers

the idea is that the cycle lengths are always prime numbers or powers of prime numbers (or 1 - yes, it may make sense to have cycles of length 1 in the solution : this only means that the answer is max{kmax[*,j] 1 <= j <= N})

kmax[0,0] = 1
kmax[i,j] = max{ prime(i)^q * kmax[i-1, j - prime(i)^q | 1 <= q <= qmax such that prime(i)^q <= j }

Note that kmax[i,j] is a large number. I don't currently know how to solve the problem without using large numbers (i.e. without using large numbers during the algorithm ; the answer itself will always be a large number, unless you simply ask for a permutation which maximizes k, like in the infoarena problem)

This problem was also used in:
* "Bursele Agora" (Agora scholarship) contest -- the 1st edition (1999-2000) if I recall well, and
* Olimpiada online (2001) -- it was a problem with dancing butterflies or something

[•mugurelionut]

17) I solved that problem many years ago   Since I don't have my source code nearby, I will give it a shot at rediscovering the solution. Here's my wild guess

(2^gcd(1,N) + 2^gcd(2,N) + ... + 2^gcd(N,N)) / N

The main tool for solving the problem is this: http://mathworld.wolfram.com/Cauchy-FrobeniusLemma.html  (also known as http://en.wikipedia.org/wiki/Burnside's_lemma)

[•gogu]

7) This one is really easy once you rewrite it as:
for i1 = 1,n
_for i2 = i1+1,n+1
__for i3 = i2+1,n+2
____…
_____for ik = ik–1 + 1,n+k-1
______print ‘*’
To anyone that has implemented enough brute-force solutions the answer is obviously N+K-1 choose K.

13) You can only have length 1 or 2 cycles in your permutation. So you can generate a N sized permutation from a N-1 permutation by adding N in a 1-length cycle, or from a N-2 permutation by adding the element N in a cycle with N-1 possible other elements and incrementing all elements in between.
So unless I’m missing something Sol(N) = Sol(N-1) + (N-1)*Sol(N-2)

15) I only have to add to Mugurel’s solution that you can get away without using large numbers if you use the logarithm of the prime numbers and try to maximize their sum to maximize the smallest common multiple.
You may get an issue if 2 possible values are closer than the floating point calculation precision, so when the value you’re improving on and the new potential best are closer than the precision for the log operation (less than 1e-9) times the maximum number of distinct prime numbers less than N. In that case you can calculate the actual values by reconstructing the solution. This probably doesn’t happen in practice though.
As a useless theoretical point, since you know that the complexity of the algorithm is polynomial, say O(N^k), if you use (k+1)-word sized floating point numbers, that will give an amortized constant time number of actual calculations with the big numbers.
I called a word the type on which you store N, so a 32 bit integer here.

[•Cosmin]

@Mugurel
15 yes butterflies was first used in the selection camp, then I saw it in the first bursele agora contest , same text. I got 100 points then and was really happy about it.
17 or Polya's lemma, could you explain it a bit more?

@Ciucu 7) I wanted to add that (i1, i2, ..., ik) are also called k-combinations with repetitions.

So we have 3 and 16 left standing.

[•vlad_D]

16.

Let's represent the problem as a complete undirected graph with 6 vertices. Each vertex represent a person and each edge represents a relationship between 2 distinct people.

Each edge is either of type A or of type B (e.g. A means friends, B means enemies. These can be interchanged with no change in proof).

Now we have to prove that any complete undirected graph with 6 vertices has at least on tuple (a, b, c) (let's call it triangle) of distinct vertices such that E(a, b), E(b, c), E(a, c) are edges of same type.

For any graph (with properties mentioned above) let's pick any vertex VS. VS is connected to 5 other vertices. Thus regardless of the configuration of the graph, among these 5 connections (edges) there are at least 3 of same type. Let's say type A.

Among these edges of type A let's pick any 3 and note the vertices that they connect a, b, c.

Now, VS-a, VS-b, VS-c are edges of type A and there are 2 cases:
1. at least one edge a-b, a-c, b-c is of type A => then we have a triangle with edges of type A => problem solved.
2. none  of the edges a-b, a-c, b-c is of type A => these 3 edges are of type B but these 3 edges form a triangle (a, b, c) => problem solved.

1 + 2 => problem solved.

[•proflaurian]

Problem 3)

Triangles can be counted according to the number of vertices located inside the circle.
If there are 3 vertices inside then we can locate exactly 6 points on the circle. But 6 points lead exactly to 1 such triangle. Hence there are comb(n,6) such triangles.
If there are 2 vertices inside and 1 on the circle then we can locate exactly 5 points on the circle. But 5 points lead exactly to 5 such triangles. Hence there are 5*comb(n,5) such triangles.
If there are 2 vertices on the circle and 1 inside circle then we can locate exactly 4 points on the circle. But 4 points lead exactly to 4 such triangles. Hence there are 4*comb(n,4) such triangles.
There are comb(n,3) triangles with all 3 vertices on the circle.

So, the solution is comb(n,6)+5*comb(n,5)+4*comb(n,4)+comb(n,3).

 

[•Cosmin]

Good job! All of them are solved. I can start thinking about some other short list.

[•mugurelionut]

A bit more explanations for problem 17:

Let's consider that our sequence consists of N positions numbered from 1 to N. Each position can be colored either white (0) or black (1). Thus, there are 2^N different sequences. However, some of them are equivalent by rotation. We are only interested in counting the number of equivalence classes.

According to Polya's lemma (or Burnside's lemma or the Cauchy-Frobenius lemma), we must first find out the group of permutations which decide if two sequences are equivalent (sequence A is equivalent to sequence B according to a permutation P if A(1)=B(P(1)), A(2)=B(P(2)), ..., and A(N)=B(P(N))).

Obviously, the permutation 2 3 4 ... N 1 is the main such permutation (which means that two sequences A and B are equivalent if: A(1)=B(2), A(2)=B(3), ..., A(N-1)=B(N) and A(N)=B(1) -- in other words if B is equal to A rotated by 1 position).

However, this is not the only such permutation: 3 4 ... N 1 2 is another one and, in general, every permutation corresponding to a rotation by a number of positions may decide the equivalence of 2 sequences. Because it is a group of permutation, the identity permutation 1 2 ... N must also be used (which simply says that any sequence is equivalent to itself).

Thus, there are N permutations which define the equivalence classes (one for each rotation from 1 to N-1 plus the identity permutation -- note that the identity permutation can be considered as an N-position rotation).

According to the lemma, the answer to our problem is the average number of fixed points of all these permutations.

Let's consider one of the permutations and let's assume that it has C cycles. Then, a fixed point for the permutation is a sequence A such that A=P(A). This implies that all the positions of A which are part of the same cycle must have the same value. Since we have two distinct possible values (0 and 1) for each position, a permutation with C cycles has 2^C fixed points.

Let's see now how many cycles a k-position rotation permutation has. Such a permutation implies that positions 1, k+1, 2k+1, ... are part of the same cycle, 2, k+2, 2k+2, ... are part of the same cycle, and so on. The number of such cycles is equal to gcd(k, N)  (note that this also works for the identity permutation which is an N-position rotation permutation).

Thus, the total number of fixed points is FP=2^gcd(1,N) + 2^gcd(2,N) + ... + 2^gcd(N,N). Since there are N permutations, the average number of fixed points is FP/N (I am not really sure  why FP is divisble by N, but it is ).

[•vlad_D]

@mugurelionut

If N is prime is easy to prove that FP is divisible by N.

If N is prime => FP = 2^1 + 2 ^ 1 + ..... 2^N = 2 * (N  - 1) + 2^N = 2(N - 1 + 2^(N-1))
2^(N-1) - 1 is divisible by N if N is prime by Fermat Little Theorem. => FP is divisible by N.

Proving it for N composite is left as an exercise for the reader 

[•S7012MY]

4).what is the answer for circles and spheres? Must the radius of the circles be equal?

[•S7012MY]

7) This one is really easy once you rewrite it as:
for i1 = 1,n
_for i2 = i1+1,n+1
__for i3 = i2+1,n+2
____…
_____for ik = ik–1 + 1,n+k-1
______print ‘*’

I hope I didn't missed anything but i3 goes from i2+1 to n+1 because initially it goes from i2 to n and then your re-writing isn't correct

[•Cosmin]

Petru you are wrong. Think about it some more.