Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem I. 194. (October 2008)

I. 194. There are various types of barcodes, but in commerce EAN-13 (EAN = European Article Number) is most commonly used. This barcode represents a 13-digit number in the following way.

The above parts may consist of various numbers of digits. The System code refers to a country or the type of the product. For example:

590 Poland
594 Romania
599 Hungary
600 - 601 South Africa
609 Mauritius
611 Morocco
613 Algeria
977 Periodicals (ISSN)
978 Books (ISBN)
979 Music (ISMN)

When a new product is released, the manufacturer can obtain a new EAN-13 code from a central database.

The last digit of an EAN-13 code is the Check digit, which gives some protection against a random misprint or improper reading of the barcode. To form this checksum, we compute a weighted sum of the first 12 digits as follows: digits at odd positions are multiplied by 1, while digits at even positions are multiplied by 3, then these products are added. This sum is rounded up to the nearest whole ten number. The 13th digit is defined by the increment made in the last step.

In the above example: 5.1+9.3+0.1+7.3+4.1+6.3+0.1+8.3+0.1+3.3+5.1+9.3=140. Since 140 is already divisible by 10, no rounding up is necessary, so the increment, and hence the Check digit should be 0. This shows that the EAN-13 barcode in the example is valid.

The layout of the barcode is described below.

- Digits are encoded by black and white areas. Scanners read these.

- The first separated digit on the left determines the method of encoding. No bars correspond to it, so it is encoded differently.

- The rest of the code contains two groups of digits. In front of, behind and between the groups there are thin double lines.

- Each digit is represented by 2 lines with varying thickness, occupying 7 units of width. There can be 3 different encodings within a barcode. Let us denote these by A, B or C. The 2 lines can be converted into digits according to the table (``Szám'' means ``Digit''), where black colour is 1 and white is 0.

Szám A B C
0 0001101 0100111 1110010
1 0011001 0110011 1100110
2 0010011 0011011 1101100
3 0111101 0100001 1000010
4 0100011 0011101 1011100
5 0110001 0111001 1001110
6 0101111 0000101 1010000
7 0111011 0010001 1000100
8 0110111 0001001 1001000
9 0001011 0010111 1110100

- The first group of digits (that is, digits from position 2 to position 7) are encoded either by A or B, while the second group (consisting of the last 6 digits) is encoded by scheme C.

- The first digit of the EAN-13 barcode determines the type of encodings of the six digits in the first group according to the table (``Első számjegy'' means ``First digit'').

The structure of the barcode in the example (a marmalade jar from Poland): The first digit is 5, which is not encoded by lines, but determines the encoding type of the first group according to the highlighted row of the table above.

Group of lines Meaning Thickness
1. Initial thin double lines 101
2. [9] with encoding A 0001011
3. [0] with encoding B 0100111
4. [7] with encoding B 0010001
5. [4] with encoding A 0100011
6. [6] with encoding A 0101111
7. [0] with encoding B 0100111
8. Separator thin double lines 01010
9. [8] with encoding C 1001000
10. [0] with encoding C 1110010
11. [3] with encoding C 1000010
12. [5] with encoding C 1001110
13. [9] with encoding C 1110100
14. [0] with encoding C 1110010
15. Terminal thin double lines 101

Putting all these together we obtain the barcode.

Using a spreadsheet application, determine whether the EAN-13 barcode in cell A1 is valid, using the Check digit: you should write either ``valid'' or ``invalid'' into cell B1. Then you should convert the given sequence of digits into a sequence of lines encoded by 0s and 1s in cells A2:A16 (as in the Thickness column of the example above).

You should not use macros or program modules, only formulae and built-in functions. Intermediate computations should be visible, so do not hide any of them. Auxiliary tables for the conversion can be placed on separate sheets.

Your worksheet (i194.xls, i194.ods, ...) together with a short documentation (i194.txt, i194.pdf, ...) should be submitted, also containing a brief description of your solution and the name and version number of the spreadsheet application used.

(10 pont)

Deadline expired on November 17, 2008.


Sorry, the solution is available only in Hungarian. Google translation

Megoldásokról:

Sok jó megoldás mellett a feladatspecifikációt többen nem tartották be. A vonalkód működési elvét néhányan titkosításnak gondolták. Erről szó nincs. A vonalkód gyors, pontos és ellenőrzött adatrögzítő és kommunikáló eszköz. EAN 13 az UPC kód (Universal Product Code) továbbfejlesztéséből alakult ki. Ez az első világméretű termékazonosító rendszer és kódtípus. Az ellenőrző számjegyet majdnem mindenki jól határozta meg, annak ellenére, hogy a 13 jegyű szám számjegyekre bontása nem kívánt hatalmas függvényapparátust.

A vonalkód rendszer csoportjainak meghatározása kétszeres mélységű keresést igényel. Az első számjegy alapján kellett meghatározni az első számjegycsoport kódolás típusát, majd ennek és a megfelelő számjegyek ismeretében már a kódot.

A feladat Pap 987 Dávid által készített megoldása (i194.xls).

Különösen ötletes, hogy a vonalkód mintát feltételes formázás segítségével egy munkalapon megjelenítette.


Statistics:

23 students sent a solution.
10 points:Dévényi Attila, Fehér Péter, Jákli Gábor, Kővágó Zoltán, Kristóf Tamás, Molnár Gábor, Pap 999 Dávid, Szabó 295 Gábor, Szabó 928 Attila, Szendrei Péter, Tóth Szabolcs, Uray Marcell János.
9 points:Balla Attila, Debreceni Bálint, Englert Péter, Horváth 135 Loránd, Kapitány Ágoston.
7 points:2 students.
6 points:3 students.
2 points:1 student.

Problems in Information Technology of KöMaL, October 2008