Existenz einer Lösung, obere Schranke

Ich habe einmal ein Folge A1 = [a1,..., an] gefunden, für die alle Teilmengen unterschiedliche Gewichte haben.
Wählt man für a[n] = (a[1]+..+a[n-1])*n sollte sich zeigen lassen, dass sich die gewichtete aller Teilmengen streng monoton steigend sortieren lassen. Damit existieren für diese Folge keine 2 Teilmengen mit dem gleichen Gewicht (also auch kein disjunkten oder verschieden).
Damit ist zumindest einmal gezeigt dass es für beide Probleme (keine 2 disjunkten Mengen mit gleichen gewicht, keine 2 verschiedenen Mengen mit gleichen gewicht) für jedes n eine Lsg gibt.
Über Minimalität braucht man bei A1 natürlich nicht weiter nachdenken.

Bsp.:
1,2,9,48, 300

Beweis will ich heute nicht mehr führen, grob gehts dabei darum dass a[n] nach konstruktion grösser ist als jede gewichtete Teilmenge ohne a[n]. Das sollte für eine Induktion reichen.

Paul Glößl schrieb:[...] Damit ist zumindest einmal gezeigt dass es für beide Probleme [...] für jedes n eine Lsg gibt.

Da bin ich aber froh, sonst wäre das für unsere "Brute Force" Implementierung ziemlich blöd wenn bei einem n angekommen für das es gar keine Lösung gibt...

Paul Glößl schrieb:Beweis will ich heute nicht mehr führen [...]

Den verstehen wir Informatiker sowieso nicht.

a_n:= ((n-1) * SUM(i:=1..n-1) a_i) + 1
Lösungen:
{1}
{1,2}
{1,2,7}
{1,2,7,31}
{1,2,7,31,165}

zB für n:=5
a₅:= 165 := 4 * (1+2+7+31) + 1

a_n sind obere Schranken.

Ich hab die beiden Threads zur Lösbarkeit und Oberen Schranken zwecks besserer Struktur zusammengefügt (erste Resultate -> Existenz einer Lösung, obere Schranken).
Ausserdem bin ich einfach mal so frech und geb der neuen oberen Schranke von Othmar den Namen A2.

Hab die Berechnung der oberen Schranke in den Code eingebaut.

Code:

Upper bound for n = 1 is 1
Upper bound for n = 2 is 2
Upper bound for n = 3 is 7
Upper bound for n = 4 is 31
Upper bound for n = 5 is 165
Upper bound for n = 6 is 1031
Upper bound for n = 7 is 7423
Upper bound for n = 8 is 60621
Upper bound for n = 9 is 554249
Upper bound for n = 10 is 5611771
Upper bound for n = 11 is 62353011
Upper bound for n = 12 is 754471433

Darüber hinaus wird Integer schon zu klein. Stellt sich nur noch die Frage wie da die Komplexität ausschaut!?

Wobei sich bei einer bekannten optimalen Lösungsmenge für n-1 aus dessen Elementen natürlich ein besseres Set für n als obere Schranke ergibt. (zB Lösung für n=7 ist {1 13 19 22 24 25 26} -> mögliche Lösung für n=8 ist {1 13 19 22 24 25 26 911}.

hab das ganze für A2 mal in Sage ein bischen weigergezogen

Code:


1 1
2 2
3 7
4 31
5 165
6 1031
7 7423
8 60621
9 554249
10 5611771
11 62353011
12 754471433
13 9876716941
14 139097096919
15 2097156230471
16 33704296561141
17 575219994643473
18 10389911153247731
19 198019483156015579
20 3971390745517868001
21 83608226221428800021
22 1843561388182505040463
23 42489700565730116170671
24 1021684163603237793376589
25 25586525140672389955865881
26 666315758871676821767340651
27 18017178119890141260588891203
28 505173955746150499191126987961
29 14668754863147481161697909576349
30 440586529996679702035283641203911
31 13673375068862473511439837140811031
32 438003781372561234816456116410646693
33 14468253939532345304904873006596845601
34 492372766879710126157543959505748901859
35 17247967227664997146609721732989264562091
36 621434113349694750135203209497407326134161
37 23010817454320125605006381700246854133424933
38 875050252637895887590381570767720647462742591
39 34150609859705990856230026707799692295572981119
40 1366923094647705581376996595330613999514908007421
41 56078896190675100774440885962281599980098790048041
42 2356715612413121110045878232564884239163651651768923
43 101396252202359649710266565908401360924016622285862931
44 4463849293384833150340068580110336103535874633489537129
45 200977028651000859978101692351014202242917518382226601901
46 9249510977688107760355816522972812716861544880091110655671
47 434932560639734133798064616946899371308422865917173114386663
48 20886217966373319599128798670341319809137089365457291514785621
49 1023869067968598475667930896520561720005358593574757439363107889
50 51214784004012602918306293386372264369434707982770679414808792531
....
....
....
100 158757132715021313286235794262453384754887294198897355556540399871309337376004965600899031234505576191943572713385771938004745006043501874942666845419932352081
....
....
....
150 97517558058278880444624385036536392955536608073295193138989090640068255217253001156655174737250517740704038973028299943445211765899875098938395652154633922004104496482135108882906335847627534698338157125371792863451654538147070008978494706160191933253754153351631
....
....
....
200 1348360799952362488596086754213658997662252937232437318474188450335790048965650537460840873937205979238584089582320723252937487147009230303143139741111321899663415311146302122753010581780952024034943768227976757301902515307719982285984881661445028013789681590127922974904359816883161250203885143164040701559264822572306686093554543186002274794224928780964321831536009240041181
....
....
....
500 2092345858461552076021901380405200465123814002394013338421796506581543021675460974581470298933539367332712930691995319300127647581220565109522047566359938742536304789232559625561814744706670196718202371468041198394044297826146285477361746470885411506781450795769325988155212958447049216524388630148935203791462016746874155158537974633035635982127592782286939123569396148993515151520604764095552614516793440689280965471649732836313173530414545918222212203367784958821306617731896715324942968810962165146669300491797407386235208598414825110489397115201095096652353307285838325599568060201358623553044662867397355903673509012159232139213592539120657927622504881353958078223987060003947524645255869255232589575230979598980053423102051419303458821025898621339770685549614940139057090444019059095488545508842113308915265279781780824024800684136317476859500721868991392295977438162921584316069382411219807208334967646204472704722126947097807587582470850209306413319170676959270402925236130782652971859647248980561066902189952004981780732512132875105910889155851604617520741245548120670455718401151180195546871541886192250543502596427061668481
....
....
....
1000 690723302276900170575521612106496066844532996217698246758742879421270299968140195224462558676269442644543318569867549856967069811829988032479027011646251455105504041848668112043815454960019758914373816108635436660465153759899478715335750722621111753876207689485262637082874991129550700724893215226516879841955432132752239835034192907294562236207392159147997812418500553321817816267571197287772032087554967557234345193513349875356919966264348019596618098296191036486218534264041740204235956242277780076637722487443041654637990007745126008090591025295827468759141677798435840195056284179799986929499215547518427419688214138601013460349526366359566382959741067241025480130187473587248102029649545815688334322490150416485405165128519992614098195384998218176101194378228484519083700119275143485676543374870725413064808310579260322108166042027748774472796869556839899710199716844087305635430286394832606614767340732672079772468563866717751091480019428711252512257514571012735522933234413546632977450715467630611447119599625039801174412430435135744907882655192963907951287736382598447544302502955491806410230032117624235685547969356532907396559870969353675798862562526448141946421669976386900477416477192676010284177943101676382760363555962998184548186119735082591359069417472858202288565615167623932040394013468318558158388269691454348193606063104785752974649144675025230298444343585818720962249989302674515139349147024719377486866767941179622907029511367017628874246111527197959570192042139456454298665290982655052059672756329973423168633647446934988968865271449010672720024273210022202475491076209547559592477695887694139204852522594588987888979792758277017760718069026652796218226512677479636455405243879865247849818798041482630791430650981334193795803941263969928446809456232151550770467884435725144987556699615963223893623366619814320495424927175790750871317147073569319463612488008316656192368736337197132040729024535798295772956394974451471521538523391140864577349479817751277463916179501631325374967696795816661000479022711132531967088811146511729948851905933198498362371991602315522791407836628221322114914805238654653972335160561038401689833456002590080762586249097792192826298425974687304310829294079676914066541129596948843085105201201689858303439147200522135543311759518956190143843124500287012509628495292143605117225567658832125682689982014948111898781523020706375583149204295988201192390648669425751599774512087682166061281120295742219734859969725860439670835525533551967017759083717444784716045516304763292664665163817015088528341020913716729615483852913981


Neue Überlegung zur unteren Schranke: Da ja Abstände nicht mehrmals vorkommen dürfen (außer nebeneinander) ergibt sich daraus eine untere Schranke die für kleine n besser ist als unsere bisherige:

Code:

zB für n = 10:
Abstände:    1 1 2 2 3  3  4  4  5
Elemente: { 1 2 3 5 7 10 13 17 21 26 }
Untere Schranke: 26

n = 11: 31
n = 12: 37
n = 13: 43 (ab hier wird die bisherige besser).

bringt mir im rekursiven Code allerdings nix...