The work presented hereafter deals with an important issue arising in frictional contact problems involving flexible bodies: the occurrence of more than one solution, with an emphasis on the quasi-static incremental problem in the presence of rectilinear obstacle and in two dimensions. The conditions for the existence of multiple solutions to the quasi-static incremental problem, with an intrinsic combinatorial character, are presented for several criteria. A simplified criterion is proposed that avoids the exponential character of the problem. An algorithm is proposed for the computation of all the solutions of the incremental problem and to verify the sharpness of the frictional coefficient estimates corresponding to the several criteria. The contributions may be summarized as follows: (i) new simplified (sufficient) criterion for uniqueness of solution based on the solution of an optimization problem, avoiding the exponential character of the (necessary and sufficient) complete criterion of Alart or of the (sufficient) criterion due to Andersson; the proposed criterion assumes that the onset of multiplicity is associated with a mode involving sliding in the whole contact candidate region. (ii) The use of the suggested algorithm to compute all the solutions of the quasi-static incremental problem (for a given loading) in a finite element version of Klarbring's two degree of freedom model. For some lumped mass examples, all the solutions were calculated and their dependencies on some parameters were discussed. The conditions under which a problem may have multiple solutions were also discussed for some lumped models.