Post in het vervolg je vragen over wiskunde liever uitsluitend in dit topic en zie ook mijn opmerkingen hier.quote:
Aangezien de animo een beetje laag was niet de hele uitwerking maar wel het argument dat werkt. Zij ALG1 het random algoritme dat n punten selecteert (uniform) zodat al die n punten niet in dezelfde rij of kolom zitten. Noem die set X en bereken daarna de verwachting van het aantal 'unieke' punten, dus punten zodat A_i,j is ongelijk aan A_k,l voor alle (k,l) in X\{i,j)}. Die verwachting blijkt strikt groter dan n-2, dus dmv de definitie van de verwachting heb je een existentie argument voor een set X met de eigenschap dat het aantal unieke punten in de set gelijk is aan n-1 óf n. Nu is n-1 onmogelijk (een niet uniek punt komt 2x voor dus dan heb je maximaal n-2 unieke punten..) en dus bestaat er een set X met n unieke punten.quote:Op dinsdag 26 maart 2019 16:33 schreef Amoeba het volgende:
Even een hersenkrakertje.
De vraagstelling:
Zij A een matrix (n x n), Aij = {1,..,n2/2} waarbij iedere waarde precies twee keer voorkomt. Neem verder aan dat n2/2 een geheel getal is én n > 2.
Te bewijzen:
Er bestaat een set X zdd |X| = n en X bestaat uit paren (i,j) zdd dat voor iedere (i,j), (k,l) de volgende beweringen waar zijn:
i =! k
j =! l
Aij =! Akl
Maw X is een set indices zodanig dat de matrix entries niet in dezelfde kolom, niet in dezelfde rij zitten én niet dezelfde waarde delen. Een (triviaal) voorbeeld is dus de diagonaal van de matrix als die niet tweemaal dezelfde waarde bevat.
Mijn poging:
Construeer een graaf G = (V,E) op de matrix waarbij twee punten verbonden zijn als ze in dezelfde kolom of rij zitten óf dezelfde waarde delen. Ieder punt heeft dus (2n-2) of 2n-1 connecties. Merk op dat |V| = n2
Het doel is nu om te bewijzen dat V een 'independent set' bevat van tenminste n punten.. Nou weten we dat er minimaal een independent set is van grootte |V|/(d+1) waarbij d de maximale graad van een punt is, in ons geval is dat 2n-1.. Dit levert zoiets als n/2 op en dat is nog niet goed genoeg...
Iemand een beter idee?
Met welke vraag heb je precies moeite?quote:Op vrijdag 20 september 2019 22:30 schreef Eendenkooi het volgende:
Succes ....
http://math.stanford.edu/~akshay/math113/linear-final-prac.pdf
Oh ik moet ze niet maken hoor, vond het gewoon leuk om de link te posten.quote:Op vrijdag 20 september 2019 23:01 schreef thabit het volgende:
[..]
Met welke vraag heb je precies moeite?
Best erg hoeveel ik hiervan alweer vergeten ben.quote:Op vrijdag 20 september 2019 22:30 schreef Eendenkooi het volgende:
Succes ....
http://math.stanford.edu/~akshay/math113/linear-final-prac.pdf
Bedankt voor jullie reacties, kwartje wil nog niet echt vallen. Maar ik ga ermee aan de slag van het weekend. zo moeilijk moet het toch niet zijn....quote:Op woensdag 2 oktober 2019 02:39 schreef Riparius het volgende:
[..]
Geen wonder, want er klopt geen donder van. Je bedoelt wellicht
[ afbeelding ]
Als we beide leden van deze ongelijkheid vermenigvuldigen met −32/71 dan krijgen we
[ afbeelding ]
Merk op dat het ongelijkheidsteken omklapt wanneer we beide leden van de ongelijkheid met een negatief getal vermenigvuldigen.
Toch wel mooi dat je zelf de vraag en het antwoord moet geven tegenwoordig.quote:Op woensdag 2 oktober 2019 02:39 schreef Riparius het volgende:
[..]
Geen wonder, want er klopt geen donder van. Je bedoelt wellicht
[ afbeelding ]
Als we beide leden van deze ongelijkheid vermenigvuldigen met −32/71 dan krijgen we
[ afbeelding ]
Merk op dat het ongelijkheidsteken omklapt wanneer we beide leden van de ongelijkheid met een negatief getal vermenigvuldigen.
|
Forum Opties | |
---|---|
Forumhop: | |
Hop naar: |