Singapore Mathematical Olympiad (SMO)

Since $31\times 32=992$ and $31\times 33=1023$, any two numbers larger than $31$ cannot be neighbours. So there must be a number $<32$ between a pair of such numbers. Also $1$ cannot be chosen. Also the two neighbours of $31$ are $32$ or less. So the maximum number of chosen integers is $\le 30\times 2-1=59$. This bound can be achieved by the following where $11$ follows $31$ to form a cycle.

$11,83,12,76,13,71,14,66,15,62,16,58,17,55,18,52,19,49,$ $20,47,3,99,2,98,4,97,5,96,6,95,7,94,8,93,9,92,10,46,21,45,$ $22,43,23,41,24,39,25,38,26,37,27,35,28,34,29,33,30,32,31$