|
%I #18 Mar 14 2023 12:59:37
%S 0,1,4,9,29,97
%N a(n) is the smallest integer t such that every length-t walk from the origin (0,0) taking steps of either (0,1) or (1,0) is guaranteed to have n points that are collinear.
%C By length-t we mean the number of steps, one less than the number of points.
%C It is known that a(7) >= 261.
%C Longest sequences avoiding n collinear points, encoded by 1 for (0,1) and 2 for (1,0):
%C n = 3: 121
%C n = 4: 11211211
%C n = 5: 1121112111211122212221222122
%C n = 6: 112111222212222122221211211112112122221222212222122221211211112111221222212222122221221112111221
%H J. L. Gerver and L. T. Ramsey, <a href="http://projecteuclid.org/euclid.pjm/1102784513">On certain sequences of lattice points</a>, Pacific J. Math. 83 (1979), 357-363.
%e a(3) = 4 because two consecutive identical steps from (0,0) generate 3 collinear points, so the first three steps must be (0,1), (1,0), (0,1) or its complement. Then no matter what is chosen for the next step, three collinear points are generated.
%K nonn,more
%O 1,3
%A _Jeffrey Shallit_, Nov 06 2013
|
