# How many students in this Math circle and can they together explain the solution of all of the 20 problems?

A Math circle leader assigned 20 problems as homework. At the next meeting, he found out that each student solved exactly 2 problems, and that each problem was solved by exactly 2 students.

• A) How many students are in the circle?

• B) Is it possible to set up a discussion of the problems so that

• a) each student explains one of the problems that he has solved and
• b) all the 20 problems get explained by the students?

From the book: Moscow math circle by Sergey Dorichenko

• Maybe it's just me, but choosing that each student solves 2 and that each problem is solved by 2 makes it very very trivial and intuitive. It would be more challenging maybe if you picked different numbers
– Ivo
Commented May 25, 2023 at 8:24
• I disagree. The second is also trivial. But maybe that's just me
– Ivo
Commented May 25, 2023 at 8:36
• in that case the answer to the second question is extremely trivial Commented May 25, 2023 at 16:19
• Yea, "at least one" doesn't make an interesting puzzle, just let each student present any of the two problems they did, and if some problems are not covered, pick random student that did it to present. "Exactly one" is a more interesting one, as shown in Manish answer. Commented May 25, 2023 at 16:25
• For those that are curious this type of problem is generalized by the concept of a "configuration" in mathematics. For example if there are 21 questions with each student answering 4 and each answered by 4, this corresponds to the Grünbaum–Rigby configuration. Commented May 26, 2023 at 1:28

20 students

Choose any student who solved problem 1 and ask them to explain that problem. Say they solved problems (1, x1). Then pick the other student who solved problem x1 and ask them to explain x1. Keep continuing the process and you will end up with a cycle looking like [(1, x1), (x1, x2), (x2, x3), ...., (x_k, 1)]. There might be multiple such cycles so everytime you get a cycle you can start the process again with any unexplained problem.

• Can you add the reasoning for the answer to A? Commented May 24, 2023 at 20:35
• rot13(Gur gjragl dhrfgvbaf jrer rnpu fbyirq gjvpr, sbe n gbgny bs sbegl fbyhgvbaf. Fvapr gjb fbyhgvbaf jrer jevggra ol rnpu fghqrag, gurer zhfg unir orra gjragl fghqragf va gur pynff.) Commented May 24, 2023 at 23:20
• @JGibbers Just consider the total number of problem solutions handed in. Commented May 25, 2023 at 8:00

The graph theory solution (equivalent to https://puzzling.stackexchange.com/a/120970/83286):

This is a bipartite graph where the parts both have uniform degree 2. Thus the part with students also has 20 nodes. Each connected component is thus a cycle with an even number of edges, and you can take every other edge from each cycle for B.

For A:

20 students. Label the questions 1-20 and the students A to T. Students A & B both solve questions 1 & 2, C & D both solve 3 & 4 ... S & T both solve 19 & 20.

For B:

Following from the logic in the first part each student can just explain the question that matches their letters position in the alphabet. A explains 1, B 2, C 3 ... T 20.

• It is not necessary that 2 questions will be solved by the same 2 people. Commented May 25, 2023 at 15:38