## Thursday, January 13, 2011

### A nice problem to test formal reasoning skills

Here's a problem that I think is easy if you're fluent with formal mathematical reasoning (and some facts from mathematics I don't want to reveal now :)), and close to impossible otherwise.

You are given two sets of positive integers: A and B. You start at point 0 on a line, and alternate jumps to the left and to the right, starting with a jump to the left. Whenever you jump to the left, you jump by a number chosen from A. Whenever you jump to the right, you jump by a number chosen from B.

Is any integer point reachable?

Example: A = {1, 5}, B = {2, 4}. To reach point -2, you can jump by -5, then by 4, then by -1, yielding -5+4-1=-2.

Constraints: A and B have at most 10000 elements, numbers in A and B are between 1 and 1000000000 (billion). Note that you can't jump to the left or to the right twice in a row - you have to alternate.

Source: SnarkNews Winter Series 2011, Round 2 (the round is over so it's fine to discuss solutions now).