最后剩下的数字？

圆圈上顺时针排列着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/

NxN行列有序的矩阵查找一个数，如何O(N)时间？

NxN行列有序的矩阵查找一个数，要O(N)的时间复杂度。

http://spellscroll.com/questionfull/248/

Maximum Consecutive Subsequence

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?

http://spellscroll.com/questionfull/247/

28,10,完全平方数

A = { 1, 2, 3, ...., 28}

证明: 如果从A中任意取10个数, 那么从这十个数中你可以找到一个子集, 这个子集中所有元素的积是完全平方数.

http://spellscroll.com/questionfull/246/

二人扑克游戏

(1)一副牌扣在桌上，庄家按顺序将牌一张张翻开。你可以在任何时候叫停（除非牌已翻完）。叫停之后再翻开下一张牌，如果花色为红，则你赢。
你的最佳策略是什么？
(2)一副牌扣在桌上，庄家按顺序将牌一张张翻开。你可以在任何时候叫停（除非牌已翻完）。叫停之后已翻开的红牌数减去黑牌数为你的所赢（或输，如果为负）。
你的最佳策略是什么

http://spellscroll.com/questionfull/57/

a set problem

what is the number of ordered triples
(A,B,C) of sets which have the property that
(i) The union of A,B,C is {1,2,3,4,5,6,7,8,9,10}
(ii) The intersection of these three is empty.


http://spellscroll.com/questionfull/53/

find a missing number

suppose you have a set of unsorted numbers from 1 to N (a big number, say 1 million). One number is missing, how to find that missing number most efficiently?

Adding the number then subtract N(N+1)/2 may not be possible since the number could be too big to store.

http://spellscroll.com/questionfull/48/

Distribute n distinguishable balls into r boxes

Suppose $n$ distinguishable balls are randomly distributed into $r$ boxes. If $S_r$ is the number of empty boxes, $S_r = X_1 + ... +X_r$ where $X_i$ is 1 or 0 according to whether box $i$ is empty or not, $1<=i<=r$.

Calculate:
(1) E[X_i]
(2) E[X_iX_j]
(3) E[S_r] and Var[S_r]

http://spellscroll.com/questionfull/224/

Black and White Sheep

A field contains a number of stationary black and white sheep. What simple condition will guarantee that a straight wire will exist which will separate the black sheep from the white sheep? What is the answer in n dimensions, rather than two?

http://spellscroll.com/questionfull/235/

Election Problem

Two candidates (R and L) are for the 2008 election. In the election, voters
are in a single line and are going to vote one by one. After each
voter makes the vote, the other voters immediately knows who he/she
voted for. Voters tend to stay with the ``winner's side'', if at the
moment the candidates have $x$ and $y$ votes respectively, the voter
will vote R with probability $x/(x+y)$, and vote L with probability
$y/(x+y)$.

Suppose R and L initially have $x0$ and $y0$ votes each ($x0$ and
$y0$ are far smaller than the total number of voters), and let $P$
be the final percentage of votes R receives.

Questions:
(1) what is $E(P)$?
(2) what is the distribution of random variable $P$?

http://spellscroll.com/questionfull/22/

不能使用除法运算

(1) 给一个数组A[1..n]，请在O(n)的时间里构造一个新的数组
B[1..n]，使得B[i]=A[1]*A[2]*…*A[n]/A[i]。不能使用除法运算
(2) 给定一个数组A[1..n]，求出任意n-1个数的乘积中最大的一个。
不能使用除法运算

http://spellscroll.com/questionfull/169/

Sample of D. E. Shaw puzzles

(1) You have twelve coins, one of which is known is known to be counterfeit and
therefore heavier or lighter than all the others. You also have a balance-pan
scale. In three weighings determine which coin is counterfeit and whether it
is heavier or lighter.
(2) You have ten big vats of 10-gram coins. Except that one of the vats contains
counterfeit coins, which weigh only 9 grams. You have an accurate (numerical)
scale. In one wieghing, determine which vat contains the counterfeit coins.
(3) What is the smallest number of coins this requires?
Same as above, except that any number of vats (including none) may contain
counterfeit 9-gram coins. In one weighing, find the counterfeit vats, using as
few coins as possible.

http://spellscroll.com/questionfull/217/

one dimensional random walk

one dimensional random walk, probability of being at a position >= m after n steps.

[pipizhupi (感受希望) 于 (Thu Mar 1 14:50:18 2007)
发布至 Quant@MITBBS.COM]

http://spellscroll.com/questionfull/213/

乘客上飞机

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

面积最大的n边形

如何用长为1，2，3，...,n的n条线段构成一个面积最大的n边形？

http://spellscroll.com/questionfull/185/

return k random numbers from a large linked list

There is a linked list of numbers of length N. N is very large and you don't know N. You have to write a function that will return k random numbers from the list. Numbers should be completely random.
给你一个长度为N的链表。N很大，但你不知道N有多大。你的任务是从这N个元素中随机取出k个元素。你只能遍历这个链表一次。你的算法必须保证取出的元素恰好有k个，且它们是完全随机的（出现概率均等）。

http://spellscroll.com/questionfull/170/

painting balls

You have a black box with N balls in it - each of a different color. Suppose you take turns as follows - randomly pick a ball in each hand,and paint the left hand ball the same color as the right hand ball. You replace both balls in the box before the next turn.

How many turns do you expect before all balls are the same color?

http://spellscroll.com/questionfull/118/

连庄 vs. 轮庄

两个赌徒A和B决定用如下规则开始赌博:
(1) 初始二人均为0分, 每局胜者得1分,先积满n=12分者为最后胜者.
(2) 另外每局需要挑选一人当庄, A当庄胜率为p=0.7, B当庄胜率为q=0.6.
有两种选庄规则, 一种是轮流当庄, 另一种是胜者连庄. 现在假设第一局由A当庄, 请问那种选庄规则对A更有利?

http://spellscroll.com/questionfull/241/

N赌徒问题

N个赌徒参加一场赌局，刚开始时第i个赌徒的赌本为a_i元(a_i为正整数)，每一轮，随机抽出两个赌徒进行公平赌博，败者交给胜者一元，如果某个赌徒输光了则他会离开赌局。整个赌局一直持续下去直到某个赌徒赢得了所有的钱才结束。求:
(1) 赌局能够持续的轮数的期望值
(2) 第i个赌徒能够成为最终胜者的概率
(3) 当N=3时,所有3个赌徒都在场的轮数的期望值

http://spellscroll.com/questionfull/240/

brain teaser

http://www.mitbbs.com/article_t/JobHunting/31310013.html
发信人: BigGump (gump), 信区: JobHunting
标 题: brain teaser
发信站: BBS 未名空间站 (Thu Oct 16 23:48:03 2008)

A = { 1, 2, 3, ...., 28}

证明: 如果从A中任意取10个数, 那么从这十个数中你可以找到一个子集, 这个子集中
所有元素的积是完全平方数.

请教算法题目

http://www.mitbbs.com/article_t/JobHunting/31310312.html
发信人: skydoor (海阔天空), 信区: JobHunting
标 题: 请教算法题目
发信站: BBS 未名空间站 (Fri Oct 17 17:46:36 2008)

平面里面n个点,请问,如果找出靠的最近的两个点,要求nlogn.

http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairDQ.html

a problem

http://news.mitbbs.cn/article_t/Quant/31186579.html
发信人: GGSS (hoping), 信区: Quant
标 题: a problem
发信站: BBS 未名空间站 (Fri Oct 17 09:02:31 2008)

N people walk on a one-direction road. Let Xi be the speed for ith people,
where Xi independently, identically follows some distribution f(x). If Xi>
Xj, then i will catch up j and keep the same speed as j, so they will crowd
together. The question is what is the expected number of people crowd
tighter after a long time.

请教一道面试题

http://www.mitbbs.com/article_t/JobHunting/31310332.html
一个SORTED ARRAY，例如 A[]＝{0, -10, 20, 30, 40, 50, -60, 70, 80, 90, 100}(注意是按绝对值来排序)，一个数NUM，求所有相加等于NUM的两个数的组合，例如NUM＝40，答案是{0，40}，{-10, 50}，{-60, 100}。要求O(N)。感觉要是按大小来排序还好办，但按绝对值来排序我就糊涂了，请高手指教。
No extra storage space, so no hash table.

请教一个随机漫步赌博的问题

http://news.mitbbs.cn/article_t/Quant/31186248.html
http://www.mitbbs.com/article_t/Mathematics/31162241.html
http://tieba.baidu.com/f?ct=335675392&tn=baiduPostBrowser&sc=4705270767&z=467963534&pn=0&rn=50&lm=0&word=%CA%FD%D1%A7#4705270767
发信人: paoti (paopao2003), 信区: Mathematics
标 题: 请教一个随机漫步赌博的问题。。。。
发信站: BBS 未名空间站 (Sun Oct 12 03:49:52 2008)

最简单的随机漫步，你现在有M块钱,每次赌博要么赢一块钱，要么输1块钱，输赢概率
是0.5，这是一个简单的随机漫步。。。

我想求一下在赌到第n次之前(包括第n次)，我亏光M元钱的概率是多少？

比如说，我现在有10块钱，我想算一下赌到第20次之前(包括第20次)我会亏光10块钱的
概率。M=10,n=20,

这个解是什么？好像随机过程里没有写过。。。

谢谢！！！！！！！！！！！