Решение:
Рассмотрим худший случай: если мы будем брать в первую очередь только левые (или только правые) туфли. Их всего 24 (12 красных и 12 серых). Следующая туфля обязательно будет парной к какой-то из тех, которые у нас есть. Значит, чтобы наверняка собрать пару, нужно взять 25 туфель.
Ответ: 25 туфель.