When I was a kid, we had six-digit bus tickets (leading zeros were allowed). A ticket was considered "lucky" if the sum of the first three digit is equal to the sum of the last three digits. I'd like to know what the probability of getting a lucky ticket is!
nope!leading zero's are not allowed.Are leading zeroes allowed?
yeah! it is allowedIs repetition of digits allowed?
yeah...i need to do on paper.....Also are you required to do this with paper and pencil? Because writing a computer program would be easy, with or without leading zeroes allowed.
but you can post the computer program too
Straightforward Java implementation, used [ PHP][/ PHP] tags for colors
[php]
public class D2010_09_15_LuckyTickets {
public static void main(String[] args) {
long t = time();
int c = 0, i;
for (i = 0; i < 1000000; i++) {
if (isLucky(i)) c++;
}
System.out.println(c);
System.out.println("Elapsed: " + (time() - t) / 1000.0 + " seconds");
}
static boolean isLucky(int n) {
// assume 0 <= n < 10^6
int a, b;
String s = Integer.toString(n);
s = addLeadingZeroes(s, 6);
a = Integer.parseInt(s.substring(0, 3));
b = Integer.parseInt(s.substring(3));
return sd(a) == sd(b);
}
static int sd(int n) {
// return sum of digits of non-negative integer n
int sum = 0;
while (n > 0) {
sum += n % 10;
n /= 10;
}
return sum;
}
static String addLeadingZeroes(String s, int len) {
if (s.length() >= len) return s;
return addLeadingZeroes("0" + s, len);
}
static long time() {
return System.currentTimeMillis();
}
}
[/php]Output:
In order to disallow leading zeroes, all you have to do is change the initializer expression in the for loop in main(). Output for that isCode:55252 Elapsed: 0.291 seconds
Code:50412 Elapsed: 0.219 seconds
For paper solution, I can think of a long way for now.
For three digits here (no leading zeroes), smallest sum is 1, largest sum is 9+9+9=27.
Simply go through each.
Count permutations, list digits in ascending order to avoid duplicate counting, and be careful to disallow leading zeroes for the left side.
For example, handle the sum 5 by
{0,0,5} -- 3 permutations, but for left side only 1
{0,1,4} -- 3! permutations, but for left side 2 * 2!
{0,2,3} -- 3! permutations, but for left side 2 * 2!
{1,1,3} -- 3 permutations
{1,2,2} -- 3 permutations
So you get (1 + 2*2! + 2*2! + 3 + 3) * (3 + 3! + 3! + 3 + 3) = 315.
I think a better paper approach can be obtained like this, I'll give a sketch.
f(n, m) = How many ways to get digit sum n for an m-digit number, leading zeroes allowed.
Notice . To disallow leading zeroes, change upper limit to 4.
I'll leave it to you to fill in the details, but this should be significantly faster than the previous paper approach.
I don't see any slick way to do this. My method is essentially the same as undefined's. Namely, for each possible three-digit sum, list how many ways that can occur in the last three digits and in the first three digits, multiply the results together and then add to get the grand total.
Here is the calculation in tabulated form:
The columns for sums 3 to 8 are omitted because the digit numbers follow a pattern of triangular numbers. Columns for sums 16 to 25 are omitted because the number of last three digits with sum x is the same as the number with sum 27 – x; and the number of first three digits with sum x is the same as the number with sum 28 – x.
I make the grand total 50412. So in answer to emakarov's question above, the probability of a "lucky" ticket is 50412/900000, or about 5.6%. When I was a kid, we had four-digit bus tickets. I used to spend the journey trying to factorise the number. For me, a ticket was lucky if it had a prime number.