No Averages Solution

I recently posted the following old Olympiad problem:

Prove that you can choose 2k numbers from the set {1, 2, 3, …, 3k−1} in such a way that the chosen set contains no averages of any two of its elements.

Let me show how to find 2k − 1 such numbers. We can pick all the numbers that have 0 or 1 in their ternary representation. Let me prove that this set doesn’t contain averages. Summing two such numbers doesn’t involve carry, and the sum will contain a 1 in each place where the digits differ. On the other hand, a double of any number in this set doesn’t contain ones.

This solution is pretty, but it is not good enough: we need one more number. We can add the number 3k−1. I will leave it to the reader to prove that the largest number in the group whose binary representation consists only of twos can be added without any harm.

There are other ways to solve this problem. It is useful to notice that multiplying a no-average set by a constant or adding a constant to it, doesn’t change the no-average property.

If we were allowed to use 0, then the problem would have been solved. As zero doesn’t belong to the initial range, we can add zero and shift everything by 1. The resulting sequence is sequence A3278. This sequence is the lexicographically first non-averaging sequence.

Another solution was suggested by devjoe in my livejournal mirror blog site. If we multiply our non-averaging set (the one that doesn’t have twos in their ternary representation) by 2, we get a set of all numbers that do not contain ones in their ternary representation. By linearity, such a set doesn’t contain averages either. We can add 1 to this set.

Share:facebooktwittergoogle_plusredditpinterestlinkedinmail

Intel ISEF Mathematics Awards 2014

The Intel International Science and Engineering Fair announced 2014 Grand Awards. I worked with three out of the top five mathematical award winners. Now I can brag that I’ve got my finger in more than half of the world’s best high-school math research.

To be clear: I wasn’t actually mentoring these projects, but I supervised two of the projects and I trained the third student for several years. So I’m proud to list the award-winning papers:

How interesting that each of these three students is from a different part of my present career. It certainly feels that I am in all the right places.

Share:facebooktwittergoogle_plusredditpinterestlinkedinmail

Some Jokes

* * *

A mathematical tragedy: two parallel lines fall in love.

* * *

Life is not fair, even among gadgets: the desktop misbehaves, the monitor gets smacked.

* * *

An amazing magic trick! Think of a number, add 5 to it, then subtract 5. The result is the number you thought of!

* * *

—How can you distinguish a mathematician from a physicist?
—Ask for an antonym for the word parallel.
—And?
—A mathematician will answer perpendicular, and a physicist serial.

* * *

—How can you distinguish a physicist from a mathematician?
—Ask the person to walk around a post.
—And?
—A physicist will ask why, and a mathematician clockwise or counter-clockwise?

* * *

—Some bike thief managed to open my combination lock. How could they possibly guess that the combo was the year of the canonization of Saint Dominic by Pope Gregory IX at Rieti, Italy?
—What year was that?
—1234.

* * *

—Hello? Is this the anonymous FBI tip-line?
—Yes, Mr. Benson.

* * *

—My five-year-old son knows the first 20 digits of Pi.
—Wow!
— I use it as the password on my laptop, where I keep all the games.

* * *

I learned three things in school: how to rite and how to count.

Share:facebooktwittergoogle_plusredditpinterestlinkedinmail

Crypto Word Search II

I recently published a crypto word search puzzle: a word search puzzle where all the letters are encrypted by a substitution cypher. The answer to such a puzzle is a word or a phrase formed by those decrypted letters that are not in the hidden words.

Crypto Word Search 2

The puzzle I posted was easy. It can be solved by analyzing the repeated letters in the hidden words. The new puzzle is more difficult. No hidden word has repeated letters.

The hidden words are: FUN, HUNT, SOLVE, STARK, TABLE, THINK.

Share:facebooktwittergoogle_plusredditpinterestlinkedinmail

Crypto Word Search

The puzzle below can be defined as a Crypto Word Search. Guess what needs to be done in this puzzle. The answer is a word.

Crypto Word Search

The hidden words are: DUKE, EYES, RUSE, WORD, WUSS.

The idea of a crypto word search came to me from a beautiful, but devilishly difficult, puzzle In the Details, designed by Derek Kisman. In the Details can be described as a fractal word search; it contains a crypto word search as one of the simpler steps.

Share:facebooktwittergoogle_plusredditpinterestlinkedinmail

Is 2014 Awesome or Not?

Let us call a natural number awesome if it can be represented as ab + ba, where a and b are natural numbers. For example, number 57 is awesome as 57 = 25 + 52. Is 2014 awesome?

Share:facebooktwittergoogle_plusredditpinterestlinkedinmail

Hong Kong Elementary School First Grade Student Admission Test Question

Parking spot

What parking spot number is the car parked in?

Share:facebooktwittergoogle_plusredditpinterestlinkedinmail

Free Fibonacci Sequences

John Conway likes playing with the Fibonacci sequence. He invented many new sequences using the following trick. The next number in the sequence is the sum of the two previous number adjusted in some way. Free Fibonacci sequences were invented this way. Here is the recurrence for an n-free Fibonacci sequence: the next number in the sequence is the sum of the previous two numbers divided by the highest possible power of n.

Let us calculate a 2-free Fibonacci sequence starting with 5 and 4: 5, 4, 9, 13, 11, 3, 7, 5, 3, 1, 1, 1, …. I leave it to the reader to show that any 2-free sequence ends with a cycle of length one.

Let us try a 3-free Fibonacci sequence starting with 5 and 6: 5, 6, 11, 17, 28, 5, 11, 16, 1, 17, 2, 19, 7, 26, 11, 37, 16, 53, 23, 76, 11, 29, 40, 23, 7, 10, 17, 1, 2, 1, 1, 2, and so on. We are now in the cycle of length 3. Is this always the case? Not quite. If there is a 1-1-2 cycle there should be a 2-2-4 cycle, or any cycle k-k-2k, where k is coprime with 3. But the question remains: does it always end in a cycle of length 3?

I published a paper Free Fibonacci Sequences with Brandon Avila. We conjecture that a 3-free Fibonacci sequence always ends in a cycle and support this conjecture with a probabilistic argument. We were amused by how the behavior changes when we move to 4-free Fibonacci sequences. It seems that in this case sequences never cycle. We were even more amused when we moved to 5-free Fibonacci sequences and discovered that the behavior changes again.

When n equals 5 there are some sequences that cycle. Can you find the cycles? There are also sequences that grow indefinitely and we do not need a probabilistic argument to prove that. Consider Lucas numbers: 2, 1, 3, 4, 7, 11, and so on. This is a Fibonacci-like sequence that never has a term divisible by 5. Thus Lucas numbers form a 5-free Fibonacci sequence. We made a probabilistic argument that most of the starting terms converge eventually to a Lucas-like sequence that grows indefinitely because there are no terms divisible by 5.

What happens for larger n? We didn’t manage to find any cycles there. Would you like to try?

Share:facebooktwittergoogle_plusredditpinterestlinkedinmail

Stuck at 225

My weight loss progress is progress no more. I am stuck at 225.

I have my morning routine. I wake up and jog to the facilities; then I weigh myself. Why do I do this in this order? Because I do not use an alarm-clock. I depend on my own hydro-alarm that wakes me up every morning very reliably. The downside is that this alarm doesn’t have a snooze button. I just have to get up, and get up very fast. So I have to relieve myself first; then I can weigh myself calmly. As a collateral benefit, by availing myself first, I get a slightly better result.

While weighing myself every day, I noticed some patterns. My weight is slightly better if I get a long night of sleep. I guess my availing is more voluminous then.

Another pattern that I noticed is that if I do not eat after 5:00 pm, I do not gain weight and sometimes I lose a bit; if I do eat after 5:00 pm, even a very light dinner, I can gain up to 3 pounds. This becomes a struggle and sometimes hunger wins. So I stick to the plan for three weeks, and then one moment of tiredness and hunger, one dinner, and, boom, I am back where I was.

This is even affecting my social life. I stopped inviting friends and family for dinner and I am tense whenever I visit my friends in the evening.

The surprising thing is that my system worked at the beginning. I keep asking myself what the difference is. I think I was strongly motivated and excited about my weight loss plan. It’s impossible to sustain that level of excitement, so I’ve adopted a new element in my plan. I decided to replace my initial excitement by external motivation. I am now listening to motivational tapes in my car. We’ll see.

Share:facebooktwittergoogle_plusredditpinterestlinkedinmail

De-stressing Jokes

Whenever I am under stress, I turn to jokes. My recent problems with spam attacks on my blog led me to surf the web for new math jokes. Here are some of my recent translations from Russian.

* * *

Two is the same thing as eight, to some degree.

* * *

A girl to her mathematician boyfriend:
— Let’s do something that is forbidden tonight.
— Divide by zero?

* * *

If thoughts converge, they are bounded.

* * *

A mathematician’s son:
— Dad, how do I write the number 8?
— That’s easy: rotate the infinity symbol by pi over 2.

* * *

My student couldn’t take an integral from my book. So he took the book together with all the integrals there.

* * *

Archimedes, Pascal and Newton play hide and seek. Archimedes is the seeker. Pascal hides, but Newton draws a 1-meter square around himself. Archimedes opens his eyes and shouts:
— I see Newton!
— Oh, no! One newton per square meter is the pascal.

* * *

What a pleasure to smoke an e-cigarette after cybersex…

* * *

Russians were the first in the world to create a computer program that passes the Turing test. Scientists tested the program using several Russians with a variety of questions, and each time the program gave the same answer as the people. The reply to every question was, “Go f*ck yourself!”

* * *

There are two types of people: those who know nothing about fractals and those who think that there are two types of people: those who know nothing about fractals and those who think that there are two types people…

Share:facebooktwittergoogle_plusredditpinterestlinkedinmail