Bad Combination

• Responsive

• Work involves Nato Phonetic Code

• Named Charlie

Great Speeches Ruined by Hobos

Deterioration

This slideshow requires JavaScript.

WMS 2009 cont

edit May 13 moved here as post was getting long

Recall the bijection from a path of exceedence n>0 to exceedence n-1

Now I think an alternate way is as follows

To those that want to figure this out themselves(the hints are hidden you have to highlight them):
1. Find the intuitive bijection between excess 1 to excess 0
2. Does this still work for 1 to 2 if not which ones of 1 are not in the image of 2?

highlight to reveal hidden contentTake the first portion of the path that goes above the diagonal to the point where it touches the diagonal again remove the first vertical and last diagonal and stick them onto the first part of the path that doesn’t cross lastly swap those

Binary Trees find a bijection from the binary trees to the catalan paths

highlight to reveal hidden content Interpret left as horizontal right as vertical whenever you can go left if stuck go right so for the above picture go left , left ,right, right

Partitions

Problem 7 count the number of ones in each partition of n and sum do the same for the number of distinct parts prove you get the same answer.

The generating function for the first is simple (0+x+2x^2+…..)(1+x^2+…)…
This is equal to (x+x^2+…)(1+x+x^2+..)(1+x^2+..)…
The interpretation of this is simple as well for a partition use x^k in the first bracket to replace k in a partition then a partition with m distinct parts is counted m times.

Problem 10. prove p_e(n)-p_o(n)=(-1)^{n-1}p_eo(n)
I someone knows a combinatorial proof that would be great. For generating functions the LHS is (1-x+x^2-x^3+..)(1-x^2+x^4-..)… which simplifies into
multiplying by and same for all odd powers of x simplifies into (1-x)(1-x^3)….
If anyone has a solution to a different problem in the set please post it here.

update May 22 added borders

My life

2009 WMC problems

These are solutions to problems 1 f) to i)

f) we could sum the left side and get sigma 1/2*n*(nCk)^2 and use sigma (nCk)^2=(2nCn) and show algebraically that the two sides are equal but the clever solution is to let one of the first n elements be special then we choose k from the first n make one special in k ways and choose n-k from the other n and for the right choose one of the first n to be special then choose the rest.

g) change one of the nCk to nC(n-k) so we are choosing m from the first n to be special the LHS chooses based on how many are of the first n.

h) this is basically g) except now note that we can choose m (j in this case) arbitrary so instead of choosing m we arbitrarily select thus the 2^k

i) consider n pairs and a loner the RHS is clear to count on the LHS some of the pairs have one chosen thus the 2^k * nCk and of the rest we know floor((n-k)/2) have both chosen in order to choose n and then we are either good or short one in which case we throw in the loner.

cannot get j) the trick is to prove that 2nCn is the number of paths in the 1st quadrant that don’t touch y=x I can’t prove this or understand how this will solve the problem but I think it may be similar to the proof of the formula for catalan numbers.

edit May 9, 2010

Prufer Sequence

to code the tree: the sequence is 3,2,5,7,5,2,7

to get the tree from this consider the leaves at the beginning 1,9,4,8 (don’t appear in the sequence) connect the smallest to the first number in our sequence or 1 to 3 since 3 appears no more 3 is now a leaf attach it to the next of our sequence or 2 and continue as so.

I must say this was really simple but for some reason I kept trying to do it backwards.

For problem j)  the first part everytime a path to (n,n) going horizontal first does touch y=x reflect the portion of the path until it touches y=x-1 except for the last horizontal part. To undo this simply take the last part that touches y=x-1 and reflect that portion after the first segment to that point then treat the rest of the path similarily. Note it cannot cross y=x-1 simply by the construction. Now if anyone can use this to solve problem j) that would be nice. edit nvm I should shoot myself for not realizing the obvious.

Hmm I may have wrote this up poorly. Actually this is really obvious if you write it as (1-4x)^(1/2)*(1-4x)^(1/2)=1/(1-4x)

WORKPLACE HAZARDS AT THE OFFICE

This slideshow requires JavaScript.

Inspiration from Romania 2003 Problem

This is fail but I committed to this when I chose this username so…

Okay so the solution is like assume that p(x^2)=f(x)g(x) and note that the roots of p(x^2) are the positive and negative square roots of p(x) now if the positive and negative square roots split up perfectly f(0) and g(0) are equal in absolute value. So a root +/-x_i are both in f(x) WLG then it is a root of the even function r(x^2)= f(x)+f(-x) since (x_i)^2 it is both a root of r(x) and p(x) their GCD is a integer non constant polynomial by the euclidean algorithm. Since p is irreducible though their GCD is p but p has greater degree than r contradiction.

Now we can extend that to prove that (x^2+x)^(2^n)+1 is irreducible similarly,
we prove that f(x)+f(1-x) is a polynomial of the form r(x^2+x) This is easy to see considering the factored form of this polynomial and noting replacing x by 1-x does not change the polynomial so the roots come in x_i and 1-x_i pairs hence the conclusion. So similar to above we have the roots split off but then consider the roots of f(x)+g(1-x) and note that for each of the 2^n (we can compute that all its roots are distinct) x_i either 1-x_i of x_i is a root of that equation but then we have a polynomial of degree no more than 2^n-1 with 2^n roots =><=.

By the way if anyone knows how to get latex to work here pm me.