De digitale vraagbaak voor het wiskundeonderwijs

home |  vandaag |  gisteren |  bijzonder |  gastenboek |  wie is wie? |  verhalen |  contact

HOME

samengevat
vragen bekijken
een vraag stellen
hulpjes
zoeken
FAQ
links
twitter
boeken
help

inloggen

colofon

  \require{AMSmath}

Bewijzen

Slechtste partner in Gale Shapley

Beste,

Gegeven is het stable marriage algoritme van Gale Shapley. Claim: Het algoritme matcht elke vrouw met haar slechtst mogelijk partner. In slide 24 van https://ocw.tudelft.nl/wp-content/uploads/Algoritmiek_Stable_Matching__continued_.pdf staat in de tweede regel van het bewijs dat er een matching S' bestaat met een eigenschap. Hoe weten we zo zeker dat S' moet bestaan met die eigenschap? Ik zie niet uit welke aanname dat volgt.

Vriendelijke groet,

Nico

Nico
11-2-2022

Antwoord

Printen
Dat volgt uit de definitie van "valid partner" eerder op de slides.
Op slide 25 staat een verwijzing naar het cursusboek (links onderaan). Dat boek is online te bekijken, zie hieronder, en dus in het bijzonder pagina's 11 en 12.

Het boek geeft wat meer uitleg dan de slides.
Zie Boek: Algorithm Design

kphart
11-2-2022


Re: Slechtste partner in Gale Shapley

Bedankt voor uw antwoord. In het boek wordt een bewijs gegeven uit het ongerijmde, met de volgende definitie: We say that m is the worst valid partner of w if m is a valid partner of w, and no man whom w ranks lower than m is a valid partner of hers. Dus: stel dat er een vrouw wordt gepaard met een man M die niet de slechtst mogelijke partner is. Dan geldt per definitie een van de volgende twee gevallen (of allebei, omdat we een negatie zetten voor de conjunctie in de definitie van worst valid partner):
1) M is geen geldige partner van de vrouw
2) Er is een man M' die de vrouw lager beoordeeld dan M, en M' is een geldige partner.

In het bewijs wordt echter alleen geval 2 (of allebei) aangenomen, maar zouden we niet ook het geval moeten bewijzen dat alleen geval 1 geldt? Waarom volstaat het om alleen geval 2 aan te nemen in het bewijs, en geval 1 te negeren?

Nico
11-2-2022

Antwoord

Printen
Die stelling gaat over de matching $S^*$ en die is stable, dus $m$ is een geldige partner van $w$.

kphart
11-2-2022


Re: Re: Som van kwadraten

Je kunt ook uitgaan van een hypothese: stel de gevraagde formule heeft de gedaante S(n) = an3 + bn2 + cn + d.

Omdat s(0) = 0, weet je al dat d = 0.

Substitutie van n = 1, 2, 3 geeft met s(1) = 1, s(2) = 5 en s(3) = 14 drie vergelijkingen met de drie onbekenden a, b, c. Oplossen geeft a = 1/3, b = 1/2, c = 1/6.

Verder moet je dan nog bewijzen dat s(n+1) = s(n) + (n+1)2, maar dat is simpel.

Op deze manier kun je ook a, b, en c bepalen wanneer n alleen even of oneven mag zijn.

John
14-2-2022

Antwoord

Printen
Zeker. Zie ook De rij 1, 4, 9, 16, 25, ...

WvR
16-2-2022


Existentiebewijs

Beste heer/mevrouw,

Ik heb veel moeite met het bewijs dat gegeven is op de volgende stelling (gevolgd door de definities).

Definities:
Zij I een eindige deelverzameling van de natuurlijke getallen. Bekijk de machtsverzameling van I, aangeduid als P(I). Een aantal elementen van P(I) worden aangeduid met het attribuut 'gewenst'. Een element J $\in $ P(I) is maximaal gewenst dan en slechts dan als de volgende twee properties gelden. 1) J is gewenst, en 2) voor alle strikte supersets K van J (waarbij K $\in $ P(I)) geldt dat K niet gewenst is. Tot zover de definities.

Stelling:
Zij C nu een verzameling van alle maximaal gewenste elementen van P(I). Laat J een element zijn van P(I) waarvoor geldt dat $\forall $ Y van C: J $\not\subset $ Y. Dan geldt dat J niet gewenst is.

Bewijs:
Er is een maximaal gewenste verzameling K $\in $ C zodanig dat K $\subset $ J. Dus J is niet gewenst. Einde bewijs.

Hoe weten we dat de verzameling K per se een strikte deelverzameling is van J in het bewijs (zodanig dat deze K ook maximaal gewenst is)?

Nico
18-2-2022

Antwoord

Printen
Het bewijs klopt niet. Er hoeft helemaal geen $K\in C$ te zijn met $K\subset J$.
Bijvoorbeeld als $I=\{1,2,3,4\}$ met $\{1,2\}$ en $\{3,4\}$ als enige gewenste verzamelingen. Dan is $C$ dus gelijk aan $\bigl\{\{1,2\},\{3,4\}\bigr\}$.
Dan voldoet $J=\{1,3\}$ aan de voorwaarden van de stelling maar er is geen $K$ als in het bewijs.

Het juiste bewijs gaat uit het ongerijmde. Stel $J$ is wel gewenst. Dan is er, omdat $I$ eindig is, een $Y\in C$ met $J\subseteq Y$. In tegenspraak met het gegeven.
De stelling had beter kunnen luiden: "Elke gewenste verzameling is bevat in een maximale gewenste verzameling."

kphart
19-2-2022


Getaltheorie delers van een geometrische functie met gehele getallen

STELLING

n Is een natuurlijk getal.
p Is een priemgetal.

f(n,p) = 1 + n + n2 + . + n^(p-1)

Als n = 1 mod p dan is p een deler van f(n,p)

Als d een deler is van f(n,p) n d ≠ p dan is d = 1 mod p

Is hier een bewijs voor?
Zo niet: Hoe bewijs je dit?

Chris
22-2-2022

Antwoord

Printen
De eerste bewering klopt: omdat $n\equiv1\bmod p$ geldt $n^i\equiv 1\bmod p$ en dan geldt dus $f(n,p)\equiv p\cdot 1\equiv0\bmod p$.

De tweede klopt niet: neem $p=2$ en $n=7$, dan $f(7,2)=8$ en $4$ is een deler van $8$, maar $4\equiv0\bmod 2$.

kphart
22-2-2022


Bewijs door volledige inductie

Beste

Ik moet het volgende bewijzen door volledige inductie: voor elke natuurlijke getal n verschillend van nul, geldt: 32n-1 is een viervoud

Ik weet hoe dat dit bewijs in elkaar zit, maar ik snap niet hoe ik moet beginnen
bv bij de eerste stap moet je bewijzen dat het geldt voor n = 1, moet je dan het zo oplossen: 32n-1 = n/4, maar dan klopt het weer niet.

Alvast bedankt

nvt
9-5-2022

Antwoord

Printen
Te bewijzen: $3^{2n}-1$ is een viervoud.

Stap 1.
Neem $n=1$
$3^{21}-1=8$
Klopt! 8 is een viervoud.

Stap 2.
Neem n+1 en laat zien dat als $3^{2n}-1$ een viervoud is dan is $3^{2(n+1)}-1$ dat ook.

[uitwerken]

...en dan nog netjes opschrijven en dan ben je er...

Lukt dat?

Naschrift
Sterker nog: $3^{2n}-1$ is zelfs een achtvoud.
Een goed begin is het halve werk...

$
\eqalign{
& 3^{2(n + 1)} - 1 \cr
& 3^{2n + 2} - 1 \cr
& 3^{2n} \cdot 3^2 - 1 \cr
& 9 \cdot 3^{2n} - 1 \cr
& 8 \cdot 3^{2n} + 3^{2n} - 1 \cr}
$

WvR
9-5-2022


Topologische vectorruimte

Beste

Zij X een topologische vectorruimte met dimX$ \ge $ 2 en f:X- $>$ ℝ continu, dan bestaat er steeds een punt x in X\{0} zodanig f(x)=f(-x). Ik zit een beetje vast bij deze opgave, wilt u aub een hint geven? Alvast dank ik u bij voorbaat.

Met vriendelijke groeten
Rafik

Rafik
30-5-2022

Antwoord

Printen
Neem twee lineair onafhankelijke vectoren $v_1$ en $v_2$ en definieer $g:\mathbb{R}\to\mathbb{R}$ door $g(t)=\cos(t)\cdot v_1+\sin(t)\cdot v_2$, en laat zien dat er een $t$ is met $g(t)-g(t-\pi)=0$.

kphart
30-5-2022


Topologie

Beste

Ik probeer dit te bewijzen: Zij X een compacte topologische ruimte en M een metrische ruimte. Zij f,g continue X- $>$ M. Stel dat f(x)=g(x) een benaderende oplossing heeft tot op een willekeurige nauwkeurigheid, hiermee bedoel ik ( $\forall $ $\varepsilon $ )( $\exists $ x $\in $ X)(d(f(x),g(x)) $<$ $\varepsilon $ ). Dan heeft de vergelijking een oplossing.

Schets van mijn aanpak: Ik wil dus hebben ( $\exists $ x $\in $ X)( $\forall $ $\varepsilon $ $>$ 0)(d(f(x),g(x) $<$ $\varepsilon $ ). Om de quantoren te verwisselen dacht ik om een set U_n={f(x):f(x) $\in $ B(g(x),1/n)} te introduceren, dan weet ik uit het gegeven dat er een x bestaat zodanig f(x) in U_n zit, waardoor die U_n niet leeg zijn, en mijn te bewijzen is dan dat de doorsnede van mijn U_n over alle n niet leeg is. Hiervoor wou ik gebruik maken dat als een eerste aftelbaarheidsruimte rijcompact $\Leftrightarrow $ elke dalende rij van niet lege,gesloten verzamelingen een niet lege doorsnede heeft. Ik weet al dat f(X) rijcompact is aangezien X compact is en f continu waardoor f(X) een compacte metrische ruimte is dus ook rijcompact. Mijn (U_n)n zijn niet leeg, en U_1 $\supseteq $ U_2 $\supset $ ... Dus resteert aan te tonen dat U_n gesloten zijn, en hier zit ik een beetje vast .

Ik vroeg me af of ik in de juiste richting zit te denken, of ben ik helemaal verkeerd? Alvast dank ik jullie!

Met vriendelijke groeten
Rafik

Rafik
4-6-2022

Antwoord

Printen
Je zit op de goede weg, maar niet helemaal.
Je $U_n$ is een deelverzameling van $M$ en de definitie is wat dubbelzinnig; heel strikt genomen kun je $U_n$ ook schrijven als $\{m:m\in B(g(x),1/n)\}$ en dat is niet wat je wilt. Je zou $U_n$ moeten beschrijven als
$$\{f(x):x\in X\text{ en }f(x)\in B(g(x),1/n)\};
$$ die is open maar niet noodzakelijk gesloten.

Maar het is beter in $X$ te werken en $F_n=\{x\in X: d(f(x),g(x))\le\frac1n\}$ te nemen.
De $F_n$ zijn niet leeg en dankzij de $\le$ gesloten, en ook geldt altijd $F_{n+1}\subseteq F_n$.
Gebruik nu de compactheid van $X$ en kijk naar $\bigcap_{n=1}^\infty F_n$.

kphart
4-6-2022


home |  vandaag |  bijzonder |  gastenboek |  statistieken |  wie is wie? |  verhalen |  colofon

©2001-2022 WisFaq - versie 3