欢迎光临散文网 会员登陆 & 注册

【日常哲学的数学原理】卡片、符号与公共符号

2019-11-21 15:20 作者:ゆのさま  | 我要投稿

《放学后骰子俱乐部》/《放学后桌游俱乐部》第8话中出现了一款名为“DOBBLE”(常译为“嗒宝”、“哆宝”)的桌游。暂且抛开其游玩过程的规则形式,其物质存在本身就饶有趣味——该桌游实物由55张卡片组成,每张卡片含有8种不同符号,每两张卡片都有且只有一个公共符号。这种物质存在如何成为可能?其构造的难度又怎样?

抽象地,想要构造N张卡片,每张卡片含有k种不同符号且每两张卡片都有且只有一个公共符号,是否一定可能?如果可能的话至少一共需要多少种不同的符号?

k=8

论存在的可能

对于可能性的问题,如果不计设计符号的代价即可以使用任意多的符号,那么对于任意N、k,均存在如下卡片符号分配方案:

  • 第1张卡片:符号1、符号(2,1)、……、符号(k,1),

  • 第2张卡片:符号1、符号(2,2)、……、符号(k,2),

  • ……

  • 第N张卡片:符号1、符号(2,N)、……、符号(k,N)。

易见所有卡片都有且只有同一个公共符号符号1。

这种朴素的方案总共需要使用1+(k-1)N个符号,对于N=55、k=8,这个数量将达到386种,即截止到第三世代为止的宝可梦的数量,设计如此多(且要易于分辨)的符号实属巨大的工作量。而且此方案中所有卡片的公共符号均是同一种,可以预见将会大大降低游戏性。在此方案的基础上,是否存在总符号数更低、每个符号的重复使用率更高的构造方案?

论存在的可能 第二部分

逆向考虑一个等价的问题(其等价性推迟到后一部分进行阐述):总共使用S种符号,每张卡片含有k种不同符号且每两张卡片都有且只有一个公共符号,最多能构造多少张卡片?

显然,当S<k时,无法构造卡片。假设S≥k,且不妨设第1张卡片含有的符号是符号1、符号2、……、符号k。进而剩余的卡片可以按照它们和第1张卡片的公共符号分为k类,即公共符号为符号1的卡片们一直到公共符号为符号k的卡片们。在同一类中,比如第1类中,由于所有卡片都含有相同的公共符号符号1,它们之间不能再产生公共符号了。如果总共只存在一个类,那么方案将退化为前述的朴素方案,因此假设至少还存在第二个类,比如第2类。考虑第2类中的一张卡片,它需要和第1类中的每张卡片都有公共符号,而第1类中所有卡片上的所有符号(除了符号1)都是不同的,因此如果第1类有n张卡片,那它(除了符号2)至少就要含有n种符号,由此可知n≤k-1。由于上述讨论并不依赖于具体是哪一个类,所以每个类都至多有k-1张卡片,进而总共最多存在1+k(k-1)张卡片。

另一方面,N=1+k(k-1)张卡片的构造在一定条件下切实存在。设第1类中的k-1张卡片的符号为:

  • 第1张卡片:符号1、符号(2,1)、符号(3,1)、……、符号(k,1),

  • 第2张卡片:符号1、符号(2,2)、符号(3,2)、……、符号(k,2),

  • ……

  • 第k-1张卡片:符号1、符号(2,k-1)、符号(3,k-1)、……、符号(k,k-1)。

则第2类中的k-1张卡片可以取符号分配:

  • 第1张卡片:符号2、符号(2,1)、符号(2,2)、……、符号(2,k-1),

  • 第2张卡片:符号2、符号(3,1)、符号(3,2)、……、符号(3,k-1),

  • ……

  • 第k-1张卡片:符号2、符号(k,1)、符号(k,2)、……、符号(k,k-1)。

即第2类中的符号方阵的每一行是第1类中的符号方阵的对应的列。这样第2类中的每一张卡片与第1类中的每一张卡片都有且只有一个公共符号,因为一个符号全不相同的方阵中的一行和一列有且只有一个公共符号,即该行该列的交点处的符号。

受此启发,由于对角线和每一行、每一列都只有一个交点,可以依照所有“回环”的对角线平行线(“回环”例如对角线平行线(3,1)到(k,k-2)之后折回(2,k-1))分配第3类中的卡片的符号;进一步,可以依照斜率为2的线分配第4类、依照斜率为3的线分配第5类、……、依照斜率为k-2的线分配第k类。直观上,这样分配后,同一类中的线斜率相同互相平行没有交点,不同类中的线斜率不同由于“回环”必定会有而且仅有一个交点。为了完整性,以下将会列出这种构造的表达式,但是具体的表达式并不十分重要,而且会因为无设计的坐标选取变得不必要地复杂,上述几何图像是这种构造最为重要的核心思想。形式化地,第i类中的第j张卡片的符号为:

  • (符号i、)符号(j+1 mod k-1,1)、符号(j+1+(i-2) mod k-1,2)、……、符号(j+1+(k-2)(i-2) mod k-1,k-1);通式即第m个符号为符号(j+1+(m-1)(i-2) mod k-1,m)。

其中mod k-1取特殊范围2到k,即计算2到k中模k-1同余的数。在有了形式化表达式后,可以对前述几何直观进行验证,会发现想要使斜率不同的“回环”线之间永远有且只有一个交点,需要同余除数k-1是素数(核心地,有且只有一个交点要求两斜率之差与k-1互素,因而若k-1是素数则直接保证了这一点)。

这种方案所需要的总符号数为k+(k-1)(k-1)=1+k(k-1),恰巧等于(最大)卡片数N。作为比较,前述的朴素方案所需的总符号数为1+(k-1)N,为此方案的k-1倍以上。

综上所述,当有1+k(k-1)种不同符号时,最大存在相同数量1+k(k-1)张卡片,而且当k-1是素数时构造切实存在,而且遵循这种构造,所有符号的重复使用次数均为k次;而若想要构造在此之上数量的卡片,只能立即退化到前述的朴素方案(因为根据之前的论述,此时只能存在一个类),此时所需的总符号数急遽上升。对于k=8,k-1=7是素数,这种构造给出的卡片数是57,实际使用N=55可能是为了美观,而且据传言有人数过实际使用的总符号数确实是57。

论解答的完备

1、当总符号数少于1+k(k-1)时,最大可构造多少卡片?

直观上,减少符号数(但仍然≥k,<k时无法构造卡片)对应在符号方阵中删去方格,进而减少的卡片数对应经过被删去方格的各种斜率的“回环”线,等于被删去方格数乘以k再减去重复计算。故想要减少的卡片数尽可能少,应使重复计算尽可能多,即删去的方格尽可能不共线。

2、当k-1不是素数时,最大切实可构造多少卡片?

一个未必最优的方案是依然采取前述基于斜率的构造,但仅使用(行、列、以及)斜率1、2、……、p-1,其中p为k-1最小的素因数,这样仍能保证不同斜率的“回环”线有且只有一个交点(由于任两个斜率之差至多为p-1,由p的最小性一定与k-1互素)。这种方案给出的切实构造是1+(p+1)(k-1)张卡片。此时依然需要1+k(k-1)种不同符号。另外,这种方案在基于斜率的构造中是最优的,因为如果使用了超过p-1个斜率——将列视作斜率0则是超过p个斜率——则由抽屉原理可知必有两个斜率模p同余,即它们的差不与k-1互素。

进一步地,亦可以考虑k-1不是素数、且总符号数少于1+k(k-1)的情况。在这一情况下,如何最优地统筹配置斜率与被删去方格似乎更为复杂。

3、(固定k,)给定卡片数N求最小总符号数S(N)与给定总符号数S求最大卡片数N(S)的等价性何以见得?

等价性可由双方的单调性易见。对于卡片数如果存在一种卡片数为N的构造那么一定存在一种(相同总符号数的)卡片数小于N的构造:只要随意删去卡片即可;对于总符号数如果存在一种总符号数为S的构造那么一定存在一种(相同卡片数的)总符号数大于S的构造:只要不使用多出的符号即可。构造性地,S(N)=min{S:N(S)≥N}、N(S)=max{N:S(N)≤S}。

4、日常哲学在哪里?

日常哲学仅出现在日常哲学不存在的地方,日常哲学的缺席本身就蕴含了日常哲学。

或者说,在《放学后骰子俱乐部》里。

知らなかった君を知るたびに、知らなかった自分を知るんだ。

每一次了解到未曾知晓的你时,也会了解到未曾知晓的我自己。


【日常哲学的数学原理】卡片、符号与公共符号的评论 (共 条)

分享到微博请遵守国家法律