You have JavaScript disable. So you will experiment an issue: you cannot submit comments (isso commenting software).

From intractable problem to tractable one

Xavier Bordoy

Table of Contents Keywords
"blog" "problema" "intractable" "simplificar" "transformar un exercici" "optimitzar" "funció afí"
Abstract

How I transform an intractable problem for my students to tractable one

I came across this problem (in castillian) from Brian Bolt “Aún más actividades matemáticas” (Bolt 1989) which consists of finding the fastest path between two points with different velocities in various regions:

Bolt’s original problem

As it is expressed in its solution this problem involves an optimization problem of a radical function, which obviously does not match the level of my students:

Solution of Bolt’s original problem

But I have liked the problem very much. So I decided to transform this to a more simple one: changing the metric in 2\mathbb{R}^2 from usual metric to taxi metric1. With this discretization, the problem is more easy (even it could be solved with try-and-see tactic): students just have to minimize an afine function. The moral of the tale is that we have to maximize the trip with the highest velocity.

The problem transformed

Perhaps this tactic of simplifying could be useful to you with other problems.

References

Bolt, Brian. 1989. Aún Más Actividades Matemáticas. Labor.


  1. Note that in the city the width and the length of the streets are not the same. So the metric is a modified taxicab: d(X,Y)=a|x1y1|+b|x2y2|d(X, Y) = a \cdot \lvert x_1 - y_1 \rvert + b \cdot \lvert x_2 - y_2 \rvert, where aa and bb are the width and lentgh of streets.↩︎