r*******s
发帖数: 303 | 1 mathproblems.info上的。
There is a street of length 4. The street is initially empty. Cars then come
along to fill the street until there is no space left that is large enough
to park a car in. Every car is length 1. Drivers will choose a location to
park at random among all possible locations left. No consideration, whether
good or bad, is given to other cars. What is the expected number of cars
that will be able to park?
Answer
11/3 - 4/3*ln(2) |
n****e
发帖数: 629 | 2 再次推荐一下这个网站……
上面的题我都做了。很好玩。
come
enough
whether
【在 r*******s 的大作中提到】
: mathproblems.info上的。
: There is a street of length 4. The street is initially empty. Cars then come
: along to fill the street until there is no space left that is large enough
: to park a car in. Every car is length 1. Drivers will choose a location to
: park at random among all possible locations left. No consideration, whether
: good or bad, is given to other cars. What is the expected number of cars
: that will be able to park?
: Answer
: 11/3 - 4/3*ln(2)
|
p*****k
发帖数: 318 | 3 anyone interested in the general case that street has a length
of x? or equivalently we could fix the street length as 1 and
vary the car size. |
n****e
发帖数: 629 | 4 maybe we can find an asymptical solution first?
【在 p*****k 的大作中提到】
: anyone interested in the general case that street has a length
: of x? or equivalently we could fix the street length as 1 and
: vary the car size.
|
n****e
发帖数: 629 | 5 猜想
when x->\inf, f(x) -> x - ln(x)
【在 n****e 的大作中提到】
: maybe we can find an asymptical solution first?
|
r*******s
发帖数: 303 | 6 结果趋近于3/4 * length.
程序算的。不知道怎么严格解。
【在 p*****k 的大作中提到】
: anyone interested in the general case that street has a length
: of x? or equivalently we could fix the street length as 1 and
: vary the car size.
|
n****e
发帖数: 629 | 7 可以先列个微分方程嘛
然后……f(x)=x是通解……然后我也不知道
【在 r*******s 的大作中提到】
: 结果趋近于3/4 * length.
: 程序算的。不知道怎么严格解。
|
r*******s
发帖数: 303 | 8 我是求积分方程
给定x 的长度，如果第一辆车停在 y 处，就把停车场分成两段了。
f(x) = int_0^(x-1) [f(y)+f(x-1-y)] dy/(x-1) + 1
初始条件是 f(x) = 0, 0<=x<=1
f(x)=1 1
几行程序就可数值解了。
f(4)=2.74,跟严格解是一致的。
得到的结果是很快就收敛到f(x)=3/4*x了。
【在 n****e 的大作中提到】
: 可以先列个微分方程嘛
: 然后……f(x)=x是通解……然后我也不知道
|
p*****k
发帖数: 318 | 9
redtulips, that's a very nice solution.
the asymptotic result for large n is c*x-(1-c)+O(1/x^n).
the coefficient c is:
int{from 0 to infty} dt exp{-2*int{from 0 to t} ds [1-exp(-s)]/s}
~0.747598, which is indeed very close to 3/4.
the earliest reference is
A.Renyi, "On a One-Dimensional Problem Concerning Random Place Filling" (1958)
【在 r*******s 的大作中提到】
: 我是求积分方程
: 给定x 的长度，如果第一辆车停在 y 处，就把停车场分成两段了。
: f(x) = int_0^(x-1) [f(y)+f(x-1-y)] dy/(x-1) + 1
: 初始条件是 f(x) = 0, 0<=x<=1
: f(x)=1 1: 几行程序就可数值解了。
: f(4)=2.74,跟严格解是一致的。
: 得到的结果是很快就收敛到f(x)=3/4*x了。
|
