Τεστ Εξάσκησης (25), Μικροί

#1

ΘΕΜΑ 1
Ένα σύνολο $\mathfrak{D}$ αποτελείται από

ευθείες του επιπέδου. Κάθε ευθεία του συνόλου $\displaystyle{\mathfrak{D}}$ τέμνει ακριβώς 2011

άλλες ευθείες του $\displaystyle{\mathfrak{D}.}$ Να βρείτε το

ΘΕΜΑ 2
Βάφουμε καθένα από τα κελιά ενός πίνακα $n \times n$ είτε μαύρο είτε άσπρο. Τα τέσσερα σημεία τομής δύο γραμμών και δύο στηλών ορίζουν ένα κουαρτέτο. Ένα κουαρτέτο λέγεται κακό όταν όλα τα κελιά του έχουν το ίδιο χρώμα.
Να βρείτε τη μέγιστη τιμή του

για την οποία υπάρχει πίνακας $n\times n$ χωρίς κακά κουαρτέτα.
Ποιος είναι ο μέγιστος αριθμός μαύρων κελιών σε αυτήν την περίπτωση;

ΘΕΜΑ 3
Ο Γιώργος έχει στη διάθεσή του απεριόριστα χρώματα. Μια μέρα έβαψε κάθε θετικό ακέραιο με ένα χρώμα. Παρατήρησε ότι:

κάθε περιττός αριθμός έχει χρώμα μπλε.

κάθε ακέραιος έχει το ίδιο χρώμα με τον

κάθε ακέραιος έχει το ίδιο χρώμα με έναν τουλάχιστον από τους αριθμούς και

Να δείξετε ότι ο Γιώργος έβαψε όλους τους ακεραίους μπλε.

ΘΕΜΑ 4
Έστω

πρώτος και

ακέραιος, που δεν διαιρείται με τον

Να δείξετε ότι υπάρχουν άπειροι ακέραιοι

τέτοιοι ώστε ο αριθμός

να διαιρεί τον q^k + 1 − k.

ΦΩΤΙΑΔΗΣ ΠΡΟΔΡΟΜΟΣ · #2

socrates έγραψε: ↑
Πέμ Μαρ 12, 2020 12:37 am
ΘΕΜΑ 1
Ένα σύνολο $\mathfrak{D}$ αποτελείται από ευθείες του επιπέδου. Κάθε ευθεία του συνόλου $\displaystyle{\mathfrak{D}}$ τέμνει ακριβώς άλλες ευθείες του $\displaystyle{\mathfrak{D}.}$ Να βρείτε το

Κάθε ευθεία τέμνεται με ακριβώς 2011

άλλες άρα είναι παράλληλη με ακριβώς n-2012

.Δηλαδή οι ευθείες εμφανίζονται σε ''ομάδες'' από παράλληλες που η κάθε ''ομάδα'' έχει n-2011

ευθείες.Πρέπει λοιπόν $n-2011\mid 2011\Rightarrow n=2012,n=4022$ (αφού ο 2011

είναι πρώτος).
Και οι δύο τιμές είναι δεκτές.Στην πρώτη υπάρχουν 2012

ευθείες ανά δύο τεμνόμενες και στην δεύτερη υπάρχουν

''ομάδες'' ευθειών με κάθε ομάδα να έχει 2011

ευθείες ,όπως το παρακάτω σχήμα.

: 264.PNG (29.6 KiB) Προβλήθηκε 980 φορές

ΦΩΤΙΑΔΗΣ ΠΡΟΔΡΟΜΟΣ · #3

socrates έγραψε: ↑
Πέμ Μαρ 12, 2020 12:37 am
ΘΕΜΑ 3
Ο Γιώργος έχει στη διάθεσή του απεριόριστα χρώματα. Μια μέρα έβαψε κάθε θετικό ακέραιο με ένα χρώμα. Παρατήρησε ότι:

κάθε περιττός αριθμός έχει χρώμα μπλε.

κάθε ακέραιος έχει το ίδιο χρώμα με τον

κάθε ακέραιος έχει το ίδιο χρώμα με έναν τουλάχιστον από τους αριθμούς και
Να δείξετε ότι ο Γιώργος έβαψε όλους τους ακεραίους μπλε.

Έστω

ο ελάχιστος άρτιος (θετικός) ο οποίο δεν είναι μπλε. Αν $4\mid n$ τότε ο $k=\dfrac{n}{4}$ είναι φυσικός και όχι μπλε άτοπο αφού ο

είναι ο ελάχιστος τέτοιος. Άρα $n\equiv 2\pmod4$ ,έστω επίσης

το χρώμα του

.Επειδή $n+2\equiv 0\pmod4$ θα πρέπει ο n+2

να είναι μπλε. Έτσι από την τρίτη συνθήκη ο n+4

θα είναι χρώματος

.Όμοια λοιπόν όλοι οι αριθμοί χρώματος

είναι της $n+4k,k\in \mathbb{N}$ και μόνο αυτοί. Αφού όμως ο

είναι χρώματος

θα πρέπει

για κάποιο

το οποίο όμως είναι αδύνατο αφού $n\not\equiv 0\pmod4$ , και έτσι έπεται το ζητούμενο αφού δεν μπορεί να υπάρχει

με χρώμα διάφορο του μπλε.

ΦΩΤΙΑΔΗΣ ΠΡΟΔΡΟΜΟΣ · #4

socrates έγραψε: ↑
Πέμ Μαρ 12, 2020 12:37 am
ΘΕΜΑ 4
Έστω πρώτος και ακέραιος, που δεν διαιρείται με τον
Να δείξετε ότι υπάρχουν άπειροι ακέραιοι τέτοιοι ώστε ο αριθμός να διαιρεί τον

Αρκεί να δείξουμε πως υπάρχουν άπειροι

ώστε $p \mid q^k+1-k,q \mid q^k+1-k$ οπότε αφού (p,q)=1

θα έχουμε το ζητούμενο.
Επειδή από το μικρό Fermat είναι $q^{p-1}\equiv 1\pmodp$ θέτουμε $k\equiv 0 \pmod {p-1}$ οπότε έστω k=a(p-1)

.Τότε $q^k+1-k\equiv q^{a(p-1)}+1-(p-1)a\equiv 2-ap+a\equiv a+2\pmod p$ άρα για να είναι $p \mid q^k+1-k$ αρκεί $a\equiv -2\pmod p$ .Δηλαδή αν a=bp-2

θα έχουμε

.
Ακόμα πρέπει $q^k+1-k\equiv 0\pmodq\Leftrightarrow k\equiv 1\pmod q$ .
Αρκεί λοιπόν $bp-2=(lq+1)\cdot (p-1)^{\varphi (q)-1},l\in \mathbb{N}$ ,και για να είναι

φυσικός αρκεί $(lq+1)(p-1)^{\varphi (q)-1}+2\equiv 0\pmod p\overset{\varphi (q)\equiv 0\pmod 2}{\Leftrightarrow} (-1)(lq+1)+2\equiv 0\pmod p\Leftrightarrow$
$\Leftrightarrow -lq+1\equiv 0\pmod p\Leftrightarrow lq\equiv 1\pmod p$ .
Άρα αρκεί $l = (mp+1)\cdot q^{\varphi (p)-1},m\in \mathbb{N}$
Έτσι παίρνουμε $b=\dfrac{\left ((mp+1)q^{\varphi (p)}+1 \right )\cdot (p-1)^{\varphi (q)-1}}{p}$

Λύση λοιπόν κάθε

της μορφής :
$k=\left (\left ((mp+1)q^{\varphi (p)}+1 \right )\cdot (p-1)^{\varphi (q)-1} -2 \right )(p-1),m\in \mathbb{N}$

#5

socrates έγραψε: ↑
Πέμ Μαρ 12, 2020 12:37 am
ΘΕΜΑ 2
Βάφουμε καθένα από τα κελιά ενός πίνακα $n \times n$ είτε μαύρο είτε άσπρο. Τα τέσσερα σημεία τομής δύο γραμμών και δύο στηλών ορίζουν ένα κουαρτέτο. Ένα κουαρτέτο λέγεται κακό όταν όλα τα κελιά του έχουν το ίδιο χρώμα.
Να βρείτε τη μέγιστη τιμή του για την οποία υπάρχει πίνακας $n\times n$ χωρίς κακά κουαρτέτα.
Ποιος είναι ο μέγιστος αριθμός μαύρων κελιών σε αυτήν την περίπτωση;

ΕΜΦΑΝΙΣΗ ΚΕΙΜΕΝΟΥ

ΦΩΤΙΑΔΗΣ ΠΡΟΔΡΟΜΟΣ · #6

socrates έγραψε: ↑
Πέμ Μαρ 12, 2020 12:37 am
ΘΕΜΑ 2
Βάφουμε καθένα από τα κελιά ενός πίνακα $n \times n$ είτε μαύρο είτε άσπρο. Τα τέσσερα σημεία τομής δύο γραμμών και δύο στηλών ορίζουν ένα κουαρτέτο. Ένα κουαρτέτο λέγεται κακό όταν όλα τα κελιά του έχουν το ίδιο χρώμα.
Να βρείτε τη μέγιστη τιμή του για την οποία υπάρχει πίνακας $n\times n$ χωρίς κακά κουαρτέτα.
Ποιος είναι ο μέγιστος αριθμός μαύρων κελιών σε αυτήν την περίπτωση;

Για αρχή δείχνω πως για n=5

είναι αδύνατον.
Έστω ότι κατασκευάστηκε τέτοιος πίνακας:
Έστω χωρίς βλάβη της γενικότητας ότι τα μαύρα κελιά είναι περισσότερα από τα λευκά,με βάση αυτό ο αριθμός των μαύρων κελιών είναι $\geq 13$ .Αν υπάρχει στήλη με

μαύρα τότε όλες οι υπόλοιπες έχουν το πολύ από ένα άρα συνολικά έχουμε το πολύ 5+1+1+1+1=9<13

μαύρα κελιά άτοπο!Αν υπάρχει στήλη με 4 μαύρα κελιά τότε κάθε άλλη έχει το πολύ 4+2+2+2+2=12<13

μαύρα κελιά άτοπο.Άρα κάθε στήλη έχει το πολύ

μαύρα κελιά.Τώρα αν οι στήλες με

μαύρα κελιά είναι λιγότερες από

τότε τα μαύρα κελιά είναι το πολύ 3+3+2+2+2=12<13 άτοπο.Άρα υπάρχουν σίγουρα

στήλες οι οποίες έχουν

μαύρα κελιά η καθεμιά.Θα δείξω ότι σε αυτές τις τρεις στήλες υπάρχει σίγουρα κακό κουαρτέτο.Χρωματίζουμε την πρώτη από αυτές,τότε για τα μαύρα κελιά της δεύτερης μόνο ένα μπορεί να βρίσκεται σε γραμμή στην οποία στην πρώτη στήλη υπάρχει μαύρο κελί.Έτσι σε αυτή θα πρέπει να χρωματίσουμε τα

κελιά των οποίων οι γραμμές δεν περιέχουν στην πρώτη στήλη μαύρο κελί και ένα ακόμη κελί.
Τώρα στην τρίτη στήλη όμοια θα χρωματίσουμε τα

κελιά των οποίων οι γραμμές δεν περιέχουν στην πρώτη στήλη μαύρο κελί και ένα ακόμη κελί.Τότε όμως δημιουργείτε αναγκαστικά κακό κουαρτέτο.,π.χ ένα σχήμα

: 284.PNG (3.92 KiB) Προβλήθηκε 784 φορές

Έτσι $4\geq n$ .Για n=4

έχουμε τον εξής δεκτό χρωματισμό

: 285.PNG (3.31 KiB) Προβλήθηκε 784 φορές

Τεστ Εξάσκησης (25), Μικροί

Τεστ Εξάσκησης (25), Μικροί

Re: Τεστ Εξάσκησης (25), Μικροί

Re: Τεστ Εξάσκησης (25), Μικροί

Re: Τεστ Εξάσκησης (25), Μικροί

Re: Τεστ Εξάσκησης (25), Μικροί

Re: Τεστ Εξάσκησης (25), Μικροί

Μέλη σε σύνδεση