For a sum x1+x2+..xN= T, what is the maximum value of N, if all terms are positive and the sum of any two adjacent terms is no less than a positive integer W > 1? In other words, what is the length of the longest such sequence?Within the set of all valid sequences, there is a number of sequences which have the maximal length. Let's call this set M.
Let's assume that
K= (k1, k2, ... ki=A, ki+1=B, ki+2 ..., kN) and A+B = 2W-2 + z, where z > 0If that was the case, we could simply redistribute A and B to three terms to make a longer sequence Y:
Y= (y1=k1, y2=k2, ... yi=W-1, yi+1=z, yi+2=W-1, yi+3=ki+2 ..., yN+1=kN)Since K was specified to be a maximal sequence, such a construction should be impossible. Hence no such K exists.
Let's assume that for some K ∈ M and some i, Ki = 2*W-1+z where z is a non-negative integer. In this case, we can form a new sequence Y such that:
y1=k1, y2=k2, .. yi-1= ki-1 yi = W-1 yi+1=ki+1, yi+2=ki+2, .. yN=kN yN+1 = W+zWe know that Y is valid because:
yi-1 = ki-1 ≥ 1 yi = W-1 + yi = W-1 yi+1 = ki+1 ≥ 1 ---------------------------------------- ≥ W ≥ WWe know that the sum of the last two terms of Y also obeys our rule since YN+1 is already no less than W by itself. Adding the previous term can only increase the sum since it's positive. We have constructed a sequence longer than K but that's a contradiction because K was chosen from M, the set of maximal sequences. This means that there is no such K ∈ M where Ki ≥ 2*W for some i.
Let's assume ki=W-1+z where z>0. We know that i can not be equal to N. If that was the case, then we could split kN into two parts, kN=W-1 and kN+1=z. This would result in a longer sequence, and thus can not happen.
From Lemma 0:
ki+ki+1 ≤ 2W-2 W-1 + z + ki+1 ≤ 2W-2 ki+1 ≤ W-1-zNow, if we subtract z from ki and add it to ki+1, we eliminate the big number and get another valid sequence:
ki = W-1+z - z = W-1 ki+1 ≤ W-1-z + z = W-1 ki+1 ≤ W-1If we do this simultaneously for all such i, we get a sequence where the maximum value is W-1.
gi = W-1 , if ki ≥ W gi = ki + ki-1-(W-1), if ki-1 ≥ W gi = ki, otherwiseNow that I have proven that all such K can be transformed according to Lemma 2, I'll consider only sequences consisting of numbers in [1..W-1]. I'll call this subset of M, Q.
Q= { G | G ∈ M and gi ≤ W-1 for all i }
Show that for positive a, b, c, end d, such that abcd=1, a^2 +b^2+c^2+d^2 + ab+ac+ad+bc+bd+cd is not smaller then 10.Some notation is in order:
F(a,b,c,d)= a^2+b^2+c^2+d^2+ab+ac+ad+bc+bd+cdF(1,1,1,1) is 10. I'll try to show that we can move from (1,1,1,1) to any other coordinate and the value of the function will still be greater than 10. First of all, let's assume that we multiply one of the coordinates by X and one of the others by 1/X. The new coordinates will be:
Xa, b/X, c,dLet's calculate F on these coordinates
F(Xa,b/X,c,d)= X2a2+ b2/X2+ c2+ d2 + Xab/X + Xac + Xad + bc/X + bd/X + cd F(a,b,c,d)= a2+ b2+ c2+ d2 +ab+ ac+ ad+ bc+ bd+ cd M= F(Xa,b/X,c,d) - F(a,b,c,d)= (X2-1)a2 + (1/X2-1)b2 + (Xa-a)(c+d) (b/X-b)(c+d) = (X2-1)a2 - (1-1/X2)b2 + (c+d)a(X-1) + (c+d)b(1/X-1) = (X2-1)a2 - (X2-1)/X2b2 + (c+d)[ a(X-1) - b(X-1)/X ] = (X2-1) (a2 - b2/X2) + (c+d)(X-1)(a-b/X) = (X-1)(a-b/X)[ (X+1)(a+b/X) + (c+d) ]Now, we want M to be always non-negative. The part in square brackets is always positive, so it doesn't contribute a sign to M. We're left with
U= (X-1)(a-b/X)If our selection of X makes U non-negative, then F(Xa,b/X,c,d) will be at least 10. For selecting X, we now have two rules:
Now, we're left with three cases
Position | Result | |||||||||
Ca | Cb | Cc | Cd | X | X≥1? | X≥green/red? | Ca | Cb | Cc | Cd |
1 | 1 | 1 | 1 | a | a≥1 | a≥1/1 | a | A | 1 | 1 | a | A | 1 | 1 | ab | ab≥1 | [1] | a | b | AB | 1 |
a | b | AB | 1 | abc | abc≥1 | [2] | a | b | c | ABC |
Position | Result | |||||||||
Ca | Cb | Cc | Cd | X | X≥1? | X≥green/red? | Ca | Cb | Cc | Cd |
ad | b | c | 1 | D | D≥1 | [3] | a | b | c | d |
I have shown that we can reach any point from (1,1,1,1) without violating our rules for the selection of X. Making such selections, we guaranteed to not reduce the value of F. F(1,1,1,1) is 10, so all values of F are at least 10.
Interestingly, the rules for choosing X don't depend on the number of variables. As long as you can show these movements, value of F will never go below F(1*).
k | |||||
1 | a | ||||
2 | a2 | a2 | |||
3 | a3 | a3 | a3 | ||
.. | .. | ||||
n | an | an | an | .. | an |
k.j | 1 | 2 | 3 | .. | n |
1 | a | ||||
2 | a2 | a2 | |||
3 | a3 | a3 | a3 | ||
.. | .. | ||||
n | an | an | an | .. | an |
(a->b) & (b->c) -> (a->c)We have:
(a->b) == a'+bLet's go:
(a->b) & (b->c) -> (a->c) ((a->b) & (b->c))' + (a->c) (a->b)' + (b->c)' + (a->c) (a'+b)' + (b'+c)' + (a->c) ab' + bc' + a'+cWe can easily AND the complex terms with the value TRUE:
ab' = ab'(c+c') = ab'c+ ab'c' bc' = (a+a')bc' = abc'+ a'bc'So, the last form becomes:
ab' + bc' + a'+c ab'c+ ab'c' + abc'+ a'bc' + a' +c ---- - Factor by a': ab'c+ ab'c' + abc' + a'(bc'+1) + c ab'c+ ab'c' + abc' + a' + c ---- - Factor by c: ab'c' + abc' + a' + c(1+ab') ab'c' + abc' + a' + c ---- --- Factor by ac': ac'(b'+b) + a' + c ac' + a' + c Now, observe that a'+c = (ac')' ac' + (ac')' = 1.
(a->b+c) -> ( a+b -> b+c ) (a'+b+c) -> [ (a+b)' + b + c ] (a'+b+c) -> ( a'b' + b + c ) (a'+b+c)' + a'b' + b + c ab'c' + a'b' + b + cJust like above, let's AND a'b' with TRUE:
ab'c' + a'b' + b + c // a'b'= a'b'c + a'b'c' ab'c' + a'b'c + a'b'c' + b + c - - Factor by c : ab'c' + a'b'c' + b + c(1+a'b') ab'c' + a'b'c' + b + c --- --- Factor by b'c' : b'c'(a+a') + b + c b'c' + b + c Again, we observe that b+c = (b'c')' b'c' + (b'c')' = 1.
Show that for any natural n, at least one of two numbers, n or n+1, can be represented in the following form: k + S(k) for a certain k, where S(k) is the sum of all digits in k. For instance, 21 = 15 + (5+1).I'll try to solve it here. Let's first reformulate the problem:
F(y)= y + S(y) P(n) iff F(k) = n for some k L(n) iff P(n) or P(n+1).I already know that L(n) is true for small numbers 4=2+2, 6=3+3 etc. I need to show:
L(n) -> L(n+1)If I expand it:
P(n) or P(n+1) -> P(n+1) or P(n+2) .. ST-1It's sufficient to prove:
P(n) -> P(n+1) or P(n+2) .. ST-2Since ST-1 is true whenever ST-2 is true (i.e. ST-2 implies ST-1). So, given P(n) if I can construct a valid P(n+1) or P(n+2), I'm done.
Let's assume P(n), ie. for some k, F(k) = n.
F(k) = k + S(k) = nI won't consider single-digit values for k, I can simply list the corresponding n-values for those and don't really need this proof for small numbers. Basicly, for k <= 9, n= 2*k. So we're concerned with n>18.
There are two cases here, either k ends with a 9 or not. The first case is easy:
k = B|a , B= arbitrary string (not including null), 0<=a<9 k+1 = B|c , c= a + 1 The | symbol is the concatentation operator, a and c are digits. S(B|c) = S(B|a) + 1 F(k+1)= k + 1 + S(k+1) = k + 1 + S(B|c) = k + 1 + S(B|a) + 1 = k + S(B|a) + 2 = F(k) + 2 = n + 2I've constructed k' = k+1 from k and reached at F(k')= n +2. For a given n, we find the corresponding k (which doesn't end with a 9) and then construct n+2 using that. So, the preposition now holds for n+1 if this is the case, since one of n+1 and n+2 can be written as F(k'). What happens if there is no such k, ie. k ends with a 9?
k= B|a|9[z] , B= arbitrary, a!=9, followed by z-9s, z>0 S(k)= S(B|a|9[z]) = S(B) + S(a) + 9z .. EQ-1Let's look at what happens to F(k+1):
k + 1 = B|a|9[z] + 1 = B|c|0[z] , c= a +1 S(k+1)= S(B|c|0[z]) = S(B) + S(c) = S(B) + S(a) + 1 , S(c)= S(a) +1 = S(k) - 9z + 1 , S(B)+S(a) is S(k) - 9z , from EQ-1 .. EQ-3 F(k+1)= k+1 + S(k+1) = k+1 + S(k) - 9z + 1 = k+S(k) + 2 - 9z = F(k) + 2 - 9z = n + 2 - 9zIt didn't quite work, but we have some clue. L(9z-1) should also be true since 9z-1 < n:
n= F(k) = k + S(k) n > k , S(k) >= 1 k = B*10^(z+1) + c*10^z + 9*10^(z-1) + 9*10^(z-2) .. 9*1 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ z terms, each not less than 9 k >= 9z n > k > 9z-1Since L(9z-1) is true, one of the following is true:
F(u)= 9z + j, j in {0,-1} .. EQ-4I'll now construct a string from u by padding it to the left by zeroes so that its total length is z.
u= Y V= 00..0|Y ^^^^^^^ z digitsThe numerical value of V is simply u. I will use this string to construct a k' from a known k.
k'= B|c|V F(k')= B|c|0[z] + u + S(B|c|V) = k+1 + u + S(B|c|0[z]) + S(V) = k+1 + S(k+1) + u + S(V) = k+1 + S(k) -9z +1 + u + S(V) , from EQ-3 = k+ S(k) + 2 - 9z + u + S(V) = n + 2 - 9z + F(u) = n + 2 - 9z + 9z + j , from EQ-4 = n + 2 + j , j in {0,-1} for j= 0, F(k') = n +2 for j= -1 F(k') = n +1So, starting with n and k, I computed a k' which gives either F(k')= n+1 or F(k')=n+2. This is what I was looking for. In summary, given F(k)= n
F(k+1) = n+2 if k doesn't end with a 9. F(k') = n+2 or n+1 k = Ba9[z] k'= Bc000..0Y where F(Y)= 9z or 9z-1
There is a group of people at a party. Show that you can introduce some of them to each other so that after the introduction, no more than two people in the group would have the same number of friends (initial configuration doesn't work because they all initially have 0 friends).Let N be the number of people in the group and let's sort the people according to how many other people they know. We will get a string of numbers, where each number is between 1 and N-1. We don't consider the case where somebody doesn't know anyone because it's a party.
For small values of N, it's easy to make the arrangement.
N Arrangement ----------------- 2 1 1 3 1 1 2 4 1 2 2 3 5 1 2 2 3 4In any case, we will end up with a string like this:
1 2 3 ... k k ... N-1When someone comes to the party, we don't introduce him to the first k people in the sorted order. We introduce him to the remaining N-k people.
Already There New Guy ------------------------------------ Before: 1 2 3 ... k k ... N-1 0 After: 1 2 3 ... k k+1 ... N N-k Set k' = N-k Sorted: 1 2 3 ... k' k' ... N -
L(0)= 1 L(1)= 1 L(n)= L(n-1) + L(n-2) + 1 L = 1 1 3 5 9 15 25 41 67 109 ...I saw this smoothsort algorithm on the Internet and on this page, there is some explanation of it. I couldn't understand the proof there, so I made my own. The lemma to be proved is:
Any positive integer can be written as the sum of O(lg n) distinct Leonardo numbers.In the first part, I will show that a sum is possible, without looking at the number of Leonardo numbers used. In the second part, I will prove that this number is O(lg n).
Let's reformulate it as follows:
n = leo_sum(X) leo_sum(X) = SUMi L(Xi), over Xi ∈ XThe lemma holds for the following numbers:
n | sequence | sum |
---|---|---|
1 | L(0) | 1 |
2 | L(0)+L(1) | 1+1 |
3 | L(2) | 3 |
4 | L(1)+L(2) | 1+3 |
Xi > Xj ,if i > jGiven n and X, we will compute Y for (n+1).
n = SUMi L(Xi), where Xi ∈ X n+1 = SUMi L(Yi), where Yi ∈ YLet a be the highest number in X, where a-1 is also an element of X.
If there is no such number, either 0 or 1 isn't an element of X. We simply add 0 or 1 to X in order to obtain Y.
Y = X ∪ { 0 } , 0 ∉ X, a doesn't exist Y = X ∪ { 1 } , 1 ∉ X, a doesn't exist leo_sum(Y) = leo_sum(X) + 1 = n + 1If there is such an a, then we remove a and a-1 from X and add a+1 to obtain Y.
Y= X - { a-1 , a } ∪ { a+1 } , { a-1, a } subsetorequal XWe know that the newly added element a+1 was not already in X because of the definition of a. If (a+1) was already in X, we would have chosen that value. By the definition of Leonardo numbers:
L(a+1) = L(a) + L(a-1) + 1 leo_sum(Y) = leo_sum(X) - L(a-1) - L(a) + L(a+1) = leo_sum(X) + 1 = n + 1The second part is done clearly enough in the page I referenced, so I'm going to skip it.
This proof is sufficient, but it doesn't match the one in the referenced page and so doesn't help us with the smoothsort algorithm. I'll do another one.
n= SUM Di*L(i), 0 <= i <= N , Di ∈ { 0, 1 } n= BL( DN DN-1 ... D1 D0 )We want to prove that:
for any positive integer n, there is a sequence x0, x1, ..., xk such that:This translates to our notation as follows:
- SUM L(xi) = n
- x0 < x1 < ... < xk.
- If x0 = 0, then x1 = 1.
- For any i > 0, xi + 1 < xi+1
Any positive integer can be written as a binary-leonardo string of the form:Now, let us construct the binary-leonardo strings for the first few numbers:Where P and R don't contain the substring 11 and M >= 0.
- R 010 0M, or
- P 011 0M
n | string | sum |
---|---|---|
1 | 10 | 1 |
2 | 11 | 1+1 |
3 | 100 | 3 |
4 | 110 | 3+1 |
5 | 1000 | 5 |
6 | 1010 | 5+1 |
n = BL(D)and we want to find G such that
n + 1 = BL(G)Both D and G are of the given forms [1] or [2].
Let us assume that D is of the first form. If we add the number 1 to D, we will have:
n + 1 = BL( R 010 0M ) + 1 , M >= 0 n + 1 = BL( R 01 0M+1 ) + 1 L(0)= 1 n + 1 = BL( R 01 0M+1 ) + L(0) n + 1 = BL( R 01 0M 1 ) G = R 01 0M 1 , M >= 0Here, if M is 0 or 1, then we end up with a string of the second form:
M= 0 G= R 01 1 M= 1 G= R 01 0 1 exchange G0 and G1 G'= R 0 1 1 0If M is 2 or more, we have:
0M = 0K 0 0 , K = M-2 >= 0 G = R 01 0K 0 0 1 exchange G0 and G1 G' = R 01 0K 0 1 0 , K = M-2 >= 0which is of the first form.
Now let's handle the case where D is of the second form. i.e
D= P 011 0M , P doesn't contain substring 11, M >= 0When we add 1 to this number, the substring 011 above gets replaced by 100 because of the definition of the Leonardo numbers:
n = BL( P 011 0M ) n = BL( P 000 0M ) + BL( 011 0M ) n = BL( P 000 0M ) + L(M+1) + L(M) n+1 = BL( P 000 0M ) + L(M+1) + L(M) + 1 n+1 = BL( P 000 0M ) + L(M+2) n+1 = BL( P 000 0M ) + BL( 100 0M ) n+1 = BL( P 100 0M ) G = P 1 0M+2 , M >= 0Since P doesn't contain the substring 11, it can only end with 00, 01 or 10.
P= Y P1 P0 G= Y P1 P0 1 0M+2 P0= 0 G= Y P1 0 1 0M+2 = Y P1 010 0M+1 G is of the first form P1P0= 01 G= Y 0 1 1 0M+2 G is of the second form
For P0=0 case, since P doesn't contain the substring 11, neither does YP1.
So, for both forms of D for n, we computed G for n+1 and showed that this can be done according to the forms we have limited ourselves to.
Dragons have to meet for a brainstorm in a convention center. The delegates have to be selected to provide the maximum efficiency of the brainstorm session. A dragon has any amount of heads, and for any N, any amount of N-headed dragons is available if needed. The problem is that the size of the convention center is limited so no more than 1000 heads can fit into the assembly hall. The intellectual power of a dragon pack is the product of head numbers of dragons in the pack. How should an optimum pack look like (the total number of dragons, the head number distribution)?Obviously, no dragon should have just one head, such a dragon would eat up one head space from the total 1000 and not contribute any power at all.
Let's assume that 3 dragons have 2 heads in the pack. They total 2+2+2=6. 6 heads could better be redistributed as 3+3 heads which contributes 9 to the pack's power instead of 8. So, this case also doesn't occur in the optimum pack. It has at most 2 dragons with 2 heads.
Let's consider the number 4. If a dragon has 4 heads, it could be replaced by two dragons with 2 heads each. The sum is the same, the product is the same and there is no other way to improve the situation. For convenience, we can split all 4 headed dragons in this way without any change to the total pack power. I will do this and ban the number 4 from the pack.
How about numbers greater than 4? Let p > 4 be the head count of a dragon in the pack. If it's odd, this number can be written as:
p= 2k + 1 for integer k ≥ 2We see that, if we replace each such dragon with two dragons who have k and k+1 heads, we improve the product.
p= 2k + 1 p0= k , p1= k+1 p0*p1 = k^2 + k k^2 + k > 2k + 1 k^2 > k + 1 since k ≥ 2Before the split, the dragon contributed p amount of power to the pack. After the split, the two new dragons contribute p0*p1 amount of power, which is greater than p. So, no odd number greater than 4 can occur in the optimum pack.
Similar reasoning applies to even-headed dragons:
p= 2k p0= k , p1= k p0*p1= k^2 k^2 > 2k since k > 2So, we have banned
We already know that no more than two dragons can have 2 heads. Let's consider the cases.
2-headed | 3-headed | Total | Power | Power/3^332 |
0 | 333 | 999 | 3^333 | 3 |
1 | 332 | 998 | 2*3^332 | 2 |
2 | 332 | 1000 | 2^2*3^332 | 4 |
Interestingly, we didn't use the number 1000 until the very end. All other arguments work for any arbitrary number of total heads. The following gives the formula for N total heads:
N | 2-headed | 3-headed | Power |
3k | 0 | k | 3^k |
3k+1 | 2 | k-1 | 4*3^(k-1) |
3k+2 | 1 | k | 2*3^k |
Does the equation, x^2 + y^3 = z^4 have solutions in prime numbers? Find at least one if yes, give a nonexistence proof otherwise.Now, let's think about whether x,y,z are odd numbers or not. The parity of the left side must be the same as the right side of the equation. If all of them are odd numbers, the equation doesn't work. Left side becomes even and the right side is still odd. So, at least one of them is 2, the only even prime.
x and y can't be both 2. The left side then becomes 12, which isn't the fourth power of any integer.
x and y can't be both odd primes. In that case, the left side becomes even. This necessiates that z is 2. However, that's impossible. The smallest value for y is 3. When we put that into the sum, we get a negative number for x2 since 24-33 is -11.
So, z isn't 2 and exactly one of x and y is 2. We have two cases:
Case 2 is also easy when think of the equation in mod 3 arithmetic. We have three cases:
If case 2.B is true, then we get the equation:
4 + 12 ≡ z4 (mod 3)
1 + 1 ≡ z4 (mod 3)
2 ≡ z4 (mod 3)
Let's have a look at the powers of numbers in mod3.
z | z2 | z3 | z4 |
0 | 0 | 0 | 0 |
1 | 1 | 1 | 1 |
2 | 1 | 2 | 1 |
Case 2.C is rather trivial: if y ≡ 2 (mod 3), then the equation becomes:
4+ 23 ≡ z4 (mod 3) 1 + 2 ≡ z4 (mod 3) 0 ≡ z4 (mod 3) 0 ≡ z (mod 3) z= 3. (since z is a prime)However, this doesn't work either:
4 + y3 = 34 4 + y3 = 81 y3 = 77This doesn't have an integer solution.