公主的意中人
一个王国的公主到了结婚的年龄,于是向全国发出消息,要为公主选择合适的郎君。由于公主有着倾国倾城的美貌,各地的青年男子都赶来了。有将近好几千人。
其实呢,公主心中早就已经有了意中人----一位年轻的侍卫。但是,按照王国的规定,公主只有权利决定如何选择丈夫,却不允许直接指定某个人。公主的问题就在于,不管她提出怎样的条件,由于来的应征者太多,难免不会出现比自己意中人在那方面更出色的人出现。
公主的是公主的知心人,猜到了公主的想法。就想出了一条妙计。
把选者意中人的方法定为:首先,公主和全部的应征者站成一个圈,然后,公主为一号,公主左边的人为二号,以次类推。然后,公主离开的队伍。那么,左边的人就变为一号了,其余的人的号码也都改变了。这时候规定,凡是单数的离开队伍。然后大家在重新遍号,再叫单数的离开,直到最后只剩一个人。当然,最开始站成一个圈的时候,不告诉所有人规则,等站好圈以后再通知规则。然后,只要巧妙的安排公主意中人的位置,就可以把保证绝对不会选到别人。
现在的问题是,包括意中人在内的应征者有1345人,应该把公主的意中人安排到哪个位置去呢。
每次遍号时,只要能保持公主的意中人站在双号就可以 |
210 = 1024. 按现题述去理解,公主最初不用进去排队,队伍也没必要排成一圈。 本贴由[yinyin]最后编辑于:2007-12-20 11:57:47 |
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? |
HF兄修改后的题才真有点意思。建议单独立题,版主推荐或给原创奖。 yinyin对新题已有答案,哪位朋友在三天(72小时)内首先给出答案并提供正确解题过程(计算机模拟、穷竭法除外),可得奖金200DD元。 本贴由[yinyin]最后编辑于:2007-12-21 11:13:0 |
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不便喧宾夺主啊。 yinyin已建议HF单独立题,版主推荐或给原创奖。给正确解题者奖是因为此坛暂时还没有相应的鼓励机制。 建议版主建立基金,为难题设奖。 |
公主应这样选第一个人,以这个人为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。 |
答案和过程都正确! |
答案正确,惜无过程。 |
奖金200DD元将用于新的佳题解答。 |
欢迎光临 珍珠湾ART (http://66.160.158.134/) | Powered by Discuz! X3 |