Detailed explanation of practical competition

Practical competition ❶ Commentary
Challenge-18
Practical competition (1) was a competition in which three people from one team cooperated to solve 3 questions related to mathematics and information with different scores, and competed for the total score obtained from the correct questions within the time limit of 18 minutes.In addition, it was written in the preliminary materials that about 100% of the questions to be asked could not be answered without calculation by the program.

The content of this competition is similar to a programming contest called competitive programming, which accurately describes a program that satisfies a given requirement, and many of these questions require knowledge of computer science and mathematics. It is a feature.

Competitive programming is held both domestically and internationally, and there are many famous contests such as AtCoder, Topcoder, and the ACM International Collegiate Programming Contest.In particular, there is a contest called Project Euler that is very close to this format.The contest presents challenging math / computer program problems that require more than just mathematical insights.

Also, knowledge of mathematics can solve problems simply and efficiently, but in many cases computer and programming skills are required.

The problem of [prime numbers] was how many times "1" was printed when a certain range of prime numbers was printed.If the range is small, it is faster to write it on paper and count it than to write the program directly, but if the range is large, how to find the prime number is important.A well-known method is the "Eratosthenes sieve".

[Takeuchi function] is a recursively defined function used for benchmarking programming language processing systems, etc., and was conceived by Ikuo Takeuchi in 1974.Recursively defined functions include the Fibonacci sequence and the Ackermann function.

The problem of [binary system] was the problem of re-expressing numbers expressed in binary system in decimal system.You can do your best to write a program and ask for it, or you can use a computer instead of a calculator to solve it.It can also be calculated by hand, but it can also be calculated efficiently and easily with a little ingenuity.It was an interesting problem that could be solved by various methods.

The problem of [the sequence in which the sum was determined] was the problem of partitioning natural numbers.For a natural number n, the number of methods expressed as the sum of natural numbers excluding the difference in the order is called the number of divisions, p (n), and the number of methods of dividing into different natural numbers is called the number of different divisions q ( It is represented by n), and the number of methods of dividing a natural number n into an odd number of natural numbers is called an odd number of divisions.At this time, Q1 was a problem to find q (50), and Q2 was a problem to find p (50).In addition, Q3 has the same value as q (50) from the "Euler's division equality" that the number of different divisions and the number of odd divisions are equal.

The problem of [divisor] is the divisor function

It was a problem with.In particular, it may be expressed as σ₀ (n) = d (n) and σ₁ (n) = σ (n). Specific methods for obtaining d (n) and σ (n) are known, and

Against

Will be.As an aside, n with σ (n) = 2n is known as a perfect number, and n with σ (n) = kn is said to be a k-fold perfect number.In other words, a perfect number can be seen as a double perfect number.

The problem of [substring] was a problem related to the idea of ​​subsets.A substring of a character string of length n with all different characters can have 2n substrings from the idea of ​​a power set.If the characters are not all different, consider the union for the 2 n sets obtained in the same way, and the duplicated parts can be removed to obtain the set of the desired character strings.In this case, since n = 11 is small, it can be solved in a realistic time even by removing the overlapping part from 2048, but if n is large, the dynamic programming method is realistic. ..

To explain the important part, it is assumed that a substring using the characters from the first character to the kth character was created.Find the union of these substrings plus the k + 1st character at the end, and use this as the substring using the characters from the first character to the k + 1st character.Hereafter, it is a method of repeating this.

The problem of [integer] was a problem of experiencing unsolved problems of number theory such as taxi number, Collatz conjecture, Goldbach's conjecture, etc. by using programming.Here are some things related to these issues.

• The following propositions are known as an extension of the taxi number problem. "For all natural numbers N, there exists an integer m3 with at least N rectification points where the cubic curve x³ + y³ = m is positive for both x and y."

• The Collatz conjecture problem was similar to the problem of the "Takuchi function" seen at the beginning, and both were problems of finding the number of recursive operations.In addition, in the 2011 Center Test, the 6th question of Mathematics II / B was a question on the theme of numerical calculation and computer, and the same question as this question was given on the theme of the famous Collatz conjecture.

• When you think of Goldbach's conjecture, you usually think of the idea that even numbers larger than all 2 can be expressed as the sum of two prime numbers.The name of this conjecture comes from Goldbach's conjecture in 2, stating that "any natural number greater than 1742 can be represented by the sum of three prime numbers."Similar conjectures include "Weak Goldbach's conjecture" that "odds greater than 5 can be represented by the sum of three prime numbers" and "strong gold" that "even numbers greater than 3 can be represented by the sum of two odd prime numbers". Bach's conjecture. "

The problem of [Doremi cipher] was a problem related to double-character substitution cipher.Question 1 was the problem of analyzing the structure of the ciphertext required for actual decoding, and Question 2 was the problem of actually creating a substitution table and encoding based on it.Substitution ciphers may appear in novels, and famous ones include Edgar Allan Poe's Golden Bug, Edogawa Ranpo's Two-sen Copper Coin, and Arthur Conan Doyle's Sherlock Holmes series dancing dolls. ..

The problem of [character string operation] was the problem due to the order of character string operations by functions.In programming, operations such as character strings and arrays and analysis techniques are required, and it is a problem that makes you think about how to actually perform the operation to obtain the desired result. there were.

The problem of [sequence operation] was a problem related to array operation and recurrence formula.If n is small as in Question 1, it can be calculated in order by hand.Regarding Question 2, it is difficult to actually write out sn, but since it is possible to formulate a recurrence formula for tn, it can be calculated manually if it goes up to that point.

As stated in the purpose of the competition in the "Competition Guide", in society, in order to solve scientific and technological problems, complicated calculations are often performed using a computer.In addition, various things such as science, mathematics, and information are intricately intertwined in familiar scientific phenomena, and programming often solves scientific and technological problems.This problem was a very good problem where I could feel the usefulness of problem solving by programming and the need for mathematical thinking.
Koichi Nakagawa, Graduate School of Science and Engineering, Saitama University