Kezdőlap


Feladat:	2012. évi Kürschák matematikaverseny 2. feladata	Korcsoport: 18-	Nehézségi fok: nehéz
Füzet:	2013/február, 72. oldal		PDF \| MathML
Témakör(ök):	Matematika, Kürschák József (korábban Eötvös Loránd), Oszthatóság, Kettes alapú számrendszer
Hivatkozás(ok):	Feladatok: 2013/február: 2012. évi Kürschák matematikaverseny 2. feladata

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

$(a)$ Indirekt bizonyítunk: tegyük fel, hogy létezik $5$ egymást követő, érdekes pozitív egész szám. Ezen számok közt bizonyosan van két olyan egymást követő szám (mondjuk $n$ és $n + 1$ ), hogy az $n$ szám $2$ -es számrendszerbeli felírása $01$ -re végződik: $n = ... 01_{2}$ . Ekkor az $(n + 1) = ... 10_{2}$ , ezért $E (n) = E (n + 1)$ . Mivel $n$ és $n + 1$ egyaránt érdekesek, $E (n) ∣ n$ és $E (n) = E (n + 1) ∣ n + 1$ miatt $E (n) ∣ (n + 1) - n = 1$ teljesül, tehát $E (n) = 1$ . Ezért $n = ... 01_{2}$ -ből $n = 1$ következik. Ekkor ugyan $n + 1 = 2$ még érdekes, de $n + 2 = 3$ már nem az, tehát nem létezik $5$ egymást követő érdekes pozitív egész szám. (Negatív számokat is megengedve létezik öt egymást követő érdekes szám: $- 2$ , $- 1$ , 0, 1, 2.) Egyúttal azt is igazoltuk, hogy ha az $n$ , $n + 1$ , $n + 2$ és $n + 3$ pozitív egészek mindegyike érdekes, akkor az $n = ... 10_{2}$ .
$(b)$ A fenti bizonyításból kitűnik, hogy ha olyan $n$ -t keresünk, amire az $n$ , $n + 1$ és $n + 2$ számok mindegyike érdekes, akkor $n + 2 = ... 00_{2}$ vagy $n + 2 = ... 01_{2}$ . Foglalkozzunk azzal az esettel, amikor $n + 2 = ... 00_{2}$ . Sőt: tegyük fel, hogy

\begin{matrix} n + 2 = ... 10000_{2}, \end{matrix}

azaz

n + 2

osztható

16

-tal, de

32

-vel nem.
Legyen

a : = E (n + 2)

. Ekkor

n + 1 = ... 01111_{2}

és

n = ... 01110_{2}

, tehát

E (n + 1) = a + 3

E (n) = a + 2

, így

a + 2 ∣ n

és

a + 3 ∣ n + 1

, valamint

a ∣ n + 2

. Ezért olyan (minél kisebb)

a

-t keresünk, amire az

a

a + 2

és

a + 3

számok közül legfeljebb csak

a

-nak és

(a + 2)

-nek lehet

1

-nél nagyobb közös osztója, és az sem lehet több

2

-nél. Éppenséggel az

a = 2

ilyen szám, ahhoz azonban, hogy ez megoldást adjon, az kellene, hogy

a + 2 = 4 ∣ n

teljesüljön, ahol

n + 2 = 10 ... 010000_{2}

. Ez pedig lehetetlen, ugyanis

n = ... 10_{2}

. Ezért a következő lehetőséggel,

a = 4

-gyel próbálkozunk. Ekkor

n + 2 = 2^{t_{1}} + 2^{t_{2}} + 2^{t_{3}} + 2^{4}

, ahol

t_{1} > t_{2} > t_{3} > 4

. Az

n

és

n + 1

érdekességéből adódnak a

E (n) = 6 ∣ n

és

E (n + 1) = 7 ∣ n + 1

feltételek.
Az

x : = n + 2 - 16 = n - 14 = 2^{t_{1}} + 2^{t_{2}} + 2^{t_{3}}

jelölést bevezetve azt kapjuk, hogy

x \equiv 6 (mod 7)

x \equiv 4 (mod 6)

teljesül, és

t_{3} > 4

miatt

x \equiv 0 (mod 32)

. Ennek a kongruenciarendszernek kell tehát olyan

x = 2^{t_{1}} + 2^{t_{2}} + 2^{t_{3}}

alakú megoldását keresnünk, amelyre

t_{1} > t_{2} > t_{3} > 4

. Nem nehéz megoldani a szimultán kongruenciarendszert sem (az

x \equiv 4 (mod 6)

helyett

x \equiv 1 (mod 3)

kongruenciát használva), de az ujjainkon számolva is célt érünk. A két első kongruencia az

x \equiv 34 (mod 42)

kongruenciával ekvivalens. A

t_{3} > 4

feltétel azt jelenti, hogy

2^{5} ∣ x

, tehát az

x = 34 + 42 k

alakú számok közül csak 160,

160 + 42 \cdot 16 = 832

...

jön szóba. A

160 = 10100000_{2}

még nem jó, de a

832 = 1101000000_{2}

már igen. Tehát

n + 2 = 2^{9} + 2^{8} + 2^{6} + 2^{4} = 848

és valóban: az

n = 846 = 1101001110_{2}

választással

E (846) = 6 ∣ 846,

E (847) = 7 ∣ 847

és

E (848) = 4 ∣ 848

.
A most talált érdekes számhármas segítségével pedig úgy kaphatunk végtelen sok megoldást, ha észrevesszük, hogy

3 ∣ 2^{6} - 1

és

7 ∣ 2^{6} - 1,

tehát

\begin{matrix} m (j) = 2^{9 + 6 j} + 2^{8 + 6 j} + 2^{6 + 6 j} + 2^{4} \end{matrix}

választással

\begin{matrix} E (m (j) - 1) = 7 ∣ m (j) - 1 = (2^{6 j} - 1) \cdot 832 + 847 \end{matrix}

és

\begin{matrix} E (m (j) - 2) = 6 ∣ m (j) - 2 = (2^{6 j} - 1) \cdot 832 + 846. \end{matrix}

(Az

E (m (j)) = 4 ∣ m (j)

pedig nyilván teljesül.)

Megjegyzések. 1. A

(b)

rész megoldásához nem tartozik hozzá, hogyan is találtuk meg a végtelen sok példát. Természetesen az is teljes értékű megoldás, ha valaki csak az utolsó bekezdésben megadott számhármasokra bizonyítja be, hogy azok érdekes számokból állnak. (Utóbbit nem nehéz megtenni). Természetesen a mintamegoldásban egyúttal azt is jelezni kívántuk, hogyan lehet találni ilyen számhármasokat.
2. A

(b)

rész megoldásának elején miért csak azt vizsgáltuk, ha

n + 2

bináris alakjában a két utolsó

0

előtt még két

0

áll? Nos azért, mert ha

n + 2 = ... 100_{2}

lenne, akkor

n + 1 = ... 011_{2}

és

n = ... 010_{2}

, vagyis

E (n) = E (n + 2) ∣ (n + 2) - n = 2

, tehát

n + 2 = 2^{t} + 4

és

3 ∣ n + 1 = 2^{t} + 3

, ami lehetetlen.
Hasonlóan, ha

n + 2 = ... 1000_{2}

, akkor

n + 1 = ... 0111_{2}

n = ... 0010_{2}

, így

a = E (m)

jelöléssel

E (n + 1) = a + 2

és

E (n) = a + 1

-nek adódik, ám ez a mintamegoldásbelinél nagyobb

a

-ra vezet. (Egyébként van ilyen megoldás is, ezek legkisebbike

n + 2 = 2360 = 2^{11} + 2^{8} + 2^{5} + 2^{4} + 2^{3}

, ahol tehát

a = 4

és

6 ∣ 2358 = 100100110110_{2}

7 ∣ 2359 = 100100110111_{2}

és

5 ∣ 2360 = 100100111000_{2}

.)
3. Ha a

(b)

részben az

n

-et

n = ... 11_{2}

alakban keresnénk, akkor hasonló gondolatmenettel még kisebb megoldást is találnánk:

n = 623

-ra

7 ∣ 623 = 1001101111_{2}

4 ∣ 624 = 1001110000_{2}

és

5 ∣ 625 = 1001110001_{2}

. Innen pedig

7 ∣ 2^{12} - 1

és

5 ∣ 2^{12} - 1

miatt kapunk végtelen sok

(m (j) - 1, m (j), m (j) + 1)

érdekes hármast, ahol

m (j) = 2^{9 + 12 j} + 2^{6 + 12 j} + 2^{5 + 12 j} + 2^{4}

.
4. A feladat

(a)

részét kiegészítő természetes kérdés persze úgy hangzik, hogy a pozitív egészek között előfordul-e vajon végtelen sokszor négy egymást követő érdekes szám. A válasz igenlő: a legkisebb ilyen négyes a

\begin{matrix} 6 ∣ 6222 = 1100001001110_{2}, 7 ∣ 6223 = 1100001001111_{2}, \\ 4 ∣ 6224 = 1100001010000_{2} és 5 ∣ 6225 = 1100001010000_{2} . \end{matrix}

Innen a fentiekhez hasonlóan kaphatunk végtelen sok

m (j) - 2

m (j) - 1

m (j)

m (j) + 1

érdekes számnégyest, ahol

m (j) = 2^{12 + 12 j} + 2^{11 + 12 j} + 2^{6 + 12 j} + 2^{4}

. A

6222

szám megtalálása pontosan ugyanolyan lépésekkel történhet, mint a

846

vagy a

623

számoké, csak valamivel több számolást (és így több időt) igényel, további említést érdemlő ötletre azonban nincs szükség. Ez hát a magyarázata annak, hogy a bizottság a feladat

(b)

részében a természetesen adódónál egy könnyebb kérdést tűzött ki.
5. A

(b)

részben használt ötletek nélkül is nagyon könnyen látható, hogy végtelen sok olyan

n

van, amire

n

és

n + 1

is érdekes. Ugyanis minden

n = 2^{t} + 4

jó, ahol

t > 2

páros, hiszen

E (2^{t} + 4) = 2 ∣ 2^{t} + 4

és

E (2^{t} + 5) = 3 ∣ 2^{t} + 5

. Vannak példák páratlan

n

-nel is, a legkisebb az

n = 115 = 1110011_{2}

.
6. Az

b

alapú számrendszerben a feladatbelihez hasonlóan definiált számokat a szakirodalom

b

-Niven számokként említi. A

10

-Niven számokat röviden Niven-számoknak (vagy Harshad-számoknak) hívják. Helen Grundman publikálta 1994-ben, hogy legfeljebb

2 b

egymást követő

b

-Niven szám létezhet, és Cai bizonyította 1996-ban, hogy végtelen sokféleképp található

4

egymást követő

2

-Niven szám, illetve hogy a

3

-Niven számok között is végtelen sok egymást követő hatos lép fel. Tudható még, hogy az egymást követő nem-Niven számok sorozata tetszőlegesen hosszú lehet, illetve hogy hány (

10

-)Niven szám van

x

-ig (DeKoninck‐Doyon tétele

szerint aszimptotikusan

c \frac{x}{log x}

, ahol

c = \frac{14}{27} log 10 \approx 1, 1939)