最后剩下的数字？

圆圈上顺时针排列着1,2,3,....2000 这2000个数. 从1开始,顺时针隔一个拿走一个(1最先被拿走,下一个是3). 问最后剩下是哪一个数字.

http://spellscroll.com/questionfull/219/

Asymmetric random walk problem

Asymmetric random walk problem:

P(X_i = 1) = p, and
P(X_i = -1) = 1-p for all i>0.

let S_n = sum_{i=0}^n X_i, S_0=0, and
S_* = max{S_0, S_1, ..., S_n} where 1<=k<=n.

let n, m, b are even positive integers
such that b<=m, m<=n, and 2m-b<=n,

then
P(S_*>=m, S_n=b) = ?

http://spellscroll.com/questionfull/212/

抛多少次硬币？求期望

(1) What's the expected number of tosses needed to get
a first consecutive 2 heads?
(2) same question for getting THHTHT?

http://spellscroll.com/questionfull/195/

Find the magic number

What is the smallest number
that cannot be written as the sum of 6, 9, and 20, yet
any integers above the number can be written as the
sum of the three numbers? (Note: the three numbers can
be repeated as many times as needed.)

For example, 55 = 20 + 20 + 9 + 6, yet 11 can not be
written as the sum of any combination of 6, 9 and 20.
However, 11 is not the answer because 13 cannot be
expressed by the sum of 6, 9, 20 either.

http://spellscroll.com/questionfull/194/

烧绳子

两根绳子，长度不同，绳子各段燃烧的速度不同
但绳子烧完的时间是一样的，都是1小时，问用
一盒火柴和这样两根绳子，怎么测出15分钟?

http://spellscroll.com/questionfull/193/

第n个重量

有m块石头，每块石头的重量已知，有可能有几块石头的重量相等。选择一些石头装进
背包，这样背包一共最多可能有2^m个可能的重量。把这些重量排序，第n个重量是多少？
由于组合数爆炸，把所有可能穷举再排序是不可行的。

http://spellscroll.com/questionfull/250/

Find the missing number

An array A[1..n] contains all the integers from 0 to n except one. It
would be easy to determine the missing integer in O(n) time by using an
auxilary array B[0..n] to record which numbers appear in A. In this
problem however we cannot access an entire integer in A with a single
operation. The elements of A are represented in binary, the only
operation we can use to access them is " Fetch the jth bit of A[i] " ,
which takes constant time. Find the missing integer in O(n) time using
only that operation.

http://spellscroll.com/questionfull/249/