Zadanie 5
2023
Etap II
★★★★☆Kombinatoryka
Teoria liczb
800 liczb na tablicy
Powiązane zadania:
Zad. 3 (2021)
Treść zadania
Na tablicy znajduje się osiemset dodatnich liczb całkowitych mniejszych od 21. Czterysta z tych liczb zapisano niebieską kredą, a czterysta — żółtą. Wykaż, że można zmazać pewne liczby z tablicy (co najmniej jedną, ale nie wszystkie) w taki sposób, aby suma pozostałych na tablicy niebieskich liczb była równa sumie pozostałych na tablicy żółtych liczb.
*Uwaga.* Liczby na tablicy mogą się powtarzać.
*Uwaga.* Liczby na tablicy mogą się powtarzać.
Umiejętności (6)
Wymagane umiejętności:
Zasada szufladkowa
Techniki zliczania
Ciągi liczbowe
Zdobywane umiejętności:
Zasada szufladkowa
Techniki zliczania
Podzielność
Wskazówki (0/4)
Wskazówka 1
Zadanie polega na znalezieniu podzbioru liczb niebieskich i podzbioru liczb żółtych o równych sumach. Pamiętaj, że musisz zmazać co najmniej jedną liczbę, ale nie wszystkie (czyli pozostałe na tablicy liczby muszą tworzyć zbiór niepusty i różny od całego zbioru).
Wskazówka 2
Liczba wszystkich możliwych podzbiorów jest ogromna, ale zakres możliwych sum jest stosunkowo mały. Zamiast rozważać losowe podzbiory, skup się na sumach kolejnych liczb ustawionych w ciągi.
Wskazówka 3
Ustaw liczby niebieskie w ciąg , a żółte w ciąg . Zdefiniuj sumy początkowe oraz dla . Zastanów się nad różnicami .
Wskazówka 4
Porównaj liczbę wszystkich par z liczbą możliwych wartości różnicy . Z Zasady Szufladkowej Dirichleta wynika, że pewne dwie pary dają ten sam wynik. Pokaż, jak z tej równości otrzymać szukane podzbiory.