公主的意中人

X10A · 发表于 2007-12-20 11:35:04

公主的意中人

www.ddhw.com

一个王国的公主到了结婚的年龄，于是向全国发出消息，要为公主选择合适的郎君。由于公主有着倾国倾城的美貌，各地的青年男子都赶来了。有将近好几千人。

www.ddhw.com

其实呢，公主心中早就已经有了意中人----一位年轻的侍卫。但是，按照王国的规定，公主只有权利决定如何选择丈夫，却不允许直接指定某个人。公主的问题就在于，不管她提出怎样的条件，由于来的应征者太多，难免不会出现比自己意中人在那方面更出色的人出现。

www.ddhw.com

公主的是公主的知心人，猜到了公主的想法。就想出了一条妙计。www.ddhw.com

www.ddhw.com

把选者意中人的方法定为：首先，公主和全部的应征者站成一个圈，然后，公主为一号，公主左边的人为二号，以次类推。然后，公主离开的队伍。那么，左边的人就变为一号了，其余的人的号码也都改变了。这时候规定，凡是单数的离开队伍。然后大家在重新遍号，再叫单数的离开，直到最后只剩一个人。当然，最开始站成一个圈的时候，不告诉所有人规则，等站好圈以后再通知规则。然后，只要巧妙的安排公主意中人的位置，就可以把保证绝对不会选到别人。

www.ddhw.com

现在的问题是，包括意中人在内的应征者有1345人，应该把公主的意中人安排到哪个位置去呢。

开开心心 · 发表于 2007-12-20 12:05:43

每次遍号时，只要能保持公主的意中人站在双号就可以

X10A · 发表于 2007-12-20 18:41:50

我题目好像没说明白，一旦站好排以后，大家的位置就不变了

开开心心 · 发表于 2007-12-20 18:58:57

这样啊！题目更不清楚。单数的离开队伍后，大家是怎样重新遍号，有规则吗？

yinyin · 发表于 2007-12-20 19:06:53

2¹⁰= 1024.

按现题述去理解，公主最初不用进去排队，队伍也没必要排成一圈。

本贴由[yinyin]最后编辑于：2007-12-20 11:57:47

HF: · 发表于 2007-12-20 19:32:05

I wonder why the candidates should form 一个圈, this prompt for a variation of the problem: all 1345 candidates form a circle, the princess pick the first person to remove, then the game start: go clockwise, keep the second person, remove the third,...(skip one, remove one...)

Since it is a circle, this process can go on, till only one person left.

Now, how the princess pick the first person if she want her lover to win the game?

yinyin · 发表于 2007-12-20 21:37:10

HF兄修改后的题才真有点意思。建议单独立题，版主推荐或给原创奖。

yinyin对新题已有答案，哪位朋友在三天（72小时）内首先给出答案并提供正确解题过程（计算机模拟、穷竭法除外），可得奖金200DD元。

本贴由[yinyin]最后编辑于：2007-12-21 11:13:0

idiot94 · 发表于 2007-12-20 22:06:55

茵茵老大，您应该为出新题的人奖励啊。。。：）

calala · 发表于 2007-12-21 04:56:03

322

If even, k=2k-1
else k=2k
end

Total -- Number to stay

1345 -- k, k=1,2,3,...

672 -- 2k, k=1,2,3,...

336 -- 2(2k-1), k=1,2,3,...

168 -- 2(2(2k-1)-1), k=1,2,3,...

84 -- 2(2(2(2k-1)-1)-1), k=1,2,3,...

42 -- 2(2(2(2(2k-1)-1)-1)-1), k=1,2,3,...

21 -- 2(2(2(2(2(2k-1)-1)-1)-1)-1), k=1,2,3,...

10 -- 2(2(2(2(2(2*2k-1)-1)-1)-1)-1), k=1,2,3,...

5 -- 2(2(2(2(2(2*2(2k-1)-1)-1)-1)-1)-1), k=1,2,3

2 -- 2(2(2(2(2(2*2(2*2k-1)-1)-1)-1)-1)-1), k=1,2

1 -- 2(2(2(2(2(2*2(2*2k-1)-1)-1)-1)-1)-1) = 322, k=1

本贴由[calala]最后编辑于：2007-12-20 20:58:50

本贴由[calala]最后编辑于：2007-12-20 21:1:26

yinyin · 发表于 2007-12-21 05:21:16

此坛有鼓励贴出创新题的机制，yinyin不便喧宾夺主啊。

yinyin已建议HF单独立题，版主推荐或给原创奖。给正确解题者奖是因为此坛暂时还没有相应的鼓励机制。

建议版主建立基金，为难题设奖。

X10A · 发表于 2007-12-21 08:38:18

一圈过后，剩下的人从最小号开始，再按一开始排号

642 · 发表于 2007-12-21 22:47:12

642

呵呵呵呵 · 发表于 2007-12-22 05:32:24

公主应这样选第一个人，以这个人为1顺时针数下去，意中人在642的位置上。

一般地，任意个人围成一圈，选一人从1开始顺时针编号，按以上规则淘汰至最后一人，则最后一人编号可以按以下公式求出：

1。若有2^m个人，则2^m号是最后一人。

呵呵，这个就不必证明了吧。也就是说：2^m个人时，第一个被淘汰人的右边位置最后被淘汰。

2。若有2^m+n个人，则2n号是最后一人。

当从1号开始，并淘汰了n个人时，此时还剩2^m个人，下一个要淘汰的是2n+1号，根据1，其右边位置即2n号最后被淘汰。

就此题而言，1345=1024+321，所以安全位置为2*321=642。

yinyin · 发表于 2007-12-22 08:48:16

答案和过程都正确！

yinyin · 发表于 2007-12-22 08:50:48

答案正确

，惜无过程。

yinyin · 发表于 2007-12-22 08:59:55

奖金200DD元将用于新的佳题解答。

孜孜不倦@. · 发表于 2007-12-22 10:22:39

哇。。。相当精辟

www.ddhw.org---

		自动登录	找回密码
密码			立即注册

动态微博

公主的意中人