四巧板是可避免的 4 种配置-计算机科学-机器学习-词组组合数学-算法.pdf

DiscreteMathematicsandTheoreticalComputerScience..................................

....................................................................vol.27:3#1(2025)

四巧板是可避免的4种配置

PascalOchemThéoPierron

LIRMM,CNRS,UniversitédeMontpellier,Montpellier,France.

UnivLyon,UCBL,CNRS,INSALyon,LIRIS,Lyon,France.

revisions3rdMar.2025,16thJune2025;accepted26thJune2025.

本

译七巧板是一个单词中每个字母出现的次数均为偶数。因此它可以被切割成可以排列成两个相同单词的部分。

中一个七巧板的割数是在这个过程中所需的最小切割数量。具有一次切割数量的七巧板对应于正方形。对于

3，设表示无穷无尽的单词避免最多次切割的七巧板所需字母表的最小大小。存在无限三元无

v平方词表明。我们证明了，回答了Dębski、Grytczuk、Pawlik、Przybyło

4

7和leszyska-Nowak的问题。

7

0Keywords:词组组合数学

2

.

2

0

51介绍

2

:

v一个七巧板是每个字母出现偶数次（可能是零）的单词。特别地，七巧板是正方形的一

i

x种推广。在这篇文章中，我们根据它们与正方形接近的程度对七巧板进行分类。这依赖于最

r

a近由Dębski、Grytczuk、Pawlik、Przybyło和leszyska-Nowak[3]引入的所谓七巧板的切割

数量。七巧板的割数定义为将部分重新排列成两个相同单词所需的最少切割次数。切割数量

最多为的七巧板称为-七巧板。请注意，-七巧板正好是正方形，并且切割数量越大，七

巧板就越远离正方形。

令01表示字母的字母表。直接检查可得，每个长度为4的二进制

词包含一个平方，而Thue在1906年的一个著名定理断言存在避免平方的无限词在上。

在[3]中，作者通过研究（无限）不含七巧板的词来考虑类似的问题。由[9]的引理3可知，

每个无限词都必须包含一些七巧板。因此，他们考虑字母表大小与被排除七巧板切分数之间

的关系。对于，作者定义为最小的字母表大小，使得存在一个无限单词避免-七

ISSN1365–8050©2025bytheauthor(s)DistributedunderaCreativeCommonsAttribution4.0InternationalLicense

2PascalOchem,ThéoPierron

巧板。根据定义，是非递减的，并且由于每个-七巧板都包含一个正方形，Thue的结

果表明。

[3]中的其他结果总结如下。

定理1([3]).

•logloglog对于每一个。

•对于每一个。

•