这个图像看起来和原不等式一样的不等式是怎么发现的？ - 知乎1420被浏览388597分享邀请回答该回答已被折叠 0添加评论分享收藏感谢收起这个图像看起来和原不等式一样的不等式是怎么发现的？ - 知乎1420被浏览388597分享邀请回答719
如果稍微试验一下，k是被17整除的，这个17是偶然和图中的17巧合吗？今天就来讨论它背后的数学原理（trick）和解读其中的一些基本想法，希望能助于理解。0.背景这是这个公式的wiki可见该方程作者Jeff Tupper是计算机图像学方面的专家，这个公式是他发的paper中用来娱乐消遣用的小作品。Paper在线阅读地址为Tupper, Jeff. "Reliable Two-Dimensional Graphing Methods for Mathematical Formulae with Two Free Variables"这个公式严格来说不能算是自我指涉方程，因为我们要用到一个k值来确定图像，而图像中却缺少k的"显示".公式更多依赖于计算机作图展现的效果，所用数学知识是初等的。其实图像完全可以有各种变种，如：令k=
以(x,y-k)作图，其中,就得到这样的一个图：也完全可以自己做一个自我指涉式的图像：设方程为：令k=1503
用同样的作图法有图像：所以这样的公式有无穷多个。其实分析后，你会发现计算k几乎是一件很简单的事。甚至可以说这个方程是一个很trick的东西，下面开始正式的分析，仅需用到简单的同余知识和进制表示知识。———————————分割线—————————————————————假设k&=17.1.方程的简化原方程为：首先，指出首先，指出1/2是完全不必要的。事实上，由于任何数除以2的余数后都在[0,2)之间，因此的值介于0与2之间。的值介于0与2之间。所以其向下取整只能为0,1.所以其向下取整的值&1/2也就只有一种可能：这就是方程本来的样子,不知道为什么作者要取1/2这个数字,也许是为了起到障眼法的作用。还原原貌后，然后我们来考虑定义域这是一长为106,宽为17的矩形:注意到k&=y&=k+17，而y-k=17这一条直线不影响最终的图像，所以不妨考虑y&k+17注意到y的取值我们有,这就说明为定值，记为 .…………①原方程化为,M为非负整数由k唯一决定。现在来研究这个方程的图像与k的关系。2.二进制表示消解方程原方程形如,其中i,j为自然数的形式.对于上面的方程,我们先来思考在什么情况下会有:,其中i,j为自然数首先j不能太大，因为当时，显然左边=0,不可能成立等式.既然是2的负整数次幂，而且左边=0或1，所以我们自然地想到了：i的二进制表示设,则在时，我们有所以注意到aj即为i在二进制表示下第j+1位因此我们有：对给定的i,方程的所有j的自然数解可由i的二进制表示给出j为解等价于i的二进制下第j+1位为1.3.原方程的解考虑设的所有自然数解j构成集合S.由上面的讨论可知，j在S中等价于M的二进制表示下第j+1位是1因而S有限，并且由M唯一决定，从而由k唯一决定。继续前进前先举个例子：如果k=则M=1003452，求出M的二进制表示，发现第20, 19, 18, 17, 15, 12, 11, 10, 9, 8, 6, 5, 4, 3位为1故S={3, 4, 5, 6, 8, 9, 10, 11, 12, 15, 17, 18, 19, 20}这说明由k求S，S求k只需要简单的转换。回到原方程由上面可见，方程变成解许多个不同的简单方程：注意到左边为一个17的倍数+一个＜17的自然数,很明显对固定的这样的j，左边两项都可以唯一确定，举个例子，37=17a+b，a,b自然数，那么你应该很快通过两边除以17得到a=2，b=3，同理我们得到两边一比较,有……②从而所以……（X）由于y-k的范围在0-17之间,只能是0，1，2，……16这17个互异的非负整数所以就是（X）式右边可能为负数，我们考虑在mod17意义下右边的值，右边总是介于0-16的整数如果右边计算为负数等，如-4，我们就认为右边是13，这种认定下就会有：……③由②③就可以表出这两个整数。如上面例子中k=,S={3, 4, 5, 6, 8, 9, 10, 11, 12, 15, 17, 18, 19, 20}mod(k,17)为103 452，j取18，则解得于是由j唯一确定了不超过x的最小整数，不超过y-k的最小整数，注意最后作图是以y-k为纵坐标作图，我们有每一个j∈S确定的的解为②③，也就是说满足这个方程的点对应的x，y-k的不超过的最小整数都可以分别确定，故图像为：（四条黑边圈住的阴影部分去掉上方和右方的两条边,即为解集区域）如例中k=,S={3, 4, 5, 6, 8, 9, 10, 11, 12, 15, 17, 18, 19, 20},j取18对应的图像为一个方块注意到……②为了这个图像能够在矩形上画出，我们还有要求:j&17X106,也就是说我们要求：还注意到每个j∈S均得到一个正方形解集，故有|S|个正方形，但是不同的j可能有相同的正方形，所以互异正方形数不大于|S|,其中|S|为S的元素个数。综合上面讨论得到第一个结果：定理1当时在约束下在约束下不等式的解集为：S为满足的二进制表示下的第j+1位为1的所有j的集合。解集直观上来看为以②③所确定的格点为左下角点的所有半开半闭单位正方形（即包含左边和下边，上边和右边）之并。且有估计互异正方形个数设为N，则有 如上面我们的例子k=，M=1003452，M二进制表示，第20, 19, 18, 17, 15, 12, 11, 10, 9, 8, 6, 5, 4, 3位为1，故S={3, 4, 5, 6, 8, 9, 10, 11, 12, 15, 17, 18, 19, 20}解集如下：还记得我们说过的取j=18还记得我们说过的取j=18对应的图像为一个方块{(x,y)|1&=x&2,1&y&=2}吗？你可以发现它就是上面的黑色方块之一，而且S的元素数为14，图中方块数为13，13&=14.现在应该可以谈谈这个公式其中的原理，具体如下：作者应该类比了像素点，即电脑上的每一个图像其实都是由一块块小的像素点生成的，每一个k就对应了一块由一个个小方块形成的图形。我们的目的就是巧妙的选取k，从而确定S中元素，然后S中每个元素对应一个小方块，最后所有对应小方块的并就是那个方程的图像。这就是图像化的奥秘，所以我们在选择恰当的k后，可以使小方块拼成我们的想要的图形。接下来就是证明这种选择是可行的：即对于每一个形如一个个半开半闭的正方形之并的上述矩形区域中的图形D，我们都能找到给定的k，使4.利用好的k,构造任意图形我们先假设这样的k存在，再寻找它要满足的充分必要条件。由于,而S由M唯一决定，因此我们总可以将k微调，使M不变，从而S不变我们不妨就假设k是17的倍数，既方便又好消去③中的k，这时候有……②……③……④现在假设均为边长为1的半开半闭正方形，互不相同，且四个顶点横纵坐标都是自然数设左下角的格点在坐标为，由②③有而且若,我们立刻由②③得到,由互不相同，便有j=k，因此两两互异，这保证了和k的选取的合理性。因此，我们只要使,由3论证知，S对应的图形就是D也就是说令M的第位全为1，其余位全为0即可，即得到第二个结果：定理2：对于每一个形如一个个半开半闭的正方形之并的上述矩形区域中的图形D，我们都能找到给定的k，使，且要求k是17的倍数时，k是唯一的。若，均为边长为1的半开半闭正方形，互不相同，且四个顶点横纵坐标都是自然数设左下角的格点在坐标为,令则取,则以(x,y-k)作图且要求以(x,y-k)作图且要求，所得图形.我们把D对应的S称为D的0-1标，所有的构成集合成为D的标志点集显然S,D,标志点集彼此互相决定.我们借助标志点集可以方便而清楚的表示出D与k.举个例子：我们可取
M=111（二进制）
0-1标为{0，1，2，3，4，……，50}能不能以更快的速度计算k？其实我们可以直接从图中得到k的信息还是举个例子：对一个黑方块，我们从坐标系左下角出发，从下到上数行数i，从左到右数列数j那么其对应的就是M的第i+17(j-1)位要是1，对应0-1标中元素为i+17(j-1)-1如图黑方块在第9行第5列，故要做出上面的图形，只要取
0000000(二进制，1在第9+17X(5-1)=77位后面9+17X(5-1)-1=76个0）
k=17*2^76=2
0-1标为{76}再回到我们开头的这家伙：我们来看看这个kk=
乍一看可能挺吓人的，我们用mathematica把它除以17然后化成二进制，果然发现k是17的倍数。那一串0-1即M的二进制表示。然后利用前人写好的程序，我们把图给导出来：…………为啥是倒的………………这和说好的不一样啊= =等等，我们看一下原图：查阅资料发现wiki上说：查阅资料发现wiki上说：If one
the set of points (x, y) in 0 ≤ x & 106 and k ≤ y & k + 17 satisfying the inequality given above, the resulting graph looks like this (note that the axes in this plot have been reversed, otherwise the picture comes out upside-down)说明这张图片的坐标系是错的，应该是0在上，15在下，否则只会产生颠倒的图片了…所以这哪里是不明觉厉啊，这明明是坑蒙拐骗了(╯‵□′)╯︵┴─┴做图片的可能以为大家都不会去检验那么大的k吧(╯‵□′)╯︵┴─┴为了使演示能进行，出来吧令k=6300
其图像为：通过mathematica计算得0-1标为共334个，即代表图像由334个黑方块组成。5.推广考虑什么是对矩阵区域的大小的根本限制.其宽度即纵方向伸长是由17决定的我们可以把17换成任何一个别的&2的素数，如素数p，这样我们绘图的矩形区域的宽度可以为p。其长度是由计算机处理数据大小和枚举循环的能力决定的。一方面，记得我们在定理2中得到的k表达式，其随着D的复杂度上升，是成指数级增长。另一方面，设矩阵长度为l，我们如果能够给出任意矩阵中的所述图形D，类比应该有，也就是说计算机要处理最大可能有将近pl/8字节的数据，幸好是二进制下的表示，所以这点问题可能在pl不超过1000时不大。所以长度也可推广为更长的情况。另外我们用2作为模也是考虑了计算机是采用二进制这样比较能算比较的大的k。 的答案提到了模10就能更直观，事实上的确如此，把17换成10,2换成10，那么上面的讨论几乎是显然的，而且利于作图。还有我们之所以说其是一个小把戏，因为它的计算其实是非常复杂的，随着D的复杂度上升，不仅情况数变多，而且k的值也会变大，所以实用性不太强，大概可以用来让人震撼一会，不过也就一会。作者自己也说了,It is for fun,作者那篇发在的paper讨论的问题要比这个复杂多了。6.便利的在线绘图网站！最后福利送上，这篇回答也得益于这个网站的帮助感谢别人提前写好的程序,可以方便的运用这个公式下方是一个在线绘制图像网站，从此无需编程就可以自己画图来获取想要的图像了，然后得到k了。同时还支持从输入的k来生成已有的图像。地址如下：其中+号内有各种设置，附带绘图中的各种辅助功能这个图像工具还是挺好玩的，其原理已经分析的很透彻了，代码其实也可以自己实现现在就可以去试试绘制出自己的有趣图像吧，再配上一条所谓的图片说明，令k=XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX，然后作图，是不是又让人觉得不（you）明（xia）觉（hu）厉（you）了呢？————————————————————————————最后的最后，还是感叹一句：k=其他有趣回答：3.7K346 条评论分享收藏感谢收起