5 students test

anna_gg · 2016-01-16 04:14:43

5 students are to pass a graduation exam and for this purpose they must pick 2 questions from a pool of 5.
In fact, each student must choose exactly 2 questions and each question must be chosen by exactly 2 students. In how many possible ways can this be done?

phrontister · 2016-01-16 23:40:00

Hi anna_gg,

anna_gg · 2016-01-17 08:48:24

Could be; I don't know the answer. Solution please?

phrontister · 2016-01-17 10:15:58

Sorry, I don't have a mathematical one...just one that I did by hand. No doubt a formula can be made for this, but how to do that escapes me.

The students' names are A, B, C, D & E.

Their questions are listed under their names, with the first entry (ie, 1 2 3 4 5) being their first choice, respectively, and the rest (numbers 1 - 44) their range of second choice options.

I assumed that the students couldn't pick the same question twice (and maybe that's what is meant by "choose exactly 2 questions").

     A B C D E
     1 2 3 4 5
     ---------
 1 | 2 1 4 5 3 
 2 | 2 1 5 3 4
 3 | 2 3 1 5 4
 4 | 2 3 4 5 1
 5 | 2 3 5 1 4
 6 | 2 4 1 5 3
 7 | 2 4 5 1 3
 8 | 2 4 5 3 1
 9 | 2 5 1 3 4
10 | 2 5 4 1 3
11 | 2 5 4 3 1
12 | 3 1 2 5 4
13 | 3 1 4 5 2
14 | 3 1 5 2 4
15 | 3 4 1 5 2
16 | 3 4 2 5 1
17 | 3 4 5 1 2
18 | 3 4 5 2 1
19 | 3 5 1 2 4
20 | 3 5 2 1 4
21 | 3 5 4 1 2
22 | 3 5 4 2 1
23 | 4 1 2 5 3
24 | 4 1 5 2 3
25 | 4 1 5 3 2
26 | 4 3 1 5 2
27 | 4 3 2 5 1
28 | 4 3 5 1 2
29 | 4 3 5 2 1
30 | 4 5 1 2 3
31 | 4 5 1 3 2
32 | 4 5 2 1 3
33 | 4 5 2 3 1
34 | 5 1 2 3 4
35 | 5 1 4 2 3
36 | 5 1 4 3 2
37 | 5 3 1 2 4
38 | 5 3 2 1 4
39 | 5 3 4 1 2
40 | 5 3 4 2 1
41 | 5 4 1 2 3
42 | 5 4 1 3 2
43 | 5 4 2 1 3
44 | 5 4 2 3 1

EDIT: I since used Excel to confirm my results, by generating a list of all 120 permutations of {1,2,3,4,5}, and then to select from the list the 44 options that met the brief.

Last edited by phrontister (2016-01-25 03:58:03)

Fruityloop · 2016-01-24 12:39:28

A derangement problem with none of the items in its own slot.

phrontister · 2016-01-24 21:13:06

Nice one, Fruityloop!

Glad to see there's a mathematical formula to confirm my manual solution.

This is all way beyond any maths I ever learnt, so I looked up derangements. I found your formula, which to me looks like the following subfactorial formula:

The website from which I got that formula also states:

The subfactorial is used to calculate the number of permutations of a set of n objects in which none of the elements occur in their natural place.

That seems to fit the 5 students test problem, as I understand it.

There's also a subfactorial calculator on that site, which gives the answer for !5 as 44.

Last edited by phrontister (2016-01-24 21:18:48)

anna_gg · 2016-01-24 23:13:25

Guys, thanks for your replies; however, I am not really sure I have correctly explained the requirement: Each student (A, B, C, D and E) must pick exactly 2 of the 5 questions, for example A can choose only 1 and 2, B can choose 2 and 3 but then, question Nr 2 cannot be chosen by any other student (as it has already been chosen by A and B) and so on. This means that there is no restriction for the repetition of digits in each set: we can have for example ABCDE -->>11223 (both A and B picked question 1).

Last edited by anna_gg (2016-01-25 00:06:33)

phrontister · 2016-01-24 23:43:23

Hi anna_gg;

That's exactly how I understood it, and is the basis of my solution method in post number 4.

Their questions are listed under their names, with the first entry (ie, 1 2 3 4 5) being their first choice, respectively, and the rest (numbers 1 - 44) their range of second choice options.

All of those 44 second choice options comprise the digits 1,2,3,4,5 (in an order where no student chooses the same question twice), and as the first choice also contains those same 5 digits, all 5 questions are chosen exactly twice each.

Students' choices of 2 questions are always from their own columns. Those questions are:
1. their first choice, from the row immediately below their names, plus
2. their second choice, from one (ie, only one) of the 44 rows listed below their first-choice row.

All 44 option rows (ie, rows numbered 1 - 44) are valid second choices.

EDIT: Oops...I didn't read your last sentence (ie, "there is no restriction for the repetition of digits in each set") properly! I'll have to rethink...

Last edited by phrontister (2016-01-25 04:14:41)

phrontister · 2016-01-25 06:00:23

Well, by my reckoning, there are 2220 different sets of first-choice questions, and the set chosen will determine which questions will form the set of second-choice questions...of which there will be varying numbers of permutations.

That's as far as I've got...

EDIT 1: I think the 2220 should be halved to 1110 to avoid choice-order duplicates where second-choice sets have already been used as first-choice sets.
EDIT 2: "...of which there will be varying numbers of permutations." There are only 3 such varieties: 24, 32 and 44.

Last edited by phrontister (2016-01-29 16:07:43)

phrontister · 2016-01-26 17:24:40

Is the answer 32640?

EDIT: It's based on the post #9 info.

Last edited by phrontister (2016-01-29 16:14:28)

Fruityloop · 2016-01-26 18:15:59

OK. The 44 permutations for the second question needs to be run through for all possible permutations of the first question which is 120 or 5!. We are counting things twice so we divide by 2.

Is this right?

phrontister · 2016-01-27 13:33:09

Hi anna_gg,

anna_gg wrote:

In how many possible ways can this be done?

Is this an example of two different ways?

     1      2
A:  1,3    1,3
B:  1,4    1,3
C:  2,4    2,4
D:  2,5    2,5
E:  3,5    4,5

It seems so to me, and my answer in post #10 is based on this example being valid.

Last edited by phrontister (2016-01-28 19:00:33)

anna_gg · 2016-01-29 01:20:11

Yes, this is such an example!!

phrontister wrote:

Hi anna_gg,
anna_gg wrote:
In how many possible ways can this be done?
Is this an example of two different ways?
     1      2
A:  1,3    1,3
B:  1,4    1,3
C:  2,4    2,4
D:  2,5    2,5
E:  3,5    4,5
It seems so to me, and my answer in post #10 is based on this example being valid.

phrontister · 2016-01-30 05:17:45

Ok...thanks.

This is how I arrived at my answer of 32640. It's a method I thought up just yesterday to verify the result from my post #9 method (which it did), but is easier to explain than that one.

There are 113400 permutations of the two lots of 5 questions, starting with 1,1,2,2,3,3,4,4,5,5 and ending with 5,5,4,4,3,3,2,2,1,1.

Formula: , where 'n' is the total number of questions picked, and letters 'p' to 't' denote the quantity of repeat numbers in different sets (in this case there are 5 sets of pairs).

So,

In each permutation, student A's questions are the first two digits, B's are the next two...and so on for C, D & E.

Of the 113400 permutations, there are 65280 where no student chooses the same two questions.

65280 is comprised 50:50 of valid possibilities and duplicates: eg,

                                    A  |  B  |  C  |  D  |  E
First valid possibility (#2528) :  1,2 | 1,2 | 3,4 | 3,5 | 4,5 
Its duplicate          (#23348) :  2,1 | 2,1 | 4,3 | 5,3 | 5,4
Last valid possibility (#90053) :  4,5 | 4,5 | 2,3 | 1,3 | 1,2 
Its duplicate          (#110873):  5,4 | 5,4 | 3,2 | 3,1 | 2,1

So the answer = 65280/2 = 32640.

That took miles of coding in Excel (also with a bit of help from M), for which you'd need a 64-bit version of Excel running on a 64-bit operating system with a truckload of ram...all of which my computer has, fortunately.

No doubt there's a tiny mathematical formula hiding out there somewhere that could solve this in less than a blink!

Last edited by phrontister (2016-02-02 14:24:02)

phrontister · 2016-02-02 12:42:29

This is my post #9 method:

Subject to the rule "each question must be chosen by exactly 2 students", there are 2220 different sets (permutations) of first-choice questions, and any set chosen determines which question numbers (but not their exact order) form the set of second-choice questions. No student has the same two questions (not exactly stated, but implied, I'd say).

Here's an explanation of the table below:

The first-choice questions only have three varieties (v1, v2, v3), and their second-choice partners the same. Examples are given.

There are different quantities of these varieties: v1=120, v2=1200, v3=900, which total 2220.

The number of permutations of second-choice questions is constant for each of the varieties: v1=44, v2=32, v3=24.

So now we can calculate the total number of different possible ways the questions can be picked:
v1 + v2 + v3 = (120 x 44) + (1200 x 32) + (900 x 24) = 5280 + 38400 + 21600 = 65280

But half of the combinations of first and second-choice sets are duplicates (eg, 1st choice 1,1,2,3,4 & 2nd choice 4,5,5,2,3 = 1st choice 4,5,5,2,3 & 2nd choice 1,1,2,3,4).

Therefore the answer is 65280/2 = 32640.

                             1st choice | 2nd choice   
                              A B C D E | A B C D E   varieties   2nd choice perms   varieties x perms
v1: no repeat digits          1 2 3 4 5 | 2 3 1 5 4      120             44                5280
v2: 1 pair of repeat digits   1 1 2 3 4 | 4 5 3 2 5     1200             32               38400
v3: 2 pairs of repeat digits  1 1 2 2 3 | 5 4 3 4 5      900             24               21600
                                                Totals  2220                              65280...less 50% duplicates = 32640

Last edited by phrontister (2016-02-02 14:21:19)

phrontister · 2016-02-09 11:59:19

Hmmm...a huge number of duplicates slipped under my guard.

I've eliminated them all now (I think!) by using a strengthened version of the post #14 method, and got 2040 as the answer.

EDIT: It's interesting that , as is mentioned in my previous two posts as being the answer before the elimination of duplicates. I guess the exponent 5 has something to do with the number of students (5) or the number of questions (5), with the 2 referring to duplicates.

Last edited by phrontister (2016-02-09 19:51:11)

phrontister · 2016-02-10 22:02:46

I'm going to try to repost this, as the page wouldn't load. Maybe listing all 2040 permutations was the problem. So here goes, with less this time:

Here are the first 50 permutations from the total of 2040.

The permutations are in ascending order of concatenated strings of chosen questions (as per the post #14 method), with each student's picks also in ascending order. These two features enabled me to eliminate all duplicates.

eg, {12 12 34 35 54} isn't listed, as it's a duplicate of {12 12 34 35 45} (ie, student E picks questions {4,5}, in any order). Only the first version of a set that contains such duplicates is listed.

  #  A  B  C  D  E
  1  12 12 34 35 45
  2  12 12 34 45 35
  3  12 12 35 34 45
  4  12 12 35 45 34
  5  12 12 45 34 35
  6  12 12 45 35 34
  7  12 13 23 45 45
  8  12 13 24 35 45
  9  12 13 24 45 35
 10  12 13 25 34 45
 11  12 13 25 45 34
 12  12 13 34 25 45
 13  12 13 34 45 25
 14  12 13 35 24 45
 15  12 13 35 45 24
 16  12 13 45 23 45
 17  12 13 45 24 35
 18  12 13 45 25 34
 19  12 13 45 34 25
 20  12 13 45 35 24
 21  12 13 45 45 23
 22  12 14 23 35 45
 23  12 14 23 45 35
 24  12 14 24 35 35
 25  12 14 25 34 35
 26  12 14 25 35 34
 27  12 14 34 25 35
 28  12 14 34 35 25
 29  12 14 35 23 45
 30  12 14 35 24 35
 31  12 14 35 25 34
 32  12 14 35 34 25
 33  12 14 35 35 24
 34  12 14 35 45 23
 35  12 14 45 23 35
 36  12 14 45 35 23
 37  12 15 23 34 45
 38  12 15 23 45 34
 39  12 15 24 34 35
 40  12 15 24 35 34
 41  12 15 25 34 34
 42  12 15 34 23 45
 43  12 15 34 24 35
 44  12 15 34 25 34
 45  12 15 34 34 25
 46  12 15 34 35 24
 47  12 15 34 45 23
 48  12 15 35 24 34
 49  12 15 35 34 24
 50  12 15 45 23 34

Done on Excel spreadsheet. I still haven't been able to write a mathematical formula for it.

Anyway, I'm feeling fairly confident about this result.

Last edited by phrontister (2016-02-10 22:08:48)

anna_gg · 2016-02-11 08:49:52

Correct!! Very well done!

phrontister · 2016-02-11 11:08:32

Hi Anna,

If you know the mathematical formula for the solution, would you please post it? Thanks.

anna_gg · 2016-02-11 20:23:00

Unfortunately not
But I will definitely work more on this riddle and will post any update. Thanks for your very valuable input!

phrontister wrote:

Hi Anna,
If you know the mathematical formula for the solution, would you please post it? Thanks.

anonimnystefy · 2016-02-12 18:17:21

Last edited by anonimnystefy (2016-02-12 18:19:05)

anna_gg · 2016-02-14 03:06:31

How do you calculate first-choice v2 and v3 and also all the second choice varieties? I only understand 1st choice v1=120 (permutation of 5 numbers / 5)

phrontister wrote:

This is my post #9 method:
Subject to the rule "each question must be chosen by exactly 2 students", there are 2220 different sets (permutations) of first-choice questions, and any set chosen determines which question numbers (but not their exact order) form the set of second-choice questions. No student has the same two questions (not exactly stated, but implied, I'd say).
Here's an explanation of the table below:
The first-choice questions only have three varieties (v1, v2, v3), and their second-choice partners the same. Examples are given.
There are different quantities of these varieties: v1=120, v2=1200, v3=900, which total 2220.
The number of permutations of second-choice questions is constant for each of the varieties: v1=44, v2=32, v3=24.
So now we can calculate the total number of different possible ways the questions can be picked:
v1 + v2 + v3 = (120 x 44) + (1200 x 32) + (900 x 24) = 5280 + 38400 + 21600 = 65280
But half of the combinations of first and second-choice sets are duplicates (eg, 1st choice 1,1,2,3,4 & 2nd choice 4,5,5,2,3 = 1st choice 4,5,5,2,3 & 2nd choice 1,1,2,3,4).
Therefore the answer is 65280/2 = 32640.
                             1st choice | 2nd choice   
                              A B C D E | A B C D E   varieties   2nd choice perms   varieties x perms
v1: no repeat digits          1 2 3 4 5 | 2 3 1 5 4      120             44                5280
v2: 1 pair of repeat digits   1 1 2 3 4 | 4 5 3 2 5     1200             32               38400
v3: 2 pairs of repeat digits  1 1 2 2 3 | 5 4 3 4 5      900             24               21600
                                                Totals  2220                              65280...less 50% duplicates = 32640

anonimnystefy · 2016-02-14 05:49:14

Hej, anna!

For v2 permutations, you need to determine which two people will get the same question, which can be done in 10 ways, and then which question each person will get, which can be done in 5*4*3*2 ways. Similar logic for v3.

phrontister · 2016-02-15 04:05:35

anna_gg wrote:

How do you calculate first-choice v2 and v3 and also all the second choice varieties? I only understand 1st choice v1=120 (permutation of 5 numbers / 5)

Sorry, Anna, but I only have a very basic understanding of permutations, which is mainly from research I've done since you started posting permutation problems. I wasn't taught permutations at school.

anonimnystefy and others here can help you with the formulas you need.

Anyway, for what it's worth, here's how I calculated the first-choice v2 and v3 and all the second-choice varieties:

I went with what I know and like to use - an Excel spreadsheet, even though I knew it would be the long way round compared to using permutation formulas (which I did try to write, btw, but your problem had too many tricks for my basic knowledge, and my research didn't unearth the info I was looking for).

I got Mathematica to list all 3125 (ie, 5^5) permutations (with repeat digits) of 5-digit numbers comprising the digits 1 to 5 and copied the list into an Excel spreadsheet, which I used for the rest of the project. There I whittled the list down to 2220 by eliminating permutations that contained the same digit more than twice.

I then got Excel to count the permutations that had distinct digits of specified lengths for first-choice questions:
(a) 5 distinct digits for v1 (no repeat digits)............of which there were 120 )
(b) 4 distinct digits for v2 (1 pair of repeat digits)...of which there were 1200 ) total 2220
(c) 3 distinct digits for v3 (1 pair of repeat digits)....of which there were 900 )

I could simply have deducted 120 and 1200 from 2220 to get 900, but I used the Excel count to verify that this component was going well.

Directly underneath the row of 2220 first-choice permutations I created a row of corresponding second-choice permutations, with each one formed from leftover question numbers after taking into account those that were used by first-choice permutations. I got Excel to display them with their digits in ascending order to help with eliminating duplicates.

And that's all there was to that!

Last edited by phrontister (2016-02-15 04:07:33)

anna_gg · 2016-02-16 06:44:20

Respect!!!

phrontister wrote:

anna_gg wrote:
How do you calculate first-choice v2 and v3 and also all the second choice varieties? I only understand 1st choice v1=120 (permutation of 5 numbers / 5)
Sorry, Anna, but I only have a very basic understanding of permutations, which is mainly from research I've done since you started posting permutation problems. I wasn't taught permutations at school.
anonimnystefy and others here can help you with the formulas you need.
Anyway, for what it's worth, here's how I calculated the first-choice v2 and v3 and all the second-choice varieties:
I went with what I know and like to use - an Excel spreadsheet, even though I knew it would be the long way round compared to using permutation formulas (which I did try to write, btw, but your problem had too many tricks for my basic knowledge, and my research didn't unearth the info I was looking for).
I got Mathematica to list all 3125 (ie, 5^5) permutations (with repeat digits) of 5-digit numbers comprising the digits 1 to 5 and copied the list into an Excel spreadsheet, which I used for the rest of the project. There I whittled the list down to 2220 by eliminating permutations that contained the same digit more than twice.
I then got Excel to count the permutations that had distinct digits of specified lengths for first-choice questions:
(a) 5 distinct digits for v1 (no repeat digits)............of which there were 120 )
(b) 4 distinct digits for v2 (1 pair of repeat digits)...of which there were 1200 ) total 2220
(c) 3 distinct digits for v3 (1 pair of repeat digits)....of which there were 900 )
I could simply have deducted 120 and 1200 from 2220 to get 900, but I used the Excel count to verify that this component was going well.
Directly underneath the row of 2220 first-choice permutations I created a row of corresponding second-choice permutations, with each one formed from leftover question numbers after taking into account those that were used by first-choice permutations. I got Excel to display them with their digits in ascending order to help with eliminating duplicates.
And that's all there was to that!

Math Is Fun Forum

#1 2016-01-16 04:14:43

5 students test

#2 2016-01-16 23:40:00

Re: 5 students test

#3 2016-01-17 08:48:24

Re: 5 students test

#4 2016-01-17 10:15:58

Re: 5 students test

#5 2016-01-24 12:39:28

Re: 5 students test

#6 2016-01-24 21:13:06

Re: 5 students test

#7 2016-01-24 23:13:25

Re: 5 students test

#8 2016-01-24 23:43:23

Re: 5 students test

#9 2016-01-25 06:00:23

Re: 5 students test

#10 2016-01-26 17:24:40

Re: 5 students test

#11 2016-01-26 18:15:59

Re: 5 students test

#12 2016-01-27 13:33:09

Re: 5 students test

#13 2016-01-29 01:20:11

Re: 5 students test

#14 2016-01-30 05:17:45

Re: 5 students test

#15 2016-02-02 12:42:29

Re: 5 students test

#16 2016-02-09 11:59:19

Re: 5 students test

#17 2016-02-10 22:02:46

Re: 5 students test

#18 2016-02-11 08:49:52

Re: 5 students test

#19 2016-02-11 11:08:32

Re: 5 students test

#20 2016-02-11 20:23:00

Re: 5 students test

#21 2016-02-12 18:17:21

Re: 5 students test

#22 2016-02-14 03:06:31

Re: 5 students test

#23 2016-02-14 05:49:14

Re: 5 students test

#24 2016-02-15 04:05:35

Re: 5 students test

#25 2016-02-16 06:44:20

Re: 5 students test

Board footer