c**********e
发帖数: 2007 | 1 一个蛋糕，切成连续的n块，有m个豆，问如果每小块上放一种豆，并且要求相邻的2块
上的豆不一样，有多少种方法。
？？？
一条东西向长街，你站在街中间，街北是一排门，你有一把钥匙，请写出一种策略，要
求X/N在最坏情况下最少，X为你到达正确的门时所走的总路程，N为正确的门距原点的
距离，可以假设门与门之间距离为1。 | C***m
发帖数: 120 | 2 第一题，如果n块蛋糕两两不同，用递归的方法可以做。如果不区分n块蛋糕，没有想法。
第二题，X/N在最坏情况下最少。这个是说 min E(X/N)吗？谁能帮忙指点一下，谢谢。 | l*******z
发帖数: 108 | 3 I saw these question in the test of WorldQuant. They are not easy! | k*****y
发帖数: 744 | 4 My naive guess for the second question is:
move right to 1,
move left to -2,
move right to 4,
move left to -8
and so on.
Since to ensure X/N is bounded the new increment should be at least
proportional to the sum of the previous increments.
【在 c**********e 的大作中提到】
: 一个蛋糕，切成连续的n块，有m个豆，问如果每小块上放一种豆，并且要求相邻的2块
: 上的豆不一样，有多少种方法。
: ？？？
: 一条东西向长街，你站在街中间，街北是一排门，你有一把钥匙，请写出一种策略，要
: 求X/N在最坏情况下最少，X为你到达正确的门时所走的总路程，N为正确的门距原点的
: 距离，可以假设门与门之间距离为1。
| x******a
发帖数: 6336 | 5 m个豆是有几种？
最坏情况什么意思？
【在 c**********e 的大作中提到】
: 一个蛋糕，切成连续的n块，有m个豆，问如果每小块上放一种豆，并且要求相邻的2块
: 上的豆不一样，有多少种方法。
: ？？？
: 一条东西向长街，你站在街中间，街北是一排门，你有一把钥匙，请写出一种策略，要
: 求X/N在最坏情况下最少，X为你到达正确的门时所走的总路程，N为正确的门距原点的
: 距离，可以假设门与门之间距离为1。
| a****h
发帖数: 126 | 6 My answers are as following, not sure... yet, anyone can confirm?
m^n - (n-1)*m^(n-1) + (n-2)*m^(n-2) -.... m
m^n : all the possibilities.
(n-1)*m^(n-1): If two neighboring cakes have the same peas, they can be
combined as one cake. all the possibilities with n-1 cakes, with conditions
considered in the next case considered twice.
(n-2)*m^(n-2): the three continuous cakes have the same peas, considered
twice in the last condition, needs to be corrected here.
so on | l*******3
发帖数: 186 | 7 看到蛋糕就开始流口水了，没法做题了呀
【在 c**********e 的大作中提到】
: 一个蛋糕，切成连续的n块，有m个豆，问如果每小块上放一种豆，并且要求相邻的2块
: 上的豆不一样，有多少种方法。
: ？？？
: 一条东西向长街，你站在街中间，街北是一排门，你有一把钥匙，请写出一种策略，要
: 求X/N在最坏情况下最少，X为你到达正确的门时所走的总路程，N为正确的门距原点的
: 距离，可以假设门与门之间距离为1。
| x*********i
发帖数: 55 | 8 My two cents on the second question.
For any stochastic or deterministic strategy, you should always go to the
nearest unchecked door either on your left or on your right.
Based on the above principle, suppose you are p steps away from the nearest
unchecked door on your left and q steps away from the nearest unchecked door
on your right, then with probability q/(p+q) you go left and with
probability p/(p+q) you go right.
【在 c**********e 的大作中提到】
: 一个蛋糕，切成连续的n块，有m个豆，问如果每小块上放一种豆，并且要求相邻的2块
: 上的豆不一样，有多少种方法。
: ？？？
: 一条东西向长街，你站在街中间，街北是一排门，你有一把钥匙，请写出一种策略，要
: 求X/N在最坏情况下最少，X为你到达正确的门时所走的总路程，N为正确的门距原点的
: 距离，可以假设门与门之间距离为1。
| E*****T
发帖数: 1193 | 9 1.蛋糕是圆形正常切的话，a(2)=m(m-1), a(n)=m(m-1)^{n-1}-a(n-1).
a(n)=(m-1)^n+(-1)^n(m-1)
2.我算出来是 正坐标到达的点a_n是个等比数列，比值q无理数介于2,3之间，负坐标b_
n是个等比数列，且b_n=\sqrt{1+q}a_n,然后再用取整函数。
原题就是找出序列{a_n},{b_m}使得min(无穷的情况是inf){(a_n+1)/(2A_n+2B_n),(b_m
+1)/(2A_{n+1}+2B_n)}最大，然后再大量的计算。 | s********r
发帖数: 529 | 10 可以展开来讲讲不？多谢大牛啦！
b_
_m
【在 E*****T 的大作中提到】
: 1.蛋糕是圆形正常切的话，a(2)=m(m-1), a(n)=m(m-1)^{n-1}-a(n-1).
: a(n)=(m-1)^n+(-1)^n(m-1)
: 2.我算出来是 正坐标到达的点a_n是个等比数列，比值q无理数介于2,3之间，负坐标b_
: n是个等比数列，且b_n=\sqrt{1+q}a_n,然后再用取整函数。
: 原题就是找出序列{a_n},{b_m}使得min(无穷的情况是inf){(a_n+1)/(2A_n+2B_n),(b_m
: +1)/(2A_{n+1}+2B_n)}最大，然后再大量的计算。
| E*****T
发帖数: 1193 | 11 题目1：就是求1到n这些位置，各放一种豆，相邻不同种且首尾不同种的情况。
对n做递归，a(n)=从1到n仅相邻不同的放法-从1到n相邻不同且首位不同的放法
=m(m-1)^{n-1}-a(n-1)
然后把m(m-1)^{n-1}写成(m-1)^n+(m-1)^{n-1}就可以算了。
题目2：又算了一次，之前忽略了一个常数，结果应该是两边均为类Fibonacci数列，也
就是每一项的值均为前面三项的线性和,通项公式可由特征根法解出。然后那个比值是1
/9
假设走法是对于两个正整数数列{a_n}{b_m}(a_0=b_0=0方便以后计算），由原点出发，
先到达坐标a_1,再回到-b_1,在走到a_2,......，令A_n,B_n分别为a_n,b_n的前n项和。
(1)走到a_n+p(其中1<=p<=a_{n+1}-a_n)所用的路程为2(A_n+B_n)+a_n+p,
走到b_m+q(其中1<=q<=b_{m+1}-b_m)所用的路程为2(A_{m+1}+B_m)+b+m+q,
题目是找到{a_n}{b_m},使得所有 路程/距离（取遍m,n,p,q）中的min或者inf最大。容
易看出，min都是在p=1或者q=1时取得的，所以，题目等价于找到{a_n}{b_m},使得
min{(A_n+B_n)/(a_n+1),(A_{m+1}+B_m)/(b_m+1)|m,n取所有非负整数}最大。
(2)证明当集合{(A_n+B_n)/(a_n+1),(A_{m+1}+B_m)/(b_m+1)|m,n取所有非负整数}中所
有元素都相等=t时min取得最大。然后我们再求t的最大值.
(3)（A_n+B_n)/(a_n+1)=t对所有n成立，从而(a_{n+1}+b_{n+1})/(a_{n+1}-a_n)=t,解
出b_{n+1}=...(*)
同理，(A_{m+1}+B_m)/(b_m+1)=t,首先m=0推出a_1=t,然后
(a_{m+2}+b_{m+1})/(b_{m+1}-b_m)=t,解出a_{m+2}=...(**),把(*)代入(**)可以看出a
_{n+3}是a_{n+2},a_{n+1},a_n的线性和。更简单的，令c_n=a_{n+1}-a{n}，可以得到c
_{n+2}^2-(t^2-2t)c_{n+1}+t^2c_n=0。
(4)如何确定t的最小值：注意到c_n必为正数列，从而用特征根法解c_n时，x^2-(t^2-
2t)x+t^2=0不可能有复根，从而t>=4恰好为整数,t的最小值为4，求得c_n=(5+6n)*4^n,
再求和得到a_n的通项公式。同理可求出b_n
(5)从而，路程/距离 的最小值的最大值为2t+1=9.
【在 s********r 的大作中提到】
: 可以展开来讲讲不？多谢大牛啦！
:
: b_
: _m
|
|
