number_arrangement.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Problem Description\n",
    "This is a mathematics problem shared by Lee Chan Lye on his youtube video [numbers arrangement](https://www.youtube.com/watch?v=sokgzCdvAIg).   \n",
    "\n",
    "Given a sequence of numbers $\\{1,2,3,4,...,2^n\\}$ with following properties:\n",
    "$$ \n",
    "1+4 = 2+3\n",
    "$$\n",
    "when $n=2$.\n",
    "<div style=\"text-align:center;\">$1+4+6+7 = 2+3+5+8 $</div>\n",
    "<div style=\"text-align:center;\">$1^2+4^2+6^2+7^2 = 2^2+3^2+5^2+8^2 $</div>\n",
    "when $n=3$.\n",
    "<div style=\"text-align:center;\">$1+4+6+7+10+11+13+16 = 2+3+5+8+9+12+14+15 $</div>\n",
    "<div style=\"text-align:center;\">$1^2+4^2+6^2+7^2+10^2+11^2+13^2+16^2 = 2^2+3^2+5^2+8^2+9^2+12^2+14^2+15^2 $</div>    \n",
    "<div style=\"text-align:center;\">$1^3+4^3+6^3+7^3+10^3+11^3+13^3+16^3 = 2^3+3^3+5^3+8^3+9^3+12^3+14^3+15^3 $</div>   \n",
    "when $n=4$.   \n",
    "\n",
    "Can you divide the integers from 1 to 32 into two disjoint sets of sixteen integers each, such that the sum of the $k$ th powers of the elements in each set are equal, for $k = 1,2,3,4$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Solution\n",
    "The basic idea is to generate next solution from current solution. Let's define some symbols to represent the number partition, $L$ stands for partition at left hand side and $R$ refers the another side. \n",
    "\n",
    "Consider intial selection for sequence $\\{1,2,3,4\\}$ is $\\{L, R, R, L\\}$. To generate next set of solution, simply duplicate the entire symbol sequence, revert it (from $L$ to $R$, from $R$ to $L$) and append it to form a new solution.\n",
    "\n",
    "Next generated solution would be\n",
    "<div style=\"text-align:center;\">Sequence $=\\{1,2,3,4,5,6,7,8\\} $</div>\n",
    "<div style=\"text-align:center;\">Arrangment $=\\{L,R,R,L,R,L,L,R\\} $</div>\n",
    "<div style=\"text-align:center;\">Left Partition $=\\{1,4,6,7\\} $</div>\n",
    "<div style=\"text-align:center;\">Right Partition$=\\{2,3,5,8\\} $</div>\n",
    "Repeat the same step yields\n",
    "<div style=\"text-align:center;\">Sequence $=\\{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16\\} $</div>\n",
    "<div style=\"text-align:center;\">Arrangment $=\\{L,R,R,L,R,L,L,R,R,L,L,R,L,R,R,L\\} $</div>\n",
    "<div style=\"text-align:center;\">Left Partition $=\\{1,4,6,7,10,11,13,16\\} $</div>\n",
    "<div style=\"text-align:center;\">Right Partition$=\\{2,3,5,8,9,12,14,15\\} $</div>\n",
    "\n",
    "Below python code will demonstrate the steps of generating solution recursively."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Round 1: \n",
      "Left partition is {1,4}.\n",
      "Right partition is {2,3}.\n",
      "Sum of power of 1 is correct.\n",
      "\n",
      "Round 2: \n",
      "Left partition is {1,4,6,7}.\n",
      "Right partition is {2,3,5,8}.\n",
      "Sum of power of 1 is correct.\n",
      "Sum of power of 2 is correct.\n",
      "\n",
      "Round 3: \n",
      "Left partition is {1,4,6,7,10,11,13,16}.\n",
      "Right partition is {2,3,5,8,9,12,14,15}.\n",
      "Sum of power of 1 is correct.\n",
      "Sum of power of 2 is correct.\n",
      "Sum of power of 3 is correct.\n",
      "\n",
      "Round 4: \n",
      "Left partition is {1,4,6,7,10,11,13,16,18,19,21,24,25,28,30,31}.\n",
      "Right partition is {2,3,5,8,9,12,14,15,17,20,22,23,26,27,29,32}.\n",
      "Sum of power of 1 is correct.\n",
      "Sum of power of 2 is correct.\n",
      "Sum of power of 3 is correct.\n",
      "Sum of power of 4 is correct.\n",
      "\n",
      "Round 5: \n",
      "Left partition is {1,4,6,7,10,11,13,16,18,19,21,24,25,28,30,31,34,35,37,40,41,44,46,47,49,52,54,55,58,59,61,64}.\n",
      "Right partition is {2,3,5,8,9,12,14,15,17,20,22,23,26,27,29,32,33,36,38,39,42,43,45,48,50,51,53,56,57,60,62,63}.\n",
      "Sum of power of 1 is correct.\n",
      "Sum of power of 2 is correct.\n",
      "Sum of power of 3 is correct.\n",
      "Sum of power of 4 is correct.\n",
      "Sum of power of 5 is correct.\n",
      "\n"
     ]
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "def print_sequences():\n",
    "    seq1 = ','.join([str(n) for n in left])\n",
    "    seq2 = ','.join([str(n) for n in right])\n",
    "    print(f\"Left partition is {{{seq1}}}.\")\n",
    "    print(f\"Right partition is {{{seq2}}}.\")\n",
    "\n",
    "def validate_sum(power):\n",
    "    sum1 = np.power(left, power).sum()\n",
    "    sum2 = np.power(right, power).sum()\n",
    "    if sum1 == sum2:\n",
    "        print(f\"Sum of power of {power} is correct.\")\n",
    "    else:\n",
    "        print(f\"Sum of power of {power} is wrong.\")\n",
    "        \n",
    "def update_sequences():\n",
    "    global left, right\n",
    "    count = len(left) + len(right)\n",
    "    left, right = np.concatenate((left, right + count)), np.concatenate((right, left + count))\n",
    "\n",
    "def print_summary(index):\n",
    "    print(f'Round {index}: ')\n",
    "    if index > 1:\n",
    "        update_sequences()\n",
    "    print_sequences()\n",
    "    for n in range(1, index + 1):\n",
    "        validate_sum(n)\n",
    "    print()\n",
    "\n",
    "# Initialize, this is first set of answer\n",
    "left = np.array([1, 4])\n",
    "right = np.array([2, 3])\n",
    "\n",
    "# Print summary for 1,2,3,4,5\n",
    "for n in range(1, 6):\n",
    "    print_summary(n)\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}