A recursive algorithm of combinatorial difference set design for least scale number on ruler(最省刻度尺设计的组合差集递推算法)

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

Keywords

• ruler with least number of scales(最省刻度尺)
• graceful labeling(优美标号)
• minimal graceful graph(极小优美图)
• graceful labeling algorithm(优美标号算法)
• combinatorial difference recursive algorithm(组合差集递推算法)