Toy problems

These are problems I've heard about recently and seem cute.

Merge arrays. You are given an array x with m comparable objects followed by n empty cells. You are also given an array y with n comparable objects. Both x and y are sorted. Your task is to add to x the element of y such that x remains sorted. You may use only a constant amount of memory. [From TopCoder forums.]

Election winner. You are given an array containing votes. A candidate wins if he has more than half the votes. Your task is to find the winner. If there is no winner by the previous definition than you can choose as winner whoever you want. You may use only a constant amount of memory. [From the 0xDE blog.]

Handshake party. You are invited to a party. At the end you ask each person how meny times they shook hands. You notice that the response you receive is an odd number for an even number of people. Why? [Henry. Also in Combinatorics by van Lint.]

Handshake party, continued. You then ask each person with how many other people they shook hands. If no one is handshakeless then you expect to receive at least two identical answers. Why? [Combinatorics by van Lint.]

Sex in New York (Times). You are given a bipartite graph. Show that the sum of the degrees for the left nodes is equal to the sum of degrees for the right nodes. What is the relation between the average number of sexual parteners of women and the average number of sexual parteners of men? [From NYT, via WebDiarios de Motocicleta blog.]

Graphs at IOI 2007. Find a maximum weighted matching in an arbitrary graph knowing that the degree of the vertices is bounded by a constant. You are supposed to give a nice and simple implementation. [Via WebDiarios de Motocicleta; I don't know (yet) the `nice' answer. Here is the general case.]

PS1: Some of these are also on my webpage.

PS2: Did you notice the list of nice blog posts below?