Kolorowe kropki

Delta, maj 2015

o artykule ...

Publikacja w Delcie: maj 2015
Publikacja elektroniczna: 30-04-2015
Wersja do druku [application/pdf]: (51 KB)

W wielu zadaniach występują różnokolorowe punkty płaszczyzny, a w ich rozwiązaniach przydatne bywają rozmaite rozumowania kombinatoryczne.

Narzędzia
Obiekty: Strategie
Słowa kluczowe
Kategoria: Kombinatoryka

o zadaniu...

Zadanie pochodzi z artykułu Kolorowe kropki
Publikacja w Delcie: maj 2015
Publikacja elektroniczna: 30-04-2015
Artykuł źródłowy w wersji do druku [application/pdf]: (51 KB)

Maja i Gucio grają w grę. Malują na przemian punkty płaszczyzny wedle następujących reguł. Maja rozpoczyna; w swoim ruchu maluje dowolnie wybrany bezbarwny punkt na kolorowo. Gdy nadchodzi kolej Gucia, wybiera on 2015 bezbarwnych punktów i maluje je na czarno. Maja wygrywa, jeśli na płaszczyźnie pojawią się trzy kolorowe punkty tworzące trójkąt równoboczny. Czy Gucio może jej to uniemożliwić?

Rozwiązanie

Nie, Maja może zastosować następującą strategię, która gwarantuje jej zwycięstwo. W pierwszych $| n$ swoich ruchach Maja maluje na kolorowo $|n$ punktów z jednej prostej. Każdą parę takich kolorowych punktów można na dwa sposoby uzupełnić do trójkąta równobocznego, par punktów spośród $n$ jest $|1n(n −1), 2$ więc łącznie po $n$ ruchach na płaszczyźnie jest $| n(n −1)$ takich punktów, że pomalowanie dowolnego z nich na kolorowo da Mai zwycięstwo.

Dla $| n > 2016$ mamy $| n(n − 1) > 2015n,$ zatem Gucio nie może w swoich początkowych $n$ ruchach wszystkich opisanych powyżej punktów pomalować na czarno i Maja może wygrać w ruchu numer $n + 1.$

Narzędzia
Obiekty
Słowa kluczowe
Kategoria: Kombinatoryka

Kolorowe kropki»Zadanie 2

o zadaniu...

Zadanie pochodzi z artykułu Kolorowe kropki
Publikacja w Delcie: maj 2015
Publikacja elektroniczna: 30-04-2015
Artykuł źródłowy w wersji do druku [application/pdf]: (51 KB)

Każdy punkt płaszczyzny pomalowano jednym z dwóch kolorów. Wykaż, że istnieje na tej płaszczyźnie prostokąt o wierzchołkach jednego koloru.

Rozwiązanie

Narysujmy 3 poziome proste, 9 pionowych i rozważmy 27 punktów ich przecięć. Każdy punkt pomalowano jednym z dwóch kolorów, łącznie jest więc $23 = 8$ możliwych układów kolorów trójki wyróżnionych punktów z pojedynczej pionowej prostej. Ponieważ mamy 9 pionowych prostych, na pewnych dwóch z nich (nazwijmy je $| k$ i $| l$ ) jest ten sam układ kolorów takiej trójki.

Wśród trzech wyróżnionych punktów na prostej $| k,$ pomalowanych dwoma kolorami, pewne dwa punkty mają ten sam kolor. Niech to będą dwa wierzchołki szukanego prostokąta, pozostałe dwa to odpowiadające im punkty tego samego koloru z prostej $l$ (leżą one na tych samych poziomych prostych).

Narzędzia
Obiekty
Słowa kluczowe
Kategoria: Kombinatoryka

Kolorowe kropki»Zadanie 3

o zadaniu...

Zadanie pochodzi z artykułu Kolorowe kropki
Publikacja w Delcie: maj 2015
Publikacja elektroniczna: 30-04-2015
Artykuł źródłowy w wersji do druku [application/pdf]: (51 KB)

Każdy punkt płaszczyzny pomalowano jednym z $n$ kolorów $|(n > 2).$ Wykaż, że istnieje na tej płaszczyźnie prostokąt o wierzchołkach jednego koloru.

Rozwiązanie

Wystarczy uogólnić rozwiązanie poprzedniego zadania i rozważyć $| n+ 1$ prostych poziomych oraz $|n+1 2 + 1$ prostych pionowych.

Narzędzia
Obiekty
Słowa kluczowe
Kategoria: Kombinatoryka

Kolorowe kropki»Zadanie 4

o zadaniu...

Zadanie pochodzi z artykułu Kolorowe kropki
Publikacja w Delcie: maj 2015
Publikacja elektroniczna: 30-04-2015
Artykuł źródłowy w wersji do druku [application/pdf]: (51 KB)
Zadanie pochodzi z obozu naukowego Olimpiady Matematycznej z 2011 roku.

Każde pole szachownicy $12 × 12$ pomalowano jednym z trzech kolorów. Wykaż, że istnieją cztery pola o tym samym kolorze, których środki są wierzchołkami prostokąta.

Rozwiązanie

Istnieje kolor, którym pomalowano przynajmniej $|1 3⋅12⋅12 = 48$ pól. Rozważmy 48 pól tego właśnie koloru i niech $wi$ oznacza liczbę tych pól występujących w $i$ -tym wierszu; oczywiście $12 Q wi = 48. i 1$ W każdym wierszu dwa spośród rozważanych pól można wybrać na $1 |2wi(wi− 1)$ sposobów. Wobec tego

12 2 12 1 1 12 12 12⎛ P wi ⎞ 48 48 2 Q -wi(wi− 1) = --(Q w2i −Q wi) ⩾ --⎜⎜ i- 1--⎟⎟ − ---= 6(---) − 24 = 72, i 1 2 2 i 1 i 1 2 ⎜ 12 ⎟ 2 12 ⎝ ⎠

przy czym nierówność wynika z nierówności średnich (na marginesie). Tymczasem dwie z 12 kolumn można wybrać na $|1⋅12⋅11 = 66 2$ sposobów - mniej niż 72. Oznacza to, że w pewnych dwóch wierszach można wybrać po dwa pola tego samego koloru i w tych samych kolumnach; ich środki tworzą szukany prostokąt.

Uwaga
Dla dowolnych liczb $w1,w2,...,wn$ zachodzi nierówność między średnią kwadratową a arytmetyczną:

-n---- n P w2i P wi i--1-- ⩾ i- 1-. n n

Obiekty: Bryły; Wielościany; Całki; Chaos; Fraktale; Ciągi liczbowe; Figury; Okręgi; Wielokąty; Funkcje; Grafy; Grupy; Gry; Konstrukcje; Krzywe; Liczby; Liczby naturalne; Liczby pierwsze; Liczby rzeczywiste; Liczby wymierne; Liczby zespolone; Losowość; Miary; Modele; Nierówności; Pochodne; Podzielność; Powierzchnie; Przekształcenia; Przestrzenie; Rachunki; Równania; Rozmaitości; Strategie; Szeregi liczbowe; Sztuczna inteligencja; Szyfrowanie; Węzły; Wielokąty; Wielomiany; Zbiory

Narzędzia: Indukcja; Jednokładności

Delta mi!

Deltoid

Kolorowe kropki