Spaß, herausforderndes Graphkombinatorikproblem
Es gibt ein Problem, mit dem ich seit einiger Zeit zu kämpfen habe und das anscheinend nicht den richtigen Weg zur Lösung findet.
Problem: Eine Prüfung hat $5$ Multiple-Choice-Fragen mit $4$Auswahlmöglichkeiten jeweils. 2000 Studenten nahmen an der Prüfung teil und beantworteten jeweils alle 5 Fragen. Es wird festgestellt, dass$(*)$ für jeden $n$ Prüfungsunterlagen finden Sie $4$ Papiere so, dass keine $2$ Papiere haben höchstens $3$gleiche Antworten. Finde das kleinste$n$.
Was ich habe: Es gibt $1024$verschiedene Möglichkeiten, wie die Prüfung beantwortet werden kann. Finden Sie zuerst die Nummer$m$ von verschiedenen Papieren aus dem $1024$ so dass Eigentum $(*)$ ist zufrieden, dann finde das Minimum $n$ Prüfungen aus dem $2000$ Prüfungsunterlagen, die enthalten würden $m$verschiedene Prüfungsantworten. Ich habe versucht, es als Grafik zu formulieren. Zwei Prüfungstypen sind miteinander verbunden, wenn sich die nur unterscheiden$1$ Antwort, dann ist jeder Prüfungstyp genau verbunden $15$Andere. Dann wurde versucht, eine Ungleichung zu verwenden, um die Anzahl von zu begrenzen$m$, aber es hat nicht funktioniert. Die Lösung ist$n=25$ was ich glaube bedeutet $m=13$.
Jeder Hinweis oder jede Lösung ist willkommen. Vielen Dank.
Antworten
Ich gehe davon aus, dass von "dem Kleinsten $n$"wir meinen" das kleinste $n$ für die es möglich ist $(*)$ zu halten "- so können wir die auswählen $2000$Prüfungsunterlagen wie wir wollen. Im schlimmsten Fall von Prüfungsunterlagen,$(*)$ würde für keine halten $n$: der schlimmste Fall ist das alles $2000$ Die Schüler geben alle die gleichen Antworten.
Um die Prüfungsunterlagen bestmöglich auszuwählen, muss nur sichergestellt werden, dass jeder Satz von Antworten höchstens zweimal gegeben wird. Dann haben Sie unter allen Recht$n=25$ Prüfungen gibt es eine Reihe von $m=13$ verschiedene Prüfungen.
Angenommen, die $4$ Auswahlmöglichkeiten für jede Frage werden die Nummern zugewiesen $0, 1, 2, 3$. Weisen Sie jeder Prüfungsarbeit einen Wert zu, indem Sie die Zahlen für alle modulo-Antworten addieren$4$. Dann haben zwei beliebige Prüfungsunterlagen mit demselben Wert entweder alle die gleichen Antworten oder stimmen zumindest nicht überein$2$ Antworten.
Es sind nur $4$ mögliche Werte für eine Prüfung, also in jedem Satz von $m=13$ Es gibt verschiedene Prüfungen $\lceil \frac m4\rceil = 4$Prüfungen mit dem gleichen Wert. Dies sind die$4$ Prüfungen, die wir finden wollten.
Es gibt eine alternative Konstruktion. Angenommen, die$2000$ Alle Schüler geben wertvolle Antworten $0$ (durch das gleiche Modulo $4$ Regel wie oben), und dass wir ihre Antworten gleichmäßig verteilen, so dass jeder Satz von $256$ Antworten wird entweder gegeben $7$ oder $8$mal. Dann unter allen$25$ Prüfungsunterlagen muss es mindestens geben $4$unterschiedliche Antwortsätze. Das können unsere Sets sein$4$: da sie alle Wert haben $0$unterscheiden sie sich an mindestens zwei Stellen.
Um das Problem zu lösen, sollten wir auch zeigen, dass unabhängig von den Antworten, die die Schüler geben, $(*)$ kann nicht halten für $n=24$.
Um dies zu sehen, gruppieren Sie die Prüfungsunterlagen in $256$Gruppen nach den ersten vier Antworten. Die durchschnittliche Anzahl der Prüfungen in einer Gruppe beträgt$\frac{2000}{256} = 7.8125$Die durchschnittliche Anzahl der Prüfungen in drei Gruppen beträgt also$\frac{6000}{256} = 23.4375$. Daher gibt es drei Gruppen, die mindestens diesen Durchschnitt enthalten: mindestens$24$ Prüfungen.
Nehmen Sie an den Prüfungen dieser drei Gruppen teil. Dann keine$4$Davon sind zwei Prüfungen aus derselben Gruppe. Daher keine$4$ von ihnen haben ein Paar von Prüfungen, die sich in höchstens einer Antwort unterscheiden, und $(*)$ gilt nicht für $n=24$.