My Graph Theory StudentsSleeping studentsTwo students guessing positive integerThe Robostanchion Exam (a puzzle about game-graph connectedness)School where every pair of students share a common grandfatherLabelling a graph with a partition of 100Picture a graph without wordsHunter chasing a fox on a graphNumber Theory classNumber Theory Class v2Identify this type of graph puzzle
Should I be concerned about student access to a test bank?
Can a medieval gyroplane be built?
What can I do if I am asked to learn different programming languages very frequently?
Do I need to be arrogant to get ahead?
Is it possible to stack the damage done by the Absorb Elements spell?
I seem to dance, I am not a dancer. Who am I?
How to terminate ping <dest> &
What does Jesus mean regarding "Raca," and "you fool?" - is he contrasting them?
Maths symbols and unicode-math input inside siunitx commands
Generic TVP tradeoffs?
What should I install to correct "ld: cannot find -lgbm and -linput" so that I can compile a Rust program?
What (if any) is the reason to buy in small local stores?
Existence of a celestial body big enough for early civilization to be thought of as a second moon
Do US professors/group leaders only get a salary, but no group budget?
How can an organ that provides biological immortality be unable to regenerate?
How does 取材で訪れた integrate into this sentence?
When did antialiasing start being available?
Is it insecure to send a password in a `curl` command?
Print last inputted byte
What exactly term 'companion plants' means?
Pronounciation of the combination "st" in spanish accents
How are passwords stolen from companies if they only store hashes?
Am I eligible for the Eurail Youth pass? I am 27.5 years old
In Aliens, how many people were on LV-426 before the Marines arrived?
My Graph Theory Students
Sleeping studentsTwo students guessing positive integerThe Robostanchion Exam (a puzzle about game-graph connectedness)School where every pair of students share a common grandfatherLabelling a graph with a partition of 100Picture a graph without wordsHunter chasing a fox on a graphNumber Theory classNumber Theory Class v2Identify this type of graph puzzle
$begingroup$
I have 18 students in my graph theory course this semester: Anne, Bernard, Clare, David,..., and Rachel. At the start of the course I asked them to draw the graph below, in which each of them is represented by a vertex, two of which are joined by a line if, and only if, they represent two students who are friends.
Fewer than half my students turned up for class last Friday. However, because each of the absent students happened to be friends with at least one of those who did attend, I was able to return everyone's assignments either personally or through a friend. In fact, had a smaller group of students shown up for my class on Friday, I would have been unable to do this.
How may students attended my class on Friday, and who were they?
mathematics no-computers graph-theory
asked 2 days ago
Bernardo Recamán SantosBernardo Recamán Santos
2,7011348
$endgroup$
add a comment |
$begingroup$
I have 18 students in my graph theory course this semester: Anne, Bernard, Clare, David,..., and Rachel. At the start of the course I asked them to draw the graph below, in which each of them is represented by a vertex, two of which are joined by a line if, and only if, they represent two students who are friends.
Fewer than half my students turned up for class last Friday. However, because each of the absent students happened to be friends with at least one of those who did attend, I was able to return everyone's assignments either personally or through a friend. In fact, had a smaller group of students shown up for my class on Friday, I would have been unable to do this.
How may students attended my class on Friday, and who were they?
mathematics no-computers graph-theory
asked 2 days ago
Bernardo Recamán SantosBernardo Recamán Santos
2,7011348
$endgroup$
add a comment |
$begingroup$
I have 18 students in my graph theory course this semester: Anne, Bernard, Clare, David,..., and Rachel. At the start of the course I asked them to draw the graph below, in which each of them is represented by a vertex, two of which are joined by a line if, and only if, they represent two students who are friends.
Fewer than half my students turned up for class last Friday. However, because each of the absent students happened to be friends with at least one of those who did attend, I was able to return everyone's assignments either personally or through a friend. In fact, had a smaller group of students shown up for my class on Friday, I would have been unable to do this.
How may students attended my class on Friday, and who were they?
mathematics no-computers graph-theory
asked 2 days ago
Bernardo Recamán SantosBernardo Recamán Santos
2,7011348
$endgroup$
I have 18 students in my graph theory course this semester: Anne, Bernard, Clare, David,..., and Rachel. At the start of the course I asked them to draw the graph below, in which each of them is represented by a vertex, two of which are joined by a line if, and only if, they represent two students who are friends.
Fewer than half my students turned up for class last Friday. However, because each of the absent students happened to be friends with at least one of those who did attend, I was able to return everyone's assignments either personally or through a friend. In fact, had a smaller group of students shown up for my class on Friday, I would have been unable to do this.
How may students attended my class on Friday, and who were they?
mathematics no-computers graph-theory
mathematics no-computers graph-theory
asked 2 days ago
Bernardo Recamán SantosBernardo Recamán Santos
2,7011348
asked 2 days ago
Bernardo Recamán SantosBernardo Recamán Santos
2,7011348
asked 2 days ago
Bernardo Recamán SantosBernardo Recamán Santos
2,7011348
asked 2 days ago
Bernardo Recamán SantosBernardo Recamán Santos
2,7011348
asked 2 days ago
Bernardo Recamán SantosBernardo Recamán Santos
2,7011348
2,7011348
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
This is an excellent question to demonstrate why the greedy algorithm doesn't always work
The minimum number is actually
$4$
Here are the students which would satisfy the criteria (I think this group is unique)
$F, J, N, O$ (Frank, Jack, Norman, Orville)
Proof that this is minimal
As El-Guest pointed out the maximum number of friendships in the group are held by $M$ & $E$ with $6$ & $5$, respectively. Every other person has four friends or fewer. Therefore, the maximum possible number of people covered by three students is $7+6+5 = 18$. This could only possibly be achieved if $M$ and $E$ were in the group of three but, as El-Guest explored, you need to add three more students to cover everyone else.
answered 2 days ago
hexominohexomino
43.4k3129208
$endgroup$
$begingroup$
I used a solver, getting the same solution and only this one ; hence i am pretty sure it is unique.
$endgroup$
– aluriak
2 days ago
1
$begingroup$
For those interested in the mathematical details, this is called the Set Cover problem. It is a well known problem in computer science and is NP-Hard.The best known linear programming approaches take exponential time.
$endgroup$
– darksky
yesterday
add a comment |
$begingroup$
I'd assume that you'd want
to have the students attend which have the maximum number of friendships...
So:
M & E have 6 & 5 friendships respectively, then P,Q,R,D,F,J don't have to go thanks to M; and A,H,K,N,R don't have to go thanks to E. This leaves us with B,C,G,I,L,O who we need to deal with. O is only connected to P,Q,R, so they have to attend; C is connected with G,I,L; and then B is the last one left who has to show up.
The minimum number of students is therefore
5, and they are Megan, Ethan, Billy, Chris, and Orville.
answered 2 days ago
El-GuestEl-Guest
20.5k24690
$endgroup$
$begingroup$
I figured as much, I didn't like how two of the students had to double up.
$endgroup$
– El-Guest
2 days ago
3
$begingroup$
How do you know this is minimal?
$endgroup$
– noedne
2 days ago
1
$begingroup$
I didn’t, as clearly demonstrated by hexomino’s answer.
$endgroup$
– El-Guest
2 days ago
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "559"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fpuzzling.stackexchange.com%2fquestions%2f80718%2fmy-graph-theory-students%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
This is an excellent question to demonstrate why the greedy algorithm doesn't always work
The minimum number is actually
$4$
Here are the students which would satisfy the criteria (I think this group is unique)
$F, J, N, O$ (Frank, Jack, Norman, Orville)
Proof that this is minimal
As El-Guest pointed out the maximum number of friendships in the group are held by $M$ & $E$ with $6$ & $5$, respectively. Every other person has four friends or fewer. Therefore, the maximum possible number of people covered by three students is $7+6+5 = 18$. This could only possibly be achieved if $M$ and $E$ were in the group of three but, as El-Guest explored, you need to add three more students to cover everyone else.
answered 2 days ago
hexominohexomino
43.4k3129208
$endgroup$
$begingroup$
I used a solver, getting the same solution and only this one ; hence i am pretty sure it is unique.
$endgroup$
– aluriak
2 days ago
1
$begingroup$
For those interested in the mathematical details, this is called the Set Cover problem. It is a well known problem in computer science and is NP-Hard.The best known linear programming approaches take exponential time.
$endgroup$
– darksky
yesterday
add a comment |
$begingroup$
This is an excellent question to demonstrate why the greedy algorithm doesn't always work
The minimum number is actually
$4$
Here are the students which would satisfy the criteria (I think this group is unique)
$F, J, N, O$ (Frank, Jack, Norman, Orville)
Proof that this is minimal
As El-Guest pointed out the maximum number of friendships in the group are held by $M$ & $E$ with $6$ & $5$, respectively. Every other person has four friends or fewer. Therefore, the maximum possible number of people covered by three students is $7+6+5 = 18$. This could only possibly be achieved if $M$ and $E$ were in the group of three but, as El-Guest explored, you need to add three more students to cover everyone else.
answered 2 days ago
hexominohexomino
43.4k3129208
$endgroup$
$begingroup$
I used a solver, getting the same solution and only this one ; hence i am pretty sure it is unique.
$endgroup$
– aluriak
2 days ago
1
$begingroup$
For those interested in the mathematical details, this is called the Set Cover problem. It is a well known problem in computer science and is NP-Hard.The best known linear programming approaches take exponential time.
$endgroup$
– darksky
yesterday
add a comment |
$begingroup$
This is an excellent question to demonstrate why the greedy algorithm doesn't always work
The minimum number is actually
$4$
Here are the students which would satisfy the criteria (I think this group is unique)
$F, J, N, O$ (Frank, Jack, Norman, Orville)
Proof that this is minimal
As El-Guest pointed out the maximum number of friendships in the group are held by $M$ & $E$ with $6$ & $5$, respectively. Every other person has four friends or fewer. Therefore, the maximum possible number of people covered by three students is $7+6+5 = 18$. This could only possibly be achieved if $M$ and $E$ were in the group of three but, as El-Guest explored, you need to add three more students to cover everyone else.
answered 2 days ago
hexominohexomino
43.4k3129208
$endgroup$
This is an excellent question to demonstrate why the greedy algorithm doesn't always work
The minimum number is actually
$4$
Here are the students which would satisfy the criteria (I think this group is unique)
$F, J, N, O$ (Frank, Jack, Norman, Orville)
Proof that this is minimal
As El-Guest pointed out the maximum number of friendships in the group are held by $M$ & $E$ with $6$ & $5$, respectively. Every other person has four friends or fewer. Therefore, the maximum possible number of people covered by three students is $7+6+5 = 18$. This could only possibly be achieved if $M$ and $E$ were in the group of three but, as El-Guest explored, you need to add three more students to cover everyone else.
answered 2 days ago
hexominohexomino
43.4k3129208
edited 2 days ago
answered 2 days ago
hexominohexomino
43.4k3129208
answered 2 days ago
hexominohexomino
43.4k3129208
answered 2 days ago
hexominohexomino
43.4k3129208
43.4k3129208
$begingroup$
I used a solver, getting the same solution and only this one ; hence i am pretty sure it is unique.
$endgroup$
– aluriak
2 days ago
1
$begingroup$
For those interested in the mathematical details, this is called the Set Cover problem. It is a well known problem in computer science and is NP-Hard.The best known linear programming approaches take exponential time.
$endgroup$
– darksky
yesterday
add a comment |
$begingroup$
I used a solver, getting the same solution and only this one ; hence i am pretty sure it is unique.
$endgroup$
– aluriak
2 days ago
1
$begingroup$
For those interested in the mathematical details, this is called the Set Cover problem. It is a well known problem in computer science and is NP-Hard.The best known linear programming approaches take exponential time.
$endgroup$
– darksky
yesterday
$begingroup$
I used a solver, getting the same solution and only this one ; hence i am pretty sure it is unique.
$endgroup$
– aluriak
2 days ago
$begingroup$
I used a solver, getting the same solution and only this one ; hence i am pretty sure it is unique.
$endgroup$
– aluriak
2 days ago
1
1
$begingroup$
For those interested in the mathematical details, this is called the Set Cover problem. It is a well known problem in computer science and is NP-Hard.The best known linear programming approaches take exponential time.
$endgroup$
– darksky
yesterday
$begingroup$
For those interested in the mathematical details, this is called the Set Cover problem. It is a well known problem in computer science and is NP-Hard.The best known linear programming approaches take exponential time.
$endgroup$
– darksky
yesterday
add a comment |
$begingroup$
I'd assume that you'd want
to have the students attend which have the maximum number of friendships...
So:
M & E have 6 & 5 friendships respectively, then P,Q,R,D,F,J don't have to go thanks to M; and A,H,K,N,R don't have to go thanks to E. This leaves us with B,C,G,I,L,O who we need to deal with. O is only connected to P,Q,R, so they have to attend; C is connected with G,I,L; and then B is the last one left who has to show up.
The minimum number of students is therefore
5, and they are Megan, Ethan, Billy, Chris, and Orville.
answered 2 days ago
El-GuestEl-Guest
20.5k24690
$endgroup$
$begingroup$
I figured as much, I didn't like how two of the students had to double up.
$endgroup$
– El-Guest
2 days ago
3
$begingroup$
How do you know this is minimal?
$endgroup$
– noedne
2 days ago
1
$begingroup$
I didn’t, as clearly demonstrated by hexomino’s answer.
$endgroup$
– El-Guest
2 days ago
add a comment |
$begingroup$
I'd assume that you'd want
to have the students attend which have the maximum number of friendships...
So:
M & E have 6 & 5 friendships respectively, then P,Q,R,D,F,J don't have to go thanks to M; and A,H,K,N,R don't have to go thanks to E. This leaves us with B,C,G,I,L,O who we need to deal with. O is only connected to P,Q,R, so they have to attend; C is connected with G,I,L; and then B is the last one left who has to show up.
The minimum number of students is therefore
5, and they are Megan, Ethan, Billy, Chris, and Orville.
answered 2 days ago
El-GuestEl-Guest
20.5k24690
$endgroup$
$begingroup$
I figured as much, I didn't like how two of the students had to double up.
$endgroup$
– El-Guest
2 days ago
3
$begingroup$
How do you know this is minimal?
$endgroup$
– noedne
2 days ago
1
$begingroup$
I didn’t, as clearly demonstrated by hexomino’s answer.
$endgroup$
– El-Guest
2 days ago
add a comment |
$begingroup$
I'd assume that you'd want
to have the students attend which have the maximum number of friendships...
So:
M & E have 6 & 5 friendships respectively, then P,Q,R,D,F,J don't have to go thanks to M; and A,H,K,N,R don't have to go thanks to E. This leaves us with B,C,G,I,L,O who we need to deal with. O is only connected to P,Q,R, so they have to attend; C is connected with G,I,L; and then B is the last one left who has to show up.
The minimum number of students is therefore
5, and they are Megan, Ethan, Billy, Chris, and Orville.
answered 2 days ago
El-GuestEl-Guest
20.5k24690
$endgroup$
I'd assume that you'd want
to have the students attend which have the maximum number of friendships...
So:
M & E have 6 & 5 friendships respectively, then P,Q,R,D,F,J don't have to go thanks to M; and A,H,K,N,R don't have to go thanks to E. This leaves us with B,C,G,I,L,O who we need to deal with. O is only connected to P,Q,R, so they have to attend; C is connected with G,I,L; and then B is the last one left who has to show up.
The minimum number of students is therefore
5, and they are Megan, Ethan, Billy, Chris, and Orville.
answered 2 days ago
El-GuestEl-Guest
20.5k24690
answered 2 days ago
El-GuestEl-Guest
20.5k24690
answered 2 days ago
El-GuestEl-Guest
20.5k24690
answered 2 days ago
El-GuestEl-Guest
20.5k24690
20.5k24690
$begingroup$
I figured as much, I didn't like how two of the students had to double up.
$endgroup$
– El-Guest
2 days ago
3
$begingroup$
How do you know this is minimal?
$endgroup$
– noedne
2 days ago
1
$begingroup$
I didn’t, as clearly demonstrated by hexomino’s answer.
$endgroup$
– El-Guest
2 days ago
add a comment |
$begingroup$
I figured as much, I didn't like how two of the students had to double up.
$endgroup$
– El-Guest
2 days ago
3
$begingroup$
How do you know this is minimal?
$endgroup$
– noedne
2 days ago
1
$begingroup$
I didn’t, as clearly demonstrated by hexomino’s answer.
$endgroup$
– El-Guest
2 days ago
$begingroup$
I figured as much, I didn't like how two of the students had to double up.
$endgroup$
– El-Guest
2 days ago
$begingroup$
I figured as much, I didn't like how two of the students had to double up.
$endgroup$
– El-Guest
2 days ago
3
3
$begingroup$
How do you know this is minimal?
$endgroup$
– noedne
2 days ago
$begingroup$
How do you know this is minimal?
$endgroup$
– noedne
2 days ago
1
1
$begingroup$
I didn’t, as clearly demonstrated by hexomino’s answer.
$endgroup$
– El-Guest
2 days ago
$begingroup$
I didn’t, as clearly demonstrated by hexomino’s answer.
$endgroup$
– El-Guest
2 days ago
add a comment |
Thanks for contributing an answer to Puzzling Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fpuzzling.stackexchange.com%2fquestions%2f80718%2fmy-graph-theory-students%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
