Thursday, July 16, 2009

2 fun maths puzzles

I guess they're fun because I figured them out! If there's anyone actually reading this, post your solutions in the comments. If I get any responses I'll post solutions and if I don't, I might not.

  1. On average, given a random permutation of N items, how many elements do we expect to stay put? E.g. if N=3 there are only 6 perumtations, 1 leaves all 3 in place, 3 leave 1 in place and 2 shift all of them (left or right). So that's (1*3 + 3*1) / 6 = 1.
  2. On average, given a random function from 1..N->1..N which may or may not be injective or surjective (that is there may be X and Y such that f(X) = F(Y) and there maybe be a Z such that f(X) != Z for any X), how many elements do we expect to stay put - f(X)=X? E.g. if N=2 there are 4 possible functions, f(X) = X, f(X) = 1, f(X) = 2 and f(X) = 3-X. These fix 2, 1, 1 and 0 elements respectively. So on average that's (2+1+1)/4 = 1 but what about larger N?
Post a Comment