All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
Prove or verify (Posted on 2021-11-18) Difficulty: 3 of 5
English gifted mathematician Philip Hall proved a certain theorem regarding matching between members of two distinct sets a.k.a. as Hall’s marriage theorem.

The following statement is a practical example supporting his theorem: If you shuffle a standard deck of 52 cards and then create a row of 13 piles each of 4 cards it will be always possible to pick up a card from each pile to assemble a set of all denominations i.e. 1,2,3…Q,K (different suits, of course).

a. Provide a formal proof.
OR
b. Faute de mieux - a simulation program with 10,000 successful results and no failures will be welcomed.

No Solution Yet Submitted by Ady TZIDON    
Rating: 4.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
simulation program Comment 1 of 1
global had shuffle  solved
 
for trial=1:10000
   shuffle0=ceil(randperm(52)/4); 
   shuffle=reshape(shuffle0,13,4);
   had=[]; solved=false;
   lookfor(1)
   if solved==false
      disp(shuffle') 
   end
end
 

function lookfor(wh)
   global had shuffle solved
   for i=1:13
       if ismember(i,had)==false && ismember(wh,shuffle(i,:))
           had=[had i];
           if wh==13
               solved=true;
               break
           else
               if wh<13
                  lookfor(wh+1) 
               end
           end
           had=had(1:end-1);
       end
   end
end

never finds a shuffle where solved remains false.

On average about 1800 ways are found of doing the matches. In a set of 5 shuffles the numbers of ways of matching came to, respectively:

        1532        1694        1061        2246        2509
        
for an average of 1808.4.

While repreated trials (I'd estimate close to 40,000, including partial runs) have not found an instance of no ways of doing a full match set, perhaps finding zero ways would be just an outlier of the statistical distribution, as this is not an actual proof of non-existence of a failure to match.

Here's a sample shuffle and random distribution into sets of 4. It's the one with 2509 ways of forming the matches:

pack 1     2     3     4     5     6     7     8     9    10    11    12    13
    --    --    --    --    --    --    --    --    --    --    --    --    --
    13    11     1     3     2     5     6    11     2     4    11     9    13
     1     5    13    12     8     3    10    12     8    10     6     3     9
     6    13    10     7     4     7     2     8    12     3    12     8     4
     5    10    11     1     1     7     9     7     5     2     9     6     4
     
The abbreviated list of forming a complete set from 1 to 13 follows. The first column below refers to the pack of 4 from which the Ace (1) is selected; the second column, the pack from which the deuce was selected; the third column, the trey's pack; the fourth column, the pack sourcing the 4; etc.    

source of the:
     1     2     3     4     5     6     7     8     9    10    11    12    13
    --    --    --    --    --    --    --    --    --    --    --    --    --
 
     1     5     4    10     2     7     6     8    12     3    11     9    13
     1     5     4    10     2     7     6     9    12     3     8    11    13
     1     5     4    10     2     7     6     9    12     3    11     8    13
     1     5     4    10     2     7     6    12    11     3     8     9    13
     1     5     4    10     2    11     6     8    12     7     3     9    13
     1     5     4    10     2    11     6     9    12     7     3     8    13
     1     5     4    10     2    11     6    12     7     3     8     9    13
     1     5     4    10     2    11     6    12    13     7     8     9     3
         
            .   .   .
     1    10     6     5     2    12     4     9    13     7    11     8     3
     1    10     6     5     2    12     8     9     7     3    11     4    13
     1    10     6     5     2    12     8     9    11     7     3     4    13
     1    10     6     5     2    12     8     9    13     7    11     4     3
     1    10     6     5     9     7     4     8    12     2     3    11    13
     1    10     6     5     9     7     4     8    12     3     2    11    13
     1    10     6     5     9     7     4    12    11     2     3     8    13
     1    10     6     5     9     7     4    12    11     3     2     8    13
     1    10     6     5     9     7     4    12    13     2     8    11     3
     1    10     6     5     9     7     4    12    13     2    11     8     3
     1    10     6     5     9     7     4    12    13     3     8    11     2
     1    10     6     5     9     7     4    12    13     3    11     8     2
     1    10     6     5     9     7     8    12    11     2     3     4    13
     1    10     6     5     9     7     8    12    11     3     2     4    13
     1    10     6     5     9     7     8    12    13     2    11     4     3
     1    10     6     5     9     7     8    12    13     3    11     4     2
     1    10     6     5     9    11     4    12     7     2     3     8    13
     1    10     6     5     9    11     4    12     7     3     2     8    13
     1    10     6     5     9    11     4    12    13     7     2     8     3
     1    10     6     5     9    11     4    12    13     7     3     8     2
     1    10     6     5     9    11     8    12     7     2     3     4    13
     1    10     6     5     9    11     8    12     7     3     2     4    13
     1    10     6     5     9    11     8    12    13     7     2     4     3
     1    10     6     5     9    11     8    12    13     7     3     4     2
     1    10     6     5     9    12     4     8     7     2     3    11    13
     1    10     6     5     9    12     4     8     7     3     2    11    13
     1    10     6     5     9    12     4     8    13     7     2    11     3
     1    10     6     5     9    12     4     8    13     7     3    11     2
     1    10     6    13     2    11     4     5    12     7     8     9     3
     1    10     6    13     2    12     4     5    11     7     8     9     3
     1    10     6    13     9     7     4     5    12     2     8    11     3
     1    10     6    13     9     7     4     5    12     2    11     8     3
     1    10     6    13     9     7     4     5    12     3     8    11     2
     1    10     6    13     9     7     4     5    12     3    11     8     2
     1    10     6    13     9     7     8     5    12     2    11     4     3
     1    10     6    13     9     7     8     5    12     3    11     4     2
     1    10     6    13     9    11     4     5    12     7     2     8     3
     1    10     6    13     9    11     4     5    12     7     3     8     2
     1    10     6    13     9    11     8     5    12     7     2     4     3
     1    10     6    13     9    11     8     5    12     7     3     4     2
     1    10     6    13     9    12     4     5     7     2     8    11     3
     1    10     6    13     9    12     4     5     7     2    11     8     3
     1    10     6    13     9    12     4     5     7     3     8    11     2
     1    10     6    13     9    12     4     5     7     3    11     8     2
     1    10     6    13     9    12     4     5    11     7     2     8     3
     1    10     6    13     9    12     4     5    11     7     3     8     2
     1    10     6    13     9    12     8     5     7     2    11     4     3
     1    10     6    13     9    12     8     5     7     3    11     4     2
     1    10     6    13     9    12     8     5    11     7     2     4     3
     1    10     6    13     9    12     8     5    11     7     3     4     2
     1    10    12     5     2     7     6     9    11     3     8     4    13
     1    10    12     5     2    11     6     9     7     3     8     4    13
     1    10    12     5     2    11     6     9    13     7     8     4     3
     1    10    12     5     6     7     4     8    11     2     3     9    13
     1    10    12     5     6     7     4     8    11     3     2     9    13
     1    10    12     5     6     7     4     8    13     2    11     9     3
     1    10    12     5     6     7     4     8    13     3    11     9     2
     1    10    12     5     6     7     4     9    11     2     3     8    13
     1    10    12     5     6     7     4     9    11     3     2     8    13
     1    10    12     5     6     7     4     9    13     2     8    11     3
     1    10    12     5     6     7     4     9    13     2    11     8     3
     1    10    12     5     6     7     4     9    13     3     8    11     2
     1    10    12     5     6     7     4     9    13     3    11     8     2
     1    10    12     5     6     7     8     9    11     2     3     4    13
     1    10    12     5     6     7     8     9    11     3     2     4    13
     1    10    12     5     6     7     8     9    13     2    11     4     3
     1    10    12     5     6     7     8     9    13     3    11     4     2
     1    10    12     5     6    11     4     8     7     2     3     9    13
     1    10    12     5     6    11     4     8     7     3     2     9    13
     1    10    12     5     6    11     4     8    13     7     2     9     3
     1    10    12     5     6    11     4     8    13     7     3     9     2
     1    10    12     5     6    11     4     9     7     2     3     8    13
     1    10    12     5     6    11     4     9     7     3     2     8    13
     1    10    12     5     6    11     4     9    13     7     2     8     3
     1    10    12     5     6    11     4     9    13     7     3     8     2
     1    10    12     5     6    11     8     9     7     2     3     4    13
     1    10    12     5     6    11     8     9     7     3     2     4    13
     1    10    12     5     6    11     8     9    13     7     2     4     3
     1    10    12     5     6    11     8     9    13     7     3     4     2
     1    10    12     5     9     7     6     8    11     2     3     4    13
     1    10    12     5     9     7     6     8    11     3     2     4    13
     1    10    12     5     9     7     6     8    13     2    11     4     3
     1    10    12     5     9     7     6     8    13     3    11     4     2
     1    10    12     5     9    11     6     8     7     2     3     4    13
     1    10    12     5     9    11     6     8     7     3     2     4    13
     1    10    12     5     9    11     6     8    13     7     2     4     3
     1    10    12     5     9    11     6     8    13     7     3     4     2
     1    10    12    13     6     7     4     5    11     2     8     9     3
     1    10    12    13     6     7     4     5    11     3     8     9     2
     1    10    12    13     6    11     4     5     7     2     8     9     3
     1    10    12    13     6    11     4     5     7     3     8     9     2
     1    10    12    13     9     7     6     5    11     2     8     4     3
     1    10    12    13     9     7     6     5    11     3     8     4     2
     1    10    12    13     9    11     6     5     7     2     8     4     3
     1    10    12    13     9    11     6     5     7     3     8     4     2
     3     5     4    10     1     7     6     8    12     2    11     9    13
     3     5     4    10     1     7     6     9    12     2     8    11    13
     3     5     4    10     1     7     6     9    12     2    11     8    13
     3     5     4    10     1     7     6    12    11     2     8     9    13
     3     5     4    10     1    11     6     8    12     7     2     9    13
     3     5     4    10     1    11     6     9    12     7     2     8    13
     3     5     4    10     1    11     6    12     7     2     8     9    13
     3     5     4    10     1    11     6    12    13     7     8     9     2
     3     5     4    10     1    12     6     8     7     2    11     9    13
     3     5     4    10     1    12     6     8    11     7     2     9    13
     3     5     4    10     1    12     6     8    13     7    11     9     2
     3     5     4    10     1    12     6     9     7     2     8    11    13
               .   .   .
     3    10    12    13     6     1     4     5    11     7     8     9     2
     3    10    12    13     6     7     4     5    11     2     8     9     1
     3    10    12    13     6    11     4     5     7     2     8     9     1
     3    10    12    13     9     1     6     5    11     7     8     4     2
     3    10    12    13     9     7     6     5    11     2     8     4     1
     3    10    12    13     9    11     6     5     7     2     8     4     1
     4     5     6    10     1     7     8     9    12     2     3    11    13
     4     5     6    10     1     7     8     9    12     3     2    11    13
     4     5     6    10     1     7     8    12    11     2     3     9    13
     4     5     6    10     1     7     8    12    11     3     2     9    13
     4     5     6    10     1     7     8    12    13     2    11     9     3
     4     5     6    10     1     7     8    12    13     3    11     9     2
     4     5     6    10     1    11     8    12     7     2     3     9    13
     4     5     6    10     1    11     8    12     7     3     2     9    13
     4     5     6    10     1    11     8    12    13     7     2     9     3
     4     5     6    10     1    11     8    12    13     7     3     9     2
     4     5     6    10     1    12     8     9     7     2     3    11    13
     4     5     6    10     1    12     8     9     7     3     2    11    13
     4     5     6    10     1    12     8     9    13     7     2    11     3
           .   .   .
     4    10    12     5     1     7     6     8    11     2     3     9    13
     4    10    12     5     1     7     6     8    11     3     2     9    13
     4    10    12     5     1     7     6     8    13     2    11     9     3
     4    10    12     5     1     7     6     8    13     3    11     9     2
     4    10    12     5     1     7     6     9    11     2     3     8    13
     4    10    12     5     1     7     6     9    11     3     2     8    13
     4    10    12     5     1     7     6     9    13     2     8    11     3
     4    10    12     5     1     7     6     9    13     2    11     8     3
     4    10    12     5     1     7     6     9    13     3     8    11     2
     4    10    12     5     1     7     6     9    13     3    11     8     2
     4    10    12     5     1    11     6     8     7     2     3     9    13
     4    10    12     5     1    11     6     8     7     3     2     9    13
     4    10    12     5     1    11     6     8    13     7     2     9     3
     4    10    12     5     1    11     6     8    13     7     3     9     2
     4    10    12     5     1    11     6     9     7     2     3     8    13
     4    10    12     5     1    11     6     9     7     3     2     8    13
     4    10    12     5     1    11     6     9    13     7     2     8     3
     4    10    12     5     1    11     6     9    13     7     3     8     2
     4    10    12     5     2     1     6     8     7     3    11     9    13
     4    10    12     5     2     1     6     8    11     7     3     9    13
     4    10    12     5     2     1     6     8    13     7    11     9     3
     4    10    12     5     2     1     6     9     7     3     8    11    13
     4    10    12     5     2     1     6     9     7     3    11     8    13
     4    10    12     5     2     1     6     9    11     7     3     8    13
     4    10    12     5     2     1     6     9    13     7     8    11     3
     4    10    12     5     2     1     6     9    13     7    11     8     3
     4    10    12     5     2     7     6     8    13     3    11     9     1
     4    10    12     5     2     7     6     9    13     3     8    11     1
     4    10    12     5     2     7     6     9    13     3    11     8     1
     4    10    12     5     2    11     6     8    13     7     3     9     1
     4    10    12     5     2    11     6     9    13     7     3     8     1
     4    10    12     5     6     1     8     9     7     2     3    11    13
     4    10    12     5     6     1     8     9     7     3     2    11    13
     4    10    12     5     6     1     8     9    13     7     2    11     3
     4    10    12     5     6     1     8     9    13     7     3    11     2
     4    10    12     5     6     7     8     9    13     2     3    11     1
     4    10    12     5     6     7     8     9    13     3     2    11     1
     4    10    12     5     9     1     6     8     7     2     3    11    13
     4    10    12     5     9     1     6     8     7     3     2    11    13
     4    10    12     5     9     1     6     8    13     7     2    11     3
     4    10    12     5     9     1     6     8    13     7     3    11     2
     4    10    12     5     9     7     6     8    13     2     3    11     1
     4    10    12     5     9     7     6     8    13     3     2    11     1
     4    10    12    13     1     7     6     5    11     2     8     9     3
     4    10    12    13     1     7     6     5    11     3     8     9     2
     4    10    12    13     1    11     6     5     7     2     8     9     3
     4    10    12    13     1    11     6     5     7     3     8     9     2
     4    10    12    13     2     1     6     5    11     7     8     9     3
     4    10    12    13     2     7     6     5    11     3     8     9     1
     4    10    12    13     2    11     6     5     7     3     8     9     1
     4    10    12    13     6     1     8     5     7     2    11     9     3
     4    10    12    13     6     1     8     5     7     3    11     9     2
     4    10    12    13     6     1     8     5    11     7     2     9     3
     4    10    12    13     6     1     8     5    11     7     3     9     2
     4    10    12    13     6     7     8     5    11     2     3     9     1
     4    10    12    13     6     7     8     5    11     3     2     9     1
     4    10    12    13     6    11     8     5     7     2     3     9     1
     4    10    12    13     6    11     8     5     7     3     2     9     1
     4    10    12    13     9     1     6     5     7     2     8    11     3
     4    10    12    13     9     1     6     5     7     2    11     8     3
     4    10    12    13     9     1     6     5     7     3     8    11     2
     4    10    12    13     9     1     6     5     7     3    11     8     2
     4    10    12    13     9     1     6     5    11     7     2     8     3
     4    10    12    13     9     1     6     5    11     7     3     8     2
     4    10    12    13     9     7     6     5    11     2     3     8     1
     4    10    12    13     9     7     6     5    11     3     2     8     1
     4    10    12    13     9    11     6     5     7     2     3     8     1
     4    10    12    13     9    11     6     5     7     3     2     8     1
     5     7     4    10     1    11     6     8    12     2     3     9    13
     5     7     4    10     1    11     6     8    12     3     2     9    13
     5     7     4    10     1    11     6     9    12     2     3     8    13
     5     7     4    10     1    11     6     9    12     3     2     8    13
     5     7     4    10     1    11     6    12    13     2     8     9     3
     5     7     4    10     1    11     6    12    13     3     8     9     2
     5     7     4    10     1    12     6     8    11     2     3     9    13
     5     7     4    10     1    12     6     8    11     3     2     9    13
     5     7     4    10     1    12     6     8    13     2    11     9     3
     5     7     4    10     1    12     6     8    13     3    11     9     2
     5     7     4    10     1    12     6     9    11     2     3     8    13
     5     7     4    10     1    12     6     9    11     3     2     8    13
     5     7     4    10     1    12     6     9    13     2     8    11     3
     5     7     4    10     1    12     6     9    13     2    11     8     3
     5     7     4    10     1    12     6     9    13     3     8    11     2
     5     7     4    10     1    12     6     9    13     3    11     8     2
     5     7     4    10     2     1     6     8    12     3    11     9    13
     5     7     4    10     2     1     6     9    12     3     8    11    13
     5     7     4    10     2     1     6     9    12     3    11     8    13
     5     7     4    10     2     1     6    12    11     3     8     9    13
     5     7     4    10     2    11     6    12    13     3     8     9     1
     5     7     4    10     2    12     6     8    13     3    11     9     1
     5     7     4    10     2    12     6     9    13     3     8    11     1
     5     7     4    10     2    12     6     9    13     3    11     8     1
     5     7     4    10     6     1     8     9    12     2     3    11    13
     5     7     4    10     6     1     8     9    12     3     2    11    13
     5     7     4    10     6     1     8    12    11     2     3     9    13
     5     7     4    10     6     1     8    12    11     3     2     9    13
     5     7     4    10     6     1     8    12    13     2    11     9     3
     5     7     4    10     6     1     8    12    13     3    11     9     2
     5     7     4    10     6    11     8    12    13     2     3     9     1
     5     7     4    10     6    11     8    12    13     3     2     9     1
     5     7     4    10     6    12     8     9    13     2     3    11     1
     5     7     4   
  Posted by Charlie on 2021-11-18 16:24:59
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (8)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information