login
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.
0
0, 1, 4, 9, 29, 97
OFFSET
1,3
COMMENTS
By length-t we mean the number of steps, one less than the number of points.
It is known that a(7) >= 261.
Longest sequences avoiding n collinear points, encoded by 1 for (0,1) and 2 for (1,0):
n = 3: 121
n = 4: 11211211
n = 5: 1121112111211122212221222122
n = 6: 112111222212222122221211211112112122221222212222122221211211112111221222212222122221221112111221
LINKS
J. L. Gerver and L. T. Ramsey, On certain sequences of lattice points, Pacific J. Math. 83 (1979), 357-363.
EXAMPLE
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.
CROSSREFS
Sequence in context: A210969 A059345 A127768 * A241393 A186650 A091658
KEYWORD
nonn,more
AUTHOR
Jeffrey Shallit, Nov 06 2013
STATUS
approved