Problemas Teoremas

Dezembro 31, 2009

Maximum of the produt of k positive integers, the sum of which is 100. Problem by Vishal Lama and a solution by Neil Dickson

Filed under: Matemática,Math,Number Theory,Problem,Problemas,Teoria dos Números — Américo Tavares @ 9:44 am
Tags: , , ,

Problem by Vishal Lama. Maximize the value of the expression \displaystyle \prod_{j=1}^{k} x_j, for some positive integer k, where \displaystyle \sum_{j=1}^{k} x_j = 100 and x_js are all positive integers.

My (corrected) guess (Ansatz). The solution to your problem seems to be satisfied by k=33+2=34 variables, such as x_{1}=x_{2}=\ldots =x_{32}=3,x_{33},x_{34}=2.
 
Thus x_{1}x_{2}\cdots x_{32}x_{33}x_{34}=3^{32}2^2. If this is correct

 x_{1}=x_{2}=\ldots =x_{32}=\left\lceil e\right\rceil .

For x_{1}=x_{2}=\ldots =x_{49}=x_{50}=\left\lfloor e\right\rfloor =2, the product is only 2^{50}<3^{33}.

I noticed that the function x\longmapsto\dfrac{x}{e^{\ln x-1}}=e and 2<e<3. I have not yet a rigorous argument.

Solution by Neil Dickson. The maximum is 3^{32}2^2.

Rough proof:
It’s definitely the case that no factor can be 1 in the maximum, since the 1 could just be added to any other factor to increase the product.  It’s also true that for any integer 5 or greater, 3(n-3)>n, so it could be split into 3 and n-3 to give a larger product and equal sum.  Any 4 can be split into 2 and 2 giving the same sum and product.  Therefore only 2 and 3 are needed to represent the maximum.  Because 2^3<3^2, maximizing the number of 3′s should give the maximum product.  The maximum number of 3′s you can fit into 100 with an even remainder is 32, leaving 4, which is two 2′s.

This turns out to also be equivalent to asking “What’s the maximum number of maximal independent sets that can occur in a graph of 100 nodes?”  The graph that satisfies this condition is just 32 K_3‘s and 2 K_2‘s (it’s 34 disconnected components, but it’s still a graph).  I’ve been using this lately to construct very bad cases to test out a couple of quantum algorithms I’ve been working on.

Abril 24, 2009

Congruences and Divisibility — A Purdue University Problem

Filed under: Congruences,Math,Number Theory,Problem,Purdue University — Américo Tavares @ 12:59 pm
Tags: ,

pdf: ver caderno

Versão portuguesa aqui

PROBLEM OF THE WEEK, Problem No. 12 (Spring 2009 Series):

“ Problem. For how many positive integers x\leq 10,000 is 2^{x}-x^{2} not divisible by 7?

Justify your answer without the use of computers. ”

Here is my solution (accepted).

If a\equiv b\quad \left( \text{mod }m\right) , then a^{n}\equiv b^{n}\quad\left( \text{mod }m\right) . Applied to 2^{n} this property gives in general for n=3k+s,1\leq s\leq 3,0\leq k

2^{n}\equiv 2^{s}\quad\left( \text{mod }7\right) ,\quad (1)

which means that the remainders of the division of 2^{n} by 7 form a periodic sequence of length 3 starting at n=1

\overset{\text{period}}{\overbrace{2,4,1}},\overset{3\text{ terms}}{\overbrace{2,4,1}},\ldots .

As for n^{2} since (a) if a\equiv b\quad \left( \text{mod }m\right) and c\equiv d\quad \left( \text{mod }m\right) , then a+c\equiv b+d\quad \left( \text{mod }m\right) and (b) if a\equiv b\quad \left( \text{mod }m\right) , then a^{2}\equiv b^{2}\quad \left( \text{mod }m\right) , we have in general for n=7j+r,1\leq r\leq 7,0\leq j

n^{2}\equiv r^{2}\quad\left( \text{mod }7\right)\quad (2)

which means that the remainders of the division of n^{2} by 7 form a periodic sequence of length 7 starting at n=1

\overset{\text{period}}{\overbrace{1,4,2,2,4,1,0}},\overset{7\text{ terms}}{\overbrace{1,4,2,2,4,1,0}},\ldots .

If a\equiv b\quad \left( \text{mod }m\right) and c\equiv d\quad \left( \text{mod }m\right) , then a-c\equiv b-d\quad \left( \text{mod }m\right) . Let u_{n}=2^{n}-n^{2}. Therefore from (1) and (2) we have

u_{n}\equiv 2^{s}-r^{2}\quad \left( \text{mod}7\right) .\quad (3)

The remainders of the division of u_{n} by 7 form another periodic sequence of length 21=\text{lcm}(3,7) which starts also at n=1. Four examples of the evaluation of these remainders are presented below.

For 1\leq n\leq 21 the following 15 terms are not divisible by 7:

u_{1},u_{3},u_{7},u_{8},u_{9},u_{11},u_{12},u_{13},u_{14},u_{16},u_{17},u_{18},u_{19},u_{20},u_{21}.

Hence for 1\leq n\leq 9996=21\times \left\lfloor \dfrac{10000}{21}\right\rfloor , there are 15\times\left\lfloor \dfrac{10000}{21}\right\rfloor =7140 terms that are not divisible by 7.

From the remaining 4 terms u_{9997} and u_{9999}  are not divisible by 7, which gives a total of 7140+2=7142 numbers u_{n}=2^{n}-n^{2} not divisible by 7.

Four examples of the evaluation of the remainders:

u_{9}=2^{9}-9^{2}

(9=3\times 2+3,s=3,9=7\times 1+2,r=2)

2^{9}\equiv 2^{3}\quad\left(\text{mod }7\right) \equiv 1\quad\left(\text{mod }7\right)

9^{2}\equiv 2^{2}\quad\left(\text{mod }7\right) \equiv 4\quad\left(\text{mod }7\right)

u_{9}\equiv 2^{3}-2^{2}\quad\left(\text{mod }7\right) \equiv -3\quad\left(\text{mod }7\right)

u_{10}=2^{10}-10^{2}

(10=3\times 3+1,s=1,10=7\times 1+3,r=3)

2^{10}\equiv 2^{1}\quad\left(\text{mod }7\right) \equiv 2\quad\left(\text{mod }7\right)

10^{2}\equiv 3^{2}\quad\left(\text{mod }7\right) \equiv 2\quad\left(\text{mod }7\right)

u_{10}\equiv 2^{1}-3^{2}\quad\left( \text{mod }7\right)\equiv 0\quad\left( \text{mod }7\right)

u_{9997}=2^{9997}-9997^{2}

(9997=3\times 3332+1,s=1,9997=7\times 1428+1,r=1)

2^{9997}\equiv 2^{1}\quad\left(\text{mod }7\right) \equiv 2\quad\left(\text{mod }7\right)

9997^{2}\equiv 1^{2}\quad\left(\text{mod }7\right) \equiv 1\quad\left(\text{mod }7\right)

u_{9997} \equiv 2^{9997}-9997^{2}\quad \left( \text{mod}7\right) \equiv 1\quad \left( \text{mod }7\right)

u_{9998}=2^{9998}-9998^{2}

(9998=3\times 3332+2,s=2,9998=7\times 1428+2,r=2)

2^{9998}\equiv 2^{2}\quad\left(\text{mod }7\right) \equiv 4\quad\left(\text{mod }7\right)

9998^{2}\equiv 2^{2}\quad\left(\text{mod }7\right) \equiv 4\quad\left(\text{mod }7\right)

u_{9998} \equiv 2^{9998}-9998^{2}\quad \left( \text{mod}7\right) \equiv 0\quad \left( \text{mod }7\right)

Remark: typos corrected. [In the 2nd. last paragraph before the examples: "there are"  added]

Edited: May 29, 2009: Portuguese version removed and posted here

Outubro 2, 2008

My solution to the Problem Of the Week-9 [Todd and Vishal's blog]: Period of a decimal expansion

Filed under: Caderno,Matemática,Math,Number Theory,Problem,Problemas,Teoria dos Números — Américo Tavares @ 5:12 pm
Tags: , ,

pdf: included in Caderno (see “caderno” page)

I submitted a solution to the following Problem that  was accepted.

Find the length of the period of the repeating decimal representation of \dfrac{1}{65537}.

My Solution:

The repeating decimal representation of the number 1/65537 is

\dfrac{1}{65537}=0.\overset{65536\text{ digits}}{\overline{000\,015\,258\,556\ldots cba}}\quad.

Let p be a prime number. The period of the repeating decimal of 1/p is equal to the order  of 10 (\mod p\; ) and is either p-1 or a divisor of p-1. Since 65537 is a prime number, the period of the repeating decimal of 1/65537 is therefore either 65536 or a divisor of 65536=2^{16}. These divisors are

k=2^{0},2^{1},2^{2},2^{3},\ldots ,2^{16}.

By the definition of the order of 10 (\mod 65537\; ), I have to find the smallest of these k=2^{m} such that

10^{k}\equiv 1\; (\mod 65537),

which means (10^{(2^{m})}-1)/65537 should be an integer.

Since

10-1<10^{2}-1<10^{3}-1<10^{4}-1<65537,

the remaining cases are m=3,4,\ldots ,16. From these I have checked in PARI that only

\dfrac{10^{65536}-1}{65537}=669179\ldots 526527

is an integer (*). For instance

\dfrac{10^{16}-1}{65537}=\dfrac{999999999999999}{65537}\notin\mathbb{Z}.

Conclusion. The length of the period of the repeating decimal representation of \dfrac{1}{65537} is 65536.

(*) Edited a little bit to improve the English text. \qquad \blacktriangleleft

A much more sophisticated and elegant solution by Philipp Lampe was posted by one of the authors of this excellent advanced mathematical blog.

Tema: Rubric. Blog em WordPress.com.