45. Answer: 7 moves. Draw all the diagonals of a 129-gon, connecting vertices that are two apart. This will form a cycle of length 129. We will call vertices adjacent if they are adjacent in this cycle. Thus, Vasya should mark a vertex adjacent to the one marked by Petya on each move. We will remove the marked vertices, so after the first pair of moves, our cycle will become a chain of length 127. After each pair of moves, we will consider the remaining chains of unmarked vertices. The length of a chain is the number of vertices in it, and a chain is called odd if it contains an odd number of vertices.

Vasya's strategy: It is not hard to see that Vasya can ensure that after the $k$-th pair of moves, among the remaining chains, there is exactly one odd chain, and its length will be at least $2^{8-k}-1$. Thus, he will be able to make at least 7 moves.

Petya's strategy: Each time, mark the midpoint of the only odd chain. Vasya will mark an adjacent point, and after their pair of moves, there will be exactly one odd chain, and its length after $k$ pairs of moves will be exactly $2^{8-k}-1$.
45. Given a 129-gon. Petya and Vasya are playing a game. They take turns marking the vertices of this polygon, with Petya making the first move. Petya can mark any unmarked vertex on each of his turns. Vasya can mark any unmarked vertex that is two positions away from the vertex Petya marked on his last turn. The game ends when Vasya cannot make his move. What is the maximum number of moves Vasya can make regardless of Petya's play?