Spoiler
The traveler can't beat that with a Sense Motive. However:
Appraise: (1d20+12)[24]
Ah, I see what you tried there. Very clever. However, I am not so easily fooled when it comes to gems. I might not have the patience to sort them all, but I can certainly tell how much they're worth. Now then, will you help me or not?