13

Part of 2003 AIME Problems

Problems(2)

Binary representations

Source:

N

be the number of positive integers that are less than or equal to 2003 and whose base-2 representation has more 1's than 0's. Find the remainder when

N

is divided by 1000.

ceiling functionfunction

Another Random Bug

Source:

A bug starts at a vertex of an equilateral triangle. On each move, it randomly selects one of the two vertices where it is not currently located, and crawls along a side of the triangle to that vertex. Given that the probability that the bug moves to its starting vertex on its tenth move is

m/n,

m

n

are relatively prime positive integers, find

m+n.

probabilitycountingdistinguishabilitymodular arithmeticfunctionlimitvector