{"id":7601,"date":"2022-04-20T09:37:57","date_gmt":"2022-04-20T04:07:57","guid":{"rendered":"https:\/\/www.goseeko.com\/blog\/?p=7601"},"modified":"2025-06-02T20:49:27","modified_gmt":"2025-06-02T15:19:27","slug":"what-is-the-pigeonhole-principle","status":"publish","type":"post","link":"https:\/\/www.goseeko.com\/blog\/what-is-the-pigeonhole-principle\/","title":{"rendered":"What is the Pigeonhole principle?"},"content":{"rendered":"\n

Pigeonhole principle <\/a>(statement)- <\/strong>If n pigeonholes are occupied by n + 1 or more pigeons, then at least one pigeonhole is occupied by more than one pigeon.<\/p>\n\n\n\n

This principle can be applied to many problems where we want to show that a given situation can occur.<\/p>\n\n\n\n

Examples<\/h2>\n\n\n\n

Example-1: Suppose a class contains 13 students, then two of the students (pigeons) were born in the same months (pigeonholes)<\/strong><\/p>\n\n\n\n

Example-2: <\/strong>Suppose a department contains 13 professors, then two of the professors (pigeons) were born in the same month (pigeonholes).<\/p>\n\n\n\n

Example-2: <\/strong>Find the minimum number of elements that one needs to take from the set S <\/em>= {1, <\/em>2, <\/em>3, . . . , <\/em>9} to be sure that two of the numbers add up to 10.<\/p>\n\n\n\n

Here the pigeonholes are the five sets {1, 9}, {2, 8}, {3, 7}, {4, 6}, {5}. Thus any choice of six elements (pigeons) of S <\/em>will guarantee that two of the numbers add up to ten.<\/p>\n\n\n\n

Example-2: Show that if seven numbers from 1 to 12 are chosen, then two of them will add up to 13.<\/strong><\/p>\n\n\n\n

 Sol.<\/p>\n\n\n\n

First we will construct six different sets, each containing two numbers that add up to 13 as follows-<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

Each of the seven numbers belong to one of these six sets. <\/p>\n\n\n\n

Since there are six sets, then according to the pigeonhole principle that two of the numbers chosen belong to the same set. These numbers add upto 13.<\/p>\n\n\n\n

Example-3: Suppose a bag contains 10 red balls, 10 white balls and 10 blue balls. what is the minimum number of balls we have to choose randomly for the bag to ensure that we 4 balls of same color?<\/p>\n\n\n\n

Solution:
By applying Pigeonhole principle-<\/p>\n\n\n\n

number of colors(pigeonholes) n = 3<\/p>\n\n\n\n

number of balls (pugeons) k + 1 = 4<\/p>\n\n\n\n

hence the minimum number of balls required = kn + 1<\/p>\n\n\n\n

by simplifying we obtain kn + 1 = 10.<\/p>\n","protected":false},"excerpt":{"rendered":"

Pigeonhole principle-If n pigeonholes are occupied by n + 1 or more pigeons, then at least one pigeonhole is occupied by more than one pigeon.<\/p>\n","protected":false},"author":3,"featured_media":7133,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[31],"tags":[],"class_list":["post-7601","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-maths"],"yoast_head":"\nWhat is the Pigeonhole principle? - Goseeko blog<\/title>\n<meta name=\"description\" content=\"Pigeonhole principle-If n pigeonholes are occupied by n + 1 or more pigeons, then at least one pigeonhole is occupied by more than one pigeon.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/www.goseeko.com\/blog\/what-is-the-pigeonhole-principle\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"What is the Pigeonhole principle? - Goseeko blog\" \/>\n<meta property=\"og:description\" content=\"Pigeonhole principle-If n pigeonholes are occupied by n + 1 or more pigeons, then at least one pigeonhole is occupied by more than one pigeon.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/www.goseeko.com\/blog\/what-is-the-pigeonhole-principle\/\" \/>\n<meta property=\"og:site_name\" content=\"Goseeko blog\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/goseeko\" \/>\n<meta property=\"article:published_time\" content=\"2022-04-20T04:07:57+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2025-06-02T15:19:27+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/www.goseeko.com\/blog\/wp-content\/uploads\/2022\/01\/kelly-sikkema-ABkfxGoB-RE-unsplash.jpg\" \/>\n\t<meta property=\"og:image:width\" content=\"3712\" \/>\n\t<meta property=\"og:image:height\" content=\"5568\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/jpeg\" \/>\n<meta name=\"author\" content=\"Team Goseeko\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@goseeko\" \/>\n<meta name=\"twitter:site\" content=\"@goseeko\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Team Goseeko\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"2 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/www.goseeko.com\/blog\/what-is-the-pigeonhole-principle\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/www.goseeko.com\/blog\/what-is-the-pigeonhole-principle\/\"},\"author\":{\"name\":\"Team Goseeko\",\"@id\":\"https:\/\/www.goseeko.com\/blog\/#\/schema\/person\/7ec300cd01b6116501943af14d546bae\"},\"headline\":\"What is the Pigeonhole principle?\",\"datePublished\":\"2022-04-20T04:07:57+00:00\",\"dateModified\":\"2025-06-02T15:19:27+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/www.goseeko.com\/blog\/what-is-the-pigeonhole-principle\/\"},\"wordCount\":282,\"commentCount\":0,\"publisher\":{\"@id\":\"https:\/\/www.goseeko.com\/blog\/#organization\"},\"image\":{\"@id\":\"https:\/\/www.goseeko.com\/blog\/what-is-the-pigeonhole-principle\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/i0.wp.com\/www.goseeko.com\/blog\/wp-content\/uploads\/2022\/01\/kelly-sikkema-ABkfxGoB-RE-unsplash.jpg?fit=3712%2C5568&ssl=1\",\"articleSection\":[\"Maths\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/www.goseeko.com\/blog\/what-is-the-pigeonhole-principle\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/www.goseeko.com\/blog\/what-is-the-pigeonhole-principle\/\",\"url\":\"https:\/\/www.goseeko.com\/blog\/what-is-the-pigeonhole-principle\/\",\"name\":\"What is the Pigeonhole principle? - Goseeko blog\",\"isPartOf\":{\"@id\":\"https:\/\/www.goseeko.com\/blog\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/www.goseeko.com\/blog\/what-is-the-pigeonhole-principle\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/www.goseeko.com\/blog\/what-is-the-pigeonhole-principle\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/i0.wp.com\/www.goseeko.com\/blog\/wp-content\/uploads\/2022\/01\/kelly-sikkema-ABkfxGoB-RE-unsplash.jpg?fit=3712%2C5568&ssl=1\",\"datePublished\":\"2022-04-20T04:07:57+00:00\",\"dateModified\":\"2025-06-02T15:19:27+00:00\",\"description\":\"Pigeonhole principle-If n pigeonholes are occupied by n + 1 or more pigeons, then at least one pigeonhole is occupied by more than one pigeon.\",\"breadcrumb\":{\"@id\":\"https:\/\/www.goseeko.com\/blog\/what-is-the-pigeonhole-principle\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/www.goseeko.com\/blog\/what-is-the-pigeonhole-principle\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/www.goseeko.com\/blog\/what-is-the-pigeonhole-principle\/#primaryimage\",\"url\":\"https:\/\/i0.wp.com\/www.goseeko.com\/blog\/wp-content\/uploads\/2022\/01\/kelly-sikkema-ABkfxGoB-RE-unsplash.jpg?fit=3712%2C5568&ssl=1\",\"contentUrl\":\"https:\/\/i0.wp.com\/www.goseeko.com\/blog\/wp-content\/uploads\/2022\/01\/kelly-sikkema-ABkfxGoB-RE-unsplash.jpg?fit=3712%2C5568&ssl=1\",\"width\":3712,\"height\":5568},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/www.goseeko.com\/blog\/what-is-the-pigeonhole-principle\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/www.goseeko.com\/blog\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"What is the Pigeonhole principle?\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/www.goseeko.com\/blog\/#website\",\"url\":\"https:\/\/www.goseeko.com\/blog\/\",\"name\":\"Goseeko blog\",\"description\":\"Learning beyond college, Students platform for life skills.\",\"publisher\":{\"@id\":\"https:\/\/www.goseeko.com\/blog\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/www.goseeko.com\/blog\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/www.goseeko.com\/blog\/#organization\",\"name\":\"Goseeko.com\",\"url\":\"https:\/\/www.goseeko.com\/blog\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/www.goseeko.com\/blog\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/i1.wp.com\/www.goseeko.com\/blog\/wp-content\/uploads\/2021\/09\/GoSeeko_Stacked-logo-01.png?fit=2471%2C2471&ssl=1\",\"contentUrl\":\"https:\/\/i1.wp.com\/www.goseeko.com\/blog\/wp-content\/uploads\/2021\/09\/GoSeeko_Stacked-logo-01.png?fit=2471%2C2471&ssl=1\",\"width\":2471,\"height\":2471,\"caption\":\"Goseeko.com\"},\"image\":{\"@id\":\"https:\/\/www.goseeko.com\/blog\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/www.facebook.com\/goseeko\",\"https:\/\/x.com\/goseeko\",\"https:\/\/www.instagram.com\/goseeko\/\"]},{\"@type\":\"Person\",\"@id\":\"https:\/\/www.goseeko.com\/blog\/#\/schema\/person\/7ec300cd01b6116501943af14d546bae\",\"name\":\"Team Goseeko\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/www.goseeko.com\/blog\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/?s=96&d=mm&r=g\",\"caption\":\"Team Goseeko\"},\"url\":\"https:\/\/www.goseeko.com\/blog\/author\/team-goseeko\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"What is the Pigeonhole principle? - Goseeko blog","description":"Pigeonhole principle-If n pigeonholes are occupied by n + 1 or more pigeons, then at least one pigeonhole is occupied by more than one pigeon.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/www.goseeko.com\/blog\/what-is-the-pigeonhole-principle\/","og_locale":"en_US","og_type":"article","og_title":"What is the Pigeonhole principle? - Goseeko blog","og_description":"Pigeonhole principle-If n pigeonholes are occupied by n + 1 or more pigeons, then at least one pigeonhole is occupied by more than one pigeon.","og_url":"https:\/\/www.goseeko.com\/blog\/what-is-the-pigeonhole-principle\/","og_site_name":"Goseeko blog","article_publisher":"https:\/\/www.facebook.com\/goseeko","article_published_time":"2022-04-20T04:07:57+00:00","article_modified_time":"2025-06-02T15:19:27+00:00","og_image":[{"width":3712,"height":5568,"url":"https:\/\/www.goseeko.com\/blog\/wp-content\/uploads\/2022\/01\/kelly-sikkema-ABkfxGoB-RE-unsplash.jpg","type":"image\/jpeg"}],"author":"Team Goseeko","twitter_card":"summary_large_image","twitter_creator":"@goseeko","twitter_site":"@goseeko","twitter_misc":{"Written by":"Team Goseeko","Est. reading time":"2 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/www.goseeko.com\/blog\/what-is-the-pigeonhole-principle\/#article","isPartOf":{"@id":"https:\/\/www.goseeko.com\/blog\/what-is-the-pigeonhole-principle\/"},"author":{"name":"Team Goseeko","@id":"https:\/\/www.goseeko.com\/blog\/#\/schema\/person\/7ec300cd01b6116501943af14d546bae"},"headline":"What is the Pigeonhole principle?","datePublished":"2022-04-20T04:07:57+00:00","dateModified":"2025-06-02T15:19:27+00:00","mainEntityOfPage":{"@id":"https:\/\/www.goseeko.com\/blog\/what-is-the-pigeonhole-principle\/"},"wordCount":282,"commentCount":0,"publisher":{"@id":"https:\/\/www.goseeko.com\/blog\/#organization"},"image":{"@id":"https:\/\/www.goseeko.com\/blog\/what-is-the-pigeonhole-principle\/#primaryimage"},"thumbnailUrl":"https:\/\/i0.wp.com\/www.goseeko.com\/blog\/wp-content\/uploads\/2022\/01\/kelly-sikkema-ABkfxGoB-RE-unsplash.jpg?fit=3712%2C5568&ssl=1","articleSection":["Maths"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/www.goseeko.com\/blog\/what-is-the-pigeonhole-principle\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/www.goseeko.com\/blog\/what-is-the-pigeonhole-principle\/","url":"https:\/\/www.goseeko.com\/blog\/what-is-the-pigeonhole-principle\/","name":"What is the Pigeonhole principle? - Goseeko blog","isPartOf":{"@id":"https:\/\/www.goseeko.com\/blog\/#website"},"primaryImageOfPage":{"@id":"https:\/\/www.goseeko.com\/blog\/what-is-the-pigeonhole-principle\/#primaryimage"},"image":{"@id":"https:\/\/www.goseeko.com\/blog\/what-is-the-pigeonhole-principle\/#primaryimage"},"thumbnailUrl":"https:\/\/i0.wp.com\/www.goseeko.com\/blog\/wp-content\/uploads\/2022\/01\/kelly-sikkema-ABkfxGoB-RE-unsplash.jpg?fit=3712%2C5568&ssl=1","datePublished":"2022-04-20T04:07:57+00:00","dateModified":"2025-06-02T15:19:27+00:00","description":"Pigeonhole principle-If n pigeonholes are occupied by n + 1 or more pigeons, then at least one pigeonhole is occupied by more than one pigeon.","breadcrumb":{"@id":"https:\/\/www.goseeko.com\/blog\/what-is-the-pigeonhole-principle\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/www.goseeko.com\/blog\/what-is-the-pigeonhole-principle\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/www.goseeko.com\/blog\/what-is-the-pigeonhole-principle\/#primaryimage","url":"https:\/\/i0.wp.com\/www.goseeko.com\/blog\/wp-content\/uploads\/2022\/01\/kelly-sikkema-ABkfxGoB-RE-unsplash.jpg?fit=3712%2C5568&ssl=1","contentUrl":"https:\/\/i0.wp.com\/www.goseeko.com\/blog\/wp-content\/uploads\/2022\/01\/kelly-sikkema-ABkfxGoB-RE-unsplash.jpg?fit=3712%2C5568&ssl=1","width":3712,"height":5568},{"@type":"BreadcrumbList","@id":"https:\/\/www.goseeko.com\/blog\/what-is-the-pigeonhole-principle\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/www.goseeko.com\/blog\/"},{"@type":"ListItem","position":2,"name":"What is the Pigeonhole principle?"}]},{"@type":"WebSite","@id":"https:\/\/www.goseeko.com\/blog\/#website","url":"https:\/\/www.goseeko.com\/blog\/","name":"Goseeko blog","description":"Learning beyond college, Students platform for life skills.","publisher":{"@id":"https:\/\/www.goseeko.com\/blog\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/www.goseeko.com\/blog\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/www.goseeko.com\/blog\/#organization","name":"Goseeko.com","url":"https:\/\/www.goseeko.com\/blog\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/www.goseeko.com\/blog\/#\/schema\/logo\/image\/","url":"https:\/\/i1.wp.com\/www.goseeko.com\/blog\/wp-content\/uploads\/2021\/09\/GoSeeko_Stacked-logo-01.png?fit=2471%2C2471&ssl=1","contentUrl":"https:\/\/i1.wp.com\/www.goseeko.com\/blog\/wp-content\/uploads\/2021\/09\/GoSeeko_Stacked-logo-01.png?fit=2471%2C2471&ssl=1","width":2471,"height":2471,"caption":"Goseeko.com"},"image":{"@id":"https:\/\/www.goseeko.com\/blog\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/goseeko","https:\/\/x.com\/goseeko","https:\/\/www.instagram.com\/goseeko\/"]},{"@type":"Person","@id":"https:\/\/www.goseeko.com\/blog\/#\/schema\/person\/7ec300cd01b6116501943af14d546bae","name":"Team Goseeko","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/www.goseeko.com\/blog\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/?s=96&d=mm&r=g","caption":"Team Goseeko"},"url":"https:\/\/www.goseeko.com\/blog\/author\/team-goseeko\/"}]}},"jetpack_featured_media_url":"https:\/\/i0.wp.com\/www.goseeko.com\/blog\/wp-content\/uploads\/2022\/01\/kelly-sikkema-ABkfxGoB-RE-unsplash.jpg?fit=3712%2C5568&ssl=1","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.goseeko.com\/blog\/wp-json\/wp\/v2\/posts\/7601","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.goseeko.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.goseeko.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.goseeko.com\/blog\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/www.goseeko.com\/blog\/wp-json\/wp\/v2\/comments?post=7601"}],"version-history":[{"count":5,"href":"https:\/\/www.goseeko.com\/blog\/wp-json\/wp\/v2\/posts\/7601\/revisions"}],"predecessor-version":[{"id":7893,"href":"https:\/\/www.goseeko.com\/blog\/wp-json\/wp\/v2\/posts\/7601\/revisions\/7893"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.goseeko.com\/blog\/wp-json\/wp\/v2\/media\/7133"}],"wp:attachment":[{"href":"https:\/\/www.goseeko.com\/blog\/wp-json\/wp\/v2\/media?parent=7601"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.goseeko.com\/blog\/wp-json\/wp\/v2\/categories?post=7601"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.goseeko.com\/blog\/wp-json\/wp\/v2\/tags?post=7601"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}