Sperner´s lemma and robust machines

Sperner´s lemma states that any admissible coloring of any triangulation of the unit triangle has a three-colored triangle. It is shown that any algorithm to find a three-colored triangle in any admissible coloring that treats the coloring itself as an oracle must be in the worst case linear in n. By making use of such lower bound, a negative answer is obtained for two problems regarding robust oracle machines left open by J. Hartmanis and L. Hemachandra (1990). By making use of techniques similar to those used in that paper, a third open problem is solved