W pewnym mieście postanowiono organizować co trzy lata turniej koszykówki, a co pięć lat - turniej siatkówki. Wiadomo, że turniej siatkówki odbył się w 2007 roku, a turniej koszykówki w 2008 - roku. W jakich kolejnych latach przed końcem 2050 roku oba turnieje odbędą się w tym samym roku?
Zacząłem robić to zadanie od wypisania pierwszej daty pokrycia się turniejów:
turnieje siatkówki 2007 2012 2017 2022
turnieje koszykówki 2008 2011 2014 2017 2020
NWD(3,5) wyszło mi 15.
Potem już tylko obliczyłem dla kolejnych lat począwszy od roku 2017 i wyszło mi ostatecznie w rozwiązaniu zadania 2017, 2032 i 2047.
.
Moje pytanie brzmi czy da się początkową datę pokrycia turniejów wyliczyć inaczej niż ręcznie poprzez wypisywanie wszystkich lat po kolei?
Czy da się to zadanie zrobić prościej?
- Premislav
- Użytkownik
- Posty: 15687
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5220 razy
Re: Czy da się to zadanie zrobić prościej?
Tak, można rozważyć równanie w liczbach całkowitych \(\displaystyle{ 2007+5k=2008+3l}\), a równoważnie \(\displaystyle{ 5k-3l=1}\). I tutaj albo pojechać rozszerzonym algorytmem Euklidesa, albo po prostu sprytny dzieciak widzi, że wystarczy wziąć \(\displaystyle{ k=2, \ l=3}\) i działa, a potem zaobserwować, że jeśli \(\displaystyle{ k,l}\) są rozwiązaniami, to \(\displaystyle{ k+3t, l+5t, \ t\in \ZZ}\) także. No i z tego równania bierzesz prawą, czy tam lewą stronę, co tam Ci wygodnie, i wstawiasz kolejne \(\displaystyle{ t}\) dodatnie dopóki nie przekroczysz \(\displaystyle{ 2050}\).
-
- Użytkownik
- Posty: 926
- Rejestracja: 24 paź 2011, o 01:24
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 75 razy
- Pomógł: 274 razy
Re: Czy da się to zadanie zrobić prościej?
Kłania się chińskie twierdzenie o resztach. Wystarczy policzyć różnicę lat pomiędzy turniejami. Różnica wynosi jeden rok, czyli oba zawody były organizowane w 2002 a kolejne w 2017, 2032 i 2047.
Dobrze to widać gdy zrobimy rysunek prostokąta: 2 rzędy po 15 kwadracików. W pierwszym rzędzie zaznaczamy po 3 kwadraty a w drugim co 5.
Dobrze to widać gdy zrobimy rysunek prostokąta: 2 rzędy po 15 kwadracików. W pierwszym rzędzie zaznaczamy po 3 kwadraty a w drugim co 5.