Ответ:

Если туфли купила Валентина, её утверждения «я не покупала» и «покупала Галина» оба ложны. Галина говорит одну правду («я не покупала») и одну неправду («Ольга тоже не покупала»), если туфли купила только Валентина. Ольга говорит обе части правдиво: Галина не покупала, Валентина купила.

Получаются требуемые типы ответов: Валентина лжёт, Галина говорит правду наполовину, Ольга говорит правду.

Ответ: туфли купила Валентина.