A231255 - OEIS

A231255

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.

%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