Viikkotehtävä: ahdas kerrostalo (viikko 37/2018)

kombinatoriikka

#1

Viikkotehtävä: ahdas kerrostalo

Vastausaikaa su 16.9.2018 klo 24 asti
Vastausaika on päättynyt. Voit keskustella tehtävästä ja sen ratkaisuideoista vapaasti tässä ketjussa.

Tehtävä

Kerrostalossa asuu 209 asukasta 210 asunnossa, mutta eivät välttämättä kaikki eri asunnoissa. Jos asunnossa on ainakin 20 asukasta, sanomme että se on ahdas. Joka päivä jossakin ahtaassa asunnossa alkaa asukkaiden kesken riita, ja kaikki tämän asunnon asukkaat muuttavat keskenään eri asuntoihin. Käykö välttämättä niin, että jonakin päivänä yksikään asunto ei ole ahdas?


#2

#3

#4

Tehtävään esitettyjen onnistuneiden ratkaisujen perusideana oli huomata, että jotta ikuiset riidat ovat mahdollisia, yhdessä asunnossa olisi oltava ainakin 20 asukasta, yhdessä ainakin 19 (ensimmäisestä voi siirtyä yksi täydentämään), yhdessä ainakin 18 (kahdesta ensimmäisestä voi siirtyä täydentäjät) jne., ja näistä tulee yhteensä 210, yksi enemmän kuin asukkaita luvattiin olevan saatavilla. Hieman voi jäädä vaivaamaan epäilys siitä, miksei yksi asunto voisi toimia useamman kuin yhden riidan paikkana.

Keksitään potentiaalifunktio ja osoitetaan, että se pienenee joka riidan jälkeen, ja että sillä toisaalta on alaraja: sovitaan, että joka päivän aluksi (ennen mahdollista riitaa) kunkin asunnon asukkaat kättelevät toisiaan, ja lasketaan kättelyiden kokonaismäärä. Jos asunnossa i on a_i asukasta, kättelyitä tapahtuu \sum_{i=1}^{210} \frac{a_i(a_i-1)}{2}. Jos riita tapahtuu, voidaan olettaa yleisyyttä rajoittamatta, että se tapahtuu asunnossa 1 ja asukkaat muuttavat asuntoihin i_1, i_2, \dots, i_k missä k=a_1. Silloin a_1\ge 20 ja riidan seurauksena tapahtuva potentiaalifunktion muutos on

-\frac{a_1(a_1-1)}{2} + a_{i_1} + a_{i_2} + \dots + a_{i_k}.

Nyt

a_{i_1} + a_{i_2} + \dots + a_{i_k} \le 209 - a_1\le 189 < 190 = \frac{19\cdot20}{2} \le \frac{a_1(a_1-1)}{2},

joten muutos on negatiivinen. Koska potentiaalifunktio pienenee jokaisen riidan jälkeen mutta on aina välttämättä ei-negatiivinen kokonaisluku, prosessin täytyy päättyä joskus.