Orzech senacki
W lutowym numerze „Wiedzy i Życia” zamieściłem zadanie poniekąd „polityczne”, które spowodowało trochę zamieszania – ale z powodów niepolitycznych. Można je bowiem nazwać z przymrużeniem oka problemem NP, czyli trudnym do rozwiązania, ale takim, poprawność rozwiązania którego dość łatwo sprawdzić, gdy się to rozwiązanie zna. Skojarzenie z problemem NP nasuwa się też dlatego, że zadanie dotyczy zbioru liczb.
Ponieważ w „WiŻ” z braku miejsca podawane jest tylko końcowe rozwiązanie, postanowiłem zadanie powtórzyć tutaj, licząc na to, że wśród moich gości znajdą się osoby, które spróbują w miarę zwięźle opisać sposób rozwiązywania. Oto ów orzech.
Senat Puzelandu składa się z przedstawicieli pięciu partii. Jeżeli senat obraduje w komplecie wówczas:
a) liczba senatorów z każdej partii jest inna;
b) łączna liczba senatorów z żadnych dwu partii – nawet z dwu najliczniej reprezentowanych – nie stanowi nie tylko większości, ale nawet połowy składu senatu;
Jeśli senat nie obraduje w komplecie, wówczas nigdy – niezależnie od tego, ilu senatorów i z jakich partii jest nieobecnych – stwierdzenia (a) i (b) nie są równocześnie prawdziwe.
Z ilu senatorów składa się senat Puzelandu?
Komentarze
Czy może być 5+6+7+8+9?
Może i musi
mp
Doznałam przed chwilą mglistego uczucia déjà vu… Czy w Lidze Intelektu, lat temu bodajże 16, nie było jakiegoś zadania tego typu o politykach? I czy można gdzieś dostać komplet tamtych zadań? Chętnie bym je sobie przypomniała. Pierwsze było z basenem, ostatnie wymagało skomplikowanej konstrukcji złożonej z rombów. Wszystkie były świetne. Czy zostały gdzieś opublikowane?
Pani Olu, gratuluję pamięci. W LI przed 18 laty było podobne zadanie. Zadania LI były zamieszczane tylko wtedy w „Polityce”. To ostatnie z rombami chyba też przypomnę w WiŻ lub w Łamiblogu, bo faktycznie jest bardzo oryginalną zagwozdką.
mp
Porządkujemy liczebności partii:
x1 < x2 < x3 < x4 = (S-1) / 2
gdyby nierówność była silna
x4 + x5 > (S-1) / 2 to po dodaniu do prawej strony 1/2 mogła by się co najwyżej osłabić bo x4 + x5 liczbą całkowitą a to przeczy warunkom zadania wobec czego mamy równość:
x4+x5 = (S-1)/2
odejmując od najliczniejszej partii 1 suma dwóch najliczniejszych to
x4 + x5 – 1 = (S-1)/2 – 1 < (S-1)/2 wobec czego musimy mieć dwie równoliczne
stąd x4 = x5 – 1
odejmując od najliczniejszej partii 2 suma dwóch najliczniejszych to
x4 + x5 -2 = (S-1)/2 – 2 < (S-2)/2 wobec czego musimy mieć dwie równoliczne
stąd
x3 = x5 -2
odejmując od najliczniejszej partii 3 suma dwóch najliczniejszych to
x4 + x3 = x4 + x5 -2 = (S-1)/2 – 2 < (S-3)/2 wobec czego musimy mieć dwie równoliczne
stąd
x2 = x5 -3
odejmując od najliczniejszej partii 4 suma dwóch najliczniejszych to
x4 + x3 = x4 + x5 -2 = (S-1)/2 – 2 < (S-4)/2 wobec czego musimy mieć dwie równoliczne
stąd
x1 = x5 -4
Stąd już łatwo dostajemy, że
S = x1 + x2 + x3 + x4 + x5 = 5 * x5 – 10
a ponieważ x4 = x5 – 1 oraz x4+x5 = (S-1)/2 to x5 = (S + 1) /4
i stąd S = 35
Jeżeli wynik 35 jest poprawny to moja metoda polegała na rozwiązaniu w głowie takiego zadania:
Proszę znaleźć najmniejszą liczbę naturalną, która jest sumą pięciu różnych liczb naturalnych,
takich, że każda suma dowolnych dwóch z tych pięciu liczb jest mniejsza niż suma pozostałych trzech.
Aby liczby senatorów z poszczególnych partii nie były równe, muszą się różnić co najmniej o 1, np.: n, n+1, n+2, n+3, n+4. Suma trzech pierwszych ma być większa od dwóch ostatnich : n+n+1 +n+2 > n+3 +n+4 , stąd 3n+3>2n+7, czyli n >4.
Partie mogą mieć następujące liczby senatorów 5, 6, 7, 8, 9. Gdyby nie wszyscy byli na obradach, nie będzie spełniony warunek (a) lub (b). Liczba wszystkich senatorów wynosi 35.
Przy większej liczbie senatorów np. 5, 8, 9, 10, 11 ( spełnione warunki (a) i( b) ), może się zdarzyć, ze obecnych będzie 5, 6, 7, 8, 9 senatorów
Jest to tylko próba rozwiązania tego zadania, być może mająca mankamenty.
Na początku zakładamy, że liczby (oczywiście naturalne) różnią się od siebie o 1. Zapewnia nam to „fałszywość”
warunku a) w przypadku gdy skład dowolnej partii jest niekompletny w czasie obrad Senatu.
Warunek b) daje nam 10 nierówności z których badamy tylko tę dającą nam największą, minimalną wartość dla zbioru ilości senatorów z wszystkich partii.
Mamy więc:
p4 + p5 < (p1 + p2 + p3 + p4 + p5)/2 (1)
gdzie p4 to ilość senatorów z 4 partii, czyli drugiej co do liczebności osób, p5 ma najwięcej senatorów
p4 = p1 + 3, p5 = p1 + 4
Po podstawieniu powyższych zależności do nierówności (1) mamy:
p1+3+p1+4 < (p1+p1+1+p1+2+p1+3+p1+4)/2 |*2 * to u mnie mnożenie
4*p1+14 4 stąd zbiór ilości senatorów byłby taki: {5, 6, 7, 8, 9}
Rozwiązanie to wydaje się prawidłowe, ale niejednoznaczne, bo zbiór {6, 7, 8, 9, 10} oraz zbiory zaczynające się od
coraz wyższych liczb wydają też być dobrymi rozwiązaniami.
Proszę o weryfikację w/w rozwiązania przez osoby bardziej biegłe w tym temacie ode mnie 🙂
Partie A, B, C, D i E mają odpowiednio 5,6,7,8 i 9 członków, łącznie 35, największe D i E dwie mają 17 członków. Mam nadzieję, że to poprawna odpowiedź, bo nie sprawdzałem tego programistycznie ani w żaden inny systematyczny sposób:)
Sposób rozwiązania przyjąłem następujący: zacząłem od minimum, czyli partii mających 1,2,3,4 i 5 posłów (aby spełnić warunek a). Następnie zwiększałem liczbę posłów w każdej partii o 1, aż doszedłem do takiej liczności, w której suma posłów dwóch największych partii (17) jest mniejsza od połowy sumy wszystkich posłów (35/2=17,5).
– Wybieranie w pierwszej kolejności liczności partii tak, aby różnica między nimi wynosiła 1 wynika z potrzeby zapewnienia, że jeśli wycofamy tylko jednego posła z dowolnej partii poza partią A, to zrównamy liczebność 2 partii, zrywając prawdziwość twierdzenia a)
– Zatrzymanie się w momencie, gdy suma liczby posłów 2 najliczniejszych partii jest mniejsza od połowy posłów o zaledwie 0,5 jest konieczne, bo gdyby różnica wynosiła >=1, to wtedy zmniejszenie liczebności partii A nie spowodowałoby zerwania prawdziwości stwierdzenia b)
.
Pani Olu, niejako tradycyjnie Pani wpis pokazuje się jako śliczna kropka :).
mp
35 senatorów.
Poszukujemy zbioru 5 liczb naturalnych a..e takich, że:
(1) a < b < c < d d + e
(3) suma a + b + c + d + e jest minimalna.
Ze względu na (1) i (3) założyłem roboczo, że b = a + 1, c = b + 1 itd.
Szybki brute-force w pamięci / na kartce doprowadził do spełniającego (2) rezultatu (5, 6, 7, 8, 9).
W opisie rozwiązania ucięło warunki wstępne. Pewnie zadziałał skrypt eliminujący próby wstawiania znaczników HTML.
Powinno być:
(1) a < b < c < d < e
(2) (d + e) < (a + b + c)
Wiadomo, że aby obydwa pierwsze warunki były spełnione, muszą składy partii wyglądać tak:
x1<x2<x3<x4<x5 i x4+x5<x1+x2+x3.
Żeby trzeci warunek był spełniony, potrzeba by x4+x5 było możliwie najmniejsze, zaś suma pozostałych (x1+x2+x3) największa, zatem skład poszczególnych partii musi wyglądać tak: {x,x+1,x+2,x+3,x+4}.
Stąd x+3+x+4 jest mniejsze od x+x+1+x+2, czyli x>4.
Najmniejszą piątką będzie więc {5,6,7,8,9}, czyli skład senatu to 35 senatorów. Większe x pozwala tak pomanewrować nieobecnościami, by a) i b) było spełnione.
Najmniejszy senat spełniający warunki a) i b) to [5,6,7,8,9].
I jest on jednocześnie rozwiązaniem zadania gdyż każdy większy można sprowadzić do niego przez odjęcie odpowiedniej ilości posłów. A tego właśnie zabrania zadanie. Wszystkie inne układy spełniające warunki a) i b) mają odpowiednie wartości większe od tego minimalnego układu. Z tego faktu wynika, że zmniejszając odpowiednio poszczególne wartości uzyskamy ten minimalny układ spełniający jednocześnie warunki a) i b) co jest zakazane. Senat składa się więc z 35 osób.
Lepszego układu minimalnego nie ma bo z nierówności: (x+3+x+4) 4 czyli x=5.
Jednocześnie z faktu, że elementy układu minimalnego są kolejnymi liczbami wynika to, że każdy inny dobry układ leży powyżej minimalnego porównując kolejne wartości.
35
Rozwiązaniem jest zbiór 5, 6, 7, 8, 9, pierwsza sekwencja pięciu kolejnych liczb, w której suma trzech mniejszych liczb S3 jest większa niż dwóch większych S2. Można pokazać, że jest to jedyne rozwiązanie. Najmniejsza liczba nie może być mniejsza od 5, bo liczba największa musi być większa od trzeciej co najmniej o 2, tak samo druga od czwartej, a 2+2=4 , więc nawet liczba 4 jako najmniejsza tylko kompensuje, ale nie daje przewagi. Każdą piątkę, w której najmniejszą liczbą jest 5, można, odpowiednio sterując nieobecnościami senatorów, sprowadzić do kanonicznego zestawu 5, 6, 7, 8, 9, i tak samo, gdy najmniejszą liczbą jest 6, 7, etc, więc jeśli w wyjściowym zestawie S3 > S2, to można skierować na chorobowe z każdego klubu tylu senatorów, by mieć inny zestaw spełniający warunki, czyli ten kanoniczny. Inny sposób, jeśli S3-S2 > 1, po prostu nie przychodzi senator z najmniejszego klubu, i dalej są różne liczby, i oczywiście S3>S2. Przykładowo, dla 6, 7, 8, 9, 10, dostajemy 5, 7, 8, 9, 10.
Dzeiń dobry,
nie wiem czy to wyczerpuje sposób rozwiązywania ale:
1. Założyłem że znajdę najmniejszy zbiór spełniający warunek a) i b) przy pełnej obecności.
– 1,2,3,4,5 nie działa – bo 4+5 > 1+2+3
– 5,6,7,8,9 działa – bo nawet 9+8 < 5+6+7
2. Sprawdziłem ten zbiór – i wydaje się być rozwiązaniem:
– jeśli brakuje jednej osoby – to tylko w przypadku partii z 5 senatorami jest nie spełniony warunek a) 9+8 = 4+6+7
– jeśli brakuje więcej osób – to
– albo zostało ich 4 lub mniej w którejś partii – wtedy mamy niespełniony warunek a)
albo liczba pozostałych się powtarza – wtedy mamy niespełniony warunek b)
W sumie niezbyt trudny orzech (o ile nie przeoczyłem czegoś w rozwiązaniu) – ale samo rozwiązanie znalezione trochę "przypadkiem" zaczynając z dobrego końca.
Pozdrawiam,
/Tomasz
Mój wpis z 19 czerwca g. 15.47 został idiotycznie poprawiony przez ten nieudaczny i irytujący edytor. Nie poprawiam bo wiadomo o co chodzi.
Psoty edytora są mi znane. Pomija lub zmienia niektóre znaki, m. in. matematyczne. Niestety, chyba nic się z tym nie da zrobić. Jedynym sposobem wydaje się zastępowanie znaków słowami.
mp
Test, co wycina, czego nie i jak reaguje:
1. Tekst pomiędzy znakiem mniejszości a znakiem większości: wycięło
2. Znaki mniejszości i większości zapisane encjami html: < >