1
$\begingroup$

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

Improve this question
$\endgroup$
11
  • 2
    $\begingroup$ 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 $\endgroup$
    – Ivo
    May 25 at 8:24
  • 3
    $\begingroup$ I disagree. The second is also trivial. But maybe that's just me $\endgroup$
    – Ivo
    May 25 at 8:36
  • 2
    $\begingroup$ in that case the answer to the second question is extremely trivial $\endgroup$
    – juicifer
    May 25 at 16:19
  • 2
    $\begingroup$ 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. $\endgroup$
    – justhalf
    May 25 at 16:25
  • 2
    $\begingroup$ 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. $\endgroup$
    – Wheat Wizard
    May 26 at 1:28

3 Answers 3

Reset to default
16
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Can you add the reasoning for the answer to A? $\endgroup$
    – JGibbers
    May 24 at 20:35
  • 2
    $\begingroup$ 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.) $\endgroup$
    – AxiomaticSystem
    May 24 at 23:20
  • 4
    $\begingroup$ @JGibbers Just consider the total number of problem solutions handed in. $\endgroup$
    – quarague
    May 25 at 8:00
3
$\begingroup$

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.

Improve this answer
$\endgroup$
-2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ It is not necessary that 2 questions will be solved by the same 2 people. $\endgroup$
    – Hemant Agarwal
    May 25 at 15:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.