Mathematical problem solving is the mainstay of the mathematics curriculum for Singapore schools. In the preparation of prospective mathematics teachers, the authors, who are mathematics teacher educators, deem it important that pre-service mathematics teachers experience non-routine problem solving and acquire an attitude that predisposes them to adopt a Pólya-style approach in learning mathematics. The Practical Worksheet is an instructional scaffold we adopted to help our pre-service mathematics teachers develop problem-solving dispositions alongside the learning of the subject matter. The Worksheet was initially used in a design experiment aimed at teaching problem solving in a secondary school. In this paper, we describe an application and adaptation of the MProSE (Mathematical Problem Solving for Everyone) design experiment to a university level number theory course for pre-service mathematics teachers. The goal of the enterprise was to help the pre-service mathematics teachers develop problem-solving dispositions alongside the learning of the subject matter. Our analysis of the pre-service mathematics teachers' work shows that the MProSE design holds promise for mathematics courses at the tertiary level.