2  Problems

“Problem. A doubtful or difficult question; a matter of inquiry, discussion, or thought; a question that exercises the mind.”

(Oxford English Dictionary 1989)

Problems often involve more complexity than straightforward exercises in that the method of solution is not proscribed. We will differentiate between two types of problems and present a general framework, introduced by Pólya in a series of monographs (Pólya 1945, 1954a, 1954b), for understanding problem solving.1 This framework is intended to serve as a foundation for analysing your approach to problem solving.

2.1 Two Types of Problems

We distinguish between different types of problems based on the desired goal. These are problems to find and problems to prove.

Problems to find

The task is to produce or create an object (often a mathematical object or an idea)2 that satisfies specified conditions, which may include a number, function, construction, example, counterexample, or algorithm. Common prompts for these tasks include terms such as determine, compute, construct, and classify. The success of these endeavors is evaluated based on criteria such as correctness, completeness, and in some cases, optimality or uniqueness.

NoteExample of a problem to find

Find all integers n such that n(n+1) is a perfect square.

Problems to prove

The task is to justify a claim beyond reasonable doubt. Typical prompts include: show, prove, disprove, establish, and deduce. To be successful, one must ensure validity, clarity, and appropriate use of definitions and prior results.

NoteExample of a problem to prove

Prove there are infinitely many primes congruent to \;3\mod 4.

In this module…

In this module, we will focus on problems to find. We will consider traditional problems arising from mathematics and physics that have well-known solutions. We will also consider problems of a computational nature and arising from industry.

When engaging in our problem solving sessions, please follow two rules: 1. If you know the solution, please do not spoil the fun. 2. If you do not know the solution, please do not be afraid to ask questions.

The first rule is to encourage you to engage in the problem-solving process without revealing the answer prematurely, allowing everyone to explore and learn. The second is to promote an open environment where you feel comfortable seeking help and guidance, fostering collaboration and learning.

WarningMany problems mix both tasks!

Find all objects with property P and prove your list is complete.

2.2 Problem solving framework

In this module, we will make use of a particular problem solving framework for reflection and organising our thoughts. This problem solving framework (see Pólya 1945) is a four-phase cycle for tackling open-ended problems. The phases of the problem solving framework are depicted in Figure 2.1; the name of each phase is listed in bold text, with key terms in normal text. Knowing which phase of the framework you are in may help you choose the best prompt to move forward (see further the table below in Section 2.3).

%%{init: { "flowchart": { "htmlLabels": false } }}%%

flowchart TB
  U[**Understand the problem**<br>Unknowns, Data, Constraints]
  P[**Devise a plan**<br>Heuristics]
  C[**Carry out the plan**<br>Justify steps, Check subgoals]
  L[**Look back**<br>Verify, Reflect, Generalise]
  
  S{Solution?}
  
  X([Stuck!])

  U --> P 
  P --> C 
  C --> S
  S -- Yes --> L
  S -- No --> X
  X -. Pivot/Refine .-> P
Figure 2.1: The four phases of problem solving within a problem solving cycle.

The phases are roughly as follows. First, understand the problem: identify data/givens, unknowns, and conditions/constraints; restate the problem in your own words; sketch, tabulate, or probe small cases. This phase involves translating abstract ideas into mathematical ones so that quantitative reasoning can be applied. Understandiing the problem is sometimes the hardest phase, particularly when considering problems arising from real-world challenges! Next, devise a plan by choosing a route. Possible routes are to work backward, look for patterns, simplify or specialise, use symmetry or invariants, introduce an auxiliary object, estimate or bound, change representation, or reduce to a known problem (we will investigate these problem solving routes later in Chapter 3). Then carry out your plan: execute cleanly, justify each step, check subgoals, and pivot if a step stalls. Remember that getting stuck is part of learning. Finally, look back: verify the result, test edge cases, assess efficiency and clarity, and capture the key idea you have uncovered. The final phase is essential; to quote Socrates, “the life which is unexamined is not worth living”.3 Use the framework to reflect on what you learned so your future problem solving gets faster and more reliable.

2.3 Phases of problem solving

Use Table 2.1 as a working checklist and a reflection guide, not a rigid recipe. As you tackle an open-ended problem, you might find that you are “stuck”. First, don’t panic! Decide which phase of the problem solving framework you are in and scan the prompts in that row. Answering the prompt may lead to a concrete next action. Reflect on this new action for a few minutes; if it stalls, return to the table, pick a different prompt, or take a break. Over time, the prompts will become more familiar and the process of solving an open-ended problme will be less daunting.

Table 2.1: Phases of problem solving, adapted from (Pólya 1945, xvi–xvii).
Phase Purpose Prompts to ask yourself Useful tactics
Understanding the problem For a problem to find, understand the problem by making the unknown, data, and conditions precise. What is unknown? What is given or what are the data? What conditions/constraints apply? Can I restate the task in my own words? What do small or extreme cases look like? What diagram/notation will help? Define symbols. Draw a figure. List constraints. Test tiny cases. Identify edge cases. Rephrase the question. Separate various parts of the condition.
Devising a plan Find the connection between the data and the unknown that provides a path towards a solution. Have I seen the problem before? Have I seen the same problem in a slightly different form? Do I know a related problem? Do I know a theorem that might be useful? Can I work backward from the goal? Can I simplify/specialise first? What pattern, invariant, or symmetry might apply? Can I introduce an auxiliary element or change representation? Did I use all the data in devising my plan? Did I account for all the conditions? Heuristics such as analogy; special/edge cases; generalisation; using invariants and symmetry; bounding/estimating; pigeonhole; substitution; set up equations or a new diagram.
Carry out your plan Carry out plan, checking each step! Would I be able to clearly explain that the step is correct? Can I prove that it is correct? Does each step follow from assumptions or known results? What subgoal can I verify now? If a step fails, which alternative route will I try next? Justify steps. Prove lemmas. Compute carefully. Frequently take stock (checkpoint). Pivot quickly if a line of attack stalls. Don't panic.
Look back Validate the result and reflect on learning. Can I check the result? Can you explain your arguments? Does the result meet all conditions? Any counterexamples? Is it complete/optimal? Can I shorten or generalise the solution? Can I derive the result differently? What key idea made it work, and where else could it apply? Record the central insight. Phases of the framework. Prompts answered. Heuristics used and how.

  1. George Pólya was a Hungarian-American mathematician who made contributions to probability theory, combinatorics, number theory, and numerical analysis. More information about his life and work can be found at the MacTutor Archive: https://mathshistory.st-andrews.ac.uk/Biographies/Polya/.↩︎

  2. We are not engineers ;).↩︎

  3. This famous remark was supposedly uttered by Socrates at his trial (for impiety and corrupting youth) and is recorded in Apology (Plato (transl. Benjamin Jowett) 2009).↩︎