Some stuff » face

a card problem

admin — Sun, 26 Sep 2010 05:33:15 +0000

Here is a problem quoted from fakalin. A full deck of cards has 52 cards. Suppose 10 of them were face up and 42 were face down. You are in a dark room holding the deck. How do you rearrange the deck into two subdecks so that they have the same number of cards facing up?

The cards can be flipped. So first, the specific numbers don’t matter. They don’t even have to be even numbers. The answer is simple.

Say there are \(n\) cards up in the full deck. If you just divide the deck without flipping cards, then however you divide, one subdeck will have \(m\in [0,n]\) cards up, and the other subdeck will have the complement \(n-m\) cards up. So take \(n\) cards out of the original deck as subdeck A, and flip them over. If this subdeck A had \(m\) cards up originally, now it has \(n-m\) cards up. In the remaining cards forming subdeck B, there were already \(n-m\) cards up. So the two subdecks have an equal number of cards up.

red-blue cross problem

admin — Sat, 11 Apr 2009 06:10:47 +0000

Here is a problem described to me by fakalin. Given n red points and n blue points, no three of which are collinear, prove that there exists a pairing of red and blue points such that the line segments connecting each pair do not intersect.

The solution is straightforward though it took a while to identify after it was already staring me in the face.

With each pairing is associated a total length (sum of line segment lengths). Since there are a finite number of pairings, there is a minimum length pairing. We claim this pairing must be one that satisfies the problem statement.

Suppose it were not, then there are some 2 red and 2 blue points such that the pairs’ connecting line segments cross. Then uncross the two pairs. This can be done because the points are not collinear. By uncrossing, the sum of the pairs’ segment lengths strictly decreases and therefore the total length also decreases. This contradicts the supposition. Therefore the claim is true.

However, note that a pairing that satisfies the statement need not be minimum total length. (The minimum total length doesn’t even need to be unique.) Nevertheless, an algorithm for reaching a solution is to start with any pairing, then identify any crossed pairs and uncross them. During this process, crossed pairs count may even increase for a time, but total length always decreases strictly at each step. Therefore, the algorithm will terminate, either when a valid pairing is reached, or when the minimum total length is reached, which also gives a valid pairing.

An extended question is, given the valid pairing, can a non-self-intersecting red-blue alternating path connecting all the points be found? I believe the answer is yes.

funny money worldwide

admin — Fri, 16 May 2008 07:03:22 +0000

The question came up about China being both a recipient and giver of foreign aid. Actually this happens with many countries. On the face of it, this seems like an absurd and illogical situation, but it brings up interesting questions about these funny money flows. To understand this, we need to look at these transactions beyond the mere exchange of money in the bank, and we need not stop with foreign aid.

When countries or individuals give, it is not a simple money transaction, but it is to fulfill some economic, political, social, or moral directive. Economically, a household or a country may be both an investor and a borrower, as this may improve the rate of return. Politically, a country may use aid for leverage, and aid in this case is simply a mediator of complicated leverage relationships that happen to have cycles. Socially, much the same happens, except in this case it is a mediator of social cohesion and community. Morally, the decision to give may be completely independent of one’s own financial condition, and hence there is no dilemma; an excellent example is that a street-begger may also give, and in fact people are often moved by this. Something less dramatic is more evident: by living in a community, everyone is receiving some form of services of value, but that does not prevent that person from giving.

Sometimes, direct money transactions given in numeric terms tend to obscure the above points that, in retrospect, seem fairly obvious.