MathsJam June 2018 - Subset

MathsJam-2018-06_Subset.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# MathsJam 2018-06\n",
    "\n",
    "## Puzzle - Subset\n",
    "\n",
    "> Does there exist a subset of {1,2,3,4,5,6,7,8,9} which contains:\n",
    "1. an odd number of odd numbers\n",
    "2. an even number of even numbers\n",
    "3. a prime number of prime numbers\n",
    "4. a composite number of composite numbers\n",
    "5. a square number of square numbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Argument\n",
    "\n",
    "This can be proved by hand. The strongest constraints are number 4 and 5, composite and square numbers.\n",
    "\n",
    "Starting from the base set:\n",
    "\n",
    "$ S = \\{1, 2, 3, 4, 5, 6, 7, 8, 9 \\} $\n",
    "\n",
    "\n",
    "#### Square numbers\n",
    "\n",
    "And applying 5, there should be a square number of squares numbers.\n",
    "There are only 3 square numbers available (1, 4, 9).\n",
    "There can't be 9 of them, and there can't be 4 either because only 3 are available. So there can only be **1** square number, which could be any of $\\{1, 4, 9\\}$\n",
    "\n",
    "This gives 3 possibilities:\n",
    "\n",
    "$S1 = \\{1, 2, 3, 5, 6, 7, 8\\}$ (keep 1)\n",
    "\n",
    "$S2 = \\{2, 3, 4, 5, 6, 7, 8\\}$ (keep 4)\n",
    "\n",
    "$S3 = \\{2, 3, 5, 6, 7, 8, 9\\}$ (keep 9)\n",
    "\n",
    "#### Composite numbers\n",
    "\n",
    "Applying 4, there must be a composite number of composite numbers. The lowest composite number is **4**, but:\n",
    "- S1 has only 2 composite numbers: 6 and 8\n",
    "- S2 has only 3 composite numbers: 4, 6 and 8\n",
    "- S3 has only 3 composite numbers: 6, 8 and 9\n",
    "\n",
    "None of the sets match condition 4. There is no solution."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Bruteforce program"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import combinations\n",
    "from sympy import primerange"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "set: {1, 2, 3, 4, 5, 6, 7, 8, 9}\n",
      "odds: {1, 3, 5, 7, 9}\n",
      "evens: {8, 2, 4, 6}\n",
      "primes: {2, 3, 5, 7}\n",
      "composites: {8, 9, 4, 6}\n",
      "squares: {1, 4, 9}\n"
     ]
    }
   ],
   "source": [
    "N = 10\n",
    "base = {i for i in range(1, N)}\n",
    "odds = {i for i in range(1, N, 2)}\n",
    "evens = {i for i in range(2, N, 2)}\n",
    "primes = set(primerange(2, N))\n",
    "composites = {i for i in range(2, N) if i not in primes}\n",
    "squares = {i ** 2 for i in range(1,int(N ** 0.5 + 1))}\n",
    "\n",
    "print(f'set: {base}')\n",
    "print(f'odds: {odds}')\n",
    "print(f'evens: {evens}')\n",
    "print(f'primes: {primes}')\n",
    "print(f'composites: {composites}')\n",
    "print(f'squares: {squares}')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def count_odds(ls):\n",
    "    return sum(n in odds for n in ls)\n",
    "\n",
    "def count_evens(ls):\n",
    "    return sum(n in evens for n in ls)\n",
    "\n",
    "def count_primes(ls):\n",
    "    return sum(n in primes for n in ls)\n",
    "\n",
    "def count_composites(ls):\n",
    "    return sum(n in composites for n in ls)\n",
    "\n",
    "def count_squares(ls):\n",
    "    return sum(n in squares for n in ls)\n",
    "\n",
    "def predicate(p):\n",
    "    return all((\n",
    "        count_odds(p) in odds,\n",
    "        count_evens(p) in evens,\n",
    "        count_primes(p) in primes,\n",
    "        count_composites(p) in composites,\n",
    "        count_squares(p) in squares\n",
    "    ))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "no solution\n"
     ]
    }
   ],
   "source": [
    "matches = []\n",
    "for n in range(1, 11):\n",
    "    for c in combinations(base, n):\n",
    "        if predicate(c):\n",
    "            matches.append(c)\n",
    "            \n",
    "if len(matches) == 0:\n",
    "    print('no solution')\n",
    "else:\n",
    "    print('solutions:')\n",
    "    print('\\n'.join(str(m) for m in matches))"
   ]
  }
 ],
 "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}