{"id":228383,"date":"2025-06-07T08:48:12","date_gmt":"2025-06-07T08:48:12","guid":{"rendered":"https:\/\/learnexams.com\/blog\/?p=228383"},"modified":"2025-06-07T08:48:14","modified_gmt":"2025-06-07T08:48:14","slug":"take-a-regular-deck-of-52-cards","status":"publish","type":"post","link":"https:\/\/www.learnexams.com\/blog\/2025\/06\/07\/take-a-regular-deck-of-52-cards\/","title":{"rendered":"Take a regular deck of 52 cards"},"content":{"rendered":"\n

Take a regular deck of 52 cards. Each card has a suit and a value. The suit is one of four possibilities: heart, diamond, club, spade. The value is one of 13 possibilities: A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K. There is exactly one card for each of the 4 x 13 possible combinations of suit and value. Ask your friend to lay the cards out into a grid with 4 rows and 13 columns. They can fill the cards in any way they’d like. In this problem, you will show that you can always pick out 13 cards, one from each column of the grid, so that you wind up with cards of all 13 possible values. (a) Explain how to model this trick as a bipartite matching problem between the 13 column vertices and the 13 value vertices. Can there be vertices in your graph with a degree less than 4? (b) Show that any n columns must contain at least n different values and prove that a matching must exist.<\/p>\n\n\n\n

The Correct Answer and Explanation is:<\/mark><\/strong><\/p>\n\n\n\n

To solve this problem, we’ll model it using bipartite graph matching<\/strong>, a classic approach in combinatorics and graph theory.<\/p>\n\n\n\n

\n\n\n\n

(a) Modeling the Trick as a Bipartite Matching Problem<\/strong><\/h3>\n\n\n\n

We define a bipartite graph<\/strong> with two sets of vertices:<\/p>\n\n\n\n

    \n
  • Left side (Columns):<\/strong> 13 vertices, one for each column in the grid.<\/li>\n\n\n\n
  • Right side (Values):<\/strong> 13 vertices, one for each card value (A, 2, …, K).<\/li>\n<\/ul>\n\n\n\n

    We draw an edge between a column<\/strong> and a value<\/strong> if that column contains at least one card of that value<\/strong>.<\/p>\n\n\n\n

    Degree of Vertices<\/strong><\/h4>\n\n\n\n

    Each column contains 4 cards (since there are 4 rows), and all values are distinct across the deck. Thus, a column can be connected to at most 4 value vertices<\/strong>\u2014so each column vertex has degree at most 4. It’s possible for a column to have less than 4 unique values<\/strong> (if, for instance, two cards in a column had the same value, which is not possible in a standard deck), but since all cards are distinct and no value repeats in a column, each column has 4 distinct values. Therefore, each column vertex has exactly degree 4<\/strong>. On the value<\/strong> side, a value appears once in each of the four suits, so there are 4 cards of each value spread across the 13 columns. Hence, each value vertex has degree 4<\/strong> as well.<\/p>\n\n\n\n

    \n\n\n\n

    (b) Hall\u2019s Theorem and Existence of Matching<\/strong><\/h3>\n\n\n\n

    We aim to find a perfect matching<\/strong>: 13 edges connecting each column to a unique value, with no values repeated.<\/p>\n\n\n\n

    Apply Hall\u2019s Marriage Theorem<\/strong>:<\/p>\n\n\n\n

    \n

    A perfect matching from the column side to the value side exists if and only if for every subset SSS of nnn columns, the union of their value neighbors contains at least nnn distinct values.<\/p>\n<\/blockquote>\n\n\n\n

    Let\u2019s prove this.<\/p>\n\n\n\n

    Each column has 4 values, so nnn columns have 4n4n4n total card entries. Since all cards are unique, no value can occur more than 4 times in total. To cover 4n4n4n card entries using fewer than nnn values, we\u2019d need some value to appear more than 4 times, contradicting the rule.<\/p>\n\n\n\n

    Thus, any nnn columns must involve at least nnn distinct values<\/strong>.<\/p>\n\n\n\n

    So Hall\u2019s condition is satisfied, and a perfect matching exists<\/strong>. That is, you can always pick 13 cards (one per column) with all 13 values represented.<\/p>\n\n\n\n

    \"\"<\/figure>\n","protected":false},"excerpt":{"rendered":"

    Take a regular deck of 52 cards. Each card has a suit and a value. The suit is one of four possibilities: heart, diamond, club, spade. The value is one of 13 possibilities: A, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K. There is exactly one card for each of the […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"footnotes":""},"categories":[25],"tags":[],"class_list":["post-228383","post","type-post","status-publish","format-standard","hentry","category-exams-certification"],"_links":{"self":[{"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/posts\/228383","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/comments?post=228383"}],"version-history":[{"count":0,"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/posts\/228383\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/media?parent=228383"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/categories?post=228383"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/tags?post=228383"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}