USAMO $1989$, Sorun $2$

Aug 17 2020

Sorun $2$ USAMO'dan, $1989$: $20$ yerel bir tenis kulübünün üyeleri tam olarak $14$her üyenin en az bir oyunda oynadığı kendi aralarında iki kişilik oyunlar. Bu program dahilinde altı oyun olması gerektiğini kanıtlayın.$12$ farklı oyuncular.

Çözüm girişimim: Var olduğundan$20$ Her biri en az bir oyun oynamış oyuncular, tüm oyuncuları barındıracak şekilde organize edilmesi gereken en az maç sayısı olacaktır. $10$. Şimdi,$4$tarafından çalınabilir bırakılan daha maçları, en fazla $8$ bunların $20$oyuncular. Bu nedenle, en azından $12$ oyuncuların oranı en fazla $1$eşleşir ve bu nedenle altı oyundan oluşan bir set olmalıdır.$12$farklı oyuncular . Bu, inanıyorum ki, katı bir ispatın yol gösterici ilkesi olacaktır.

Aklımı bulandıran şu şüphelerim var:

  1. Muhakeme sesim, yani herhangi bir tuzaktan muaf mı?
  2. Doğruysa, yukarıdaki akıl yürütme matematiksel olarak titiz bir ispatla nasıl çerçevelenir?

Düzenleme: Ben'in yorumlarda işaret ettiği gibi, italik yazılan ifade gerekçesizdir. Görünüşe göre bu kanıtı çerçevelendirirken pek çok olasılığı gözden kaçırdım. Bu nedenle, daha makul kanıtlarla devam etmek için bazı ipuçları almak istiyorum.

Yanıtlar

2 cgss Aug 17 2020 at 12:31

Korkarım bir tuzak var. Tam olarak 1 oyun oynayanlar arasında 12 farklı oyuncuyla 6 oyun olduğunu kanıtlamaya çalışırsanız başarısız olursunuz. İşte bir örnek:

$$ 1-2\\ 3-4\\ 5-6\\ 7-8\\ 9-10\\ 11-12\\ 12-13 \\ 13-14\\ 14-15\\ 15-16\\ 16-17\\ 17-18\\ 18-19\\ 19-20$$

12 farklı oyuncuyla 6 oyun varken, tam olarak bir oyunu olan oyuncular arasında sadece 5 oyun bulunmaktadır.

İşte bir ipucu: oyuncuları iki gruba ayırın, tek oyun olanlar ve daha fazlası olanlar. Daha sonra oyuncuları bir oyunla daha fazla oyuncuyla ve son olarak daha fazla oyunla oyuncuları eşleştirdikten sonra bir oyunla eşleştirin.

EDIT : İkinci yaklaşım

Her insan bir tepe noktası olarak görülüyorsa ve her oyun bir kenar olarak görülüyorsa, soru en azından bir boyut eşleşmesi olduğunu kanıtlamayı ister. $6$. Aynı şekilde, maksimum eşleşmenin boyutunun$MM$ en azından boyutunda $6$. Eşleşen maksimum değerin köşeleri iki kümeye ayırdığına dikkat edin.$MM$, boyut $2\cdot |MM|$ve boyutu olmayan biri $20 - 2\cdot |MM|$bizim sorunumuz için. Tüm köşeler en azından derece olduğu için$1$, en azından olduğu sonucuna vardık $20 - 2\cdot |MM|$iki bölüm arasındaki kenarlar. Şimdi,

$$ E_{MM} + E_{\text{between}} \le |E| = 14 \implies \\ |MM| + 20 - 2\cdot |MM| \le 14 \implies \\ |MM| \ge 6$$