Problem 2 (Probability):

100名乘客要上飞机，飞机上100个座位。第一个乘客不按号，随便乱坐，剩下的人都安分守己，会对照自己的座位号（第二个去2号位，第三个去3号位，so on and so forth），除非座位已经被占，他们才会随即挑一个，请问第100个乘客（最后一个）能坐自己号的概率是多少？

 

递归,n-2/2*(n-1)

 

Problem 3 (Probalility):

flip a fair coin, 你期望扔多少次， 才能扔出俩脑袋连一起的？

 

6

 

Problem 4 (Mathematics):

derivative of x^x

 

d(x^x)/dx

 

Problem 5 (IT):

You are given an array of integer of size N (A[0],A[1],A[2],...A,[N-1]) containing both negative and non-negative integers. Design an efficient algorithm to find the sub sequence A[i],A[i+1],A[i+2]...,A[j] having the maximum summation (A[i]+A[i+1]+A[i+2] + ...+A[j] have the highest sum). What is the complexity of your algorithm?

 

转黄亦元同学处阅。

 

Problem 6 (Most difficult one):

Alice and Bob play a game in which they take turns removing stones from a heap that initially has n stones. The number of stones removed at each turn must be one
less than a prime number. The winner is the player who takes the last stone. Alice plays first. Prove that there are infinitely many n such that Bob has a winning strategy. (For example, if n = 17, then Alice might take 6 leaving 11; then Bob might take 1 leaving 10; then Alice can take the remaining stones to win.)

 

反证。