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.
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 |
simulation program
