logo标签列表

在 floor(sqrt(floor(x))) 中，哪一层是多余的？

mathfloor
14

我有floor(sqrt(floor(x)))。下列哪种说法是正确的：

  1. 内部的floor是多余的。
  2. 外部的floor是多余的。
为什么称之为“Floor and Ceiling Question”？ - Renze de Waal
6
实际上，通过扩展以下 Elazar Leibovich 的思路，可以证明以下非常普遍的结果：如果 f(x) 是任何连续、单调递增的函数，满足： f(x) 是整数 ==> x 是整数， 则 floor(f(x)) = floor(f(floor(x))) 并且同样地，ceiling(f(x)) = ceiling(f(ceiling(x)))。 （参考文献：《具体数学》Graham、Knuth、Patashnik；第71页，式3.10）。 - Ashutosh Mehra
我的下一个问题是开发一个通用框架。感谢提供参考，我一定会仔细研究这些发现。 - unj2
@Ashutosh：顺便说一下，你的博客看起来很酷。 - unj2
9个回答
38

显然，外层floor函数不是多余的，因为例如sqrt(2)不是整数，因此floor(sqrt(2))≠sqrt(2)。

对于非整数x，很容易看出sqrt(floor(x))≠sqrt(x)。因为sqrt是单调递增函数。

我们需要找出是否对于所有有理数（或实数）都满足floor(sqrt(floor(x)))==floor(sqrt(x))。

让我们证明如果对于整数m,n，sqrt(n)<m则sqrt(n+1)<m+1。很容易看出：

n<m^2 ⇒ n+1 < m^2+1 < m^2+2m+1 = (m+1)^2

因此，由于sqrt是单调的，我们有：

sqrt(n) < m -> sqrt(n+1) < m+1 -> sqrt(n+eps)<m+1 for 0<=eps<1

对于所有的n为整数，以及所有的0<eps<1，都有floor(sqrt(n))=floor(sqrt(n+eps))。假设否定这个结论，即存在floor(sqrt(n))=m和floor(sqrt(n+eps))=m+1的情况，则会出现sqrt(n)<m+1但sqrt(n+eps)>=m+1的矛盾。

因此，如果需要外层的floor，那么内层的floor就是多余的。

换句话说，总是成立：

floor(sqrt(n)) == floor(sqrt(floor(n)))

内部的ceil怎么办？

很容易看出floor(sqrt(n)) ≠ floor(sqrt(ceil(n)))。例如：

floor(sqrt(0.001))=0, while floor(sqrt(1))=1

然而，您可以以类似的方式证明

ceil(sqrt(n)) == ceil(sqrt(ceil(n)))
您的解决方案是否意味着内部天花板也是多余的？ - unj2
我在这里看不到任何问题。除非有人能证明不正确，否则这是正确的。 - unj2
18

内部的是多余的，而外部的当然不是。

外部的不是多余的，因为一个数 x 的平方根只有在 x 是平方数时才会得到整数结果。

内部的是多余的，因为在区间 [x，x+1[（其中 x 是整数）中的任何数字的平方根总在区间 [floor(sqrt(x)),ceil(sqrt(x))[ 内，因此如果你只对结果的整数部分感兴趣，则无需在取平方根之前对数字进行向下取整。

1
有很多好的证明，但这个是最棒的。谢谢。 - unj2
谁说在 [sqrt(x), sqrt(x+1)] 区间内没有整数？例如，如果 sqrt(x)==0.9 并且 sqrt(x+1)=1.2，则 floor(sqrt(floor(x))) 的结果可能与 floor(sqrt(x)) 不同。 - Elazar Leibovich
我很高兴你喜欢它。在阅读了所有不同且做得很好的实际证明之后，我认为我的解释可能对某些人来说过于不正式了。 - Simon Lehmann
哇，解决方案中有漏洞吗？ - unj2
@Elazar：我写的是[sqrt(x)，sqrt(x)+1[而不是[sqrt(x)，sqrt(x+1)[，但即使如此，你也是对的（尽管你的例子是错误的）。我已经更正了区间，以符合我的实际意思。任何整数x的sqrt(x)和sqrt(x+1)都在同一个整数区间内。 - Simon Lehmann
5
直觉上我认为内部的是多余的，但我无法证明。
除非你能提供一个证明我错误的x值，否则你不能对我进行投票。 8-)
编辑：请参考v3在此答案中的评论以获取证明 - 谢谢，v3！
我也尝试了几个例子，感觉内部的那个是多余的，但很难证明我是正确的。 - unj2
确实。有一个回答说内部的是多余的，但在我能点赞之前它被踩和删除了。不过，我相信那是正确的情况。 - GSerg
5
你能不能简单地说，当x为整数时，floor(sqrt(x))才会改变值？如果x不是整数，向下取整也不会改变平方根的整数部分。 - v3.
4

内部地面是多余的。反证法：

假设内部地面不是多余的。这意味着：

floor(sqrt(x)) != floor(sqrt(x+d))

对于一些x和d，其中floor(x) = floor(x+d)。那么我们需要考虑三个数字：a = sqrt(x)，b = floor(sqrt(x+d))，c = sqrt(x+d)。b是一个整数，且a < b < c。 这意味着a^2 < b^2 < c^2，或者x < b^2 < x+d。但是如果b是一个整数，则b^2是一个整数。因此floor(x) < b^2，并且b^2 <= floor(x+d)，然后floor(x) < floor(x+d)。但我们开始假设floor(x) = floor(x+d)。我们已经得出矛盾，所以我们的假设是错误的，内部floor是多余的。
4
内部地板是多余的。
2
那好吧，我会把你失去的十个积分还给你 :) 我很惊讶 Richie 能够得到那么多赞同，因为他的回答并不是很好。 - Peter Perháč
任何人如果给我点踩，也需要给 Richie 点踩。因为我在他之前回答了问题。 - ichiban
3
如果x是整数，则内部的floor函数是多余的。 如果x不是整数，则两个floor函数都不是多余的。
问题实际上是为什么第二部分。 - unj2
1
周围有太多的废话，而 Macker 只是简明扼要地表达了正确的意思。 - majkinetor
那个人试图说服我们相信这是真的。 - unj2
你说它是错误的，但你在选择答案时却同意了相同的结论，这很奇怪。我感到困惑。顺便说一句，在你的问题中你没有要求证明。 - Macker
抱歉，这个问题仍然是开放的。您能否编辑它并提供您的证明呢？ - unj2
实际上，Ned Batchelder已经让我相信内部现在总是多余的，干得好Ned。 - Macker
3

外层 floor 不是多余的。反例：x = 2。

floor(sqrt(floor(2))) = floor(sqrt(2)) = floor(1.41...)

如果没有外层 floor，结果将为 1.41...

2
如果内部地板不是冗余的，那么我们会预期 floor(sqrt(n)) != floor(sqrt(m))，其中 m = floor(n)。
注意，n - 1 < m <= n。m始终小于或等于n。
floor(sqrt(n)) != floor(sqrt(m)) 要求 sqrt(n) 和 sqrt(m) 的值至少相差1.0。
然而，没有任何值n使得sqrt(n)与sqrt(n + 1)相差至少1.0，因为对于所有在0和1之间的值，该值的平方根定义为<1。
因此，对于所有值n，floor(sqrt(n)) == floor(sqrt(n + 1))。这与最初的假设矛盾。
因此内部地板是冗余的。
“floor(sqrt(n)) != floor(sqrt(m)) requires that the values of sqrt(n) and sqrt(m) differ by at least 1.0” 这个说法似乎不正确，如果sqrt(n) = 0.999而sqrt(m) = 1，则它们的差远小于1，但是floor(sqrt(n))!=floor(sqrt(m))。 - Elazar Leibovich
请注意，其中 n ≤ m < n + 1。但这并非总是正确的，因为floor(n)可以小于n。 - melfar
0

如果 n^2 <= x < (n+1)^2，其中 n 是整数，则

  1. n <= sqrt(x) < n+1，因此 floor(sqrt(x)) = n；
  2. n^2 <= floor(x) < (n+1)^2，因此 n <= sqrt(floor(x)) < n+1，因此 floor(sqrt(floor(x))) = n。

因此，floor(sqrt(floor(x))) = floor(sqrt(x))，这意味着内部的 floor 是多余的。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接