The New Sudoku Players' Forum

[champagne]

In the mood of recent posts,

a hunter sees a ducks flight of x rows
each row rank (n) has exactly (n) ducks

a shoot does not kill any duck, but the flight is split is 2 equal flights

( trivial 1+2+3 -> 2 x 1+2)

the flight had clearly something around 1000 to 10000 ducks

What is/are the possible solutions??

It happened that I found years ago a nice solution, but I am not 100% sure to get it back.

[Leren]

The hardest thing about this was figuring out what the question was.

AFAIK a perfect V formation is split into equal halves. The front part is already a perfect V formation and the second part has the same number of ducks as the front part and quickly forms up into a similar perfect V formation.

The perfect V formation is what all birds do, because it reduces the total wind resistance for the group, making it easier for the whole group to fly.

So mathematically what this boils down to is to find integral solutions such that (n+x) * (n+x+1) = 2*(n) * (n+1) => n^2 - x^2 - 2*n*x +n - x = 0 where n & x are integers.

Easy to do algorithmically. The first 3 solutions are:

Code: Select all

n =  2, x =  1. Flight numbers are both 3.

n = 14, x =  6. Flight numbers are both 105.

n = 84, x = 35. Flight numbers are both 3570.

I'll bet there are more solutions but I'll stop there because I was given the first one and found the other two by hand, with a little help from a spreadsheet.

[Hajime]

Nice problem. Here the manual exercise.

Each group of ducks have n rows with 1 to n ducks per row.
That is n(n+1)/2 in total.
The first 22 groups have the following total:
1 3 6 10 15 21 28 36 45 55 66 78 91
105 120 136 153 171 190 210 231 253...
Now it is to find 2 numbers with one is double of the other.
That is 105 (14th) and 210 (20th) andalso 3 (2nd) and 6 (3rd).
Further search in the 1000s was too difficult manually. I checked up to 1000.
Leren has cross post me with a larger number.

Next question is if the gunshot split up the group in 3 equal parts:
A solution is 15 and 45 andalso 3 and 1.

What about 5 groups? That is 21 and 105 (again)

What about 4 equal groups? Not yet found this...
Or 4 unequal groups then? To be continued...

[champagne]

The hardest thing about this was figuring out what the question was.

AFAIK a perfect V formation is split into equal halves. The front part is already a perfect V formation and the second part has the same number of ducks as the front part and quickly forms up into a similar perfect V formation.

The perfect V formation is what all birds do, because it reduces the total wind resistance for the group, making it easier for the whole group to fly.

So mathematically what this boils down to is to find integral solutions such that (n+x) * (n+x+1) = 2*(n) * (n+1) => n^2 - x^2 - 2*n*x +n - x = 0 where n & x are integers.

Easy to do algorithmically. The first 3 solutions are:

Code: Select all

n =  2, x =  1. Flight numbers are both 3.

n = 14, x =  6. Flight numbers are both 105.

n = 84, x = 35. Flight numbers are both 3570.

I'll bet there are more solutions but I'll stop there because I was given the first one and found the other two by hand, with a little help from a spreadsheet.

Hi leren

No problem with the 2 first solutions

6 duck in a flight 1+2+3 giving 2 flights 1+2

210 ducks in a flight 1+2+...+20 giving 2 flights 1+2+...14

I have a problem with your third case

2 flights 1 + 2+....+35 2x1260 ducks
I see no flight corresponding to this

Edit : sorry, Bad reading of your post

the next answer is correct

2* 84 rows giving 119 rows the flight has 7140 ducks.

[champagne]

years ago, I found a series giving next solution, but I lost the rule
next solution should be
696 rows giving 2 * 492 rows
242556 ducks

[Leren]

Just for fun I used my simple algorithm to get to 9 solutions. Solutions 4 to 9 are :

Code: Select all

Total Lines(n+x) Split Line(n)    Lines above Split Line(x)     Ducks below and above Split Line               Total Ducks

        696           492                       204                              121,278                           242,556
      4,059         2,870                     1,189                            4,119,885                         8,239,770
     23,660        16,730                     6,930                          139,954,815                       279,909,630
    137,903        97,512                    40,391                        4,754,343,828                     9,508,687,656
    803,760       568,344                   235,416                      161,507,735,340                   323,015,470,680
  4,684,659     3,312,554                 1,372,105                    5,486,508,657,735                10,973,017,315,470

The solution finding algorithm is very simple and very fast. Just keep evaluating A = n^2 - x^2 - 2*n*x +n - x. If it is 0 you have a solution.

When you have a solution increase x by 1. A will be a negative number. Then you keep adding 1's to n and evaluate A. It will get less negative and if it >= 1 you have no solution for that x so it must increased by another 1.

Eventually for some x and n > those in the previous solution, A = 0 and you have another solution. Quite quick and easy to code.

Presumably the number of solutions is infinite.

Leren

[champagne]

Presumably the number of solutions is infinite.

Leren

from my lost serie, I can say "yes", but the growth is so quick...
the suite was based on two start values and gave the next total number of ranks 2 terms later

here 3 20 119 696 4059 23660 137903 803760 4684659 27304196
this to be checked but in line with "leren" findings;

[dobrichev]

The exact solution:

Code: Select all

#include <iostream>
#include <math.h>
const double sqrt_2 = sqrt(2.0L);
unsigned long long n_m(unsigned int m) {
   return llround(0.25L * (-pow(3 - 2 * sqrt_2, m) - sqrt(2.0L) * pow(3 - 2 * sqrt_2, m) - pow(3 + 2 * sqrt_2, m) + sqrt_2 * pow(3 + 2 * sqrt_2, m) - 2));
}
unsigned long long t_m(unsigned int m) {
   return (llround(-0.25L * (-2 * pow(3 - 2 * sqrt_2, m) - sqrt(2.0L) * pow(3 - 2 * sqrt_2, m) - 2 * pow(3 + 2 * sqrt_2, m) + sqrt_2 * pow(3 + 2 * sqrt_2, m))) - 1) / 2L;
}
int main() {
   std::cout << "Initial Rows\tSplit Rows" << std::endl;
   for(unsigned int m = 2; m < 27; m++) {
      std::cout << n_m(m) << "\t"   << t_m(m) << std::endl;
   }
}


Results (not double-checked for m > 14, rounding errors may occur)

Code: Select all

     Initial Rows          Split Rows
                  3                   2
                 20                  14
                119                  84
                696                 492
               4059                2870
              23660               16730
             137903               97512
             803760              568344
            4684659             3312554
           27304196            19306982
          159140519           112529340
          927538920           655869060
         5406093003          3822685022
        31509019100         22280241074
       183648021599        129858761424
      1070379110496        756872327472
      6238626641379       4411375203410
     36361380737780      25711378892990
    211929657785303     149856898154532
   1235216565974040     873430010034203
   7199369738058936    5090723162050687
  41961001862379568   29670908962269927
 244566641436218368  172934730611568895
1425438846754931200 1007937474707143167
8308066439093366784 4611686018427387903

real    0m0.005s
user    0m0.005s
sys     0m0.001s


[blue]

Results (not double-checked for m > 14, rounding errors may occur)

Code: Select all

     Initial Rows          Split Rows
                  3                   2
                 20                  14
                119                  84
                696                 492
               4059                2870
              23660               16730
             137903               97512
             803760              568344
            4684659             3312554
           27304196            19306982
          159140519           112529340
          927538920           655869060
         5406093003          3822685022
        31509019100         22280241074
       183648021599        129858761424
      1070379110496        756872327472
      6238626641379       4411375203410
     36361380737780      25711378892990
    211929657785303     149856898154532
   1235216565974040     873430010034203
   7199369738058936    5090723162050687
  41961001862379568   29670908962269927
 244566641436218368  172934730611568895
1425438846754931200 1007937474707143167
8308066439093366784 4611686018427387903

real    0m0.005s
user    0m0.005s
sys     0m0.001s


There are (indeed) rounding errors (in the last 6 lines).
There's a recursive solution too:

Code: Select all

uint64_t N = 0, M = 0;
for (int i = 0; i < 26; i++)
{
   printf("(N, M) = (%llu, %llu)\n", N, M);
   uint64_t N2 = 3 * N + 4 * M + 3;
   uint64_t M2 = 2 * N + 3 * M + 2;
   N = N2;
   M = M2;
}
// (N, M) = (0, 0)
// (N, M) = (3, 2)
// (N, M) = (20, 14)
// (N, M) = (119, 84)
// (N, M) = (696, 492)
// (N, M) = (4059, 2870)
// (N, M) = (23660, 16730)
// (N, M) = (137903, 97512)
// (N, M) = (803760, 568344)
// (N, M) = (4684659, 3312554)
// (N, M) = (27304196, 19306982)
// (N, M) = (159140519, 112529340)
// (N, M) = (927538920, 655869060)
// (N, M) = (5406093003, 3822685022)
// (N, M) = (31509019100, 22280241074)
// (N, M) = (183648021599, 129858761424)
// (N, M) = (1070379110496, 756872327472)
// (N, M) = (6238626641379, 4411375203410)
// (N, M) = (36361380737780, 25711378892990)
// (N, M) = (211929657785303, 149856898154532)
// (N, M) = (1235216565974040, 873430010034204)
// (N, M) = (7199369738058939, 5090723162050694)
// (N, M) = (41961001862379596, 29670908962269962)
// (N, M) = (244566641436218639, 172934730611569080)
// (N, M) = (1425438846754932240, 1007937474707144520)
// (N, M) = (8308066439093374803, 5874690117631298042)


[champagne]

There's a recursive solution too:
[code]
uint64_t N = 0, M = 0;
for (int i = 0; i < 26; i++)
{
printf("(N, M) = (%llu, %llu)\n", N, M);
uint64_t N2 = 3 * N + 4 * M + 3;
uint64_t M2 = 2 * N + 3 * M + 2;
N = N2;
M = M2;
}

as usual, "blue" is the best in such a problem.

From my notes, my recursive solution seems slightly different, but very close.

As far as I remember, I got it trying to solve in "N" the square root of the basic relation.

[rjamil]

Reading from top to bottom several times and trying to decipher the riddle, found something interesting to share.

This elegant mathematical riddle uses triangular numbers and Pell's equation to find a very specific solution.

The exact answer that fits between 1,000 and 10,000 ducks is indeed 7,140 ducks flying in 119 rows.

The Row Pattern: Since each row (n) has exactly (n) ducks (1 duck in row 1, 2 ducks in row 2, etc.), the total number of ducks forms a triangular number. The formula for the total ducks in (x) rows is:

x ( x + 1 ) / 2

The "Equal Flights" Split: When the shot splits the flock into "two equal flights", it means the two new smaller flocks keep the exact same row formation rule (each row (n) has (n) ducks). If each smaller flock has (y) rows, then:

2 x y ( y + 1 ) / 2 => y ( y + 1 )

Setting up the Equation:

x ( x + 1 ) / 2 = y ( y + 1 )

Multiplying this out transforms it into a famous algebra problem known as Pell's Equation:

( 2x + 1 ) ^2 - 2 ( 2y + 1 ) ^2 = -1

The Solution Matching Specific Range

When solving this equation, there are only a few perfect integer matches in existence:

Small option: ( x = 3 ) rows (6 total ducks), which splits into two flights of ( y = 2 ) rows (3 ducks each).
Medium option: ( x = 20 ) rows (210 total ducks), which splits into two flights of ( y = 14 ) rows (105 ducks each).
Exact option: ( x = 119 ) rows, which gives a total of 7,140 ducks.

Why 7,140 is the Perfect Answer:

The original flight has 119 rows, totaling 7,140 ducks. This perfectly fits the requirement of being between 1,000 and 10,000.
After the split, it forms two identical flights of 84 rows each.
Each 84-row flight has exactly ( 84 x 85 ) / 2 = 3,570 ducks 3,570 x 2 = 7,140.

R. Jamil

[champagne]

I likely got this years ago in a newspaper or in a book of games.

What I liked was the recursive solution. My serie was not the same as the very nice step shown by "blue", but I had (I think) the proof to cover all solutions in a very simple way.

Starting from "blue" sequence, it's easy to verify that any valid solution can be attached to a smaller number of ranks, leading at the end to the double 0 first solution (and the next one: 3,2)

It seems not very hard to find in "N" the small values of both aN+bM+c given by "blue".

How "blue" got the idea to use this remains a secret...