喵宅苑 MewoGarden × 技术宅社区II | Z站 Z Station 棒棒哒纯文字二次元技术社区

正文

作者:轻舟过

[i=s] 本帖最后由轻舟过于 2013-4-12 19:56 编辑 IBM Ponder This 谜题：原链接：http://domino.research.ibm.com/C ... nges/March2013.html 英文原文：

There are five products in a store; let's call them A, B, C, D, and E.
The prices of those products are all integers between one and five cents each.
When you pay, the sum is rounded to the closest five cents.
Let's assume that your account is fined with half a point every time your purchase is not an integer multiplication of five cents.
The price of A is one cent, but you don't know anything about the prices of B-E, nor are you aware of the fines you accumulate along the way. The only information you get, at the end of the month, is whether the cumulative number of points you were fined is an integer or not.
For example, after buying the following six purchases: AB AC AABC AAABCC AAABBC BBBBC you can know whether B and C are both 4 or not.
Can you devise a set of purchases, one for each day, such that at the end of the month you'd be able to know whether or not the prices of B-E have exactly two different values?
Please submit your answer as at most 31 lines (one per day) where each line contains a list of items you buy on that day.
We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!
We invite visitors to our website to submit an elegant solution. Send your submission to the webmaster.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: webmster@us.ibm.com

用中文来说，大意就是说商店里有5种商品A、B、C、D、E 每种商品的价格是1-5之间的整数每次买完东西结账的时候，商品的价格总和将四舍五入到5的倍数如果买的东西的东西的价格之和不是5的倍数，结账的时候你的账号将会被扣除0.5分商品A的价格是1，而B-E的价格是未知的，你也无法得知你的账号被累计扣除的分数。你能得知的信息，就只有到月底的时候被累计扣除的分数是不是一个整数例如，进行下列6次购买后： AB AC AABC AAABCC AAABBC BBBBC 你可以知道B和C的价格是否都是4 你能给出一个购买方案，每天至多购买一次，然后在月底的时候你能推断出B-E的商品价格是否只有两种值吗？你的答案应该至多只有31行（一行对应一天的情况），每行包含了当天购买了物品的列表 Using your Head is Permitted谜题：原链接：http://www.brand.site.co.il/riddles/201303q.html

Consider Sequence A185028 of the Online Encyclopedia of Integer Sequences.Can you answer the question that appears in the "COMMENTS"? Specifically, can you prove or disprove the finiteness of the sequence? The sequence and the question were both formulated by Moshe Wolf. It got to me in riddle form by Oded Margalit. Thanks, Oded and Moshe!

回答数列百科全书中数列A185028中COMMENTS部分的问题。数列A185028中数字的特点是，数字的十进制表示所有位数都为d，并且将该数字转化成二进制之后，其中有d个1。COMMENTS部分所问的是，888888是否是这个数列中最大的元素？也就是证明或者证伪“该数列只有有限个元素”这一命题。 ———————————————————————————— 这两个问题都不简单，做出的话会有很多奖励哦~（奖励下个月出了答案了再发放哦）

本帖最后由

作者:轻舟过

[i=s] 本帖最后由轻舟过于 2013-4-29 18:57 编辑

wgxzzq 发表于 2013-4-27 00:15 解法不难，看完就明白了，我就贴英文的解答了。不过网站给的答案我没看懂，应该比我的解答smart。 lz，奖 ...

好厉害～官方给的答案貌似根本没讲怎么构造的，只是给了几个答案暂时脑子有点乱，等静下心来研究一下话说4月的题目忘记转载了

查看回复

我知道你说啥了

作者:wgxzzq

我知道你说啥了。对F1，6个表达式：For F1, b=c=d can be written as x=y=0, where x=4b+d(means bbbbd), y=4c+d. Six days of buying x, y, x+y, 2x+y, x+2y, x+4y, same as your example, can satisfy F1. 对G1,25个表达式：For G1, (b=c!=d=e) can be written as x=y!=0&z=0, where x=4b+d, y=4c+e, z=4b+c(or 4d+e). A similar method to the example, given 25 days of buying can satisfy it: x y x+y 2x+y x+2y x+z y+z x+y+z 2x+y+z x+2y+z 2x+z 2y+z 2x+2y+z 4x+2y+z 2x+4y+z x+2z y+2z x+y+2z 2x+y+2z x+2y+2z x+4z y+4z x+y+4z 2x+y+4z x+2y+4z 具体拆法不是都写在这里了么。

查看回复

本帖最后由

作者:wgxzzq

[i=s] 本帖最后由 wgxzzq 于 2013-4-27 13:29 编辑具体怎么拆不是讲了么：F1代表(b=c=d)的identity函数，F2代表 (b=c=e)的identity函数...。容易验证F1 XOR F2 XOR...XOR...G3的结果为奇数 <==> b,c,d,e恰好取2个不同值。难道你跟我说的不是一个东西？

查看回复

解法不难

作者:dchneric

wgxzzq 发表于 2013-4-27 00:15 解法不难，看完就明白了，我就贴英文的解答了。不过网站给的答案我没看懂，应该比我的解答smart。 lz，奖 ...

嗯，两个keypoint~ 一个是把原命题拆成F1 XOR F2 XOR...XOR...G3，即布尔代数的表示形式，一个是把F和G类命题拆成p1 XOR p2 ... pn，即模五代数群的表示形式具体怎么拆的还是没讲，嘛... 如果计算机解的话，只能求个F或G命题的通解，总solution还是有点太大了..

查看回复

本帖最后由

作者:wgxzzq

[i=s] 本帖最后由 wgxzzq 于 2013-4-27 00:24 编辑

dchneric 发表于 2013-4-21 22:49 他的solution里面没有写，我估计是不是靠猜或者写个程序啥的...应该还有别的规律，没费心去找= =.. ...

解法不难，看完就明白了，我就贴英文的解答了。不过网站给的答案我没看懂，应该比我的解答smart。 lz，奖励的分给我呀:) Let F1 be the indicator function of (b=c=d), ie. (b=c=d) iff the F1 outcomes integeral cumulative number of points. F1 represents several days of purchase. Similarly, let F2,F3,F4 be the indicator function of (b=c=e), (c=d=e), (b=d=e). Let G1,G2,G3 be the indicator function of (b=c!=d=e), (b=d!=c=e), (b=e!=c=d), while it indicate non-integeral cumulative number of points. Let H be the Combining days of F1,F2,F3,F4,G1,G2,G3, it is easy to see that "B-E have exactly two different values" is equivalent to H outcomes non-integeral cumulative number of points. For F1, b=c=d can be written as x=y=0, where x=4b+d(means bbbbd), y=4c+d. Six days of buying x, y, x+y, 2x+y, x+2y, x+4y, same as your example, can satisfy F1. F2,F3,F4 is the similar. For G1, (b=c!=d=e) can be written as x=y!=0&z=0, where x=4b+d, y=4c+e, z=4b+c(or 4d+e). A similar method to the example, given 25 days of buying can satisfy it: x y x+y 2x+y x+2y x+z y+z x+y+z 2x+y+z x+2y+z 2x+z 2y+z 2x+2y+z 4x+2y+z 2x+4y+z x+2z y+2z x+y+2z 2x+y+2z x+2y+2z x+4z y+4z x+y+4z 2x+y+4z x+2y+4z The resulting days of purchase is 4*6+25*3=99. But there are many duplicated and equivalent days, for example, 4x+y and x+4y, 4x+2y+z and 3x+4y+2z are all equivalent days. Dropping these duplicated/equivalent days we find a solution of 19.

查看回复

吐血身亡

作者:Applstz

@ou#吐血身亡

查看回复

里面没有写

作者:轻舟过

dchneric 发表于 2013-4-21 22:49 他的solution里面没有写，我估计是不是靠猜或者写个程序啥的...应该还有别的规律，没费心去找= =.. ...

不清楚额，逻辑电路之类的是有方法的，这个模5的可能也有方法

查看回复

还是不知道怎么构造啊

作者:dchneric

轻舟过发表于 2013-4-14 12:20 还是不知道怎么构造啊

他的solution里面没有写，我估计是不是靠猜或者写个程序啥的...应该还有别的规律，没费心去找= =..

查看回复