s*****j
发帖数: 6435 | 1 On a table is a row of fifty coins, of various denominations. Alice picks
a coin from one of the ends and put it in her pocket; then Bob choose a coin
from one of the (remaining) ends, and the alternation continues until Bob
pockets the last coin.
prove that Alice can play so as to guarantee at least as much money as Bob. |
s***n
发帖数: 1280 | 2 看奇偶项的总和哪个大。总项数是偶数时，先选的那个在选奇偶项上有主动权。
picks
coin
Bob.
【在 s*****j 的大作中提到】
: On a table is a row of fifty coins, of various denominations. Alice picks
: a coin from one of the ends and put it in her pocket; then Bob choose a coin
: from one of the (remaining) ends, and the alternation continues until Bob
: pockets the last coin.
: prove that Alice can play so as to guarantee at least as much money as Bob.
|
s*****j
发帖数: 6435 | 3 exactly.
【在 s***n 的大作中提到】
: 看奇偶项的总和哪个大。总项数是偶数时，先选的那个在选奇偶项上有主动权。
:
: picks
: coin
: Bob.
|
x***1
发帖数: 999 | 4 有意思，妙，先选的可以从两端的任何一端拿，挑总数最大的那一端拿起，剩下的两端
，无论那端，都是最小的（之和）。
【在 s***n 的大作中提到】
: 看奇偶项的总和哪个大。总项数是偶数时，先选的那个在选奇偶项上有主动权。
:
: picks
: coin
: Bob.
|
t******l
发帖数: 10908 | 5 这题是中学老师投机取巧了好像。
这题貌似有一个很简单的 stronger solution，就是 A 总是从两头里选最大的那个，
剩下那个给 B。（前提是总 coin 数是偶数，不用把一个硬币切成两半）。
这样 a(k) >= b(k)，所以 Sigma(a(k)) >= Sigma(b(k))。不等式性质。 |
t******l
发帖数: 10908 | 6 我理解错了题目，应该是 A 先选然后 B 选，然后换过来 B 先选再 A 选。
然后再换过来。
否则这题目不可能这么简单。
【在 t******l 的大作中提到】
: 这题是中学老师投机取巧了好像。
: 这题貌似有一个很简单的 stronger solution，就是 A 总是从两头里选最大的那个，
: 剩下那个给 B。（前提是总 coin 数是偶数，不用把一个硬币切成两半）。
: 这样 a(k) >= b(k)，所以 Sigma(a(k)) >= Sigma(b(k))。不等式性质。
|
t******l
发帖数: 10908 | 7 这个理解也错了，应该是 A 选一次，然后 B 选一次，但 B 是在新的 list 上
选，B 每次也有两个 choice。这样就不是那么简单。
【在 t******l 的大作中提到】
: 我理解错了题目，应该是 A 先选然后 B 选，然后换过来 B 先选再 A 选。
: 然后再换过来。
: 否则这题目不可能这么简单。
|
t******l
发帖数: 10908 | 8 这样 make sense，不过这题是不是有比奇偶性更 strong 的 solution？
【在 t******l 的大作中提到】
: 这个理解也错了，应该是 A 选一次，然后 B 选一次，但 B 是在新的 list 上
: 选，B 每次也有两个 choice。这样就不是那么简单。
|
x***1
发帖数: 999 | 9 有些题给的条件不明说，得去猜，这道题就这样，如果题里告诉说已知处在奇数和偶数
的coins的和，那么大多数人会做，问题是题里没有明说，谁那儿知道这些条件啊。
【在 t******l 的大作中提到】
: 这个理解也错了，应该是 A 选一次，然后 B 选一次，但 B 是在新的 list 上
: 选，B 每次也有两个 choice。这样就不是那么简单。
|
t******l
发帖数: 10908 | 10 这个主要是教娃，反正大家也不会真的身体力行了不是。
教娃最终还得靠事后诸葛亮，只要合理解释就行了。
比如这题进行事后诸葛亮的话，属于 partitioning problem，但其中有一半的 choice
是对手 make 的。要选到两个 partition 里较大的那个 partition。
这种只能合理猜测，其中一个猜测是能不能得到 “stable” 的 partition，也就是不
管 B 如何选择，A 总是可以 counter offer，最终导致 stable 的 partition。如果
再猜测用着色算法 partitioning 的话，这个只能是奇偶分开才能 “stable”，
binary choice 但 order 不可控的缘故
当然是不是存在不 “stable” 的 partition 也能保证 A 比 B 大的策略，我不知道。
：有些题给的条件不明说，得去猜，这道题就这样，如果题里告诉说已知处在奇数和偶
数的coins的和，那么大多数人会做，问题是题里没有明说，谁那儿知道这些条件啊。
： |
|
|
t******l
发帖数: 10908 | 11 应该有个基于这个 solution 但更 strong 的 solution，基本就是 recursive down，
灵活选择奇偶，不一路都 stick 在相同的奇偶。
：有些题给的条件不明说，得去猜，这道题就这样，如果题里告诉说已知处在奇数和偶
数的coins的和，那么大多数人会做，问题是题里没有明说，谁那儿知道这些条件啊。
： |
t******l
发帖数: 10908 | 12 这个不行，recursive 不能保证最大，因为是 difference 加起来，而前面的决定会改
变 trajectory，导致递归不变式不能保持。
还是得一开始就确定奇偶后 stick to 一开始的 decision。
：应该有个基于这个 solution 但更 strong 的 solution，基本就是 recursive down
，灵活选择奇偶，不一路都 stick 在相同的奇偶。
： |
N*******M
发帖数: 3963 | 13 “prove that Alice can play so as to guarantee at least as much money as Bob
.“
这是人说的话吗？ 五年纪小学生会这样问吗？五年纪小学生会明白这问题吗？ |
N*******M
发帖数: 3963 | 14 美国大学的原题参考：
On a table there is a row of fifty coins, of various denominations (the
denominations could be of any values). Alice picks a coin from one of the
ends and puts it in her pocket, then Bob chooses a coin from one of the ends
and puts it in his pocket, and the alternation continues until Bob pockets
the last coin. Prove that Alice can play so that she
guarantees at least as much money as Bob.
-Answer:
Alice adds the values of the coins in odd positions 1st, 3rd, 5th, etc.,
getting a sum Sodd. Then she does the same with the coins placed in even
positions 2nd, 4th, 6th,etc., and gets a sum Seven. Assume that
Sodd ≥ Seven. Then she will pick all the coins in odd positions, forcing
Bob to pick only coins in the even positions. To do so she stars by picking
the coin in position 1, so Bob can pick only the coins in position 2 or 50.
If he picks the coin in position 2, Alice will the pick coin in position 3,
if he picks the coin in position 50 she picks the coin in position 49, and
so on, with Alice always picking the coin at the same side as the coin
picked by Bob. If Sodd ≤ Seven, then Alice will use a similar strategy
ensuring that she will end up picking all the coins in the even positions,
and forcing Bob to pick the coins in the odd positions—this time she will
pick first the 50th coin, and then at each step she will pick a coin at the
same side as the coin picked by Bob |
t*******d
发帖数: 12895 | 15 这个不但可行，而且更好
down
【在 t******l 的大作中提到】
: 这个不行，recursive 不能保证最大，因为是 difference 加起来，而前面的决定会改
: 变 trajectory，导致递归不变式不能保持。
: 还是得一开始就确定奇偶后 stick to 一开始的 decision。
:
: ：应该有个基于这个 solution 但更 strong 的 solution，基本就是 recursive down
: ，灵活选择奇偶，不一路都 stick 在相同的奇偶。
: ：
|
w**d
发帖数: 2334 | 16 这个解释的够清楚。
ends
pockets
【在 N*******M 的大作中提到】
: 美国大学的原题参考：
: On a table there is a row of fifty coins, of various denominations (the
: denominations could be of any values). Alice picks a coin from one of the
: ends and puts it in her pocket, then Bob chooses a coin from one of the ends
: and puts it in his pocket, and the alternation continues until Bob pockets
: the last coin. Prove that Alice can play so that she
: guarantees at least as much money as Bob.
: -Answer:
: Alice adds the values of the coins in odd positions 1st, 3rd, 5th, etc.,
: getting a sum Sodd. Then she does the same with the coins placed in even
|
t******l
发帖数: 10908 | 17 我有空时去证一下看看递归变换奇偶选择有没有存在 trajectory issue，也
就是是不是严格的递归不变式保证最大。
我目前只是怀疑，没有真的去证明或证伪。但我感觉存在 trajectory issue，
应该严格遵循一开始的奇偶选择。当然证伪只要构造反例就可以了。
【在 t*******d 的大作中提到】
: 这个不但可行，而且更好
:
: down
|
t*******d
发帖数: 12895 | 18 如果Alice严格遵循一开始的奇偶选择，得到的钱是
（T+D0）/2
T是总数，D0是初始奇偶差值
如果Alice递归变换奇偶选择，得到的钱是
（T+D0）/2+∑Di
Di是第i次出现奇偶变换时的奇偶差值
【在 t******l 的大作中提到】
: 我有空时去证一下看看递归变换奇偶选择有没有存在 trajectory issue，也
: 就是是不是严格的递归不变式保证最大。
: 我目前只是怀疑，没有真的去证明或证伪。但我感觉存在 trajectory issue，
: 应该严格遵循一开始的奇偶选择。当然证伪只要构造反例就可以了。
|
t*******d
发帖数: 12895 | 19 还有一个辅助策略是：
如果数额大的那一端也同时比它邻位大，Alice可以优先取这个大的一端。
因此Alice如果想得到尽可能多的钱，
可以优先考虑上述的辅助策略，其次采用递归变换奇偶选择。
【在 t*******d 的大作中提到】
: 如果Alice严格遵循一开始的奇偶选择，得到的钱是
: （T+D0）/2
: T是总数，D0是初始奇偶差值
: 如果Alice递归变换奇偶选择，得到的钱是
: （T+D0）/2+∑Di
: Di是第i次出现奇偶变换时的奇偶差值
|
t******l
发帖数: 10908 | 20 你这个是对的，也是可以证明的。
这个证明的主要 trick，是不要画成类似 constructive 的递归不变式，因为这个
问题本质不是从底向上的 construction 问题。要画成类似 branch & bound
的递归不变式。
具体就是每个 node 下选奇偶分支时，mark 上假设该奇偶选择保持不变到底的 sum，
然后选最大的 lower bound 的 branch，recurse down 时不断 update lower bound，
就能证明。
我昨天陷在类似 constructive 的递归不变式里，就无法 handle 证明里的
trajectory change。类似 branch & bound 的递归不变式就能绕过 trajectory
change 的问题。
【在 t*******d 的大作中提到】
: 如果Alice严格遵循一开始的奇偶选择，得到的钱是
: （T+D0）/2
: T是总数，D0是初始奇偶差值
: 如果Alice递归变换奇偶选择，得到的钱是
: （T+D0）/2+∑Di
: Di是第i次出现奇偶变换时的奇偶差值
|
|
|
N*******M
发帖数: 3963 | 21 我来改变一下题目，看在中国的老中能不能给出答案。
还是原始问题，新的条件是每一个硬币都是被遮住的，Alice和Bob拿硬币时还是不知道
硬币面值，Alice和Bob也不知道所有硬币的总面值。 Prove that Alice can play so
that she guarantees at least as much money as Bob. |
s***n
发帖数: 1280 | 22 Alice can either marry Bob or rob Bob. Either way, she gets all the money...
so
【在 N*******M 的大作中提到】
: 我来改变一下题目，看在中国的老中能不能给出答案。
: 还是原始问题，新的条件是每一个硬币都是被遮住的，Alice和Bob拿硬币时还是不知道
: 硬币面值，Alice和Bob也不知道所有硬币的总面值。 Prove that Alice can play so
: that she guarantees at least as much money as Bob.
|
x***1
发帖数: 999 | 23 脑筋急转弯？有其他解吗？交替地拿，感觉无解阿。
..
【在 s***n 的大作中提到】
: Alice can either marry Bob or rob Bob. Either way, she gets all the money...
:
: so
|
t******l
发帖数: 10908 | 24 香浓刚才发特急电报曰：“果断蓝屏！”
：脑筋急转弯？有其他解吗？交替地拿，感觉无解阿。
：【 在 syuan (头) 的大作中提到: 】 |
