分油有关问题的一些想法

2013-09-28

分油问题的一些想法一般的平分油问题这样表述：某人用只 10 千克的桶装满了一桶油去卖，正好来了两个买油的

分油问题的一些想法
一般的平分油问题这样表述：
某人用只 10 千克的桶装满了一桶油去卖，正好来了两个买油的，每人要买 5 千克，但没有秤，只有两只可装 7 千克和 3 千克的空桶。问怎样利用这两只空桶将油平均分成两份。

但是进一步推广如果要求不是平分，而是分出任意X千克，从1-10，那些分油可以做到的那些是不可以做到的？

有没有一个数学公式可以判断是否可分。
即可抽象成下面的问题：

设有容器L升油，中型容器可容纳M升，小型容器可容纳S升，目标为分出R升油。
L、M、S 与R这四个数满足什么关系的时候，分油可以实现，什么时候分油不可以实现。

想说二元一次不定方程的同学，再仔细考虑一下。
二元一次不定方程只能在可以分油的基础上计算出什么时候最优，并不能用这个来判断是否可以分油。

希望高手指教。
[解决办法]
假设共有 L 升油，要分出来 R 升，两个桶分别可装 M and S。这个问题实际上就是找一个线性组合(x,y)，满足
R = M*x + S*y， for x,y∈Z
而根据数理论里的定理有
gcd(M,S) = M*x + S*y 总有解
所以考虑两种情况，
case 1) gcd(M,S)能整除R，包括M and S coprime，都有可能成功找到(x,y)，注意，是有可能！
case 2) gcd(M,S)不能整除R，则必然没戏。

接下来考虑case 1在哪些情况下一定可以实现。
1) 当M+S < R，在中途倒换的时候，没有容器能装下R升的油。不能实现
2) 当M+S > L, 这种情况下，虽然中途倒换能装下，但是由于油不足，没办法做出来差，用来产生R。
3) 只有当 R<= M+S <= L时候，才能满足。
[解决办法]

引用:

Quote: 引用:

又想了一下，M+S==L 不是必须的。
需要的是 M+S <= L，因为如果油量总数不够，那肯定不可能分出来。

分油的要求似乎没那么高，很纠缠。。。。。。。感觉很难。模型一直建立不起来。

#5 和 #7 都给了你数学模型，然后你还一直说模型建立不起来；是建立不起来，还是你不会用啊？

引用:

楼上思考很深.
1.M+S < R 的情况下也可以分油。比如 10,3，2 要求分7升油，很显然只需要把10升油倒入3升中即可得解。
2.M+S > L 的情况也可能可以分油。比如 10 ，8， 4 要求分4升油，很显然只需要把10升油倒入4中即可得解。

所以感觉总没有一个数学模型可以概括所有情况....

你这个根本就是胡搅蛮缠。
1. 看似通过 2,3 能分出 7，实际上是隐性的使用了 10，根本就是偷换命题。我要是不给你一个 10 的罐子，只跟你说要多少有多少，你看还能弄出 7 来吗？
2. gcd(4,8) == 2，你的目标油量 R=4，刚好能够整除 2，就是 #7 说的 case (1)。

互质的情况下，只要总油量大于等于目标油量，就肯定能分。
不互质的情况下，如果目标油量 R 整除 gcd(M,S)，并且 R<=M+S，则也能分。
实际上和互质就是一个特例，因为互质的数字 gcd 总为 1，所以只要 R 为整数即可。
[解决办法]

引用:

Quote: 引用:

Quote: 引用:

Quote: 引用:

又想了一下，M+S==L 不是必须的。
需要的是 M+S <= L，因为如果油量总数不够，那肯定不可能分出来。

分油的要求似乎没那么高，很纠缠。。。。。。。感觉很难。模型一直建立不起来。

#5 和 #7 都给了你数学模型，然后你还一直说模型建立不起来；是建立不起来，还是你不会用啊？

引用:
楼上思考很深.
1.M+S < R 的情况下也可以分油。比如 10,3，2 要求分7升油，很显然只需要把10升油倒入3升中即可得解。
2.M+S > L 的情况也可能可以分油。比如 10 ，8， 4 要求分4升油，很显然只需要把10升油倒入4中即可得解。

所以感觉总没有一个数学模型可以概括所有情况....

你这个根本就是胡搅蛮缠。
1. 看似通过 2,3 能分出 7，实际上是隐性的使用了 10，根本就是偷换命题。我要是不给你一个 10 的罐子，只跟你说要多少有多少，你看还能弄出 7 来吗？
2. gcd(4,8) == 2，你的目标油量 R=4，刚好能够整除 2，就是 #7 说的 case (1)。

互质的情况下，只要总油量大于等于目标油量，就肯定能分。
不互质的情况下，如果目标油量 R 整除 gcd(M,S)，并且 R<=M+S，则也能分。
实际上和互质就是一个特例，因为互质的数字 gcd 总为 1，所以只要 R 为整数即可。

实际上就是3个容器分7，那个10本来就是拿来用的。难道其他的分油能不使用10这个罐子吗？

5,7的模型是不对的，我说的几个能分油的情况，按照他的模型都是不可分的。。。你让我怎么用？

10，7,5，R=4的情况。
（3,7,0）--》（3,2,5）--》（8,2,0）--》（8,0,2）--》（1,7,2）--》（1,4,5）。R=4 即实现。

10,3,2 ,R=6这种情况也是完成分油的。
（7,3，0）--》（7,1,2）--》（9,1,0）--》（9,0,1）--》（6,3,1） R=6得解。

另外你说的：互质的情况下，只要总油量大于等于目标油量，就肯定能分。这也是不对的。
12,3,2 ，R = 6 ，就没法分。

1. 我见过的分油的问题，或类似的问题，无论是特例，还是通例，都是只能用两个容器的。
2. 你从来没说你的题目允许用三个容器，主楼的时候你自己还建议使用"二元一次不定方程"，这里的二元不就是模拟两个容器吗，这种陈述给我的理解就是你的问题也是两个容器的，我相信 #7 也是理解为两个容器的，这么多楼大家的讨论都是基于两个容器的，这会儿你又说可以用三个容器，早怎么不说啊。

三个容器是另一种泛化，比主楼问题更加推广，我相信用数论的方法也能够解，因为本质都是数字互质的性质应用，只不过现在多了一个数而已，但 gcd 一样能求，其他的逻辑一样能用。

这里回答问题的不是老师，有的时候陈述存在出入，或不全面，你自己需要补充完善一下。
不是一字不落的抱过去，发现那里不行了，就说模型有问题。
比如，你举例说 “12,3,2 ，R = 6 ，就没法分。”。这不是显然的吗，2+3 都小于 6，能分得出来 6 吗？
你自己变通一下，加个条件 R<=M+S 不就完了吗。
况且 #5 我也说了，能分出的数字都在 [1,M+S] 中，你这个例子里的 R 压根都不在那个区间，可不是分不出来吗，模型明确的说分不出来，没问题啊。#7 不是也要求 R<= M+S <= L 吗，模型怎么不能应用了。
[解决办法]

引用:

Quote: 引用:

Quote: 引用:

Quote: 引用:

Quote: 引用:

Quote: 引用:

又想了一下，M+S==L 不是必须的。
需要的是 M+S <= L，因为如果油量总数不够，那肯定不可能分出来。

分油的要求似乎没那么高，很纠缠。。。。。。。感觉很难。模型一直建立不起来。

#5 和 #7 都给了你数学模型，然后你还一直说模型建立不起来；是建立不起来，还是你不会用啊？

引用:
楼上思考很深.
1.M+S < R 的情况下也可以分油。比如 10,3，2 要求分7升油，很显然只需要把10升油倒入3升中即可得解。
2.M+S > L 的情况也可能可以分油。比如 10 ，8， 4 要求分4升油，很显然只需要把10升油倒入4中即可得解。

所以感觉总没有一个数学模型可以概括所有情况....

你这个根本就是胡搅蛮缠。
1. 看似通过 2,3 能分出 7，实际上是隐性的使用了 10，根本就是偷换命题。我要是不给你一个 10 的罐子，只跟你说要多少有多少，你看还能弄出 7 来吗？
2. gcd(4,8) == 2，你的目标油量 R=4，刚好能够整除 2，就是 #7 说的 case (1)。

互质的情况下，只要总油量大于等于目标油量，就肯定能分。
不互质的情况下，如果目标油量 R 整除 gcd(M,S)，并且 R<=M+S，则也能分。
实际上和互质就是一个特例，因为互质的数字 gcd 总为 1，所以只要 R 为整数即可。

实际上就是3个容器分7，那个10本来就是拿来用的。难道其他的分油能不使用10这个罐子吗？

5,7的模型是不对的，我说的几个能分油的情况，按照他的模型都是不可分的。。。你让我怎么用？

10，7,5，R=4的情况。
（3,7,0）--》（3,2,5）--》（8,2,0）--》（8,0,2）--》（1,7,2）--》（1,4,5）。R=4 即实现。

10,3,2 ,R=6这种情况也是完成分油的。
（7,3，0）--》（7,1,2）--》（9,1,0）--》（9,0,1）--》（6,3,1） R=6得解。

另外你说的：互质的情况下，只要总油量大于等于目标油量，就肯定能分。这也是不对的。
12,3,2 ，R = 6 ，就没法分。

1. 我见过的分油的问题，或类似的问题，无论是特例，还是通例，都是只能用两个容器的。
2. 你从来没说你的题目允许用三个容器，主楼的时候你自己还建议使用"二元一次不定方程"，这里的二元不就是模拟两个容器吗，这种陈述给我的理解就是你的问题也是两个容器的，我相信 #7 也是理解为两个容器的，这么多楼大家的讨论都是基于两个容器的，这会儿你又说可以用三个容器，早怎么不说啊。

三个容器是另一种泛化，比主楼问题更加推广，我相信用数论的方法也能够解，因为本质都是数字互质的性质应用，只不过现在多了一个数而已，但 gcd 一样能求，其他的逻辑一样能用。

这里回答问题的不是老师，有的时候陈述存在出入，或不全面，你自己需要补充完善一下。
不是一字不落的抱过去，发现那里不行了，就说模型有问题。
比如，你举例说 “12,3,2 ，R = 6 ，就没法分。”。这不是显然的吗，2+3 都小于 6，能分得出来 6 吗？
你自己变通一下，加个条件 R<=M+S 不就完了吗。
况且 #5 我也说了，能分出的数字都在 [1,M+S] 中，你这个例子里的 R 压根都不在那个区间，可不是分不出来吗，模型明确的说分不出来，没问题啊。#7 不是也要求 R<= M+S <= L 吗，模型怎么不能应用了。

用两个容器分油的例子您拿出来我看看，两个容器怎么能实现分油。
这个我还真没见过两个容器能分油的。没有第三个容器，他们之间是怎么实现倒腾的？

分油问题中的容器说的是具有特定容量的容器，且容器的容积对题目产生本质影响，比如主楼中的 3 和 7，换作其他的数字，题目就会变化。
题目中通常还加设一种不具有标度的容器，作为中间倒换的途径，对该容器唯一的要求就是它必须足够大，比如主楼中 10 那个容器。但 10 这个数字在这道题里面并不重要，实际上都不需要知道，换作 15 也行，600 也行。
如果你喜欢咬文嚼字，那就精确定义两种 "容器"：
(1) 具有特定容积的容器。此容器就是我上面贴子说的容器。
(2) 不需要知道其容积的容器，唯一的要求即该容器足够大，能够作为中间倒换用。
[解决办法]

引用:

Quote: 引用:

很确定你说的分油问题和我见过的本质一样。
不过我水平有限，就当我没说吧。

可能我们见过的东西不一样理解出现了偏差。

就现在这种情况：
已知L、M、S三容器，求R的这种操作模式。其中L是最大容器，且盛满油。
如何判定，R是何值的时候分油不成立。

我这样描述，应该不至于有偏差了，我是诚心求教，谢谢。

我大概看出了我们那里出现不同的理解。
我的理解是 R 只能通过 M 和 S 容器来满足。
我感觉你的理解是允许 L 中的容量也参与构造 R，而不仅仅作为中间倒换用的容器。
#5 确实没有考虑这种情况。
这两天有事，下周闲下来，我要是能想出来，再来这里回帖。
[解决办法]
既然这样，让计算机自己判断好了。先按gcd(M,S)不能整除R进行排除，如果可以整除，就把每次的状态记录下来，一旦出现重复状态就结束。没必要特意找一个通解出来，不是任何问题都有最优雅的解决方案的。

热点排行

C语言

分油有关问题的一些想法