The problem of calculating the number of lucky tickets has been known for a long time. It was asked to almost any student learning programming. On the Internet, you can find many of its solutions in different programming languages. All these options boil down to sorting out all existing tickets and checking them for "luck". It turns out a million options.
But this problem can be solved in another way, going through just a thousand options.
Let me remind you that tickets are lucky if the sum of the first three digits of the number is equal to the sum of the last three digits of the number. For example, a ticket with the number "546780" is lucky, since the sum of the first three digits (5 + 4 + 6) is equal to the sum of the last three digits (7 + 8 + 0). The challenge is to determine how many lucky tickets there are.
In all examples, it is solved head-on, but what if we go the other way? First, let's answer another question. How many different combinations of three numbers (triplets) are there that add up to n? To answer this question, you need to sort out all possible triplets (one thousand options).
The sum of any triplets is between zero (0 + 0 + 0) and 27 (9 + 9 + 9). Therefore, an array of sums can be prepared:
{n _0, n _1, n _2, n _3, …., n _25, n _26, n _27}
where n _ i- the number of triplets giving in the sum i... In this case, the sum of the digits is equal to the index of this element in the array.
Okay, we'll prepare an array like this, but what does this have to do with tickets? Let's consider a special case. Of everything exists n _25 triples giving a total of 25. For each such triplet, there is n _25 triplets, when combined with each of which you get a lucky number. Therefore there is n _25*n _25 lucky tickets, the sum of the first three digits of which is 25. Similarly for other amounts. Thus, the total number of lucky tickets is:
n _0*n _0 + n _1*n _1 + …. + n _26*n _26 + n _27*n _27
Below is the complete source code of the application that implements this algorithm.
#include
The code is well commented, so there shouldn't be any questions.
If you look at the array of sums, you can make two observations.
1. It is symmetrical:
n_13 = n_14,
n_12 = n_15,
n_11 = n_16,
n_10 = n_17,
………………
n _1 = n _26,
n _0 = n _27.
2. Most of all there are tickets, the sum of the first three digits of which is 13 and 14 (there are 75 of them).
An array of sums of 28 elements is prepared in one iteration of triplets. Therefore, to count the number of lucky tickets, it is enough to enumerate 1000 options.
Most students are well aware of what a "lucky ticket" is. And often schoolchildren too. True, what exactly they are and what to do with them - here opinions most often differ.
First of all, "happy as a student" a ticket is considered, the answers to which you know. Don't even go to your grandmother - you were lucky on the exam, pulled out a lucky ticket and passed it the first time, even though you managed to learn only these two out of a hundred questions. Yes, he answered so briskly that the teacher, tired of "whining and meeking," did not even listen to you to the end - he sent you with an A in the record book and with instructions to the rest: "Look! Look and learn how to take a subject! Take an example from this good man! "
This is what I understand - "happy ticket"!
But there are tickets, they are also tickets for travel, which are considered either happy or beautiful. The second is extremely rare. Most often they are called "happy"! What kind of tickets are considered as such?
Firstly, and this is an extremely rare case, a ticket is considered lucky if its numbers are the same or are arranged symmetrically.
For example: 555555
or 252252
... There is complete symmetry.
But symmetry is incomplete or mirror-like. For example like this: 251251
- the numbers are arranged symmetrically here, but the numbers are not.
In any case, the above examples are really "happy" tickets. Are there many of them? Well, I think you can easily count that very, very little - a thousand to a million, or every thousandth ticket. The likelihood of such a ticket falling into the hands of a passenger is extremely small. So far, only two such tickets have fallen to me in my life, although I travel by public transport quite often,
Do you want happiness? Therefore, quirky and quick-witted passengers in the boredom of the way immediately came up with other options for "happiness". For example, just the same digits in a number, in no particular order: 251521
, for example. There is no symmetry here, but all the numbers are present. Further more. A ticket was considered lucky if the sum of the triplets was the same. For example, 474195:
4+7+4=15= 1+9+5
1. Examples of tickets, "lucky in amount":
Again, everyone knows that such tickets are found, though not every day, but still quite often. Approximately every 18th ticket is "lucky in amount". And if you travel constantly, then they meet at least once a week. Once I conducted a small experiment: I did not throw them away, but put these tickets in my bag pocket to count them at the end of the month. It was a long time ago, I don't remember exactly how many, but I had at least ten of them a month. Considering that I use municipal transport on average two or three times a day (the rest of the time I use minibuses, and for some reason we don't issue tickets there), it turns out that every 6-9 trip is "rewarded" with such simple happiness ... Well, or one ticket every three days. But this, you see, I just got a lucky month, because every 18th ticket should come across, as it were, less often.
Indeed, there are times when in a month and not a single one will be caught. So what do you do? And the need for invention is cunning. For example, there are tickets, "happy in Moscow"(they are - "in Leningrad") - this is when not triplets of digits are counted, but their pairs. For example, the sum of each even number with odd numbers: 6 3
49
86
.
Here:
3+9+6= 18= 6+4+8
What do you think, is it possible, in addition to addition, to use the operation subtraction? Of course you can! The main thing is to decide for yourself how to subtract - in order or from more to less: 720821 ... Here:
7-2-0=5= 8-2-1
But ... it is not customary for us to somehow "subtract happiness". Better when it is added or even multiplied!
Therefore, I came up with another type of lucky tickets for myself: "happy to multiply"!
It is enough to multiply the numbers in threes to get yourself an additional "multiplier" cheerfulness. For example: 338924.
Here:
3*3*8=72= 9*2*4
Use it to your health! And then why are you summing everything up and summing up ... You can also multiply!
Upd: Moreover, you can not just multiply! Here, in the comments docbrowns noticed that you can also raise to a power! For example 261812 :
(2^6)^1 = 64 = (8^1)^2
And this many times increases both the chances of "finding happiness" and the amusement of the trip.
2. An example of a ticket, "happy in multiplication" a la: 
If you use public transport, take a closer look at the passengers. Very, very often you can see how, when they receive a ticket, they begin to study its numbers. Everyone is looking for happiness ... And then what to do with it? Once I overheard a conversation between two girls who were going to test: "Wow! I have a lucky ticket!" one exclaimed. "Eat it! Then you will pass the test !!!" the second responded immediately. Really, I was laughing. Better they hoped for that happy "as a student" the ticket I mentioned at the beginning. And even better - so that all fifty course tickets are happy for them. But ... they would rather eat the trolley than learn the lecture.
Guys! No need to eat coupons! It's not even useful at all. And it will not bring you happiness. Treat lucky tickets easier - once it fell for you, then happiness will not come, no - you already happy or, more simply, lucky human! That's all. This is just a reason to slightly improve your mood. Do not believe in omens - they are far from always based on facts, and often they can also bring harm, especially if you start eating four-leaf flowers from the ground or paper coupons from recycled materials and on the bus! As in that joke: I ate a lucky ticket, and then happiness fell - the controller came in!
Treat "lucky tickets" as a way to pass the time of your trip with arithmetic exercises, and as an additional reason to rejoice in it.
By the way, for dads and moms, note: it is very useful to tell children about such exercises. At school, they do not really like verbal counting, so even if they have fun in trolleybuses, adding or multiplying numbers. And it will not hurt adults either: both in a row and through one, assimilating the concepts of parity, symmetry, multiplicity ... And you can also remember about subtraction with division. In any case, such fun tasks will not harm the development of the child.
And if you are unlucky with a ticket - do not be discouraged! There are so many cars with "lucky numbers" driving along the street!
Good luck and happiness!
"Happy ticket"
We all go to transport. On the way to work, home, to rest and
etc. And very often we buy a travel ticket, which in most
cases a six-digit number. Adding the first three digits of the ticket number and
comparing them with the sum of the second three digits, we define "happiness"
of this ticket. With the "lucky" number, everything is more or less clear and
most people know. What about other nonzero numbers? It's clear that
the difference in numbers varies from 0 to 27. This is how this tablet was born ...
The action of the ticket is trivial (by the way, it is not necessary to have it at all!) -
the ticket is valid for 24 hours from the moment of activation or until purchase
next ticket with a meaningless number. Ticket activation
occurs after counting the number and realizing its meaning - so
say a magic ritual.
(Note: If the next ticket has an independent value, and
the previous one has not yet been extinguished - one value is superimposed on another. Well,
for example - you took a ticket with a difference in numbers = 1 = - which means
date. We moved to another transport, without meeting anyone we knew -
that is, the ticket is still active and has not been "triggered". We took a new ticket - and at
his difference in numbers = 7 = - that is, lime. So what or what can happen
two events, or they merge into one - on a date you still get
news ("I'm pregnant!" - joke ...). And so on. Combinations of
sequences of three numbers were not tested by the authors - there are no large
statistical data when driving with three transfers - a rarity,
understand).
This scheme is determined empirically. As in any experimental
in fact, errors are possible. Send your observations and they will
taken into account next time.
Difference of numbers Meaning Interpretation
0 Luck Any business planned will end well or you will
something is clearly lucky.
1 Date You will meet a person whom you will be glad to see (meeting
personal, not for work).
2 Meeting You have a business meeting.
3 Repeat Something has to be repeated, otherwise it will not work.
4 Warning Be careful! Today you may be late to the point
destination! Do not relax and everything will be successful. But if you gape -
late arrival guaranteed!
5 Pleasantness A pleasant meeting or event will improve your mood!
6 Trouble An unpleasant meeting or event can ruin your
mood. Don't worry too much!
7 News You will receive news from someone!
8 Chaos Something today will not be able to grow together, dock, end ...
9 Closing Some business started today will be closed completely.
10 Getting Started Today you will start a new project or a new thought will dawn on you,
idea.
11 Walk Well, or a traffic jam, or you just have to take a walk ...
12 Dozen Possibly drinking alcoholic beverages ...
13 Devil's dozen
states ...
14 Means Nothing
15 Means Nothing
16 Means Nothing
17 Means Nothing
18 Means Nothing
19 Means Nothing
20 Means Nothing
21 Means Nothing
22 Means Nothing
23 Means Nothing
24 Means Nothing
25 Repeat Something has to be repeated, otherwise it will not work.
26 Meeting You have a business meeting.
27 Date You will meet a person whom you will be glad to see
(personal meeting, not for work).
How many ways are there to pay 50 cents? We believe that you can pay 1 pennies, 5 nickels, 10 dimes, 25 quarters and 50 half dollars. Gyorgy Poya popularized this problem by demonstrating an instructive way to solve it using generating functions.
Let's write down an infinite amount representing all possible exchange methods. The easiest place to start is when there are fewer varieties of coins, so let's start by assuming we don't have any coins other than a penny. The sum of all the ways to pay a certain amount of a penny (and only a penny) can be written as
since each payout option includes a number of nickels, chosen from the first multiplier, and a certain number of pennies, chosen from P... (Note that N does not equal the amount of 1 + 1 + 5 + (1 + 5) 2 + (1 + 5) 3 + ..., since this amount includes many types of payments more than once. For example, the term (1 + 5) 2 = 1 1 + 1 5 + 5 1 + 5 5 treats 1 5 and 5 1 as if they were different, but we want to list all sets of coins once, regardless of their order. )
Similarly, if we also allow dimes, then we get an infinite amount
Our task is to find how many terms in C cost exactly 50 cents.
The problem is solved with a simple trick. Replace 1 with z, 5 on z 5, 10 on z 10, 25 on z 25 and 50 on z 50 . Each term will then be replaced by z n, where n- the cost of the original term in pennies. For example, the term 50 10 5 5 1 becomes z 50+10+5+5+1 = z 71. Each of the four possible ways to pay 13 cents, namely 10 1 3, 5 1 8, 5 2 1 3 and 1 13, will be reduced to z 13 ; therefore, the coefficient at z 13 after z-substitution will be 4.
Let be P n, N n, D n, Q n and C n denote the number of ways to pay the amount in n cents, if you can use coins no older, respectively, 1, 5, 10, 25 and 50 cents. Our analysis showed that these numbers are coefficients at z n in the corresponding power series
| P = | 1 + z + z 2 + z 3 + z 4 + ... , |
| N = | (1 + z 5 + z 10 + z 15 + z 20 + ...)P, |
| D = | (1 + z 10 + z 20 + z 30 + z 40 + ...)N, |
| Q = | (1 + z 25 + z 50 + z 75 + z 100 + ...)D, |
| C = | (1 + z 50 + z 100 + z 150 + z 200 + ...)Q. |
It's obvious that P n= 1 for all n≥0. On a short reflection, it is easy to prove that N n = [n/ 5] + 1: to add up the amount in n cents from pennies and nickels, we must take 0, or 1, or ..., or [ n/ 5] nickels, after which there is only one way to choose the required number of pennies. So the values P n and N n are easy to compute, but with D n , Q n and C n the matter is much more complicated.
One of the approaches to the study of these formulas is based on the observation that 1 + z m + z 2m+ ... is just 1 / (1 - z m). Therefore, we can write
Now, equating the coefficients at z n in these equations, we obtain recurrence relations, from which the desired coefficients are easily calculated:
For example, the coefficient at z n v D= (1 - z 25)Q is equal to Q n Q n–25; so there should be Q n Q n–25 = D n as written above.
It would be possible to reveal these relationships and express Q n, for example, in the form Q n = D n + D n–25 + D n–50 + D n–75 + ... where the sum breaks off when the indices go negative. However, the original, non-iterative form is convenient in that each coefficient is calculated using just one addition, as in Pascal's triangle.
We use these relations to find C 50 . At first, C 50 = C 0 + Q 50 so we need to know Q 50 . Further, Q 50 = Q 25 + D 50 and Q 25 = Q 0 + D 25; therefore we are also interested in D 50 and D 25. These values D n in turn depend on D 40 , D 30 , D 20 , D 15 , D 10 and D 5 and from N 50 , N 45 , ..., N 5 . Thus, in order to determine all the necessary coefficients, it is enough to perform simple calculations:
| n | 0 | 5 | 10 | 15 | 20 | 25 | 30 | 35 | 40 | 45 | 50 |
| P n | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| N n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| D n | 1 | 2 | 4 | 6 | 9 | 12 | 16 | 25 | 36 | ||
| Q n | 1 | 13 | 49 | ||||||||
| C n | 1 | 50 | |||||||||
At the very bottom of the table is the answer C 50: There are exactly 50 ways to tip 50 cents.
And what about the closed form for C n? Multiplying all the equations gives us a compact expression for the generating function
which is a rational function of z, the denominator of which has a degree of 91. Thus, we can factor the denominator into 91 factors and express C n in "closed form", consisting of 91 terms. But such a terrible expression does not go into any gate. Is it possible in this particular case to find something better, and not to apply the general method?
And here is the first glimmer of hope: if in C(z) replace 1 / (1 - z) to (1 + z + z 2 + z 3 + z 4) / (1 - z 5):
then the degree of the denominator of the "squeezed" function Č (z) is already only 19, so this function is much better than the original one. New expression for C(z) shows, in particular, that C 5n = C 5n+1 = C 5n+2 = C 5n+3 = C 5n+4; indeed, this relationship is easy to explain: a tip of 53 cents can be given in exactly the same ways as a tip of 50 cents, since the number of pennies modulo 5 is known in advance.
However, even for Č (z) there is no simple expression based on the roots of the denominator. Probably the simplest way to calculate odds Č (z) will be obtained if we notice that each factor in the denominator is a divisor of 1 - z ten . Therefore, we can write
Here, for the sake of completeness, a detailed expression for A(z):
(1 + z + ... + z 9) 2 (1 + z 2 + ... + z 8)(1 + z 5) =
= 1 + 2z + 4z 2 + 6z 3 + 9z 4 + 13z 5 + 18z 6 + 24z 7 +
+ 31z 8 + 39z 9 + 45z 10 + 52z 11 +57z 12 + 63z 13 + 67z 14 + 69z 15 +
+ 69z 16 + 67z 17 + 63z 18 + 57z 19 + 52z 20 + 45z 21 + 39z 22 + 31z 23 +
+ 24z 24 + 18z 25 + 13z 26 + 9z 27 + 6z 28 + 4z 29 + 2z 30 + z 31 .
And finally, taking advantage of the fact that
we obtain the following expression for the coefficients Č n at degrees z n in function expansion Č (z), in which n = 10q + r and 0≤ r<1 0:
| Č 10q+r = | ∑ | A j | ( | k + 4 k |
) | = | ||||||||||||||||
| j, k 10k+j=n |
||||||||||||||||||||||
| = A r | ( | q + 4 q |
) | + A r+10 | ( | q + 3 q |
) | + A r+20 | ( | q + 2 q |
) | + A r+30 | ( | q + 1 q |
) | . |
This actually contains 10 different cases, one for each value. r; but it's still a pretty good closed formula compared to the alternatives that include powers of complex numbers.
Using this expression, we can find out, for example, the value C 50q = Č 10q... Here r= 0 and we have
for an amount of 1 dollar it turns out
| ( | 6 4 |
) | + 45 | ( | 5 4 |
) | + 52 | ( | 4 4 |
) | = 292 ways; |
and for a million dollars this number will be
| ( | 2000004 4 |
) | + 45 | ( | 2000003 4 |
) | + 52 | ( | 2000002 4 |
) | + 2 | ( | 2000001 4 |
) | = |
= 66666793333412666685000001.
