Все жители города А всегда говорят правду, а все жители города В всегда врут. Известно, что жители города А бывают в городе В и наоборот.

ответ:

Путешественник спросить у нескольких (чтобы встретить жителей городов А и В) прохожих: «Вы из города А?».
Если услышит ответ «Да», то он в городе А, если услышит разные ответы, то он в городе В.