Consider two lists A and B of three strings on {0,1} 𝑋 : List A List B 1 111…

PCP instance X (pairs): A = [1, 10111, 10], B = [111, 10, 0].

Solution for X:

1. Take the index sequence 2,1,1,3 (use the second tile, then the first tile twice, then the third tile).

2. Concatenate A-sides: 10111 · 1 · 1 · 10 = 101111110.

3. Concatenate B-sides: 10 · 111 · 111 · 0 = 101111110.

4. Since the two concatenations are equal, the PCP instance X has a solution.

PCP instance Y (pairs): A = [10, 011, 101], B = [101, 11, 011].

Proof that Y has no solution:

• Length constraint: lengths of A-tiles are 2,3,3 and of B-tiles are 3,2,3. For counts x1,x2,x3 of how many times each tile is used, length equality requires 2x1+3x2+3x3 = 3x1+2x2+3x3, which simplifies to x2 = x1.

• Count difference of 1s minus 0s: A-tiles contribute 0,1,1 respectively; B-tiles contribute 1,2,1 respectively. Equating totals gives x2 + x3 = x1 + 2x2 + x3, which simplifies to x1 = -x2, so x1 = x2 = 0 (counts nonnegative).

• Combining with the length constraint (x2 = x1) forces x1 = x2 = 0, so any hypothetical solution would use only the third tile repeated.

• But the third tile gives A3 = 101 and B3 = 011; for any positive n, (101)^n starts with '1' while (011)^n starts with '0', so they can never be equal. Therefore no solution exists for Y.

Conclusion: The first instance (X) has a solution (example sequence 2,1,1,3) and the second instance (Y) has no solution. Hence only the PCP in X has a solution.