The Code, Part 3

Here is another interesting puzzle from the book (as I stated previously you need the passwords from the pre-selections).

Basil, a friend of mine, gave me this interesting array of numbers. He told me that if I grab any five numbers from it such that none of the numbers shares a row or column with another, then my five chosen numbers will always add up to the same sum. I think he made an error, however, because it does not always seem to verify properly. Exactly where is the glitch and what quantity should go in its place to improve the matrix's reliability?

82	105	87	243	141
77	100	82	142	136
142	165	147	303	201
274	297	279	435	333
63	86	68	224	122

Let's start with some analysis. The claim is that a_1,j1+a_2,j2+a_3,j3+a_4,j4+a_5,j5=const, where j_k≠j_m, ∀k,m∈{1..5}

This implies that, e.g. a_1,j1+a_2,j2=a_1,j2+a_2,j1 or by simplifying it a_1,i+a_2,j=a_1,j+a_2,i. We make this expression even more generic (easy to prove)
a_p,i+a_q,j=a_p,j+a_q,i

Indeed, this is what is happening:
Example 1

82	105	87	243	141
77	100	82	142	136
142	165	147	303	201
274	297	279	435	333
63	86	68	224	122

Or 274+86=63+297

Example 2

82	105	87	243	141
77	100	82	142	136
142	165	147	303	201
274	297	279	435	333
63	86	68	224	122

Or 86+303=165+224

A quick check for all of the 2x2 sub-matrices (stepwise, can be done by a computer program) shows the problem:

82	105	87	243	141
77	100	82	142	136
142	165	147	303	201
274	297	279	435	333
63	86	68	224	122

The answer is, 142 should be replaced by 238.

The Code, Part 2

For the last two weeks I am addicted to The Code. Those, who successfully passed pre-selection, were offered to download a PDF file (you need the passwords from the pre-selection to open it) with even more puzzles.

Here is another one I liked:

A Mathematician's Apology
ABC = A³ + B³ + C³
CDE = C³ + D³ + E³
CDA = C³ + D³ + A³
FED = F³ + E³ + D³
A⋅100 + A⋅10 + D = ?

Now, if you Google for "A Mathematician's Apology", you will come to the following link, which is a book with the same title by Hardy. Section 15 reveals all the solutions for the equation:
x⋅100 + y⋅10 + z = x³ + y³ + z³
where x∈{1..9}, y,z∈{0..9}. They are (1,5,3), (3,7,0), (3,7,1) and (4,0,7).

The pattern is easy to spot now:
(A,B,C) = (1,5,3)
(C,D,E) = (3,7,0)
(C,D,A) = (3,7,1)
(F,E,D) = (4,0,7)
and A⋅100 + A⋅10 + D = 117

However, if (like me) "Google search" isn't (always) an obvious option, the following Java code:

public class Code {
  public static int func(int a, int b, int c) {
    return a*100 + b*10 + c - a*a*a - b*b*b - c*c*c;		
  }

  public static void main(String[] args) {
    for (int a = 1; a < 10; a++) {
      for (int b = 0; b < 10; b++) {
        for (int c = 0; c < 10; c++) {
          if (func(a,b,c) == 0) {
            System.out.println("("+a+","+b+","+c+")");
          }
        }
      }
    }
  }
}                                       

will also return (1,5,3), (3,7,0), (3,7,1) and (4,0,7).

More maths from IMO 2011

Last week I was looking for something on Google. The reason I can't remember what I was looking for is the IMO website (International Mathematical Olympiad) that "accidently" was returned in the search results. So I stuck on resolving one of the exercises for ... 3 days!!!

The problem that attracted my attention was number 3 from IMO 2011:

For any function ƒ:R→R that satisfies:

ƒ(x+y)≤y⋅ƒ(x)+ƒ(ƒ(x)), for ∀x,y∈R

prove that ƒ(x)=0, for all x≤0.

Here is the solution. Few inequalities that will be used later first:

- y=0 ⇒ ƒ(x)≤ƒ(ƒ(x)) (1)

- x=0 ⇒ ƒ(y)≤y⋅ƒ(0)+ƒ(ƒ(0)) ≡ ƒ(x)≤x⋅ƒ(0)+(ƒ(0)) (2)

- ƒ(0)=ƒ(x+(-x))≤-x⋅ƒ(x)+ƒ(ƒ(x)) ≡ ƒ(0)+x⋅ƒ(x)≤ƒ(ƒ(x)) (3)

- ƒ(ƒ(x))=ƒ(x+ƒ(x)-x)≤[ƒ(x)-x]⋅ƒ(x)+ƒ(ƒ(x)) ≡ [ƒ(x) - x]⋅ƒ(x)≥0 (4)

Let's note ƒ(0)=c and rewrite/expand the above expressions:

- from (1) ⇒ c≤ƒ(c) (1A)

- from (2) ⇒ ƒ(x)≤x⋅c+ƒ(c) (2A)

- from (3) ⇒ c+x⋅ƒ(x)≤ƒ(ƒ(x)) (3A)

- from (1) and (2A) ⇒ ƒ(x)≤ƒ(ƒ(x))≤ƒ(x)⋅c+ƒ(c) or ƒ(x)≤ƒ(x)⋅c+ƒ(c) (5)

- from (5), if x=c ⇒ ƒ(c)⋅c≥0 (6)

All these are true for ∀x∈R. Let's prove that c=0.

1. First of all, let's suppose c<0.

From (6) ⇒ ƒ(c)≤0.

From (5) ⇒ ƒ(x)⋅[1-c]≤ƒ(c)≤0. 1–c>1, from which we have ƒ(x)⋅[1-c]≤0 ≡ ƒ(x)≤0, for ∀x∈R.

From (4) and because ƒ(x)≤0 ⇒ ƒ(x)–x≤0 ≡ ƒ(x)≤x, for ∀x∈R. Considering this and (1A) ⇒ c≤ƒ(c)≤c ⇒ ƒ(c)=c.

From (3A) and x=c ⇒ c+c⋅ƒ(c)<ƒ(ƒ(c)) ≡ c+c²≤c ≡ c²≤0 ⇒ c=0 - contradiction.

2. Let's suppose c>0.

From (1A) ⇒ 0<c≤ƒ(c).

From (2A) we have ƒ(x)≤x⋅c+ƒ(c), where x⋅c+ƒ(c) is a line with positive "c" as a coefficient (i.e. increasing line). This means that for ∀x≤-ƒ(c)⁄c ⇒ ƒ(x)≤x⋅c+ƒ(c)≤0 (*).

From (4) and (*) ⇒ ƒ(x)–x≤0 for ∀x≤-ƒ(c)⁄c or ƒ(x)≤x ≤-ƒ(c)⁄c (again, for ∀x≤-ƒ(c)⁄c). But because ƒ(x)≤-ƒ(c)⁄c ⇒ ƒ(ƒ(x))≤-ƒ(c)⁄c (**).

From (3A) and (**) ⇒ c+x⋅ƒ(x)≤ƒ(ƒ(x))≤-ƒ(c)⁄c, for ∀x≤-ƒ(c)⁄c. Both "c" and ƒ(c) are positive ⇒ x⋅ƒ(x)≤-[ƒ(c)⁄c]–c≤0 or x⋅ƒ(x)≤0 for ∀x≤-ƒ(c)⁄c. Because x is negative and (from (*)) ƒ(x) is negative ⇒ x⋅ƒ(x)≥0. So, 0≤x⋅ƒ(x)≤0, for ∀x≤-ƒ(c)⁄c. This is possible only if ƒ(x)=0, for ∀x≤-ƒ(c)⁄c (***).

From (*) and (***) ⇒ 0=ƒ(x)≤x⋅c+ƒ(c)≤0, for ∀x≤-ƒ(c)⁄c, which has sense only if c=0 - contradiction.

We proved that c=0 and ƒ(0)=0. As a result:

- from (2A) ⇒ ƒ(x)≤x⋅c+ƒ(c)=0 ≡ ƒ(x)≤0, for ∀x∈ R (2B).

- from (3A) ⇒ x⋅ƒ(x)≤ƒ(ƒ(x)), for ∀x∈R (3B).

From (2B) ⇒ for ∀x≤0, x⋅ƒ(x)≥0.

From (3B) ⇒ 0≤x⋅ƒ(x)≤ƒ(ƒ(x)), for ∀x≤0.

But ƒ(x)≤0 always (2B). So must be ƒ(ƒ(x))≤0 ⇒ 0≤x⋅ƒ(x)≤ƒ(ƒ(x))≤0, for ∀x≤0. From this ⇒ ƒ(x) = 0, for ∀x≤0.

Love this stuff :)

HTML5 <video> tag, IE9 and Sophos antivirus

I was playing with HTML5 <video> tag recently. Everything was working fine with Safari and Chrome; however IE9 constantly stopped playing the video at ~11-20 seconds. I thought the problem was in compatibility, but, after spending half of the day (and night), I figured out the problem.

The problem was the "Sophos Web Content Scanner" add-on (Sophos v9.5). Once disabled (from the menu, Tools -> Manage add-ons), <video> tag works as it should with IE9.

If you have Sophos installed, you can test this by using, for example, this link videojs.com (or HTML5 version of YouTube). IE9 needs to be restarted each time the add-on is enabled/disabled.

The Code

Just in case you didn't know, BBC started recently a new TV series with the name "The Code". Apart from being a TV documentary, it is also a quest for the treasure hunt. Some of the questions, in this quest, are quite interesting. It's all about observing the patterns, nothing complicated.

For example, have a look at this puzzle. After about 20 minutes of looking at the pictures I came with the following solution:

For the "six-sided dice" the repeating numbers are 1,2,3. For the "eight-sided dice" the repeating numbers are 1,2,3,4. It looks like these numbers generate the others.

1. For the first "six-sided dice" - 1,2,3 generate 2,3,4
2 = 1 + 1¹
3 = 1 + 2¹
4 = 1 + 3¹

2. For the second "six-sided dice" - 1,2,3 generate 2,5,10
2 = 1 + 1²
5 = 1 + 2²
10 = 1 + 3²

3. For the third "six-sided dice" - 1,2,3 generate 2,9,28
2 = 1 + 1³
9 = 1 + 2³
28 = 1 + 3³

4. For the first "eight-sided dice" - 1,2,3,4 generate 2,3,4,5
2 = 1 + 1¹
3 = 1 + 2¹
4 = 1 + 3¹
5 = 1 + 4¹

5. For the second "eight-sided dice" - 1,2,3,4 generate 2,5,10,17
2 = 1 + 1²
5 = 1 + 2²
10 = 1 + 3²
17 = 1 + 4²

Now, following this pattern...

6. For the third "eight-sided dice" - 1,2,3,4 generate
1 + 1³ = 2
1 + 2³ = 9
1 + 3³ = 28
1 + 4³ = 65

And the answer is: 65