In how many ways can the set of integers $\{1,2, \ldots, 1995\}$ be partitioned into three nonempty sets so that none of these sets contains two consecutive integers?
We construct the three subsets by adding the numbers successively, and disregard at first the condition that the sets must be non-empty. The numbers 1 and 2 must belong to two different subsets, say $A$ and $B$. We then have two choices for each of the numbers $3,4, \ldots, 1995$, and different choices lead to different partitions. Hence there are $2^{1993}$ such partitions, one of which has an empty part. The number of partitions satisfying the requirements of the problem is therefore $2^{1993}-1$.