Treść zadania

Najlepsze rozwiązanie

• 

  1 0

  antekL1 6.4.2011 (14:01)

  Nie jest to wcale duża liczba, jest ona mniejsza niż 111.
  Rozumujemy tak: Losujemy pierwszą liczbę. Niech to będzie X.
  
  Zwracamy uwagę, na razie,
  aby różnica X i kolejnej wylosowanej liczby Y nie była podzielna przez 111.
  
  Możemy wybrać Y = X+1, Y= X+2, Y = X+3.... Y = X + 110 (czyli 110 różnych liczb)
  ale nie Y = X + 111, bo różnica dzieli się przez 111.
  
  Zauważ, że wybór na przykład X+2 jest tym samym, co wybór X + 2 + 111, czyli X + 113,
  tym samym co X + 2 + 222, X + 2 + 333 i tak dalej.
  Czyli wybierając X mogę wybrać jeszcze co najwyżej 110 innych liczb ze względu na różnice.
  Razem 111 liczb.
  
  Wybieram 1, 2, 3, 4, .... 110, 111.
  
  W zadaniu jest jeszcze warunek, "LUB suma nie dzieliła się przez 111". Wobec tego jak wybiorę
  liczbę 1, to nie mogę już wybrać 110, bo 1 + 110 = 111. Z tego samego powodu wybór 2 wyklucza
  wybór 109, wybór 3 - wyklucza 108 i tak dalej aż do 55 wyklucza 56.
  
  Pozostają więc liczby 1, 2, 3, .... 55 (razem 56 liczb) i to jest szukane najmniejsze "n".
  
  Rar jeszcze podkreślam, ze chodzi o ilość wybranych liczb, a nie o ich wartości.
  W miejsce np. "2" mogę wylosować 100 * 111 + 2 czyli 111002, a wpływ tej liczby będzie taki sam,
  jak wpływ liczby 2, tzn wykluczy np. liczbę 109, gdyż:
  111002 + 109 = 111111, co jest podzielne przez 111. Dlatego mogę się ograniczyć w powyższym
  "niby-dowodzie" do liczb od 1 do 111. Dokładny "matematyczny" zapis dowodu wymagałby bardziej
  skomplikowanego zapisu.
  
  W każdy razie odpowiedzią jest:
  Gdy losujemy przypadkowo więcej niż 56 liczb naturalnych to NA PEWNO jest wśród nich para,
  której suma lub różnica jest podzielna przez 111.
  
  Antek

  Dodawanie komentarzy zablokowane - Zgłoś nadużycie