notebooks/01_proofs_convincing_arguments.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Existential Statements in Number Theory\n",
    "\n",
    "To check whether $a$ is divisible by $b$, one checks whether the remainder of $a$ when divided by $b$ is equal to zero. The remainder is found using the % operator. The following snippet shows that $237$ is divisible by $3$ and is not divisible by $7$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "6\n"
     ]
    }
   ],
   "source": [
    "print(237 % 3)\n",
    "print(237 % 7)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Problem.** Is there a positive integer that is divisible by $13$ and ends with $15$?\n",
    "\n",
    "To prove that such a number exists, it is enough to give a single example. One such example is $715$: it ends with $15$ and it is divisible by $13$ ($715=13\\cdot 55$). This already proves the existence, and we don't even need to explain how we have found this integer. Still, the following three lines of code help to find all such integers in the range $[0, 9\\,999]$. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "715\n",
      "2015\n",
      "3315\n",
      "4615\n",
      "5915\n",
      "7215\n",
      "8515\n",
      "9815\n"
     ]
    }
   ],
   "source": [
    "for n in range(10 ** 4):\n",
    "    if n % 13 == 0 and n % 100 == 15:\n",
    "        print(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This program checks all numbers in $\\texttt{range(10 ** 4)}$. Here, $\\texttt{10 ** 4}$ stands for $10^4=10\\,000$. In $\\texttt{python}$, $\\texttt{range(N)}$ where $N$ is some non-negative number is \n",
    "a *list* (sequence) of $\\texttt{N}$ numbers $0,1,2,\\ldots,\\texttt{N}-1$. The $\\texttt{for}$ loop goes over all of them in this order; the $\\texttt{if}$ operator checks whether they have the required properties. The last two digits of an integer $\\texttt{n}$ can be computed as $\\texttt{n % 100}$. In general, $\\texttt{n % m}$ denotes the *remainder* when dividing $\\texttt{n}$ by $\\texttt{m}$. (Imagine we have $n$ identical books on the table and pack them into boxes that contain $m$ books each. Then $n\\,\\%\\,m$ books *remain* unpacked.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Problem.** Find a two-digit (positive) integer that becomes 7 times smaller when its first (=leftmost) digit is removed.\n",
    "\n",
    "Let's try. Consider all two-digit integers that are divisible by 7:\n",
    "$$\n",
    "14,\\, 21,\\, 28,\\, 35,\\, 42,\\, 49,\\, 56,\\, 63,\\, 70,\\, 77,\\, 84,\\, 91,\\, 98.\n",
    "$$\n",
    "We know that dividing the required integer by $7$ should result in a single digit integer. This allows us to rule out all numbers starting from $70$ from the list. We can then check manually that out of the remaining numbers the only one satisfying the required property is $35$. \n",
    "\n",
    "The argument above is simple, but still some reasoning is needed. One could use a brute force search instead."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "35\n"
     ]
    }
   ],
   "source": [
    "for n in range(10, 100):\n",
    "    if n == 7 * int(str(n)[1:]):\n",
    "        print(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This code goes through all integers in the range $[10,99]$. In general, $\\texttt{range(a, b)}$ where $\\texttt{a}\\le\\texttt{b}$ are integers, denotes a list that contains $\\texttt{a},\\texttt{a+1},\\ldots,\\texttt{b-1}$ (empty if $\\texttt{a}=\\texttt{b}$). To remove the first digit of a number, we convert it to a string \n",
    "(by calling the $\\texttt{str()}$ function), then use slicing ($\\texttt{[1:]}$) to remove the first symbol \n",
    "of the resulting string, and finally convert the resulting string back to an integer."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Non-constructive Proofs\n",
    "\n",
    "Can we prove the existence of an object with some property without giving an example? This sounds counterintuitive, but sometimes it is possible. \n",
    "\n",
    "**Problem.** There exists an integer $n$ such that\n",
    "$$\n",
    "2^n + 3^n \\le 10^{1000} \\quad\\text{and}\\quad 2^{n+1}+3^{n+1} > 10^{1000}\n",
    "$$\n",
    "Do you see why?\n",
    "\n",
    "For small $n$ (say, for $n=1$) the first inequality is true. On the other hand, for large $n$ the second one is true. Consider, for example, $n=4000$. For this $n$, the first term alone is large enough: $2^{n+1}>2^{4000}=16^{1000}>10^{1000}$. But we need to find $n$ such that both inequalities are true at the same time. We need to find $n$ such that $2^n+3^n \\le 10^{1000}$, but increasing $n$ by $1$, we reverse the inequality.\n",
    "\n",
    "Intuitively, if we were inside and now are outside, we had to cross the boundary at some point. Let us increase $n$ (going from $1$ to $4000$) and just stop before $2^n+3^n$ becomes greater than $10^{1000}$. This will give us the required value of $n$. This finished the proof, but we can also find the value of $n$ as follows."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2096\n"
     ]
    }
   ],
   "source": [
    "for n in range(4000):\n",
    "    if 2 ** n + 3 ** n > 10 ** 1000:\n",
    "        print(n)\n",
    "        break"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us generate thirty $7$-digit numbers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1546686 8195564 9096041 1248847 4457754 8760813 \n",
      "9242586 5656024 3688205 1577196 9735382 9222271 \n",
      "6499115 2276567 5194248 7059236 1747532 8053077 \n",
      "3326819 6957282 7402286 8067637 5758324 5401017 \n",
      "8664354 3930486 6085259 7083207 3231003 8665986 \n"
     ]
    }
   ],
   "source": [
    "from random import randint, seed\n",
    "\n",
    "seed(10)\n",
    "\n",
    "for i in range(30):\n",
    "    print(randint(10 ** 6, 10 ** 7 - 1), end=' ')\n",
    "    if i % 6 == 5:\n",
    "        print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The function $\\texttt{randint(a,b)}$ returns \"randomly\" an integer in the range $\\texttt{a...b}$. \n",
    "We call it thirty times, using some additional tricks to have a nice printout. \n",
    "The second argument $\\texttt{end=' '}$ tells the $\\texttt{print}$ function that it should print a space character\n",
    "(instead of the newline character as it does by default). Then a call $\\texttt{print()}$ is used to get a newline character after groups of six numbers. (The call $\\texttt{seed()}$ initializes the pseudorandom generator used. This is done for reproducibility: it ensures that every time this program is called, the same thirty integers are generated. To get different thirty numbers, just change the argument of the $\\texttt{seed}$ function.)\n",
    "\n",
    "We claim that *there exist two disjoint subsets of this set of $30$ integers that have equal sum*. \n",
    "In other words, we can color some of the elements blue, and color *some* other elements red \n",
    "so that the sum of the red numbers is equal to the sum of the blue numbers.\n",
    "\n",
    "It looks counterintuitive: the numbers are rather long, and having two equal sums looks at first as a strange coincidence. Still the following (non-constructive) argument proves our claim. For every subset $A$ of this $30$-element set consider an integer $S(A)$, the sum of all elements in $A$. All $S(A)$ are less than  $30 \\cdot 10^7$ (about third of a billion). On the other hand, we have $2^{30}$ subsets (each can be described by a $30$-bit string saying which of the numbers are included and which are not, and there are $2^{30}$ binary strings of length $30$). Now the crucial point (pigeonhole principle):\n",
    "\t*since $2^{30} =1024^3 > 10 ^9 > 30\\cdot 10^7$, there exist different $A$ and $B$ such that $S(A)=S(B)$.*\n",
    "These $A$ and $B$ may include some common numbers, but these numbers can be deleted and still $S(A)=S(B)$ (since we delete the same numbers). This is exactly what we claimed. (Note that $A$ and $B$ are both non-empty: since $A\\ne B$, at least one of them is non-empty and has positive sum, and the other has the same sum.) Still, this non-constructive argument does not give any information about these two subsets."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}