Please wait a minute...
浙江大学学报（理学版）
Journal of Zhejiang University (Science Edition)  2024, Vol. 51 Issue (2): 178-185    DOI: 10.3785/j.issn.1008-9497.2024.02.006
Mathematics and Computer Science     
A recursive algorithm of combinatorial difference set design for least scale number on ruler
Baoxiang TANG1(),Han REN2
1.School of Mathematics and Statistics，Tianshui Normal University，Tianshui 741001，Gansu Province，China
2.School of Mathematics Sciences，East China Normal University，Shanghai 200062，China
Download: HTML( 2 )   PDF(672KB)
Export: BibTeX | EndNote (RIS)      

Abstract  

For a positive integer n≥2, what is the minimum number of ticks to be engraved on an unscaled ruler of length n to measure all lengths from 1 to n. This is an unsolved problem of ruler with least number of scales. This paper clarifies the relationship between ruler with the least number of scales and the minimal graceful graph, and a combined difference recursive algorithm for calculating all the least scale values of ruler with the least number of scales is given. This algorithm calculates that the length is 3 to all the minimum scale values of the most scale-saving ruler of 40, and combined with the graph theory model, the minimum scale values of ruler with least number of scales with lengths from 41 to 82 are given.

Key words： ruler with least number of scales      graceful labeling      minimal graceful graph      graceful labeling algorithm      combinatorial difference recursive algorithm     
Received: 04 July 2022      Published: 08 March 2024
CLC:  O 157  
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Baoxiang TANG
Han REN
Cite this article:

Baoxiang TANG,Han REN. A recursive algorithm of combinatorial difference set design for least scale number on ruler. Journal of Zhejiang University (Science Edition), 2024, 51(2): 178-185.

URL:

https://www.zjujournals.com/sci/EN/Y2024/V51/I2/178


最省刻度尺设计的组合差集递推算法

在长度为n（n≥2为正整数）的直尺上最少刻多少个刻度就能度量1到n的所有长度，这便是至今未解决的最省刻度尺问题。阐明了最省刻度尺与极小优美图之间的关系，给出了计算最省刻度尺的所有最省刻度值的组合差集递推算法，得到长度为3~40的最省刻度尺的所有最省刻度值，同时，结合图论模型，给出了长度为41~82的最省刻度尺的最省刻度值。


关键词： 最省刻度尺,  优美标号,  极小优美图,  优美标号算法,  组合差集递推算法 
Fig1 4 different scale values for the ruler with least number of scales with a length of 9
Fig.2 All minimal graceful graphs with 9 edges
（0，1）（1，2）（2，3）（3，4）…（ n-1，n ）
（0，2）（1，3）（2，4）…（n-2，n）
（0，3）（1，4）…（n-3，n）
………
（0，n-1）（1，n）
（0，n ）
Table 1 A subset of all 2 elements of set ｛0，1，2，…，n｝
长度其中的一组最省刻度

每组

中的

刻度数

所有不同的刻度组数长度其中的一组最省刻度

每组

中的

刻度数

所有不同的刻度组数
30，2，332220，4，9，14，19，20，21，22818
40，2，3，443230，2，5，8，12，21，22，2384
50，3，4，544240，6，12，19，20，21，22，23，249944
60，2，5，642250，6，13，20，21，22，23，24，259460
70，4，5，6，7512260，5，11，16，22，23，24，25，269166
80，3，6，7，858270，5，11，17，23，24，25，26，27956
90，3，7，8，954280，2，4，6，7，18，19，37，28912
100，4，7，8，9，10638290，2，5，8，11，15，27，28，2996
110，4，8，9，10，11630300，6，13，18，25，26，27，28，29，30102 036
120，4，9，10，11，12614310，6，13，19，26，27，28，29，30，3110890
130，3，7，11，12，1366320，6，13，20，27，28，29，30，31，3210304
140，5，10，11，12，13，147130330，5，11，17，23，29，30，31，32，3310120
150，5，11，12，13，14，15780340，3，6，10，14，19，31，32，33，341020
160，4，8，13，14，15，16732350，2，8，10，17，19，30，31，34，351010
170，4，9，14，15，16，17712360，1，5，9，16，23，30，33，35，36102
180，6，13，14，15，16，17，188500370，7，15，23，31，32，33，34，35，36，37112 678
190，5，10，15，16，17，18，198326380，6，13，19，26，33，34，35，36，37，3811974
200，5，10，16，17，18，19，208150390，6，13，20，27，34，35，36，37，38，3811362
210，5，11，17，18，19，20，21866400，5，11，16，23，30，36，37，38，39，4011100
Table 2 Scale data for the most scale-saving rulers with lengths from 3 to 40
Fig.3 Graceful labeling θ of the graph K1，1，m，n
xf （x）的上下界xf （x）的上下界xf （x）的上下界xf （x）的上下界
64≤f（6）≤4268≤f（26）≤94611≤f（46）≤126612≤f（66）≤15
75≤f（7）≤5278≤f（27）≤94711≤f（47）≤136713≤f（67）≤15
85≤f（8）≤5288≤f（28）≤104811≤f（48）≤136813≤f（68）≤15
95≤f（9）≤5299≤f（29）≤104911≤f（49）≤136913≤f（69）≤15
106≤f（10）≤6309≤f（30）≤105011≤f（50）≤137013≤f（70）≤16
116≤f（11）≤6319≤f（31）≤105111≤f（51）≤137113≤f（71）≤16
126≤f（12）≤6329≤f（32）≤105211≤f（52）≤137213≤f（72）≤16
136≤f（13）≤6339≤f（33）≤105311≤f（53）≤137313≤f（73）≤16
146≤f（14）≤7349≤f（34）≤105411≤f（54）≤147413≤f（74）≤16
156≤f（15）≤7359≤f（35）≤105511≤f（55）≤147513≤f（75）≤16
166≤f（16）≤7369≤f（36）≤105612≤f（56）≤147613≤f（76）≤16
177≤f（17）≤73710≤f（37）≤115712≤f（57）≤147713≤f（77）≤16
187≤f（18）≤83810≤f（38）≤115812≤f（58）≤147813≤f（78）≤16
197≤f（19）≤83910≤f（39）≤115912≤f（59）≤147914≤f（79）≤17
207≤f（20）≤84010≤f（40）≤126012≤f（60）≤148014≤f（80）≤17
218≤f（21）≤84110≤f（41）≤126112≤f（61）≤148114≤f（81）≤17
228≤f（22）≤84210≤f（42）≤126212≤f（62）≤158214≤f（82）≤17
238≤f（23）≤94310≤f（43）≤126312≤f（63）≤15
248≤f（24）≤94410≤f（44）≤126412≤f（64）≤15
258≤f（25）≤94510≤f（45）≤126512≤f（65）≤15
Table 3 Upper and lower bounds on the number of vertices f （x） for minimal graceful graphs with x edges
直尺长度其中一组包括两端点的最省刻度数值最省刻度数
410，1，4，10，16，22，28，34，36，39，4111
420，1，2，3，19，24，28，32，36，39，4211
430，1，3，6，13，20，27，34，38，42，4311
440，1，2，3，4，10，16，22，28，34，39，4412
450，1，2，3，4，5，12，20，26，33，39，4512
460，6，13，20，27，34，41，42，43，44，45，4612
470，1，2，3，4，10，17，24，31，36，42，4712
480，1，2，3，23，24，29，33，37，41，45，4812
490，1，2，3，24，29，30，34，38，42，46，4912
500，1，3，6，13，20，27，34，41，45，49，5012
510，1，2，3，4，5，6，7，16，26，34，43，5113
520，1，2，3，4，10，17，24，31，36，42，47，5213
530，7，15，23，31，39，47，48，49，50，51，52，5313
540，1，2，3，4，5，6，14，23，32，39，47，5413
550，1，2，3，4，5，12，20，28，36，42，49，5513
560，1，2，3，27，28，33，37，41，45，49，53，5613
570，1，3，6，13，20，27，34，41，48，52，56，5713
580，1，2，3，27，32，36，40，44，48，52，55，5813
590，1，2，3，4，5，12，20，28，36，42，49，55，5914
600，1，2，3，4，10，17，24，30，37，44，49，55，6014
610，1，2，3，4，5，6，14，23，32，39，47，54，6114
620，1，2，3，4，5，6，14，23，31，40，47，55，6214
630，1，2，3，4，5，6，14，23，32，41，48，56，6314
640，1，3，6，13，20，27，34，41，48，55，59，63，6414
650，1，6，14，22，30，38，46，54，56，58，61，63，6514
660，1，2，3，31，36，40，44，48，52，56，60，63，6614
670，1，2，3，4，5，12，19，26，33，40，47，54，61，6715
680，1，2，3，4，10，17，24，31，38，45，52，57，63，6815
690，1，2，5，12，19，26，33，40，47，54，61，63，67，6915
700，1，2，3，4，5，6，14，23，32，41，48，56，63，7015
710，1，3，6，13，20，27，34，41，48，55，62，66，70，7115
720，1，2，6，14，22，30，38，46，54，62，65，69，71，7215
730，1，6，14，22，30，38，46，54，62，64，66，69，71，7315
740，1，2，3，35，40，44，48，52，56，60，64，68，71，7415
750，1，2，3，4，10，17，24，31，38，45，52，59，64，70，7516
760，1，2，5，12，19，26，33，40，47，54，61，68，70，74，7616
770，1，2，3，4，5，6，14，22，30，38，46，54，62，70，7716
780，1，3，6，13，20，27，34，41，48，55，62，69，73，77，7816
790，1，2，3，4，5，12，20，28，36，44，52，60，66，73，7916
800，1，2，3，4，5，6，14，23，32，40，49，58，65，73，8016
810，1，2，3，4，5，6，7，16，26，36，46，56，64，73，8116
820，1，2，3，39，44，48，52，56，60，64，68，72，76，79，8216
Table 4 Scale data for the most scale-saving rulers with lengths from 41 to 82
[1]   曾令辉. 省刻度问题初探［J］. 数学通报， 2001 （10）： 36-37.
ZENG L H. A preliminary probe into the problem of the question of ruler with least number of scales［J］. Mathematical Bulletin， 2001 （10）： 36-37.
[2]   马克杰. 优美图［M］. 北京： 北京大学出版社， 1991.
MA K J. Graceful Graph［M］. Beijing： Peking University Press， 1991.
[3]   唐保祥. 2类包含K4的优美图及其注记［J］. 河北师范大学学报（自然科学版）， 2001， 25（3）： 304-305. DOI：10.3969/j.issn.1000-5854.2001.03.007
TANG B X. Two kinds of graceful graphs including K4 and their labeling［J］. Journal of Hebei Normal University （Natural Science Edition）， 2001， 25（3）： 304-305. DOI：10.3969/j.issn.1000-5854. 2001.03.007
doi: 10.3969/j.issn.1000-5854. 2001.03.007
[4]   唐保祥， 任韩. 优美图所有优美标号的生成算法［J］. 天津师范大学学报（自然科学版）， 2010， 30（4）： 5-8. DOI：10.3969/j.issn.1671-1114.2010.04.002
TANG B X， REN H. Generating algorithm for all graceful labeling of graceful graph［J］. Journal of Tianjin Normal University （Natural Science Edition）， 2010， 30（4）： 5-8. DOI：10.3969/j.issn. 1671-1114.2010.04.002
doi: 10.3969/j.issn. 1671-1114.2010.04.002
[5]   PEREIRA J， SINGH T， ARUMUGAM S. Edge consecutive gracefulness of a graph ［J］. Discrete Applied Mathematics， 2020， 280： 214-220. DOI：10.1016/j.dam.2018.09.019
doi: 10.1016/j.dam.2018.09.019
[6]   LLADO A， MOKHTAR H， SERRA O， et al. Distance-constrained labellings of Cartesian products of graphs［J］. Discrete Applied Mathematics， 2021， 304： 375-383. DOI：10.1016/j.dam.2021.08.012
doi: 10.1016/j.dam.2021.08.012
[7]   DEEN M， ELMAHDY G. New classes of graphs with edge δ-graceful labeling［J］. AIMS Mathematics， 2021， 7（3）： 3554-3589. DOI：10.3934/math.2022197
doi: 10.3934/math.2022197
[8]   DEEN M Z. Edge δ-graceful labeling for some cyclic-related graphs［J］. Advances in Mathematical Physics， 2019， 93： 1245-1260. DOI：10.1155/2020/6273245
doi: 10.1155/2020/6273245
[9]   牟亚蓉， 刘信生， 姚兵. 基于含圈非连通图优美性的拓扑图密码［J］. 华东师范大学学报（自然科学版）， 2020 （1）： 51-57. DOI：10.3969/j.issn.1000-5641. 201811045
MU Y R， LIU X S， YAO B. Topological graph passwords based on the gracefulness of disconnected graphs with circles［J］. Journal of East China Normal University （Natural Science）， 2020， 45（1）： 51-57. DOI：10.3969/j.issn.1000-5641. 201811045
doi: 10.3969/j.issn.1000-5641. 201811045
[10]   魏众德， 李敬文， 武永兰. 双圈图的优美性［J］. 吉林大学学报（理学版）， 2019， 57（1）： 42-48. DOI：10. 13413/j.cnki.jdxblxb.2017490
WEI Z D， LI J W， WU Y L. Gracefulness of bicyclic graphs［J］. Journal of Jilin University （Natural Science Edition）， 2019， 57（1）： 42-48. DOI：10. 13413/j.cnki.jdxblxb.2017490
doi: 10. 13413/j.cnki.jdxblxb.2017490
[11]   把丽娜， 刘倩， 刘信生， 等. 完全二部图优美性质探索［J］. 大连理工大学学报， 2017， 57（6）： 657-662. DOI：10.7511/dllgxb201706016
BA L N， LIU Q， LIU X S， et al. Exploration of gracefulness of some complete bipartite graphs［J］. Journal of Dalian University Technology， 2017， 57（6）： 657-662. DOI：10.7511/dllgxb201706016
doi: 10.7511/dllgxb201706016
[12]   唐保祥， 任韩. 两类图及其冠的优美标号［J］.东北师大学报（自然科学版）， 2017， 49（3）： 158-160. DOI：10.16163/j.cnki.22-1123/n.2017.03.031
TANG B X， REN H. The graceful labeling of two kinds graphs and its coronas［J］. Journal of Northeast Normal University （Natural Science Edition）， 2017， 49（3）： 158-160. DOI：10.16163/j.cnki.22-1123/n.2017.03.031
doi: 10.16163/j.cnki.22-1123/n.2017.03.031
[13]   唐保祥，任韩. 2类优美图的冠的优美标号［J］. 中山大学学报（自然科学版）， 2015， 54（5）： 24-27.
TANG B X， REN H. Graceful labeling of the crown for two kinds of graceful graphs ［J］. Acta Scientiarum Naturalium Universitatis Sunyatseni， 2015， 54（5）：24-27.
[14]   唐保祥， 任韩. 3类特殊图的优美性［J］. 武汉大学学报（理学版）， 2014， 60（6）： 553-556. DOI： 10. 14188/j.1671-8836.2014.06.001
TANG B X， REN H. The gracefulness of three types special graphs［J］. Journal of Wuhan University （Natural Science Edition）， 2014， 60（6）： 553-556. DOI：10.14188/j.1671-8836.2014.06.001
doi: 10.14188/j.1671-8836.2014.06.001