kombinatoryka Ratarcia: Podpowiedzcie coś Udowodnij, że jeśli A jest 10− elementowym podzbiorem zbioru {1, 2, 3, …, 50}, to istnieją dwa czteroelementowe zbiory A dające taka samą sumę elementów.

PW: Nieprecyzyjne sformułowanie. To mają być rozłączne czteroelementowe podzbiory zbioru A?

Panko: Śmiem wątpić ,że tak zalecany CHŁOPSKI ROZUM tu wystarczy

PW: Tak, jest to bardzo trudne zadanie, już było na tym forum i nikt go nie rozwiązał. Przyznaję, że musiałem się poddać po paru dniach, żeby nie zwariować. Ratarcia, ma to może coś wspólnego z zasadą pudełkową? Mieliście jakieś sugestie?

~r.: No to może tak: Taki podzbiór A może mieć sumy elementów od 55 ( {1,2,3,4,5,6,7,8,9,10}) do 455 ({41,42,43,44,45,46,47,48,49,50}). Z kolei 4−elementowe podzbiory danego podzbioru A mogą przyjmować 24 różne wartości sumy swoich elementów np. dla podzbioru A={1,2,3,4,5,6,7,8,9,10} skrajne wartości sum elementów wynoszą 10 dla pod−podzbioru {1,2,3,4} i 34 dla {7,8,9,10} czyli 34−10=24. Dla podzbioru A={41,42,43,44,45,46,47,48,49,50} będzie to odpowiednio 170 ({41,42,43,44}} i 194 ({47,48,49,50}) i 194−170=24. A teraz liczymy ile takich 4−elementowych pod−podzbiorów możemy utworzyć:

10 4		10!
	=		=...=30
		(10−4)!*4!

No to teraz jeżeli sumy elementów mogą przyjmować 24 wartości a może tych podzbiorów być 30 to muszą istnieć 2 takie pod−podzbiory które mają taką samą sumę elementów (w najbardziej niekorzystnej sytuacji − 24 pod−podzbiory mają różne wartości sumy swoich elementów i zostaje jeszcze 6 które muszą powtórzyć którąś z 24 wartości). Nie wiem czy to formalnie jest dobry dowód ale myślę że tak. Tym niemniej proszę o krytykę (konstruktywną, oczywiście )

Ratarcia: mamy to zadanie rozwiązać przy pomocy zasady szufladkowej Dirichleta.

PW: Mam jedną uwagę: 34−10 = 24 i 194−170 = 24, ale sum może w takim razie być 25. Żeby się nie wdawać w dyskusję, czy wszystkie wartości są osiągane, lepiej napisać "co najwyżej 25". Nie zmienia to na szczęście sensu dowodu. gratuluję. A byłem tak blisko parę miesięcy temu, jestem zły bo byłem na dobrym tropie, ale za bardzo komplikowałem.

PW: A, i jeszcze jedno w ramach "konstruktywnej krytyki":

	10 4
		= 210, a nie 30.

Rozwiązałeś jednak tylko szczególny przypadek − dlatego, że nie ma w treści zadania stwierdzenia "A składa się z kolejnych 10 liczb naturalnych". Gdyby A = {1,2,3,4,25,26,47,48,49,50}, to rozpiętość sum 4−elementowych podzbiorów jest inna: najmniejsza suma jest równa 10, a największa 194. Da się dowód poprawić? Spróbuj, Ratarciu.

Ratarcia: Dzięki za pomoc !