Julekalender #2

[Emilga]

Hvert rom i et hus har et partall antall dører. Vis at huset må ha et partall antall ytterdører.

[DennisChristensen]

Hvert rom i et hus har et partall antall dører. Vis at huset må ha et partall antall ytterdører.

Metode 1: Vi viser resultatet direkte med litt enkel grafteori. Introduser en graf $G$ som har én node for hver dør i huset, og hvor to noder er koplet sammen hvis og bare hvis dørene ligger i samme rom. Ettersom hvert rom har et partall antall dører, har alle nodene som ikke representerer ytterdører et partall antall naboer, mens nodene som representerer ytterdører har et oddetall antall naboer. Vi konstruerer så grafen $H$ ved å legge til én node $v$ til $G$, som koples sammen med alle nodene som representerer ytterdører. Vi vet at alle nodene $\ne v$ i $H$ har et partall antall naboer. Derfor følger det som en konsekvens av "handshaking"-lemmaet at $v$ har et partall antall naboer. Altså har huset et partall antall ytterdører.

Metode 2: Induksjon over antall rom $r$.

Basistilfelle: $r=1$. I dette tilfelle er antall ytterdører lik totalt antall dører i rommet, så påstanden er trivielt tilfredsstilt. $✓$

Induksjon: Anta at påstanden gjelder for hus med $r$ dører. La $H$ være et hus med $r+1$ rom, hvor hvert rom har et partall antall dører. Hvis $H$ ikke har noen ytterdører, er vi ferdige. La derfor $H$ ha $Y\ge 1$ ytterdører. Vi vet at $H$ må ha et rom $\rho$ med minst én ytterdør. La $h$ være huset vi får når vi "fjerner" rommet $\rho$ (Det vil si, vi river ned ytterveggene til $\rho$, så dørene til $\rho$ som ikke er ytterdører, blir til ytterdører i $h$). Si at $h$ har $y$ ytterdører. Ettersom hvert rom i $H$ hadde et partall antall dører, gjelder dette også for rommene i $h$, så fra induksjonshypotesen vet vi at $y$ er partall, si $y=2a$, $a\in \mathbb{N}$. La $$y_{\rho }=\mathrm{\#}\left(\text{ytterdører i rommet }\rho \text{ i }H\right)$$ og $${\overline{y}}_{\rho }=\mathrm{\#}\left(\text{antall dører i rommet }\rho \text{ i }H\text{ som ikke er ytterdører}\right).$$
Vi vet at $y_{\rho }+{\overline{y}}_{\rho }$ er partall, si $y_{\rho }+{\overline{y}}_{\rho }=2b$, $b\in \mathbb{N}$. Derfor får vi at $$Y=y-{\overline{y}}_{\rho }+y_{\rho }=2a+2b-2{\overline{y}}_{\rho },$$ så $Y$ er partall. $✓$

Dermed er påstanden bevist for alle hus med induksjon.

[Gustav]

La $R_i$ være antall dører i rom $i$, og $S=\sum _i{R}_i$. La videre $I$ og $Y$ være totalt antall innvendige dører og ytterdører. Siden vi i $S$ teller alle innvendige dører to ganger får vi sammenhengen $S=2I+Y$. Siden $R_i$ er partallig for alle $i$ må S være partallig, og følgelig må Y være partallig.

Edit: omformulerte litt for klarhetens skyld

[Emilga]

Ser riktig ut!

Det er veldig kult å se forskjellige løsningsmetoder på samme problem. Jeg tenker det også kan være nyttig for de som leser tråden uten at de nødvendigvis svarer selv.

Min løsning var ved bruk av grafteori og bevis ved selvmotsigelse.

Representer hvert Rom i huset samt Utsiden med hver sin node. Tegn kanter mellom nodene som har dører som kobler dem.

Tegn videre en sirkel rundt alle rommene i huset og plasser noden som representerer Utsiden utenfor sirkelen.

La alle rommene ha et partall antall dører. Anta videre at Utsiden har et odde antall dører.

Da vil det eksistere et odde antall kanter som krysser sirkelen. Altså må minst ett av rommene innenfor sirkelen ha et odde antall kanter som krysser sirkelen.

Flytt dette rommet, "Rom 1", utenfor sirkelen. Siden Rom 1 totalt sett har et partall antall dører, må Rom 1 fortsatt ha et odde antall kanter som krysser sirkelen. Legg merke til det totale antall kanter som krysser sirkelen fortsatt er odde, siden vi startet med et odde antall kanter, trakk fra et odde antall kanter, og så la til et odde antall kanter. ($o-o+o=e+o=o$.)

Altså må det finnes minst én node innenfor sirkelen som fortsatt har et odde antall kanter som krysser sirkelen.

Flytt denne noden, Rom 2, utenfor sirkelen. Siden dette rommet totalt har et partall antall dører, må det også ha et odde antall kanter som krysser sirkelen. (...) Altså må det finnes minst én node innenfor sirkelen som har et odde antall kanter som krysser sirkelen.

Osv.

Siden huset har et endelig antall rom, vil vi komme til et steg i prosessen der vi bare har én node igjen inni sirkelen. Denne noden vil ha et odde antall kanter som krysser sirkelen. Siden dette er det eneste rommet som er igjen, vil disse kantene representere antall dører i rommet. Altså har rommet et odde antall dører. Altså har vi en selvmotsigelse. Altså kan ikke antall ytterdører være odde.