Treść zadania

Najlepsze rozwiązanie

• 

  1 0

  antekL1 23.3.2014 (13:56)

  Weźmy dwa ciągi, np. ciągi rosnące:
  
  pierwszy ciąg: a = (1, 2, 3)
  drugi ciąg: b = (4, 5, 6)
  
  Bierzemy dowolny wyraz z pierwszego ciągu i dowolny wyraz z drugiego
  i mnożymy je, dostajemy iloczyn aj * bk
  Te wyrazy wykreślamy (drugi raz już nie można ich użyć)
  i ponownie bierzemy po jednym wyrazie, mnożymy, wykreślamy, itd.
  
  Następnie wszystkie te iloczyny sumujemy. Przykład takiej sumy:
  1 * 5 + 2 * 4 + 3 * 6 = 31 albo
  1 * 6 + 2 * 5 + 3 * 4 = 28
  
  Twierdzenie o ciągach jednomonotonicznych mówi, że największą sumę
  dostaniemy mnożąc pierwszy wyraz pierwszego ciągu przez pierwszy wyraz drugiego,
  drugi wyraz pierwszego ciągu przez drugi wyraz drugiego itd.
  Sprawdźmy:
  1 * 4 + 2 * 5 + 3 * 6 = 32 <---------- faktycznie, największa z osiągniętych sum.
  
  Dodatkowo: Najmniejszą sumę osiągniemy mnożąc pierwszy wyraz
  pierwszego ciągu przez ostatni wyraz drugiego, następnie
  drugi wyraz pierwszego ciągu przez przedostatni wyraz drugiego itd.
  Faktycznie - suma 1 * 6 + 2 * 5 + 3 * 4 = 28, mniej się nie dostanie...
  ---------------------------------------
  
  To jest bardzo sensowne twierdzenie!
  Dam Ci przykład, myślałem o zestawianiu par brydżystów, ale to nie to samo.
  Będzie "aspołecznie".
  Powiedzmy, że klasa jest oceniana w taki sposób, że sadza się uczniów parami,
  wszyscy rozwiązują ten sam test (BEZ porozumiewania się w tych parach),
  a następnie mnoży się wyniki testu w każdej parze i sumuje iloczyny
  (tak, jak na początku sumowaliśmy iloczyny dwóch ciągów).
  
  Aby osiągnąć najlepszy wynik MUSZĘ posadzić dwóch najgorszych uczniów razem,
  i tak dalej aż do posadzenia dwóch najlepszych razem.
  W przeciwnym wypadku (np. sadzając najlepszego z najgorszym)
  tracę możliwości tego dobrego ucznia, którego punkty dałyby lepszy iloczyn
  gdyby siedział z kimś dobrym. Oczywiście najwięcej zyskam sadzając go
  z drugim z kolei najlepszym.
  Widzisz logikę? Para najlepszych zyska najwięcej, potem zestawiam kolejną
  "dobrą" parę, itd.
  Każdy inny układ zmniejszy sumę iloczynów.
  Najmniejszą sumę uzyska się łącząc najlepszego z najgorszym itd.
  ---------------------------------------
  
  Twoje zadanie: Nie mam w tej chwili koncepcji,
  napiszę na priv, jak coś wymyślę.
  Twierdzenie jest prawdziwe, ale muszę wymyślić, jak użyć jednomonotoniczności.

  Dodawanie komentarzy zablokowane - Zgłoś nadużycie