Skip to content

Posts from the ‘Interesting Maths’ Category

27
Nov

网络上的抽奖如何保证公平性

//这篇文章是美国信用卡指南近期搞的一个抽奖活动所使用的方案,原文在这里


抽奖的公平性向来是抽奖活动中最受人质疑的部分。由于涉及随机数的选取,网上的抽奖活动几乎无法保证公平性,因为很难保证中奖号码是随机生成而非平台人工选取的,也很难保证平台是否删掉了一部分用户的中奖资格而未告知用户。例如:前阵子支付宝锦鲤活动就有人怀疑中奖者是否是钦定的;前阵子王思聪在微博平台上的抽奖,中奖者男女比例为 1:112,甚为蹊跷。

为了解决抽奖公平性的问题,消除暗箱操作的可能性,我们特别设计了以下抽奖过程。

什么样的抽奖是公平的

抽奖过程可以描述为从 0~N-1 (N为奖券总数) 的整数中抽取一个或多个随机整数的过程。除了抽奖算法和抽奖过程需要公开透明之外,一个公平的抽奖过程所使用的随机数(其实是伪随机数)应具有如下的性质:

  1. 随机数的生成过程不需要依赖于用户对本网站或者任何第三方平台的信任。
  2. 事先无法预测。
  3. 事后公开可查。
  4. 概率上满足均匀分布。

为了保证性质1~3,我们选择使用比特币区块的哈希值来作为我们的随机数种子;性质4只要选取常用的哈希函数即可保证

我们的抽奖算法

假设奖券编号是连续发放的整数。我们的的抽奖算法如下:

  1. 选取指定时刻(即抽奖时间)后被挖出的第一个比特币区块的哈希值作为随机数种子,记作 S。
  2. 用 SHA-256 算法计算 S 的的哈希值 H,然后把 H 作为16进制数字转换为长整数 L。
  3. W = L % N 为中奖的奖券编号,其中 N
8
Feb

一道有趣的数学题

昨天刚看见的数学趣题,是我近期见过的最有意思的了!大家可以尽管尝试一下,数学方法或者写程序暴力算都行~ 保证解是存在的。

解法见这个链接,不过最好先自己想想,实在不行了再点开看,否则会丧失乐趣:https://www.quora.com/How-do-you-find-the-positive-integer-solutions-to-frac-x-y+z-+-frac-y-z+x-+-frac-z-x+y-4

15
Dec

五子棋/连珠近况简介

五子棋作为一个规则简单易懂、入门门槛低的棋类,我想同年龄段的很多人都曾下过吧。不过相信大多数人跟我一样,都没有对五子棋有过专业的研究,当时只是下着玩而已。估计很多人都听说过五子棋黑棋必胜所以五子棋被终结了的传言,也有很多人认为计算机AI可以在五子棋上很轻易的下过人类吧,不过这几天我看了看五子棋/连珠的一些最新近况,过去确实曾对五子棋产生过一些误解,而且最近几年五子棋AI也有了较大的进步。我虽然不是专业人士,但是最近看到了一些网上靠谱资料,在这里给大家简介一下吧,如果有错误请告知!

首先要做一些名词解释。五子棋(Gomoku)现在特指无禁手类的规则,而有禁手类的规则现在被称为连珠(Renju),下文中将区分对待这两个词。禁手(Disallowed moves)的意思是,如果黑棋(原始规则下的先手)下出了双活三、双四或者长连,那么算黑棋输。显然,禁手是对先手优势的一种平衡措施。

黑棋必胜是真的吗?原始规则下,无论有没有禁手,答案都是,是的。对于五子棋(Gomuku,无禁手),1992年Victor Allis已经证明黑必胜的,文章在这里;对于连珠(Renju,有禁手),2001是Janos Wagner第一次证明的黑必胜的,文章在这里。当然,早在这两篇论文很久很久之前,五子棋界就已经通过经验知晓这一事实了,只是最近才有人真的用计算机穷尽了所有可能性证明这一命题为真了而已。我想应该下过五子棋的很多人都听说过所谓的“花月”“蒲月”必胜开局吧,说的其实就是这回事。

那么我们知道黑棋必胜之后,五子棋/连珠就被终结了吗?从某种意义上来说,原始规则下的五子棋/连珠确实是被终结了,但是,通过修改规则,五子棋/连珠仍然可以作为一个正规的职业比赛继续生存下去,下面就分别简介一下国际上正式比赛用的规则:

一、五子棋规则:

  1. 黑白双方轮流落子。
  2. 首先在横、竖、斜方向上成五(连续五个己方棋子)者为胜。
  3. 超过五子以上不算赢也不算输。

在五子棋规则基础上,还有一些细分的规则,目前(2014年)国际上比赛采用的规则为 Gomoku swap 2 规则。

Gomoku swap 2:

  1. 假先在棋盘任意下三手(二黑一白)假后方有三种选择:(1)选黑;(2)选白;(3)下四、五两手(一黑一白)再假先方选择黑或白。
  2. 此后按 Gomoku 规则继续进行。
25
Jul

小游戏“围住神经猫”背后的数学问题

围住神经猫

一夜之间,微信朋友圈便被这个有趣的小游戏“围住神经猫”刷屏了。如果没有见过的可以点开这个链接玩玩看:围住神经猫。一开始看到刷屏的小游戏,我不以为意,以为又是一个无聊的游戏罢了,但是当进去玩了一次之后,便恍然大悟为什么它会火了:这不就是数学游戏界神人John Conway设计的“天使与魔鬼”游戏么!John Comway最有名的数学游戏作品大概是“生命游戏”了,其规则之简单和产生的变化之丰富多彩实在是让人叹为观止;另外著名的“自由意志定理”也出自他的手中。这次的“天使与魔鬼”游戏,于1982年发表,也是他的作品中极其有趣的一个。

最原始的“天使与魔鬼”游戏规则是这样的:在无限大的2维正方形格点上,两个玩家,分别称为天使和魔鬼,轮流行动。初始时,格点是空的,只有天使站在棋盘的原点处。魔鬼每轮的行动是可以在天使站立的格点之外的任意一个格点处挖一个陷阱,挖好的陷阱会始终存在在棋盘上;天使每轮的行动是可以每次移动至多k步,其中每一步可以是横向、竖向或者斜向走一格,k为正整数。下图为示意图,红色是魔鬼挖好的陷阱,而蓝色虚线框表示k=3时天使一次行动可以到达的范围。天使行动时可以跨过陷阱,但是不可以踩在陷阱上。最终,如果天使被围困得无论如何也不得不踩在陷阱上,魔鬼就赢了;如果天使可以无限地逃跑,天使就赢了。问题是:k等于几的时候魔鬼有必胜策略,等于几的时候天使就有必胜策略了?…

30
Jan

钝角其实和直角相等!我们的教科书真实率低于5%,连数学也不例外。

“我们的教科书真实率低于5%,连数学也不例外,年轻人要敢于怀疑。越是从小学习,看起来理所当然的知识越值得怀疑。钝角其实等于直……”1968年冬天,在刺骨的寒风中,数学教授赵文武凛然站在后海的岸边,最后一句尚未说完,便被疯狂的红卫兵挂上石头沉入了后海。

在我们的少年时代,有很多人都有这样的经历,在各种平面几何问题中抓耳挠腮,证明来证明去,为了证明一个角是直角而浪费了精力,荒废了青春。很多人因为不会证明平面几何中关于直角的问题,遭到父母的毒打,乃至与梦中的重点中学、大学失之交臂。可又有多少人知道,其实钝角就等于直角。所有钝角尽管看起来不一样大,但是早在欧几里得时代,伟大的古希腊数学家们就早已通过严格的数学证明了钝角统统等于直角!可是在中国,黑暗的中国教育界却可耻的隐藏了这一秘密,当今中国几乎就没有人知道钝角和直角相等这一本该人尽皆知的秘密!

众所周知,平面几何的最经典著作当属欧几里得的《几何原本》,当今所有的平面几何课本都基本按照原本的框架讲述。而关于钝角等于直角的证明,其实就静悄悄的隐藏在《几何原本》的后记当中。下面贴出古希腊数学家给出的证明:

14
Aug

盘点数学里十大不需要语言的证明

0. 勾股定理&余弦定理

这个大家小学就学过的古老定理,有着无数传奇故事。我可以很随意的写出她的10个不同的证明方法。而路明思(Elisha Scott Loomis)在 《毕达哥拉斯命题》( Pythagorean Proposition)提到这个定理的证明方式居然有367种之多,实在让人惊讶。这里给出一个不需要语言的证明方法。


实际上勾股定理是余弦定理的一种特殊情况,而余弦定理的证明,同样可以不用语言。

1. 关于反正切的恒等式