少即是多
Lesses More
题目详情
题目从一个方格四角的非负整数出发，定义相邻差分操作并反复迭代。需要分析初始排列在归一化后的长期行为，并找出满足条件的整数序列。
英文原题
Assign four nonnegative integers to the corners of a square, which we designate the active square. During a step, for each side of the active square, the absolute difference between the numbers on that side’s endpoints is assigned to its midpoint. Then these four new midpoints are connected into a new square (tilted 45 degrees from the previous). This new smaller square becomes the active square. Continue these steps until the active square has all zeroes on its corners.
Define f(a, b, c, d) to be the total number of squares drawn during this process when beginning with the numbers (a, b, c, d) written on the starting square in clockwise order. For example, given a starting arrangement of (10, 6, 3, 1), we would get the sequence of
(4, 3, 2, 9)
(1, 1, 7, 5)
(0, 6, 2, 4)
(6, 4, 2, 4)
(2, 2, 2, 2)
(0, 0, 0, 0)
where the game ends (pictured above). So f(10, 6, 3, 1) = 7. And trivially, f(0, 0, 0, 0) = 1.
Consider the set S = {(a, b, c, d) | a, b, c, and d are all integers with 0 <= a, b, c, d <= 10,000,000}. Let M be the maximum value f obtains on S. Find (a, b, c, d) in S with minimum sum (a+b+c+d) where f(a, b, c, d) = M. Enter your answer as a semicolon-separated list, 10;6;3;1 for example.
解析
把活动方格四角数推广为实数向量 ，一步操作为 。归一化后只需研究 。寻找归一化不动点得到方程 ，其根约为 ，对应 。在整数点中搜索最接近该不动点的候选，得到 ，其 值为 44。
英文解析
This month we searched for a starting arrangement to an algorithm that maximized its number of steps. We can generalize the active square’s corner numbers from integers to reals, consider the four numbers on the corners of the active square to be an element of R4, and the function representing a step to be
| f((a,b,c,d)) = ( | a-b | , | b-c | , | c-d | , | d-a | ). |
Without loss of generality we can consider an input (a,b,c,d) to have a largest and b>d. By simple case checking, the only such arrangement that doesn’t lead to (0,0,0,0) in fewer than 10 steps has a>b>c>d. We further can “normalize” our input by subtracting d from everything, and then dividing by a-d, to get a general input of the form (1,x,y,0) for 1>x>y>0. In order to find arbitrarily long sequences of integer inputs for f we want to search for a real input to f that never reaches (0,0,0,0). This would be achieved if the normalized output of f matches the input. In normalized space, we want either
x = (1-x-y)/(1-y) AND y = (x-2y)/(1-y)
or
x = (x+y-1)/x AND y = (2x-y-1)/x
The first set of equations resolves to
x3-4x2+6x-2=0
which happily has a zero at approximately x=0.456311…, and a corresponding y=0.160713….
The second set of equations resolves to a cubic without a zero between 0 and 1, so there is a unique fixed point of this normalized function. Now the only challenge is to find integer points (a,b,c,0) that are as close as possible, when normalized, to (1,x,y,0), and test them to see how large their g values are. Searching over all c values between 1 and 10,000,000, choosing a small set of a and b that are near to c/y and cx/y respectively, will find the optimal quadruple 8646064;3945294;1389537;0, which has g value 44. Observant solvers noticed some overlaps with these special input integers and the Tribonacci sequence!
Congrats to this month’s solvers that found the smallest maximal input!