---

Hej NG....!

Jeg har et problem som delvist er matematisk, og jeg kan bare ikke hitte ud
af det.....

Hvis jeg f.eks. har tallene fra 100 til 160, dette er ialt 60 "enheder"
eller hvad vi nu skal
kalde dem.
Hvis jeg nu ønsker at kombinere disse 60 enheder på en sådan måde, at alle
kan
"se" hinanden, men at jeg har et begrænset råderum. Jeg kan ikke ligge alle
60 i en
stor gruppe, jeg har nemlig 16 grupper til rådighed, og hver gruppe kan
indeholde
16 "enheder".
Kan det lade sig gøre at putte tallene fra 100 til 160 ind i disse 16
grupper med
hver 16 medlemmer, på en sådan måde at alle "enheder" mellem 100 og 160 er
kommet i berøring med hinanden....?
Håber jeg har formuleret mit problem præcist nok, eller skal i bare slå mig
over
fingrene...

P.f.h. tak for jeres hjælp..
søren....

---

Scripsit "Søren Jul Nielsen" <soren.jul.nielsen@mail.tele.dk>

> Kan det lade sig gøre at putte tallene fra 100 til 160 ind i disse 16
> grupper med hver 16 medlemmer, på en sådan måde at alle "enheder"
> mellem 100 og 160 er kommet i berøring med hinanden....?

Hm, er følgende rigtigt forstået: Du vil have 16 mængder med 16
elementer hver, så der for ethvert par af (forskellige) elementer i
(100,101,...,160) findes en af de 16 mængder der indeholder begge
parrets elementer.


Hver af de 16 mængder bidrager med 120 forskellige (uordnede)
par. Altså kan et sæt på 16 mængder højst kan dække 1920 par i alt.

Med en grundmængde på 61 forskellige elementer skal du dække 1830 par.
Det vil sige at vi ikke med et simpelt tælleargument kan afvise
opgaven som uladsiggørlig, men der er knageme heller ikke meget
rum for redundans.

Hmm...

--
Henning Makholm "What has it got in its pocketses?"

---

Henning Makholm skrev i meddelelsen ...
>Scripsit "Søren Jul Nielsen" <soren.jul.nielsen@mail.tele.dk>
>
>> Kan det lade sig gøre at putte tallene fra 100 til 160 ind i disse 16
>> grupper med hver 16 medlemmer, på en sådan måde at alle "enheder"
>> mellem 100 og 160 er kommet i berøring med hinanden....?
>
>Hm, er følgende rigtigt forstået: Du vil have 16 mængder med 16
>elementer hver, så der for ethvert par af (forskellige) elementer i
>(100,101,...,160) findes en af de 16 mængder der indeholder begge
>parrets elementer.

Ja - det skal være sådan at alle tal mellem 100 og 160 har lagt i samme
gruppe på et tidspunkt.

>
>Hver af de 16 mængder bidrager med 120 forskellige (uordnede)
>par. Altså kan et sæt på 16 mængder højst kan dække 1920 par i alt.
>
>Med en grundmængde på 61 forskellige elementer skal du dække 1830 par.
>Det vil sige at vi ikke med et simpelt tælleargument kan afvise
>opgaven som uladsiggørlig, men der er knageme heller ikke meget
>rum for redundans.
>
>Hmm...
>
>--
>Henning Makholm "What has it got in its
pocketses?"

---

Scripsit "Søren Jul Nielsen" <soren.jul.nielsen@mail.tele.dk>
> Henning Makholm skrev i meddelelsen ...

> >Hm, er følgende rigtigt forstået: Du vil have 16 mængder med 16
> >elementer hver, så der for ethvert par af (forskellige) elementer i
> >(100,101,...,160) findes en af de 16 mængder der indeholder begge
> >parrets elementer.

> Ja - det skal være sådan at alle tal mellem 100 og 160 har lagt i samme
> gruppe på et tidspunkt.

OK.

I mit forige indlæg udregnede jeg at der højst må gå 90 par til
spilde. Et bevis for at opgaven er umulig at løse kan derfor føres ved
at vise at der altid må være større spild end det.

Antag at en påstået løsning er givet, og udvælg en vilkårlig gruppe;
kald den A. Kald de andre grupper "standardgrupper". Vi ser nu på
ordnede par <x,X> med x i A, x i X, X standard. Sådan et par kalder
jeg et "hit" - det dokumenterer at x er blevet ramt af standardgruppen
B. Jeg vil indledningsvis antage at ethvert x i A har mindst fire
hits. Det giver at der i alt er 64 hits. De 15 standardgrupper skal
fordele de 64 hits mellem sig - det vil sige at nogen standardgrupper
må have ansvaret for flere hits, men hver gang én standardgruppe har n
hits, må vi også tælle n(n-1)/2 stk spild, fordi den så omfatter par
der allerede er ramt af A. Minimum af

sum_i af n_i(n_i-1)/2

når n_i'erne skal være hele og mindst have en given sum, opstår når
n_i'erne er så tæt på hinanden som muligt - i dette tilfælde ved at 4
n_i'er er 5 og 11 n_i'er er 4. Da bliver der i alt
4*5*4/2+11*4*3/2 = 106 spild, og det er for mange - modstrid!

Betragt nu tilfældet at der findes et eller flere x der har mindre end
4 hits. Dette x skal stadig være forbundet med alle de 45 elementer
udenfor A, og det skal der mindst 3 hits til. Men hvis der kun er 3
hits, må det betyde at de tre grupper (kald dem B, C og D) der rammer
x, er parvis disjunkte bortset fra x. Det vil igen sige at der ikke er
noget spildt par i hele løsningen der involverer både B, C og D. Og
det vil igen sige at der er mindst en af grupperne B, C og D der højst
deltager i 30 spild! (Idet 30 er en tredjedel af 90). Antag at det
gælder for B.

Begynd nu forfra på konstruktionen med B i stedet for A (A er nu en
standardgruppe og et hit er et par <y,Y> med y i B, y i Y, Y
standard). Vi får nu mindst 16*3=48 hits. Det vil sige at 15
standardgrupper skal dele 48 hits, og for at minimere spildet der
involverer B, skal disse hits fordeles på 3 standardgrupper med 4 hits
og 12 standardgrupper med 3 hits. Det giver i alt 3*4*3/2+12*3*2/2=54
spild der involverer B. Modstrid med at B var valgt til højst at
deltage i 30 spild.

Ergo kan den oprindelige opgave ikke løses.


Bemærk at hvis der kun er 60 elementer i grundmængden i stedet for som
ovenfor antaget 61, duer mit modbevis ikke, for så er der råd til 150
spild. Det vil dog næppe sige at der er en løsning. Man kan
sandsynligvis komme igennem med et modbevis efter nogenlunde samme
principper ved at holde nøje regnskab med grænser for størrelsen af to
gruppers fællesmængde.

--
Henning Makholm "We're trying to get it into the
parts per billion range, but no luck still."

---

Henning Makholm skrev i meddelelsen ...
>Scripsit "Søren Jul Nielsen" <soren.jul.nielsen@mail.tele.dk>
>
>> Kan det lade sig gøre at putte tallene fra 100 til 160 ind i disse 16
>> grupper med hver 16 medlemmer, på en sådan måde at alle "enheder"
>> mellem 100 og 160 er kommet i berøring med hinanden....?
>
>Hm, er følgende rigtigt forstået: Du vil have 16 mængder med 16
>elementer hver, så der for ethvert par af (forskellige) elementer i
>(100,101,...,160) findes en af de 16 mængder der indeholder begge
>parrets elementer.
>
>
>Hver af de 16 mængder bidrager med 120 forskellige (uordnede)
>par. Altså kan et sæt på 16 mængder højst kan dække 1920 par i alt.

Hej Henning, jeg forstår ikke hvor de 120 dukker op (er ikke helt stiv ud i
matematikkens forunderlig verden)...

>Med en grundmængde på 61 forskellige elementer skal du dække 1830 par.
>Det vil sige at vi ikke med et simpelt tælleargument kan afvise
>opgaven som uladsiggørlig, men der er knageme heller ikke meget
>rum for redundans.

Er grundmængden = de numre som skal være i gruppen (100-160) = 61 ialt.....?
>
>Hmm...
>
>--
>Henning Makholm "What has it got in its
pocketses?"

---

Scripsit "Søren Jul Nielsen" <soren.jul.nielsen@mail.tele.dk>
> Henning Makholm skrev i meddelelsen ...

> >Hver af de 16 mængder bidrager med 120 forskellige (uordnede)
> >par. Altså kan et sæt på 16 mængder højst kan dække 1920 par i alt.

> Hej Henning, jeg forstår ikke hvor de 120 dukker op

Det er antallet af uordnede par (af forskellige elementer) der kan
laves med 16 elementer. Udregnet som 1+2+3+4+...+15 = 16*15/2 = 120.

> Er grundmængden = de numre som skal være i gruppen (100-160) = 61 ialt.....?

Ja.

--
Henning Makholm "Jeg har tydeligt gjort opmærksom på, at man ved at
følge den vej kun bliver gennemsnitligt ca. 48 år gammel,
og at man sætter sin sociale situation ganske overstyr og, så
vidt jeg kan overskue, dør i dybeste ulykkelighed og elendighed."

---

Søren Jul Nielsen wrote:
> Jeg har et problem som delvist er matematisk, og jeg kan bare ikke
> hitte ud af det.....

Et lille eksempel med tallene 1,2,3,4,5,6 og 3 tre grupper måske
gøre det mere klart, hvad du mener med "rører" og "ser".

--
Jens Axel Søgaard

---

Jens Axel Søgaard skrev i meddelelsen ...
>Søren Jul Nielsen wrote:
>> Jeg har et problem som delvist er matematisk, og jeg kan bare ikke
>> hitte ud af det.....
>
>Et lille eksempel med tallene 1,2,3,4,5,6 og 3 tre grupper måske
>gøre det mere klart, hvad du mener med "rører" og "ser".

Hvis vi f.eks. siger at hver af de 3 grupper max. kan indeholde 2 tal.
Så skal det gerne kombineres således at alle tal mellem 1 og 6
har lagt i samme gruppe.
Det skal bruges i forbindelse med et telefonanlæg, hvor lokalnumrene
fra 100 til 160 alle skal kunne trække hinandens telefoner hvis den ringer.
Men der kan kun være 16 grupper, og hver gruppe kan max. indeholde
16 lokalnumre. Så ville jeg gerne vide om det i det hele taget kan lade sig
gøre at kombinere det så alle lokalnumre kan komme i gruppe med
hinanden.

>
>

---

Søren Jul Nielsen wrote:
> Jens Axel Søgaard skrev i meddelelsen ...
>> Søren Jul Nielsen wrote:
>>> Jeg har et problem som delvist er matematisk, og jeg kan bare ikke
>>> hitte ud af det.....
>>
>> Et lille eksempel med tallene 1,2,3,4,5,6 og 3 tre grupper måske
>> gøre det mere klart, hvad du mener med "rører" og "ser".
>
> Hvis vi f.eks. siger at hver af de 3 grupper max. kan indeholde 2 tal.
> Så skal det gerne kombineres således at alle tal mellem 1 og 6
> har lagt i samme gruppe.

Her er tre grupper med 2 tal: A=12 B=34 og C=56
Hvad mener du så med at "alle tal har lagt i samme gruppe", hvis
der højst må være 2 tal i hver gruppe?

Er der forbindelse mellem grupperne? Er der forbindelse mellem nogle
bestemte af tallene i en gruppe til bestemte af tallene i en anden?
Og hvormange?

--
Jens Axel Søgaard

---

Jens Axel Søgaard skrev i meddelelsen
<7lV2a.84813$Hl6.7857031@news010.worldonline.dk>...
>Søren Jul Nielsen wrote:
>> Jens Axel Søgaard skrev i meddelelsen ...
>>> Søren Jul Nielsen wrote:
>>>> Jeg har et problem som delvist er matematisk, og jeg kan bare ikke
>>>> hitte ud af det.....
>>>
>>> Et lille eksempel med tallene 1,2,3,4,5,6 og 3 tre grupper måske
>>> gøre det mere klart, hvad du mener med "rører" og "ser".
>>
>> Hvis vi f.eks. siger at hver af de 3 grupper max. kan indeholde 2 tal.
>> Så skal det gerne kombineres således at alle tal mellem 1 og 6
>> har lagt i samme gruppe.
>
>Her er tre grupper med 2 tal: A=12 B=34 og C=56
>Hvad mener du så med at "alle tal har lagt i samme gruppe", hvis
>der højst må være 2 tal i hver gruppe?

Nu er vi jo lidt låst her, da vi kun har 3 grupper og der altså ikke er
nogle "frie"
grupper at gøre godt med, men hvis vi nu havde haft f.eks. 5 grupper.
Så skal det gerne være således, at alle tal mellem 1 og 6 på et eller andet
tidspunkt har lagt i samme gruppe.

>Er der forbindelse mellem grupperne?
Nej grupperne skal betragtes som "selvstændige"
Medlemmer i en gruppe, kan ikke "se" tallene i en anden gruppe.

Er der forbindelse mellem nogle
>bestemte af tallene i en gruppe til bestemte af tallene i en anden?
>Og hvormange?

Nej det er der ikke.
>
>--
>Jens Axel Søgaard
>
>

---

Søren Jul Nielsen wrote:

>> Et lille eksempel med tallene 1,2,3,4,5,6 og 3 tre grupper måske
>> gøre det mere klart, hvad du mener med "rører" og "ser".

Jeg tror jeg har forstået spørgsmålet. Med to numre i hver gruppe,
ville resultatet komme til at se sådan ud:

1 2
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6
4 5
4 6
5 6

> Det skal bruges i forbindelse med et telefonanlæg, hvor lokalnumrene
> fra 100 til 160 alle skal kunne trække hinandens telefoner hvis den
> ringer. Men der kan kun være 16 grupper, og hver gruppe kan max. indeholde
> 16 lokalnumre. Så ville jeg gerne vide om det i det hele taget kan lade
> sig gøre at kombinere det så alle lokalnumre kan komme i gruppe med
> hinanden.

Dvs. du mener, at f.eks 100 skal ligge i en gruppe, hvor 101-115 også
ligger. Desuden skal den ligge i en gruppe, hvor 116-130 ligger. Og i
en gruppe hvor også 131-145 ligger ? Så et nummer kommer til at ligge
i flere grupper på een gang ?

(er du i øvrigt sikker på, at telefonanlægget kan klare det ?)

-Claus