On Problem Solving
Author:
61plus
Last Updated:
6 лет назад
License:
Creative Commons CC BY 4.0
Аннотация:
Note on problem solving
\begin
Discover why 18 million people worldwide trust Overleaf with their work.
Note on problem solving
\begin
Discover why 18 million people worldwide trust Overleaf with their work.
\documentclass[11pt]{extarticle}
%% Language and font encodings
\usepackage[english]{babel}
\usepackage[utf8x]{inputenc}
\usepackage{gensymb}
\usepackage{amssymb}
\usepackage[inline]{asymptote}
\usepackage[dvipsnames]{xcolor}
\usepackage{mdframed}
%% Sets page size and margins
\usepackage[a4paper,top=3cm,bottom=2cm,left=3cm,right=3cm,marginparwidth=1.75cm]{geometry}
\definecolor{used}{RGB}{250, 200, 200}
\definecolor{ri}{RGB}{200, 250, 200}
%% Useful packages
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage[colorinlistoftodos]{todonotes}
\usepackage[colorlinks=true, allcolors=blue]{hyperref}
\newmdenv[skipbelow=6mm]{kotak}
\title{On Problem Solving}
\author{}
\date{8 May 2019}
\begin{document}
\maketitle
\section{Introduction}
It is important to sit back and reflect on how one solves a problem. You may find that you can solve some problems but not others, even if it maybe your strongest topic. It is common to see it as, "oh I have not seen this method before". However, as now you possess a majority of the tools you will need to solve a question, perhaps it is more important to peer into your own thought process to see how you can come up with such methods yourself.
\\\\
There are a few ways to think about this.
\section{Motivation}
It is good that most people now talk about the "motivation" for a solution. Talking about the motivation allows us to peer into the subconscious of the problem-solver, for example, a person can rule out certain approaches to an inequality question just by looking at the equality cases and knowing whether the approach allows for them.
However it can be dangerous if one equates this to that every solution comes from small motivatable steps. This is certainly not the case. Two different people will most likely solve the question via different thoughts, even if their solutions in the end are identical.
\begin{kotak}
A rectangle $\mathcal{R}$ with odd integer side lengths is divided into small rectangles with integer side lengths. Prove that there is at least one among the small rectangles whose distances from the four sides of $\mathcal{R}$ are either all odd or all even.
\end{kotak}
For this problem, one can certainly say that, the motivation to try colouring is that odd and even hints at parity. This is certainly possible if the person has a lot of experience in dealing with such parity problems. However, for another person, this may not be an adequate motivation, and he will never think in this manner anyway. Indeed, one finds that many people will find this easy simply because, it is a Q1 so try all the simple tools available, or colouring is just the most instinctive thing to do without any actual thought process.
\section{Hard and Soft Techniques}
\url{https://usamo.wordpress.com/2019/05/03/hard-and-soft-techniques/}
\\\\
This is from a post by Evan Chen. The idea is that techniques can be categorised into two types, hard and soft ones.
\subsection{Hard Techniques}
Hard techniques refer to those bread and butter skills that most people have picked up. For example:
\begin{itemize}
\item Looking at $v_p$ in number theory problems
\item Knowing how to induct
\item Bashing geometry problems with Coord-Geom/Trigo/Complex
\end{itemize}
\subsection{Soft Techniques}
Soft techniques refer to things you try that do not yield the solutions, but give hints to what kind of approach you should take. Examples are:
\begin{itemize}
\item Looking at small cases allow you to guess the general bound.
\item Going to the end results and derive some equivalent conditions, especially in geometry.
\end{itemize}
And the idea is that you should attempt a mix of hard/soft techniques, especially soft techniques if you are stuck for a long time after throwing hard techniques at the problem.
\section{Boldness and Carefulness}
This comes from a Chinese article. A careful attempt to solve a problem is to understand the entire structure of what's given. A bold attempt is to make some big leaps and only look at specific parts of the structure. To put it in clearer context, consider the following problem:
\begin{kotak}
Let $A = (a_1, a_2, \ldots, a_{2001})$ be a sequence of positive integers. Let $m$ be the number of 3-element subsequences $(a_i,a_j,a_k)$ with $1 \leq i < j < k \leq 2001$, such that $a_j = a_i + 1$ and $a_k = a_j + 1$. Considering all such sequences $A$, find the greatest value of $m$.
\end{kotak}
It is an easy problem (you can try it). The careful attempt to do this is to arrange all the $a_i$ in non-decreasing order then slowly smooth your way to victory. However, the bold way destroys it instantly: Take the numbers $\pmod{3}$ and let there be $a,b,c$ of remainder $0,1,2$. It is clear that any tuple that satisfies must have one number from each residue class. Hence total number of tuples is bounded by $abc\leq 667^3$. Equality is easily achieved by choosing $667$ of each of $1,2,3$.
For the mast majority of problems, making careful attempts at figuring out the structure of the problem is the most critical part. However sometimes $1$ or $2$ bold steps are needed to reduce the amount of information you have to handle. A problem that can be done via careful attempts is usually easy-medium as they are considered "standard". On the other hand, the bold steps are often the hardest parts of the problem and can make a problem become underrated, since not every time you take a bold step it is guaranteed to work.
It maybe true that for stronger contestants, they are able to handle more information/complicated structures, and thus become hesitant to throw away any information. This is a disadvantage when it comes to certain type of problems. For example, many sequence problems are resolved by finding a clever bound for the terms. However it can be very difficult to make this bold step because you are throwing away something that is deterministic (the sequence) for a set of ranges. The key here is how much information you can afford to lose without making the problem statement false. Inequalities require the most balance in your approach, as every step seem to be a bold step which loosens something, and to solve these problems you need good intuition on the size of terms and how far you can loosen them.
Finally, they also mentioned that 2017 Problem 3 and 5 are also example of such problems, where bold steps are needed.
\begin{kotak}
Q5: An integer $N \ge 2$ is given. A collection of $N(N + 1)$ soccer players, no two of whom are of the same height, stand in a row. Sir Alex wants to remove $N(N - 1)$ players from this row leaving a new row of $2N$ players in which the following $N$ conditions hold:
\\($1$) no one stands between the two tallest players,
\\($2$) no one stands between the third and fourth tallest players,
\\$\;\;\vdots$
\\($N$) no one stands between the two shortest players.
Show that this is always possible.
\end{kotak}
The bold step is to try algorithms instead of fiddling around with direct induction which doesn't work well. One possible way of telling that algorithms might work out, is that for any situation one can quite easily pick out the required list of people, so the there should be some flexibility in picking the people.
\begin{kotak}
Q3: A hunter and an invisible rabbit play a game in the Euclidean plane. The rabbit's starting point, $A_0,$ and the hunter's starting point, $B_0$ are the same. After $n-1$ rounds of the game, the rabbit is at point $A_{n-1}$ and the hunter is at point $B_{n-1}.$ In the $n^{\text{th}}$ round of the game, three things occur in order:
The rabbit moves invisibly to a point $A_n$ such that the distance between $A_{n-1}$ and $A_n$ is exactly $1.$
A tracking device reports a point $P_n$ to the hunter. The only guarantee provided by the tracking device to the hunter is that the distance between $P_n$ and $A_n$ is at most $1.$
The hunter moves visibly to a point $B_n$ such that the distance between $B_{n-1}$ and $B_n$ is exactly $1.$
Is it always possible, no matter how the rabbit moves, and no matter what points are reported by the tracking device, for the hunter to choose her moves so that after $10^9$ rounds, she can ensure that the distance between her and the rabbit is at most $100?$
\end{kotak}
This was a crazy one, which explains the number solves. If you read Jeck's solution, and compare to others' solutions he retains a lot of unnecessary information in the ice-cream, as only two points are really needed. However he also pointed out that it is very daring (and a sign of a genius) to make the bold step of throwing away everything except the two crucial points. Jeck's solution throws away just enough clutter to make the problem solvable.
\section{Conclusion}
The purpose of this is to bring awareness to the meta-problem solving skills. There is no clear cut formula one should follow. The important thing is to reflect on what is lacking in your problem solving process as it is easy to only tunnel on the various tricks/methods during intensive training.
\end{document}