A Mathematical Problem in ACM/ICPC Danang 2007

I have used a program to check the following fact. However, I prefer a non-computational proof.

Prove that the following 3 generators generate A_6 (all even permutations of 6 elements): (14)(23), (25)(34) and (36)(45).

If anyone have any idea, please tell me.

Two Algorithm Problems

I used one hour to solve the following problem. If you have solution too, welcome to share it here.

Given int N,
you are given array (1,2,3,…,N)
The array is permuted.
Now deleted one number and replace it with another number on list
e.g. if we replace i by j, there will be no "i" and two "j" in the list
You are given the modified array of size N.
Use a linearly time w/ const memory algorithm (you can read the array only; you cannot change the array) to find i and j

This problem reminds me one problem I met in my algorithm class in Stony Brook:

We have an array of n numbers. What we know is that there is one number occurring more than N/2 times in the array. Find the mode of these n numbers with linear time w/ constant memory algorithm.

雜記20070914

順利完成了那件從未出過30歲前要做的工作。今朝「交貨」，才知道這件「貨物」比想像中重要。希望他順順利利，不再需要我的「貨」吧。

今日，李衛平用了一個偉大的證據，去證明三維空間比二維空間好得多。他首先在白板上畫了一條河，一男一女在河的兩邊。然後他說："The boy cannot swim, then in 2-dim space, he cannot cross the river (to meet the girl and make...)."續著的是："But if this is a 3-dim space, he can jump acroos the river."「金句王」真的無封錯他。

我無法想像為甚麼會有MATH310學生在第二個星期要求make appointment。不過，我想她之前也無法想像我是會拒絕的。我是這樣跟她說的："Making appointments will be accepted only with reasons proving you are NOT available (say you have lectures in both office hours) during the office hours."

ACM做問題。見到以下兩條式，真想叫人爆粗：

0.41 * 0.61 * 6.91 * 10.89 = 18.81999999
0.41 + 0.61 + 6.91 + 10.89 = 18.82