Saturday, January 31, 2009

Another quick "2009" stuff

Let



and let




be a function satisfying






Then f has at least one fixed point, that is, there exists an element x in X such that f(x)=x.

Indeed, it is not hard to see that f is a bijection and induces a permutation of X in which all cycles are either of length 3 or 1 (those of length one correspond to the fixed points of f ). Since 2009 is not divisible by 3, there must be a cycle of length 1.

A complicated way of characterizing the constant functions

Show that the constant functions are the only continuous functions




satisfying






for all real numbers x,y.

Wednesday, January 28, 2009

Squares and walks


The (quasi-) random walk represented in the picture corresponds to the cubic polynomial
f(X) = X^3-X-1 mod 2003.
Every step is a unit step. The n-th step is made to the right if f(n) is a perfect square modulo 2003, and to the left, if f(n) is a non-square.

Sunday, January 25, 2009

Factorials and squares

If N > 1, then N! is not a perfect square.

Indeed, let N > 1 and let p be the largest prime that is less than or equal to N. Then 2p cannot be less than or equal to N - otherwise, a prime q greater than p and less than 2p (such a q exists by Bertrand's theorem), would be a prime greater than p that is less than or equal to N. Thus p defined as above appears with an exponent of 1 in the prime decomposition of N! and therefore N! cannot be a perfect square if N > 1.

Tuesday, January 20, 2009

Un sir neperiodic

Sa consideram sirul binar a_n, n=0,1,2,... definit dupa cum urmeaza:

a_n=0, daca scrierea lui 2^n in baza 10 are un numar par de cifre, si a_n=1, in caz contrar.
Sa se arate ca {a_n} nu este "eventual periodic" (nu exista un intreg pozitiv k astfel incat egalitate a_{n+k}=a_n are loc pentru orice n suficient de mare). Aceasta problema (plus variatii pe aceeasi tema) a constituit o tema de "undergraduate research" pe care am propus-o unui student, acum 6 ani. Este o modalitate frumoasa de a introduce teorema de distributie uniforma in [0,1] a partilor fractionare ale multiplilor unui numar irational.

Saturday, January 17, 2009

On Putnam A1/2008






This is problem A1 from the 2008 Putnam Exam.
The proof is quite straightforward:






















Thursday, January 15, 2009

"modulo n"...

Pentru fiecare n > 1 "inelul intregilor modulo n" Z/nZ consta din 0,1,...,n-1, adica toate resturile ce pot fi obtinute la impartirea cu n. Aceste elemente nu sunt "numere intregi obisnuite", similaritatea in notatie putand fi inselatoare. Astfel, "0"-ul lui Z/nZ reprezinta toti intregii care dau restul 0 la impartirea cu n, "1"-ul lui Z/nZ reprezinta toti intregii care dau restul 1 la impartirea cu n, si asa mai departe. Z/nZ este un univers aparte, in care se definesc o "adunare modulo n" si o "inmultire modulo n". Ideea este simpla: sa ne imaginam ca adunam/inmultim "normal" si, in cele din urma, pentru a identifica rezultatul adunarii/inmultirii in Z/nZ vom scrie numai restul adunarii/inmultirii "normale" la impartirea cu n. De exemplu: in Z/3Z = {0,1,2} avem 1+2=0, 2+2=1, 2^9=2, iar (X+Y)^3=X^3+Y^3 este o identitate valida! Putem considera "19" ca element al lui Z/3Z? Sigur! Iarasi, pentru a-l identifica pe 19, vom lua restul lui 19 la impartirea cu 3 - astfel, 19=1 in Z/3Z. Asemenea identificari sunt uneori foarte utile. De exemplu care dintre elementele 0,1,...,8 ale lui Z/9Z il reprezinta pe 11^99? In sfarsit, ca aplicatie la ecuatii in numere intregi, sa se arate ca ecuatia 3*X^2-Y^2=1 nu are solutii in numere intregi. 

Wednesday, January 14, 2009

2009

Since we are at the beginning of 2009, I will try to break the ice with a list of problems involving the number 2009.
  1. Factor 2009.
  2. Write 2009 as a sum of two squares: 2009=x^2+y^2 with integers x and y.
  3. If x and y are integers and if x^2+y^2 is a multiple of 2009, is it true that both x and y must be multiples of 7?
  4. How many zeros are there at the end of 2009! ?