diff options
| author | hardythe1 | 2015-05-05 14:21:39 +0530 |
|---|---|---|
| committer | hardythe1 | 2015-05-05 14:21:39 +0530 |
| commit | 435840cef00c596d9e608f9eb2d96f522ea8505a (patch) | |
| tree | 4c783890c984c67022977ca98432e5e4bab30678 /Elements_of_discrete_mathematics/Chapter3.ipynb | |
| parent | aa1863f344766ca7f7c20a395e58d0fb23c52130 (diff) | |
| download | Python-Textbook-Companions-435840cef00c596d9e608f9eb2d96f522ea8505a.tar.gz Python-Textbook-Companions-435840cef00c596d9e608f9eb2d96f522ea8505a.tar.bz2 Python-Textbook-Companions-435840cef00c596d9e608f9eb2d96f522ea8505a.zip | |
add books
Diffstat (limited to 'Elements_of_discrete_mathematics/Chapter3.ipynb')
| -rwxr-xr-x | Elements_of_discrete_mathematics/Chapter3.ipynb | 1585 |
1 files changed, 1585 insertions, 0 deletions
diff --git a/Elements_of_discrete_mathematics/Chapter3.ipynb b/Elements_of_discrete_mathematics/Chapter3.ipynb new file mode 100755 index 00000000..fe88d5b7 --- /dev/null +++ b/Elements_of_discrete_mathematics/Chapter3.ipynb @@ -0,0 +1,1585 @@ +{
+ "metadata": {
+ "name": "",
+ "signature": "sha256:d6505774a4cce1c5726d5bf482120157569ff894ee6f05281095d53b18882117"
+ },
+ "nbformat": 3,
+ "nbformat_minor": 0,
+ "worksheets": [
+ {
+ "cells": [
+ {
+ "cell_type": "heading",
+ "level": 1,
+ "metadata": {},
+ "source": [
+ "3 Relations and Functions"
+ ]
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 06:Page 118"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"Given a relation R on a set A={a,b,c,d} in the form of a graph, the transitive closure of R is to be found using Warshall's algorithm\"\n",
+ "#Each element in A acts as a node\n",
+ "nodes=input(\"Enter the number of nodes\")#This is the total number of elements in the given set A\n",
+ "w0=[[0 for i in range (nodes)]for j in range(nodes)]#Matrix elements are initialised to zero\n",
+ "#Gets the initial value for the matrix elements\n",
+ "print \"Enter the elements of W0. (Enter only 0 or 1)\"# The value is 1 if there is a path between i and j in the given graph, else it is 0\n",
+ "for i in range(0,nodes):\n",
+ " for j in range(0,nodes):\n",
+ " print \"Enter value for w\",i,j\n",
+ " w0[i][j]=input()\n",
+ "#To print the given matrix\n",
+ "print \"The given matrix W0=MR(Matrix relation on R) is\"\n",
+ "for i in range(0,nodes):\n",
+ " for j in range(0,nodes):\n",
+ " print w0[i][j],\n",
+ " print \"\\n\"\n",
+ "for k in range(0,nodes):#To find the transitive relation matrix using Warshall's algorithm\n",
+ " for i in range(0,nodes):\n",
+ " for j in range(0,nodes):\n",
+ " w0[i][j]=w0[i][j] or (w0[i][k] and w0[k][j])\n",
+ "#To print the transitive relation matrix\n",
+ "print \"The required transitive relation matrix is\"\n",
+ "for i in range(0,nodes):\n",
+ " for j in range(0,nodes):\n",
+ " print w0[i][j],\n",
+ " print \"\\n\"\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Given a relation R on a set A={a,b,c,d} in the form of a graph, the transitive closure of R is to be found using Warshall's algorithm\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the number of nodes4\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the elements of W0. (Enter only 0 or 1)\n",
+ "Enter value for w 0 0\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter value for w 0 1\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "1\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter value for w 0 2\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter value for w 0 3\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter value for w 1 0\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "1\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter value for w 1 1\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter value for w 1 2\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "1\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter value for w 1 3\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter value for w 2 0\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter value for w 2 1\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter value for w 2 2\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter value for w 2 3\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "1\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter value for w 3 0\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "1\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter value for w 3 1\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter value for w 3 2\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter value for w 3 3\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "The given matrix W0=MR(Matrix relation on R) is\n",
+ "0 1 0 0 \n",
+ "\n",
+ "1 0 1 0 \n",
+ "\n",
+ "0 0 0 1 \n",
+ "\n",
+ "1 0 0 0 \n",
+ "\n",
+ "The required transitive relation matrix is\n",
+ "1 1 1 1 \n",
+ "\n",
+ "1 1 1 1 \n",
+ "\n",
+ "1 1 1 1 \n",
+ "\n",
+ "1 1 1 1 \n",
+ "\n"
+ ]
+ }
+ ],
+ "prompt_number": 2
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 07:Page 119"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"Given a relation R on a set A={a,b,c,d,e} in the form of a graph, the transitive closure of R is to be found using Warshall's algorithm\"\n",
+ "print \"Given:R={(b,c),(b,e),(c,e),(d,a),(c,b),(e,c)}\"\n",
+ "#Each element in A acts as a node\n",
+ "nodes=input(\"Enter the number of nodes\")#This is the total number of elements in the given set A\n",
+ "w0=[[0 for i in range (nodes)]for j in range(nodes)]#Matrix elements are initialised to zero\n",
+ "#Gets the initial value for the matrix elements\n",
+ "print \"Enter the elements of W0. (Enter only 0 or 1)\"# The value is 1 if there is a path between i and j in the given graph, else it is 0\n",
+ "for i in range(0,nodes):\n",
+ " for j in range(0,nodes):\n",
+ " print \"Enter value for w\",i,j\n",
+ " w0[i][j]=input()\n",
+ "#To print the given matrix\n",
+ "print \"The given matrix W0=MR(Matrix relation on R) is\"\n",
+ "for i in range(0,nodes):\n",
+ " for j in range(0,nodes):\n",
+ " print w0[i][j],\n",
+ " print \"\\n\"\n",
+ "for k in range(0,nodes):#To find the transitive relation matrix using Warshall's algorithm\n",
+ " for i in range(0,nodes):\n",
+ " for j in range(0,nodes):\n",
+ " w0[i][j]=w0[i][j] or (w0[i][k] and w0[k][j])\n",
+ "#To print the transitive relation matrix\n",
+ "print \"The required transitive relation matrix is\"\n",
+ "for i in range(0,nodes):\n",
+ " for j in range(0,nodes):\n",
+ " print w0[i][j],\n",
+ " print \"\\n\"\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Given a relation R on a set A={a,b,c,d,e} in the form of a graph, the transitive closure of R is to be found using Warshall's algorithm\n",
+ "Given:R={(b,c),(b,e),(c,e),(d,a),(c,b),(e,c)}\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the number of nodes5\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter the elements of W0. (Enter only 0 or 1)\n",
+ "Enter value for w 0 0\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter value for w 0 1\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter value for w 0 2\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter value for w 0 3\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter value for w 0 4\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter value for w 1 0\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter value for w 1 1\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter value for w 1 2\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "1\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter value for w 1 3\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter value for w 1 4\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "1\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter value for w 2 0\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter value for w 2 1\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter value for w 2 2\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter value for w 2 3\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter value for w 2 4\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "1\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter value for w 3 0\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "1\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter value for w 3 1\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter value for w 3 2\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter value for w 3 3\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter value for w 3 4\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter value for w 4 0\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter value for w 4 1\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "1\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter value for w 4 2\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "1\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter value for w 4 3\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Enter value for w 4 4\n"
+ ]
+ },
+ {
+ "name": "stdout",
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "0\n"
+ ]
+ },
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "The given matrix W0=MR(Matrix relation on R) is\n",
+ "0 0 0 0 0 \n",
+ "\n",
+ "0 0 1 0 1 \n",
+ "\n",
+ "0 0 0 0 1 \n",
+ "\n",
+ "1 0 0 0 0 \n",
+ "\n",
+ "0 1 1 0 0 \n",
+ "\n",
+ "The required transitive relation matrix is\n",
+ "0 0 0 0 0 \n",
+ "\n",
+ "0 1 1 0 1 \n",
+ "\n",
+ "0 1 1 0 1 \n",
+ "\n",
+ "1 0 0 0 0 \n",
+ "\n",
+ "0 1 1 0 1 \n",
+ "\n"
+ ]
+ }
+ ],
+ "prompt_number": 3
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 41:Page 154"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "#Given function definition is as follows\n",
+ "print \"RECURSIVE FUNCTIONS\"\n",
+ "def f(x):\n",
+ " if x==0:\n",
+ " return 1\n",
+ " else:\n",
+ " return 3*f(x-1)+1\n",
+ "print \"f(1)=\",f(1)\n",
+ "print \"f(2)=\",f(2)\n",
+ "print \"f(3)=\",f(3)\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "RECURSIVE FUNCTIONS\n",
+ "f(1)= 4\n",
+ "f(2)= 13\n",
+ "f(3)= 40\n"
+ ]
+ }
+ ],
+ "prompt_number": 5
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 43:Page 156"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"A recursive function to calculate the GCD of two numbers\"\n",
+ "def GCD(x,y):\n",
+ " if x>y:\n",
+ " x=x-y\n",
+ " return GCD(x,y)\n",
+ " elif x<y:\n",
+ " y=y-x\n",
+ " return GCD(x,y)\n",
+ " else:\n",
+ " print \"The GCD of the two numbers is\",x\n",
+ "\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "A recursive function to calculate the GCD of two numbers\n"
+ ]
+ }
+ ],
+ "prompt_number": 6
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 44:Page 157"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"EXAMPLE OF TREE RECURSION\"\n",
+ "print \"The first six fibonacci numbers are\"\n",
+ "def fib(n):\n",
+ " if n==0:\n",
+ " return 0\n",
+ " elif n==1:\n",
+ " return 1\n",
+ " else:\n",
+ " print \"fib(\",n-1,\")+fib(\",n-2,\")=\",\n",
+ " return fib(n-1)+fib(n-2)\n",
+ "print \"fib(0)=\",fib(0),\n",
+ "print \"\\nfib(1)=\",fib(1),\n",
+ "print \"\\nfib(2)=\",fib(2),\n",
+ "print \"\\nfib(3)=\",fib(3),\n",
+ "print \"\\nfib(4)=\",fib(4),\n",
+ "print \"\\nfib(5)=\",fib(5),\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "EXAMPLE OF TREE RECURSION\n",
+ "The first six fibonacci numbers are\n",
+ "fib(0)= 0 \n",
+ "fib(1)= 1 \n",
+ "fib(2)= fib( 1 )+fib( 0 )= 1 \n",
+ "fib(3)= fib( 2 )+fib( 1 )= fib( 1 )+fib( 0 )= 2 \n",
+ "fib(4)= fib( 3 )+fib( 2 )= fib( 2 )+fib( 1 )= fib( 1 )+fib( 0 )= fib( 1 )+fib( 0 )= 3 \n",
+ "fib(5)= fib( 4 )+fib( 3 )= fib( 3 )+fib( 2 )= fib( 2 )+fib( 1 )= fib( 1 )+fib( 0 )= fib( 1 )+fib( 0 )= fib( 2 )+fib( 1 )= fib( 1 )+fib( 0 )= 5\n"
+ ]
+ }
+ ],
+ "prompt_number": 7
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 45:Page 159"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"HASH FUNCTIONS\"\n",
+ "import math\n",
+ "print \"Employee IDs are 6713,4409,5835\"\n",
+ "print \"L consists of 100 two digit address:00,01,.....,99 \"\n",
+ "m=97#Prime number close to 99\n",
+ "def H(ID):\n",
+ " print ID,\"mod\",m,\"=\",\n",
+ " return ID%m\n",
+ "print \"Division method\"\n",
+ "print \"H(6713)=\",H(6713)\n",
+ "print \"H(4409)=\",H(4409)\n",
+ "print \"H(5835)=\",H(5835)\n",
+ "print \"Midsquare method\"\n",
+ "\n",
+ "def H1(ID):\n",
+ " key=math.pow(ID,2)#Square the given key value\n",
+ " key1=int(key)#Convert it into integer to eliminate decimal point\n",
+ " number=str(key1)#Integer is converted to string for indexing purpose\n",
+ " length=len(number)#Finding the length of the string\n",
+ " number2=number[3:length-3]#Slicing the string to eliminate 3 digits from both ends\n",
+ " return number2\n",
+ " \n",
+ "print \"k=6713\",\"square(k)=\",pow(6713,2),\"\\tH(6713)=\",H1(6713)\n",
+ "print \"k=4409\",\"square(k)=\",pow(4409,2),\"\\tH(4409)=\",H1(4409)\n",
+ "print \"k=5835\",\"square(k)=\",pow(5835,2),\"\\tH(5835)=\",H1(5835)\n",
+ "print \"Folding method\"\n",
+ "#Here the given key is divided in such a way that each part has two digits. Since it has even number of digits there is no exception to this rule\n",
+ "def H2(ID):\n",
+ " ID1=str(ID)#Convert it into string in order to slice it\n",
+ " key1=ID1[0:2]#Split the string into two halves. First part in key1\n",
+ " key2=ID1[2:]#Second half is stored in key2\n",
+ " print key1,\"+\",key2,\"=\",\n",
+ " key=int(key1)+int(key2)#Convert these into int in order to perform addition\n",
+ " key3=str(key)#To eliminate the carry,convert it back to string\n",
+ " length=len(key3)#Since here each part contains only 2 digits, a carry means the presence of a third digit.\n",
+ " if length==3:\n",
+ " res=key3[1:]#If length is 3 , eliminate the leftmost digit\n",
+ " return res\n",
+ " else:\n",
+ " return key#If it is less than 3, print it as such\n",
+ "print \"6713=\",H2(6713)\n",
+ "print \"4409=\",H2(4409)\n",
+ "print \"5835=\",H2(5835)\n",
+ "\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "HASH FUNCTIONS\n",
+ "Employee IDs are 6713,4409,5835\n",
+ "L consists of 100 two digit address:00,01,.....,99 \n",
+ "Division method\n",
+ "H(6713)= 6713 mod 97 = 20\n",
+ "H(4409)= 4409 mod 97 = 44\n",
+ "H(5835)= 5835 mod 97 = 15\n",
+ "Midsquare method\n",
+ "k=6713 square(k)= 45064369 \tH(6713)= 64\n",
+ "k=4409 square(k)= 19439281 \tH(4409)= 39\n",
+ "k=5835 square(k)= 34047225 \tH(5835)= 47\n",
+ "Folding method\n",
+ "6713= 67 + 13 = 80\n",
+ "4409= 44 + 09 = 53\n",
+ "5835= 58 + 35 = 93\n"
+ ]
+ }
+ ],
+ "prompt_number": 8
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 46:Page 161"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"Linear probing to overcome collision in the numbers 89,18,49,58,69\"\n",
+ "memory=[\"\" for i in range (0,10)]#An array indicating the memory space. Initially all the locations are empty\n",
+ "\n",
+ "def h(n):\n",
+ " temp=n#Get a copy as we might change the value in the original variable\n",
+ " count=0#Initial collision count is zero\n",
+ " flag=0#Flag=1 indicates that the key has been placed in the memory. So initially it is zero\n",
+ " while flag==0:\n",
+ " num=n%10#10 is the number of buckets or partitions\n",
+ " if memory[num]==\"\":#Checks if the location is empty\n",
+ " memory[num]=temp#Inserts value if nothing is already present\n",
+ " flag=1#Indicates that the key is placed in memory\n",
+ " else:\n",
+ " count=count+1#If the location is not empty, the collision count is increased by one\n",
+ " def f(i):#Collosion resolution function\n",
+ " return i\n",
+ " n=num+f(count)#Facilitates linear probing by increasing the count by 1\n",
+ "#Hash the values \n",
+ "h(89)\n",
+ "h(18)\n",
+ "h(49)\n",
+ "h(58)\n",
+ "h(69)\n",
+ "print \"MEMORY |\\t\\tVALUE\"\n",
+ "print \"------------------------------------\"\n",
+ "for i in range(0,10):#Print the hashed memory area\n",
+ " print i,\"\\t|\\t\",memory[i]\n",
+ " print \"---------------------------------\"\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Linear probing to overcome collision in the numbers 89,18,49,58,69\n",
+ "MEMORY |\t\tVALUE\n",
+ "------------------------------------\n",
+ "0 \t|\t49\n",
+ "---------------------------------\n",
+ "1 \t|\t58\n",
+ "---------------------------------\n",
+ "2 \t|\t69\n",
+ "---------------------------------\n",
+ "3 \t|\t\n",
+ "---------------------------------\n",
+ "4 \t|\t\n",
+ "---------------------------------\n",
+ "5 \t|\t\n",
+ "---------------------------------\n",
+ "6 \t|\t\n",
+ "---------------------------------\n",
+ "7 \t|\t\n",
+ "---------------------------------\n",
+ "8 \t|\t18\n",
+ "---------------------------------\n",
+ "9 \t|\t89\n",
+ "---------------------------------\n"
+ ]
+ }
+ ],
+ "prompt_number": 9
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 47:Page 163"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"Quadratic probing in the numbers 89,18,49,58,69\"\n",
+ "memory=[\"\" for i in range (0,10)]#An array indicating the memory space. Initially all the locations are empty\n",
+ "\n",
+ "def h(n):\n",
+ " temp=n#Get a copy as we might change the value in the original variable\n",
+ " count=0#Initial collision count is zero\n",
+ " flag=0#Flag=1 indicates that the key has been placed in the memory. So initially it is zero\n",
+ " while flag==0:\n",
+ " num=n%10#10 is the number of buckets or partitions\n",
+ " if memory[num]==\"\":#Checks if the location is empty\n",
+ " memory[num]=temp#Inserts value if nothing is already present\n",
+ " flag=1#Indicates that the key is placed in memory\n",
+ " else:\n",
+ " count=count+1#If the location is not empty, the collision count is increased by one\n",
+ " def f(i):#Collosion resolution function\n",
+ " return i*i\n",
+ " n=num+f(count)#Facilitates quadratic probing by squaring the count \n",
+ "#Hash the values \n",
+ "h(89)\n",
+ "h(18)\n",
+ "h(49)\n",
+ "h(58)\n",
+ "h(69)\n",
+ "print \"MEMORY |\\t VALUES\"\n",
+ "print \"-------------------------------------\"\n",
+ "for i in range(0,10):#Print the hashed memory area\n",
+ " print i,\"\\t|\\t\",memory[i]\n",
+ " print \"-------------------------------------\"\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Quadratic probing in the numbers 89,18,49,58,69\n",
+ "MEMORY |\t VALUES\n",
+ "-------------------------------------\n",
+ "0 \t|\t49\n",
+ "-------------------------------------\n",
+ "1 \t|\t\n",
+ "-------------------------------------\n",
+ "2 \t|\t\n",
+ "-------------------------------------\n",
+ "3 \t|\t58\n",
+ "-------------------------------------\n",
+ "4 \t|\t69\n",
+ "-------------------------------------\n",
+ "5 \t|\t\n",
+ "-------------------------------------\n",
+ "6 \t|\t\n",
+ "-------------------------------------\n",
+ "7 \t|\t\n",
+ "-------------------------------------\n",
+ "8 \t|\t18\n",
+ "-------------------------------------\n",
+ "9 \t|\t89\n",
+ "-------------------------------------\n"
+ ]
+ }
+ ],
+ "prompt_number": 10
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 48:Page 164"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "print \"Double hashing in the numbers 89,18,49,58,69\"\n",
+ "memory=[\"\" for i in range (0,10)]#An array indicating the memory space. Initially all the locations are empty\n",
+ "r=7#Assume\n",
+ "def h(n):\n",
+ " temp=n#Get a copy as we might change the value in the original variable\n",
+ " count=0#Initial collision count is zero\n",
+ " flag=0#Flag=1 indicates that the key has been placed in the memory. So initially it is zero\n",
+ " while flag==0:\n",
+ " num=n%10#10 is the number of buckets or partitions\n",
+ " if memory[num]==\"\":#Checks if the location is empty\n",
+ " memory[num]=temp#Inserts value if nothing is already present\n",
+ " flag=1#Indicates that the key is placed in memory\n",
+ " else:\n",
+ " count=count+1#If the location is not empty, the collision count is increased by one\n",
+ " def h1(t):\n",
+ " return r-(t%r)#Assume \n",
+ " \n",
+ " def f(i):#Collosion resolution function\n",
+ " return i*h1(temp)\n",
+ " n=num+f(count)#Facilitates probing \n",
+ "#Hash the values \n",
+ "h(89)\n",
+ "h(18)\n",
+ "h(49)\n",
+ "h(58)\n",
+ "h(69)\n",
+ "print \"MEMORY |\\tVALUES\"\n",
+ "print \"-------------------------------------\"\n",
+ "for i in range(0,10):#Print the hashed memory area\n",
+ " print i,\"\\t|\\t\",memory[i]\n",
+ " print \"----------------------------------------\"\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Double hashing in the numbers 89,18,49,58,69\n",
+ "MEMORY |\tVALUES\n",
+ "-------------------------------------\n",
+ "0 \t|\t69\n",
+ "----------------------------------------\n",
+ "1 \t|\t\n",
+ "----------------------------------------\n",
+ "2 \t|\t\n",
+ "----------------------------------------\n",
+ "3 \t|\t58\n",
+ "----------------------------------------\n",
+ "4 \t|\t\n",
+ "----------------------------------------\n",
+ "5 \t|\t\n",
+ "----------------------------------------\n",
+ "6 \t|\t49\n",
+ "----------------------------------------\n",
+ "7 \t|\t\n",
+ "----------------------------------------\n",
+ "8 \t|\t18\n",
+ "----------------------------------------\n",
+ "9 \t|\t89\n",
+ "----------------------------------------\n"
+ ]
+ }
+ ],
+ "prompt_number": 11
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 49:Page 166"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "import math\n",
+ "magazine=30#Magazines are considered as pigeonholes\n",
+ "total_pages=61324#Pages are considered as pigeons. Assign each page to the magazine in which it appears\n",
+ "print \"If 30 magazines contain a total of 61,324 pages, then one magazine must contain at least\",int((math.floor((total_pages-1)/magazine)+1)),\"pages\"#According to extended pigeonhole principle\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "If 30 magazines contain a total of 61,324 pages, then one magazine must contain at least 2045 pages\n"
+ ]
+ }
+ ],
+ "prompt_number": 12
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 50:Page 166"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "a=0\n",
+ "b=0\n",
+ "s=[[0 for i in range(13)]for j in range(13)]#Initialise the matrix\n",
+ "#If the summation turns out to be 13, then put them in a 2D array\n",
+ "for i in range(1,13):\n",
+ " for j in range(i+1,13):\n",
+ " \n",
+ " if i+j==13:\n",
+ " \n",
+ " s[a][b]=i\n",
+ " s[a][b+1]=j\n",
+ " a=a+1\n",
+ "#Print the 2D array containing the possible combinations \n",
+ "for i in range(0,a):\n",
+ " print \"s\",i+1,\"=(\",\n",
+ " for j in range(0,2):\n",
+ " print s[i][j],\",\",\n",
+ " print \"),\",\n",
+ " print \"\\n\"\n",
+ "\n",
+ "print \"These are the combination of numbers between 1 and 12 those on summation will yield 13 as a result.\"\n",
+ "print \"Each of the chosen 7 numbers must contain any of these combinations, so that summation of 2 among that will yield 13. Therefore there are 6 ways to do so \"\n",
+ "#According to pigeonhole principle\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "s 1 =( 1 , 12 , ), \n",
+ "\n",
+ "s 2 =( 2 , 11 , ), \n",
+ "\n",
+ "s 3 =( 3 , 10 , ), \n",
+ "\n",
+ "s 4 =( 4 , 9 , ), \n",
+ "\n",
+ "s 5 =( 5 , 8 , ), \n",
+ "\n",
+ "s 6 =( 6 , 7 , ), \n",
+ "\n",
+ "These are the combination of numbers between 1 and 12 those on summation will yield 13 as a result.\n",
+ "Each of the chosen 7 numbers must contain any of these combinations, so that summation of 2 among that will yield 13. Therefore there are 6 ways to do so \n"
+ ]
+ }
+ ],
+ "prompt_number": 13
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 52:Page 166"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "import math\n",
+ "total_num=10#Total number of people volunteering\n",
+ "committee_num=3#Number of people to be there in the committee\n",
+ "print \"Ten people come forward to volunteer for a committee of three\"\n",
+ "print \"Every possible committee of three that can be formed from these ten names is written on a slip of paper\"\n",
+ "slips=(math.factorial(total_num)/(math.factorial(total_num-committee_num)*math.factorial(committee_num)))#Slips are compared to pigeons.By formula for combinations\n",
+ "hats=10#Hats are compared to pigeonholes\n",
+ "print \"Total number of combinations to choose 3 out of ten is\",slips\n",
+ "print \"These possible \",slips, \"slips, one slip for each possible committee and the slips are put in \",hats,\"hats\"\n",
+ "print \"Therefore, One hat must contain at least\",int((math.floor((slips-1)/hats)+1)),\"or more slips of paper\"\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "Ten people come forward to volunteer for a committee of three\n",
+ "Every possible committee of three that can be formed from these ten names is written on a slip of paper\n",
+ "Total number of combinations to choose 3 out of ten is 120\n",
+ "These possible 120 slips, one slip for each possible committee and the slips are put in 10 hats\n",
+ "Therefore, One hat must contain at least 12 or more slips of paper\n"
+ ]
+ }
+ ],
+ "prompt_number": 14
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 53:Page 166"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "import math\n",
+ "types=12#Types of chocolates\n",
+ "choice=5#Types to choose from\n",
+ "print \"A store has an introductory sale on 12 types of chocolates. A customer can choose 1 chocolate of any 5 different types and will be charged no more than 1.75 \"\n",
+ "c=math.factorial(types)/(math.factorial(choice)*math.factorial(types-choice))#By the formula for finding combinations\n",
+ "print \"The customer can choose chocolates in \",c,\"ways\"\n",
+ "amount=175#In paise\n",
+ "print \"we have\",int((math.floor((c-1)/amount)+1)),\"choices having the same cost\"#By extended pigeonhole principle\n",
+ "print \"Therefore, there must be at least two different ways to choose, so that the cost will be the same for both choices\"\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "A store has an introductory sale on 12 types of chocolates. A customer can choose 1 chocolate of any 5 different types and will be charged no more than 1.75 \n",
+ "The customer can choose chocolates in 792 ways\n",
+ "we have 5 choices having the same cost\n",
+ "Therefore, there must be at least two different ways to choose, so that the cost will be the same for both choices\n"
+ ]
+ }
+ ],
+ "prompt_number": 15
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 54:Page 167"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "import math\n",
+ "print \"A store has an introductory sale on 12 types of chocolates. A customer can choose 1 chocolate of any 5 different types and will be charged no more than 1.75. The store allows repetition in choices\"\n",
+ "types=12#Total types of chocolates\n",
+ "choice=5#Customer can choose 1 from 5 types\n",
+ "c=math.factorial(types)/(math.factorial(choice)*math.factorial(types-choice))#By formula of finding combinations\n",
+ "print \"The customer can choose chocolates in \",c,\"ways\"\n",
+ "amount=175#In paise\n",
+ "ans=int((math.floor((c-1)/amount)+1))#By extended pigeonhole principle\n",
+ "print \"we have\",ans,\"choices having the same cost\"\n",
+ "choice=(math.factorial(types+choice-1)/(math.factorial(ans)*math.factorial(types+choice-1-ans)))#Considered as pigeonhole\n",
+ "print \"If repetitions are allowed, then we have 5 groups and there are C(12+5-1,5)=C(16,5)=\",choice,\"choices\"\n",
+ "print \"At least\",int(math.floor(choice/amount)+1),\"choices will have the same cost. So, there are at least 10 ways to make different choices that have the same cost\"\n",
+ "#By extended pigeonhole principle\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "A store has an introductory sale on 12 types of chocolates. A customer can choose 1 chocolate of any 5 different types and will be charged no more than 1.75. The store allows repetition in choices\n",
+ "The customer can choose chocolates in 792 ways\n",
+ "we have 5 choices having the same cost\n",
+ "If repetitions are allowed, then we have 5 groups and there are C(12+5-1,5)=C(16,5)= 4368 choices\n",
+ "At least 25 choices will have the same cost. So, there are at least 10 ways to make different choices that have the same cost\n"
+ ]
+ }
+ ],
+ "prompt_number": 16
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 55:Page 167"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "import math\n",
+ "total=15#Total number of choices\n",
+ "choice=6#Number of choices to select\n",
+ "c=math.factorial(total)/(math.factorial(choice)*math.factorial(total-choice))\n",
+ "print \"6 numbers out of 1 to 15 can be chosen in\",c,\"ways\"#These are considered as pigeons\n",
+ "sum1=0#Initial sum of first 6 numbers is set to zero\n",
+ "sum2=0#Initial sum of last 6 numbers is set to zero\n",
+ "for i in range(1,7):\n",
+ " sum1=sum1+i#Calulates the sum of first six numbers\n",
+ "for i in range(10,16):\n",
+ " sum2=sum2+i#Calulates the sum of first six numbers\n",
+ "num_of_sums=(sum2-sum1+1)\n",
+ "print \"Number of sums that can be generated is\",num_of_sums#Considered as pigeon holes\n",
+ "print \"There are\",int((math.floor((c-1)/num_of_sums)+1)),\"ways\"#By extended pigeon hole principle\n",
+ "print \"Hence, there must be at least 90 ways to choose 6 numbers from 1 to 15 so that all the choices have the same sum\"\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "6 numbers out of 1 to 15 can be chosen in 5005 ways\n",
+ "Number of sums that can be generated is 55\n",
+ "There are 91 ways\n",
+ "Hence, there must be at least 90 ways to choose 6 numbers from 1 to 15 so that all the choices have the same sum\n"
+ ]
+ }
+ ],
+ "prompt_number": 17
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 56:Page 167"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "import math\n",
+ "print \"ABCD is the required square. Join AD and BC.Now we get 4 triangles,namely ACD,BCD,ABC,ABD.\"\n",
+ "print \"If five points are selected in a square, two of them must belong to the same triangle.\"#According to pigeonhole principle\n",
+ "distance=math.sqrt(math.pow(1,2)+math.pow(1,2))\n",
+ "print \"The largest distance in a triangle is\",distance,\"So the points must be no more than \",distance,\"inches apart\" \n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "ABCD is the required square. Join AD and BC.Now we get 4 triangles,namely ACD,BCD,ABC,ABD.\n",
+ "If five points are selected in a square, two of them must belong to the same triangle.\n",
+ "The largest distance in a triangle is 1.41421356237 So the points must be no more than 1.41421356237 inches apart\n"
+ ]
+ }
+ ],
+ "prompt_number": 18
+ },
+ {
+ "cell_type": "heading",
+ "level": 2,
+ "metadata": {},
+ "source": [
+ "Example 57:Page 167"
+ ]
+ },
+ {
+ "cell_type": "code",
+ "collapsed": false,
+ "input": [
+ "import math\n",
+ "print \"The sum of entries in A cannot be more than 64\"#Because A is a boolean matrix and so can hold 0 and 1 only. If all the entries in A are 1, the sum will be 64\n",
+ "sum=51#Actual sum of entries in A\n",
+ "rows=8#8*8 matrix\n",
+ "columns=8#8*8 matrix\n",
+ "row_ones=int(math.floor((sum-1)/rows)+1)#Minimum number of ones in a row by extended pigeonole principle\n",
+ "print \"One row must have at least\",row_ones,\"ones\"\n",
+ "column_ones=int(math.floor((sum-1)/columns)+1)#Minimum number of ones in a column by extended pigeonhole principle\n",
+ "print \"One column must have at least\",column_ones,\"ones\"\n",
+ "print \"The sum of elements of row and column is\",row_ones+column_ones\n",
+ "print \"So, the sum of entries will add up to be more than 13\"\n"
+ ],
+ "language": "python",
+ "metadata": {},
+ "outputs": [
+ {
+ "output_type": "stream",
+ "stream": "stdout",
+ "text": [
+ "The sum of entries in A cannot be more than 64\n",
+ "One row must have at least 7 ones\n",
+ "One column must have at least 7 ones\n",
+ "The sum of elements of row and column is 14\n",
+ "So, the sum of entries will add up to be more than 13\n"
+ ]
+ }
+ ],
+ "prompt_number": 19
+ }
+ ],
+ "metadata": {}
+ }
+ ]
+}
\ No newline at end of file |