Springen naar inhoud

Duivenhok


  • Log in om te kunnen reageren

#1

Ernie

    Ernie


  • >100 berichten
  • 179 berichten
  • Ervaren gebruiker

Geplaatst op 29 november 2003 - 10:57

Wel, misschien doe ik jullie een plezier met wat leuke vraagjes over het duivenhokprincipe:

- Bewijs dat er een getal van de vorm 20042004...2004 bestaat dat deelbaar is door 2003.

- Bewijs dat elke verzameling van 13 verschillende rele getallen twee getallen a en b bevat zodat
0 < (a - b)/(1 + ab) <= 2 - 3^(1/2).

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

Elmo

    Elmo


  • >1k berichten
  • 3437 berichten
  • VIP

Geplaatst op 01 december 2003 - 09:04

- Bewijs dat er een getal van de vorm 20042004...2004 bestaat dat deelbaar is door 2003.


Edit: ONZIN WEG GEHAALD :shock:

- Bewijs dat elke verzameling van 13 verschillende rele getallen twee getallen a en b bevat zodat
0 < (a - b)/(1 + ab) <= 2 - 3^(1/2).


Geen idee. Zal er eens over nadenken. Heb je zelf het bewijs?

#3

Ernie

    Ernie


  • >100 berichten
  • 179 berichten
  • Ervaren gebruiker

Geplaatst op 01 december 2003 - 12:53

Voor (1):
Sorry, maar je bewijs is fout. Trouwens, 20042004...2004 = 0 (mod 6).
Waarom zou uit 2003 = 5 (mod 6) volgen dat 2003|20042004...2004?
Ik kan je redenering niet volgen. Mijn bewijs steunt op het duivenhokprincipe.

Voor (2):
Ja, ik heb een bewijs :shock:

In beide gevallen moet je echt het duivenhokprincipe gebruiken:

Verdeelt men n + 1 duiven over n duivenhokken,
dan bevat minstens n hok minstens twee duiven.

Je moet dan duiven en duivenhokken identificeren met wiskunde.
Voor (2) bijvoorbeeld moet je 13 getallen verdelen over 12 intervallen.

#4

Elmo

    Elmo


  • >1k berichten
  • 3437 berichten
  • VIP

Geplaatst op 01 december 2003 - 12:59

(1): ja mijn bewijs was onzin. (Had nog geen thee gehad :shock: ).

(2): ik neem aan dat de 13 willekeurige getallen allen strikt positief moeten zijn? Of mogen ze ook <0 of 0 zijn?

#5

Ernie

    Ernie


  • >100 berichten
  • 179 berichten
  • Ervaren gebruiker

Geplaatst op 01 december 2003 - 13:07

Ze mogen negatief zijn! :shock:

#6

Ernie

    Ernie


  • >100 berichten
  • 179 berichten
  • Ervaren gebruiker

Geplaatst op 01 december 2003 - 19:55

Tjah, ik heb niet gezegd dat het makkelijke oefeningetjes zijn h :shock:
Ze komen niet voor niets uit de voorbereiding van het Belgische team op de IMO
(IMO = Internationale wiskunde olympiade)

#7

Ernie

    Ernie


  • >100 berichten
  • 179 berichten
  • Ervaren gebruiker

Geplaatst op 02 december 2003 - 14:48

Wel, ik zal al de oplossing geven voor vraag 1:

Beschouw de 2004 getallen
2004
20042004
200420042004
...
200420042004...200420042004 (2004 keer '2004').
Beschouw de resten van deze getallen modulo 2003.
Er zijn 2003 mogelijke resten maar we hebben 2004 van die getallen.
Volgens het duivenhokprincipe hebben dus twee van die getallen dezelfde rest.
[Beschouw de getallen als duiven en de restklassen als duivenhokken.]
Dus, stel dat a en b dezelfde rest hebben (mod 2003) en van deze vorm zijn.
Dan is |a - b| deelbaar door 2003.
Maar |a - b| is een getal van de vorm 2004...20040000...000.
We kunnen dus stellen dat |a - b| = s*10^t voor natuurlijke getallen s, t.
Hierbij is s opnieuw van de vorm 2004...2004.
Omdat 2003 een deler is van |a - b|, en omdat 2003 en 10^t relatief priem zijn,
is 2003 een deler van s, een getal van de vorm 2004...2004.
Dus we zijn klaar.

#8

Elmo

    Elmo


  • >1k berichten
  • 3437 berichten
  • VIP

Geplaatst op 03 december 2003 - 08:22

Leuk!
Wil je ook het bewijs voor de tweede stelling posten? Ik denk namelijk niet dat iemand ermee komen gaat....

Mijn gevoel is dat het ongeveer zo gaat:
1) deel (-oo , oo) op in 12 delen zodanig dat voor a,b element twee willekeurige delen de stelling niet geldt en voor a,b element het zelfde deel de stelling altijd geldt.

Waarschijnlijk deel je dus [0, oo) op in zes delen, want het probleem is a <-> b symmetrisch.

Toen had ik geen zin meer om het allemaal uit te schrijven... :shock:

#9

Ernie

    Ernie


  • >100 berichten
  • 179 berichten
  • Ervaren gebruiker

Geplaatst op 03 december 2003 - 12:42

Ja, die tweede vraag ... ik ben er dol op :shock: Je moet weten, die is echt niet gemakkelijk.
Vorig jaar op de training voor de IMO losten er slechts 2 van de 15 die vraag op.
En ja, ik was er n van ;)

Noem de gegeven getallen s_1, s_2, ..., s_13. Stel t_i = arctan(s_i) voor i = 1, 2, ..., 13.
Dan hebben we dertien getallen t_i, allen in [-pi/2, pi/2].
Verdeel dit interval [-pi/2, pi/2] in twaalf deelintervallen van gelijke lengte (pi/12).
Dit zijn dus de intervallen [-pi/2, -5pi/12], ..., [5pi/12, pi/2].
We hebben 13 t_i's, dus volgens het duivenhokprincipe liggen er 2 in n interval.
Dan geldt voor zekere indices p, q dat 0 <= t_p - t_q <= pi/12.
We nemen van deze uitdrukking de tangens.
De tangensfunctie stijgt op [-pi/2, pi/2] dus geldt er:

0 <= tan(t_p - t_q) <= tan(pi/12) = 2 - 3^(1/2)
0 <= (s_p - s_q)/(1 + s_p*s_q) <= 2 - 3^(1/2).

We stellen nu s_p = a en s_q = b, en we zijn klaar.

#10

Elmo

    Elmo


  • >1k berichten
  • 3437 berichten
  • VIP

Geplaatst op 03 december 2003 - 13:05

Ziet er allemaal heel erg leuk uit! 8) Daar was ik nooit op gekomen. :shock:

Ik voel me een beetje dom, maar ik zie even de laatste stap niet:

0 <= tan(t_p - t_q) <= tan(pi/12) = 2 - 3^(1/2)
0 <= (t_p - t_q)/(1 + t_p*t_q) <= 2 - 3^(1/2).

waarom geldt dit voor alle t_p en t_q? (ik=dom)

#11

Elmo

    Elmo


  • >1k berichten
  • 3437 berichten
  • VIP

Geplaatst op 03 december 2003 - 13:31

Laat maar, ik was de volgende identiteit even vergeten:

tan(x+y) = [tan(x) + tan(y)] / [1 - tan(x)*tan(y)]

:shock:

#12

Ernie

    Ernie


  • >100 berichten
  • 179 berichten
  • Ervaren gebruiker

Geplaatst op 03 december 2003 - 14:10

Ja, die probleempjes over het duivenhokprincipe zijn echt leuk.
Hier is er een heel gemakkelijk:

Men plaatst 51 punten binnen een vierkant met zijden van lengte 1.
Bewijs dat er een cirkel met straal 1/7 bestaat die minstens 3 van deze punten bedekt.

#13

Ernie

    Ernie


  • >100 berichten
  • 179 berichten
  • Ervaren gebruiker

Geplaatst op 04 december 2003 - 16:32

Aangezien niemand reageert zal ik zelf dan maar de oplossing geven:

Verdeel het vierkant in 25 kleine vierkantjes met zijde 1/5.
We hebben 51 punten en 25 vierkantjes, dus er liggen 3 punten in n vierkantje.
(Dit is inderdaad het duivenhokprincipe :shock: ietwat anders geformuleerd.)
Een cirkel met straal 1/7 kan een vierkantje met straal 1/5 volledig bedekken.
(Dat volgt uit de stelling van Pythagoras.)
Dus er zullen drie punten bedekt worden door n cirkelschijf.

#14


  • Gast

Geplaatst op 17 november 2004 - 00:33

1) n mensen bevinden zich in een kamer. Toon aan dat er minstens 2 mensen zijn die evenveel kennissen hebben.
2) Op het ZxZ-rooster kiezen we 5 punten. Toon aan dat er tussen die 5 punten steeds 2 punten zijn zodat het lijnstuk tussen die 2 punten door een roosterpunt gaat.
3) In elke convexe 2n-hoek is er een diagonaal die niet parallel is met 1 van de zijden. (gaat niet op voor veelhoeken met een oneven aantal zijden)
4) Tussen 52 verschillende gehele getallen kan men er steeds 2 selecteren zodat hun som of verschil een veelvoud van 100 is.

#15

Elmo

    Elmo


  • >1k berichten
  • 3437 berichten
  • VIP

Geplaatst op 17 november 2004 - 08:46

De eerste vraag begrijp ik al niet eens.

Je zegt dus dat als jij en ik (n=2) samen in een kamer zitten zonder anderen erbij, dat jij dan kan bewijzen dat wij evenveel kennissen hebben? Dat snap ik niet (en ik denk ook niet dat het klopt).
Never underestimate the predictability of stupidity...





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures