Euler 2015/1

#1

Έχουμε

άτομα οι οποίοι κάθονται γύρω από ένα στρογγυλό τραπέζι και πίνουν κρασί. Θέλουν όλοι να τσουγκρίσουν τα ποτήρια τους μεταξύ τους. Σε κάθε γύρο τσουγκρίσματος πρέπει να ικανοποιούνται οι πιο κάτω συνθήκες:
(α) Κάθε άτομο τσουγκρίζει το ποτήρι του με το πολύ ένα άλλο άτομο.
(β) Δεν υπάρχουν άτομα που να σταυρώνουν τα χέρια τους.
(γ) Δεν γίνονται τσουγκρίσματα πίσω από τις πλάτες άλλων ατόμων.

Π.χ. στην συνημμένη εικόνα έχουμε στα αριστερά έναν επιτρεπόμενο γύρο τσουγκρίσματος με δυο ζεύγη ατόμων που τσουγκρίζουν τα ποτήρια τους. (Στην εικόνα μόνο τα ευθύγραμμα τμήματα δηλώνουν τσούγκρισμα και όχι τα τόξα του κύκλου.) Στα δεξιά έχουμε τρία ζεύγη ατόμων που τσουγκρίζουν μεταξύ τους τα οποία όμως παραβιάζουν τις συνθήκες. (Τόσο την (β) όσο και την (γ).)

Να βρεθεί ο ελάχιστος αριθμός των γύρων που χρειάζονται ώστε όλοι να τσουγκρίσουν το ποτήρι τους με όλους.

#2

Βάζω μια λύση.

Υπενθυμίζω ότι στην αρχή της Δημόσιας Συζήτησης βρίσκονται αρχεία με όσα θέματα μαζέψαμε από Seemous,IMC,Putnam,Vojtech Jarnik και Euler. Σε κάθε αρχείο είναι κοκκινισμένα αυτά που δεν λύθηκαν. Υπάρχουν άλυτα από εύκολα έως εξαιρετικά δύσκολα.

Έστω $1,2,\ldots,n$ τα άτομα με αυτήν την κυκλική σειρά. Κοιτάζουμε τα τσουγκρίσματα $12,13,\ldots,1n$ και

. Μπορούμε να κάνουμε το πολύ ένα από αυτά τα τσουγκρίσματα σε κάθε γύρο, οπότε χρειάζονται τουλάχιστον

γύροι. Θα δείξω ότι

γύροι είναι αρκετοί.

Στον γύρο

τσουγκρίζουν ποτήρια όλα τα ζεύγη $\{i,j\}$ με $i+j \equiv k \bmod n$ . Προφανώς κάθε ζεύγος τσουγκρίζει ποτήρια και μένει να δείξουμε ότι κάθε γύρος είναι επιτρεπόμενος.

Αλλά σε αντίθετη περίπτωση, έχουμε a,b,c,d

με

και $a+c \equiv b+d \equiv k \bmod n$ . Τότε όμως είναι και $d-a \equiv c-b \bmod n$ το οποίο είναι αδύνατον αφού c-b < d-a < n

.

Euler 2015/1

Euler 2015/1

Re: Euler 2015/1

Μέλη σε σύνδεση